  A procedure is presented which considerably improves the performance of local
search based heuristic algorithms for combinatorial optimization problems. It
increases the average `gain' of the individual local searches by merging pairs
of solutions: certain parts of either solution are transcribed by the related
parts of the respective other solution, corresponding to flipping clusters of a
spin glass. This iterative partial transcription acts as a local search in the
subspace spanned by the differing components of both solutions. Embedding it in
the simple multi-start-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 annealing.
