A brief description of the dynamic programming routine for the
eighth DIMACS Challenge
A more complete description can be downloaded from the publications on the
website (http://www.andrew.cmu.edu/~neils/tsp/):
- Linear Time Dynamic Programming Algorithms for New Classes of Restricted
TSPs: A Computational Study (to appear in INFORMS Journal on Computing)
- Applications of a Dynamic Programming Approach to the Traveling Salesman
Problem (PhD Thesis)
Our tour-improving heuristic is based on a dynamic programming approach. A
straight forward dynamic program for the TSP would require a running time of
O(2^n), which, of course, is impractical for TSPs larger than 20 or so nodes.
By putting a simple restriction on the TSP, we can reduce our running time to
O(n*2^k), and still find an optimal solution among a neighborhood of O((k/2)^n)
tours, where k is a constant related to the simple restriction.
The simple restriction is this: Given a starting tour T and any two cities,
i and j, such that city i appears in T k or more positions before city j,
i must appear before j in the final tour. Our algorithm will find an optimal
tour for a TSP subject to this restriction when given an initial tour. From
this point, we name this algorithm DPk, where k is a prechosen constant. For
the DIMACS challenge, we are submitting results from DP6, DP8, and DP10.
As with any dynamic programming routine, finding the optimal value is done by
first travelling forward through a state-space, finding the cost of optimal
sub-paths while building up to the final tour, and then backtracking to
construct the final tour. The memory required to backtrack in this sense would
be prohibitive for large problems (O(n*(2^k))) unless we exploit another
feature of this algorithm.
When given an initial tour of reasonable quality, our algorithm tends to find
improvements to local areas, while leaving most of the cities positions in the
tour unchanged. While travelling forward through the state-space, we can
detect when one of these possible improvements is found, and backtrack at that
time until the most recent unchanged city is found. (This is described more in
the publications mentioned above.) Since these local improvements tend to be
short (usually 3*k or less), we can replace our memory dependence on n*(2^k)
with h*(2^k), where h is the length of the longest allowable backtrack. For
our test runs, we chose a default value of h = 5*k before beginning our trials.
This was sufficient for all runs of DP10, and all but one run for DP6 and DP8.
In these two cases, the same problem pla85900 required a value of h greater
than 5*k and less than 8*k. Even though the final tour could not be generated,
the value of the optimal tour subject to our restriction could still be
returned. Note that this was far from being the largest instance, as these
algorithms had no problems with the 316k node instances or the 1 million node
instance. (We cannot completely remove our dependence on n since storing the
data itself for Euclidean problems requires storing 2*n doubles. In addition,
to speed up the dynamic program, we create a 3*k by n matrix to store all arc
costs we might need. (This is not n by n because of the restriction mentioned
above.)
Starting tours for our runs were generated by the latest chained Lin-Kernighan
code from the CONCORDE website, with default parameter settings except the
random seed, which was set to 1. We felt it was important to use a starting
tour of as high a quality as possible to demonstrate the value of our routine.
In examining our results at first glance we only improved 20 of 81 tours with
DP6, 22 of 81 tours with DP8, and 26 of 81 tours with DP10. However, looking
closer at the data shows that the larger problems (30,000 or more nodes) we
improved 11 of 13 tours with DP6, 12 of 13 tours with DP8, and 12 of 13 tours
with DP10, performing the best on the clustered Euclidean instances as we
suspected in our earlier published results. Another important feature that
makes our algorithm appealing in these larger instances is that our linear
running time becomes a smaller fraction of the total running time as the
problem sizes grow. For E1M.0, DP6 runs in less than 1/250th of the time
required by the chained Lin-Kernighan code.