TSP Tour in 3D through 2,079,471 stars

2,079,471 stars

To strike fear in the computing world, just whisper "traveling salesman problem." The echo will be "if we want to figure out the route for 28 cities, the universe will die before we get the result."

Indeed, the reputation of the problem is such that advances on small instances (using admittedly cool technology) are newsworthy, such as recent reports on a new AI "processor to solve 22 cities" or an 8-stop tour found by an ameoba "that might just change the face of computing forever".

Our work is decidedly less exotic, but at a much, much larger scale. With Keld Helsgaun, from Roskilde University in Denmark, we aim to compute the shortest-possible tour through the 3D positions of over two million individual stars, a point set based on the ESA Gaia Data Release 1.

28,884,352 parsecs

From October 2017 through October 2019, week by week, we produced shorter and shorter 3D star tours, employing an array of heuristic-search techniques and ever-increasing amounts of computing power. The foundation for this effort was Keld's LKH software package, a powerhouse code for obtaining near-optimal solutions to the TSP and related routing problems. On top of LKH, we added methods specialized for such a large data set, combining local search and genetic algorithms, together with decomposition strategies to allow for parallel computation.

The search continued through the end of last year, but we found no further improvements on a solution from October 6, 2019. That's the tour displayed in the moving image. Its total length is 28,884,352.4 parsecs, or, if you prefer, 94,208,157.5 light years.

0.0000074 guarantee

A crucial point is this is not just any route through the stars. Ours comes together with a proof that its length, if not the absolute shortest possible, is off by at most a factor of 0.0000074. To put this in perspective, it's like a New York to Los Angles road trip guaranteed to be within half a city block of the optimal cross-country drive.

Our quality guarantee is provided by another difficult computation. Over the past two-and-a-half years we have been running a linear programming, cutting-plane method to slowly close the gap between our solution and a lower bound on the length of each of the unimaginably many possible tours through the point set. Our work here builds on the Concorde TSP Solver, again making numerous adjustments to handle the expectionally large number of points and to permit extensive parallel computation.

Parsecs to dollars

We know there is no tour more than 213.4 parsecs shorter than our route. Close enough for Jean-Luc Picard, perhaps, but attacks on closing the remaining gap may lead to mathematical techniques having wide application beyond the world of Star Trek. If you think you can help, I'm offering a bounty of $50 for each parsec you can save by rearranging the flight through the stars. It would aid our work to have an improved target tour if one exists, so I'm happy to offer a reward to encourage more eyes on the data set.

And don't worry about the budget. Keld and I won $17,000 in a Kaggle competition last year; I put some of my share aside to payoff any shortcut finders. If you want to join the hunt for parsecs, check out the details on the Challenge page.

Research team

  • William Cook, University of Waterloo and Johns Hopkins University
  • 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 and on the LKH web site.

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 University and the University of Waterloo. Support was provided by an NSERC Discovery Grant.

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.

from Hacker News https://ift.tt/2GXNukj