After success with hyg109399, we decided to step up to a 250,000-point instance. These are the 3D locations of the nearest 250,000 stars in the Gaia DR1 data set.
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.
The tour was found with Keld Helsgaun's LKH heuristic code, and the lower bounds were found with the Concorde TSP solver.
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.
Research team
• David Applegate, Google Research
• Robert Bixby, Gurobi Optimization and Rice University
• Vašek 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
Notes
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.
Details on the point set for the star TSP instance are given on the Data page; further images can be found on the Tour page.
The computations were carried out on systems located at Roskilde and Waterloo. We thank our universities for their support.
The tour is rendered with the three.js JavaScript 3D library.
We thank Michael Boyle for suggesting the use of color hue to indicate the order stars appear in our solution.