Mona Lisa TSP (100,000 cities): shorter tour than 5,757,191 or a proof of optimality
Difficulty 52: a 107-unit gap on 100,000 cities, unchanged since 2012, is within a factor of a few of instances already solved, so a long dedicated run plus better branching could close it; below the World TSP (62). Application value 5 and leverage 10: a showcase instance for TSP research only.
The problem
A 100,000-point round trip that draws the Mona Lisa: find a shorter one or prove the best is perfect.
- 1Dots form a Mona Lisa
- 2Heuristics found a tour in 2009
- 3Cutting planes proved a bound in 2012
- 4107 units remain between them
The instance. The Mona Lisa TSP is a set of 100,000 points in the plane placed so that a short tour through them draws the Mona Lisa. The task is the travelling salesman problem: the shortest closed path visiting every point once, with straight-line (Euclidean) distances.
The two bounds. The best known tour, found by Yuichi Nagata on 17 March 2009 with a genetic algorithm (a search that combines pieces of good tours, like breeding, and keeps the shortest offspring), has length 5,757,191. The best lower bound, computed with the Concorde code on 27 July 2012, is 5,757,084. The gap is 107 units, about 0.0019%. So the 2009 tour is either optimal or at most 107 units too long. A prize of USD 1,000 is offered for the first tour shorter than 5,757,191.
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
- Mona Lisa TSP (100,000 cities): shorter tour than 5,757,191 or a proof of optimalityThe problem
State of the art
The best known tour has length 5,757,191, found by Yuichi Nagata on 17 March 2009 using a genetic algorithm. The best lower bound is 5,757,084, established with Concorde on 27 July 2012. The gap is 107 units, about 0.0019%. The page states that optimality is not proven.
Realistic applications
No practical application beyond testing: it is the cleanest 100,000-city case on which exact methods meet record heuristics. Gains in cut separation or branching would carry over to large routing problems.
What counts as solved
A tour of length at most 5,757,190 checked from the published coordinates, or a Concorde-style cutting-plane certificate of a lower bound of 5,757,191 verified independently.
How it gets verified
Bound / recordA numeric bound or record checked from a certificate or recomputation.
Quantity: length of the shortest tour on the 100,000-city Mona Lisa instance; record 5,757,191 (Nagata, 2009) against lower bound 5,757,084 (Concorde, 2012) per the Waterloo page. A shorter tour is checked by recomputing its length from the instance file. An optimality proof needs an independently checkable cutting-plane certificate of the lower bound.
Claims under verification
+ add a claimNo claimed results on the Verification board for this problem yet.
Where the work is
Same structure as the World TSP at a smaller scale: cut separation and LP scaling with long compute.
Bottlenecks
ranked by votes- #1EngineeringBranching with 100,000-city LPs
Closing a gap of 107 units needs branch-and-cut trees whose every node solves a large LP; the cost per node limits progress.
Community grades
Sign in to add your own grade.
Connected problems
- This problem is related to Prove optimality of the World TSP (1,904,711 cities), or close the 0.047% gap