describe.txt -- 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: - 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.