Python implementation of the fast approximation subset sum algorithm from Przydatek, 2002.

Home   »   Python implementation of the fast approximation subset sum algorithm from Przydatek, 2002.

import numpy as np

def error(target, solution, data):
    return target - sum(data[solution])

def przydatek_approx_subset(data, target, trials, key=lambda x:x):
    '''
    Przydatek, B. (2002), A Fast Approximation Algorithm for the Subsetā€sum Problem. 
    International Transactions in Operational Research, 9: 437-459. https://doi.org/10.1111/1475-3995.00366
    '''
    arr = np.array([key(x) for x in data])
    n = len(arr)
    best = np.zeros(n, dtype=bool)

    for _ in range(trials):
        # random selection phase
        solution = np.zeros(n, dtype=bool)
        r = list(range(n))
        np.random.shuffle(r)
        for i in r:
            if arr[i] <= error(target, solution, arr):
                solution[i] = 1
        
        # local improvement phase
        indices = [i for i in range(n) if solution[i] == 1]
        np.random.shuffle(indices)
        for i in indices:
            if error(target, solution, arr) == 0:
                break

            replacements = [arr[l] for l in range(n) if solution[l] == 0 and 
                            0 < (arr[l] - arr[i]) and (arr[l] - arr[i]) <= error(target, solution, arr)]
            
            if len(replacements) > 0:
                k = np.where(arr == max(replacements))[0]
                solution[k] = 1
                solution[i] = 0

        # update best solution phase
        if error(target, solution, arr) < error(target, best, arr):
            best = solution
        if error(target, best, arr) == 0:
            break

    return [x for x, i in zip(data, best) if i]
  

Leave a Reply

Your email address will not be published. Required fields are marked *