For a second warmup, we sorted the 1.33 billion stars in the Gaia DR2 challenge and selected the closest 100,000,000. An order of magnitude below target, but 100 million points is not exactly a walk in the park for TSP solvers.
Well, finding a 100-million-point tour is not a problem. Keep moving to a star you haven't already seen. When you've hit them all, turn your ship towards home. Easy peasy. The challenge is to find the shortest-possible one.
As of June 8, 2023, the best tour we had for this example measured 194,429,057.6 parsecs. This is very likely not a shortest-possible tour. At the time the computation was stopped, we were still make small progress in the tour length each few days.
It's not clear how much further the code will able to improve the tour, but it's a safe bet that 194,429,057.6 parsecs is not the final word.
So, we haven't solved the problem. But we are getting close. By approximately solving a single linear-programming model, we know no tour can have length less than 194,297,429.7 parsecs. That leaves a gap of 131,627.9 parsecs, so a factor of under 0.00068. Not bad, but will hopefuly improve the bound by working with a larger (but better) LP model.
You don't need an abacus to spot that our gap is larger than the 0.00003 factor we have for the 10,000,000-point warmup. The trouble again comes down to size. For star10m we obtained the bound by solving a short sequence of LP models, using commercial barrier-method codes. Each of the LP solves needed several days on a 32-core machine, and used in excess of 600 GB of memory. We don't have the hardware to even attempt to duplicate this process on the 10-times larger star100m instance.
Instead, we made a first run of the methodology we aim to employ on Gaia DR2. We began by running the cutting-plane method in parallel on overlapping subregions of the point set, using a 288-core network of compute nodes. The inequalities were gathered into a single huge LP model, that was solved approximately with a first-order technique. The LP solution was adjusted to make it dual feasible, and the resulting lower bound computed with fixed-point arithmetic. And out popped the guarantee that no tour can be shorter than 194,297,429.7 parsecs.
• David Applegate, Google Research
• William Cook, University of Waterloo and Johns Hopkins University
• Keld Helsgaun, Roskilde University
Links to lots of information on the mathematical techniques we have employed can be found on the TSP home page and on the LKH web site.
Details on the point set for the star TSP instance are given on the Data page; images can be found on the Tour page.
Computations were carried out on systems located at Google Research, Roskilde University, and the University of Waterloo. We thank our institutions for their support.