Slice of Star 100m Tour

100,000,000 Stars

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 October 6, 2020, the best tour we had for this example measured 194,432,401.4 parsecs. This is not a shortest-possible tour. I can say this with certainty, because on October 7 we found one that was 5 parsecs shorter, and by October 9 the heuristic search code shaved 14.5 parsecs on top of that.

It's not clear how much further the code will able to improve the tour, but it's a safe bet the October 9 value of 194,432,381.9 parsecs is not the final word.

So, we definitely 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 134.971.7 parsecs, so a factor of just under 0.0007. Not bad, but we hope to improve this substantially in the next month or so, 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.

Research team

  • 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.