At first we implemented the Large-Step Markov Chain for the three-opt local
search. We checked that we could solve to optimality problems of sizes up to
200 by comparing with a branch and bound program. For **N=100**, the
optimum was found in a few minutes on a SUN-3, while for **N=200** an hour or
two was required. For larger instances, we used problems which had been
solved to optimality by other people. We ran our program on the Lin-318
instance solved to optimality by Padberg and Crowder. Our iterated three-opt
found the optimal tour on each of five separate runs, with an average time of
less than 20 hours on the SUN-3. We also ran on the AT&T-532 instance
problem solved to optimality by Padberg and Rinaldi. By using a postreduction
method inspired by tricks explained in the Lin-Kernighan paper, the program
finds the optimum solution in 100 hours. It is of interest to ask what is
the expected excess tour length for very large problems using our method with
a reasonable amount of time. We have run on large instances of cities
randomly distributed in the unit square. Ordinary three-opt gives an average
length 3.6% above the Held-Karp bound, whereas the iterated three-opt does
better than **L**-**K** (which is 2.2% above): it leads to an average of less
than 2.0% above **H**-**K**. Thus we see that without much more algorithmic
complexity, one can improve three-opt by more than 1.6%.

In [Martin:91a], we suggested that such a dramatic improvement should
also carry over to the **L**-**K** local opt algorithm. Since then, we have
implemented a version of **L**-**K** and have run it on the instances mentioned
above. Johnson [Johnson:90b] and also Cook, Applegate, Chvatal
[Cook:90b] have similarly investigated the improvement of iterated
**L**-**K** over repeated **L**-**K**. It is now clear that the iterated **L**-**K**
is a big improvement. Iterated **L**-**K** is able to find the solution to the
Lin-318 instance in minutes, and the solution to the AT&T-532 problem in an
hour. At a recent TSP workshop [TSP:90a], a 783-city instance
constructed by Pulleyblank was solved to optimality by ourselves, Johnson,
and Cook et. al., all using the large-step method.

For large instances (randomly distributed cities), Johnson finds that
iterated **L**-**K** leads to an average excess length of 0.84% above the
Held-Karp bound. Previously it was expected that the exact optimum was
somewhere above 1% from the Held-Karp bound, but iterated **L**-**K** disproves
this conjecture.

One of the most exciting results of the experiments which have been performed to date is this: For ``moderate''-sized problems (such as the AT&T-532 or the 783 instance mentioned above), no careful ``annealing'' seems to be necessary. It is observed that just setting the temperature to zero (no uphill moves at all!) gives an algorithm which can often find the exact optimum. The implication is that, for the large-step Markov chain algorithm, the effective energy landscape has only one (or few) local minima! Almost all of the previous local minima have been modified to saddle points by the extended neighborhood structure of the algorithm.

Steve Otto had the original idea for the large-step Markov chain. Olivier Martin has made (and continues to make) many improvements towards developing new, fast local search heuristics. Steve Otto and Edward Felten have developed the programs, and are working on a parallel implementation.

Wed Mar 1 10:19:35 EST 1995