It was easy to create the data set, but not so easy to solve. Combining linear programmig with a branch-and-bound search was not sufficient to prove that we have a shortest-possible tour. Here are the results, measured in parsecs as described on the data page.
• 979419.1, tour length,
• 979414.0, linear-programming bound,
• 979414.9, branch-and-bound search.
We are close, but there remains a 4.2 parsec gap between the length of our tour , displayed in the moving image, and the lower bound. Bad luck. But this is where the fun begins.
• David Applegate, Google Research
• Robert Bixby, Gurobi Optimization and Rice University
• Vaek Chvátal, Charles University
• William Cook, University of Waterloo and Johns Hopkins University
• Daniel Espinoza, Google Inc.
• Marcos Goycoolea, Universidad Adolfo Ibanez
• Keld Helsgaun, Roskilde University
For a guide to navigating the moving image, click the ⓘ button in the top right corner of the page.
Links to lots of information on the mathematical techniques we have employed can be found on the TSP home page.
The computations were carried out on systems located at Roskilde and Waterloo. We thank our universities for their support.
We thank Michael Boyle for suggesting the use of color hue to indicate the order stars appear in our solution.