Combining simulated annealing with local search heuristics

The authors introduce a meta-heuristic to combine simulated annealing with local search methods for combinatorial optimization (CO) problems. This new class of Markov chains leads to significantly more powerful optimization methods than either simulated annealing or local search. The main idea is to embed deterministic local search techniques into simulated annealing so that the chain explores only local optima. It makes large, global changes, even at low temperatures, thus overcoming large barriers in configuration space. The authors have tested this meta-heuristic for the traveling salesman and graph partitioning problems. Tests on instances from public libraries and random ensembles quantify the power of the method. The present algorithm is able to solve large instances to optimality, improving upon local search methods very significantly. For the traveling salesman problem with randomly distributed cities in a square, the procedure improves on 3-opt by 1.6%, and on Lin-Kernighan local search by 1.3%. For the partitioning of sparse random graphs of average degree equal to 5, the improvement over Kernighan-Lin local search is 8.9%. For both CO problems, the authors obtain new best heuristics.