Large-Step Markov Chains for the Traveling Salesman Problem
Olivier Martin
Department of Physics, City College of New York,
New York, NY, 10031, USA
Steve W. Otto
Department of Computer Science and Engineering,
Oregon Graduate Institute of Science and Technology,
19600 NW von Neumann Dr, Beaverton, OR, 97006-1999, USA
Edward W. Felten
Department of Computer Science,
University of Washington, Seattle, WA, 98195, USA
Abstract
We introduce a new class of Markov chain Monte Carlo search procedures that lead to more powerful optimization methods than simulated annealing. The main idea is to embed deterministic local search techniques into stochastic algorithms. The Monte Carlo explores only local optima, and it is able to make large, global changes even at low temperatures, thus overcoming large barriers in configuration space. We test these procedures in the case of the Traveling Salesman Problem. The embedded local searches we use are 3-opt and Lin-Kernighan. The large change or step consists of a special kind of 4-change followed by local-opt minimization. We test this algorithm on a number of instances. The power of the method is illustrated by solving to optimality some large problems such as the LIN318, the AT&T532, and the RAT783 problems. For even larger instances with randomly distributed cities, the Markov chain procedure improves 3-opt by over 1.6%, and Lin-Kernighan by 1.3%, leading to a new best heuristic.
