Prove optimality of the World TSP (1,904,711 cities), or close the 0.047% gap
Difficulty 62: the 2007 lower bound has never moved, and an optimality proof would have to scale Concorde-style branch-and-cut from the largest certified instances (tens of thousands of cities) to 1.9 million; level with the kissing number in dimension 5 (64) as a finite question with no route in sight. Application value 10: no routing need for this instance. Leverage 18: large-scale cutting-plane methods.
The problem
Find the shortest round trip through 1.9 million places, or prove the current tour is within a hair of the best.
- 1Heuristics find a record tour
- 2Cutting planes give a lower bound
- 3Gap of 0.047% remains
- 4Closing it needs a checkable proof
The problem. The travelling salesman problem (TSP) asks for the shortest closed tour that visits every city once. The number of possible tours of cities is ; for just 20 cities that is about , so trying them all is hopeless. The has 1,904,711 cities: populated places worldwide plus research bases in Antarctica, with distances given by a fixed great-circle formula rounded to whole metres.
Path to understanding
foundations → problemThe research entries this problem rests on, in the order to read them. Each links to its explainer.
- Start with
- Step 2
- Step 3
- Fast matrix multiplicationAlgorithm
- Step 4
- Linear programmingAlgorithm
- Step 5
- Then
- Prove optimality of the World TSP (1,904,711 cities), or close the 0.047% gapThe problem
State of the art
The best tour has length 7,515,755,912, found by Yuichi Nagata on 17 October 2025; it improved by 44 metres the tour of 7,515,755,956 found by Keld Helsgaun on 15 February 2021. The best lower bound is 7,512,218,268, established by the Concorde code in June 2007 with CPLEX as LP solver. The gap is 3,537,644 metres, about 0.047% of the tour length (arithmetic from the two published figures; the page states the same percentage for Helsgaun's tour). Optimality is not proven.
Realistic applications
Practical routing never needs this instance. The value is as a stress test: closing the gap needs scaling branch-and-cut, LP solving and cut separation to millions of variables, and techniques developed for it transfer to large vehicle routing and chip layout problems.
What counts as solved
Improvement: a tour file with length strictly below 7,515,755,912 verified by the dataset's distance function. Optimality: a lower-bound certificate (Concorde cut proof or an equivalent exact LP dual solution) of the tour length, checkable by an independent program.
How it gets verified
Bound / recordA numeric bound or record checked from a certificate or recomputation.
Quantity: tour length for the 1,904,711-city World TSP; record 7,515,755,912 (Nagata, 2025-10-17) against lower bound 7,512,218,268 (Concorde, 2007), both from the Waterloo World TSP page. A shorter tour is checked by recomputing its length from the published city coordinates; an optimality claim needs a cutting-plane proof of the lower bound that an independent checker (rational LP dual plus the listed cuts) accepts.
Claims under verification
+ add a claimNo claimed results on the Verification board for this problem yet.
Where the work is
Progress needs better cutting-plane theory and implementation at the scale of millions of variables, plus long compute for LP solves and separation.
Bottlenecks
ranked by votes- #1EngineeringLP size and memory for 1.9 million cities
The LP relaxations have millions of variables; solving them repeatedly with new cuts needs memory and solver scaling far beyond past certified instances.
Community grades
Sign in to add your own grade.
Connected problems
- This problem is related to Mona Lisa TSP (100,000 cities): shorter tour than 5,757,191 or a proof of optimality