The full StarHorse catalogue contains 3D positions for 265,637,087 stars, providing a beautiful example of the traveling salesman problem. But the StarHorse authors note they can raise the overall quality of the collection by filtering out certain entries that may be problematic.
The surviving set of 136,606,128 stars is still plenty large for a TSP challenge, and a good stepping stone towards the StarHorse and Gaia DR2 instances. Details of the point set can be found on the data page.
As of December 19, 2023, our best tour for this example has length 1.417,520,624.8 parsecs. This is a result of a long and steady computation. Keld has been keeping two or three computer cores busy now for over three years, racking up small, but important, gains in the tour quality on a daily basis. Since October 6, 2020, the tour has been improved by 69,911.4 parsecs.
To put Keld's work in perspective, we have to mention a computational breakthrough we had in April 2023, thanks to a new linear-programming solver called PDLP. This new code, developed by Google Research, allowed us to show there is no tour shorter than 1,417,289,796.6 parsecs for the StarHorse 1 point set. So we are now within 230,828.2 parsecs of a shortest-possible tour. A quick division shows Keld has thus lowered the gap by over 23% through his marathon computation and steady stream of code improvements and adjustments.
Similar to the 100,000,000-star example, our bound was achieved by approximately solving a single LP, put together through a massive parallel computation. The LP weighs in at 1,798,992,347 variables, 241,211,398 constraints, and with 25,165,026,517 non-zero coefficients in the constraint matrix. It is amazing to me that Dave was able to run a distributed version of PDLP to produce a near-optimal (dual) solution for a model of this size. With the dual solution in hand, we were able to compute in exact arithmetic the 1,417,289,796.6 lower bound for the StarHorse 1 TSP, proving we are within a factor of 0.000173 times the optimal tour.
Many thanks to the full PDLP team. We are looking forward to taking a second shot at StarHorse 1, using a more detailed model to hopefully push the bound under the magic target of 0.0001.
Research team
• David Applegate, Google Research
• William Cook, University of Waterloo and Johns Hopkins University
• Keld Helsgaun, Roskilde University
Notes
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.
Information on the point set for the StarHorse 1 TSP is given on the Data page; images can be found on the Tour page.
Details on the PLDP solver can be found in the research paper Practical large-scale linear programming using primal-dual hybrid gradient by D. Applegate, M. Díaz, O. Hinder, H. Lu, M. Lubin, B. O'Donoghue, W. Schudy.
Computations were carried out on systems located at Google Research, Roskilde University, and the University of Waterloo. We thank our institutions for their support.