Combinatorial optimization by iterative partial transcription

A procedure is presented that considerably improves the performance of loca l search based heuristic algorithms for combinatorial optimization problems . It increases the average "gain" of the individual local searches by mergi ng pairs of solutions: certain parts of either solution are transcribed by the related parts of the respective other solution, corresponding to flippi ng clusters of a spin glass. This iterative partial transcription acts as a local search in the subspace spanned by the differing components of both s olutions. Embedding it in the simple multistart-local-search algorithm and in the thermal-cycling method, we demonstrate its effectiveness for several instances of the traveling salesman problem. The obtained results indicate that, for this task, such approaches are far superior to simulated anneali ng.