Problem space local search for number partitioning

The authors show how simple and effective metaheuristics can be developed for the number partitioning problem using the ‘problem space’ approach. In a previous application of local search to number partitioning, it was found that the performance of simulated annealing used in conjunction with ‘swap neighborhoods’ was disappointing relative to the differencing heuristic of Karmarkar and Karp. Using problem space neighborhoods as an alternative to swapping, the authors empirically demonstrate several orders of magnitude improvement over the differencing algorithm, albeit with greater computation time. This improvement in performance comes as little surprise since a modified version of the differencing heuristic is explicitly embedded in the problem space algorithm.