Instance Created:  March 14, 2002
Number of Cities:  16,862
Optimal Value:  557,315
Solved:  December 8, 2002
Solution Method:  Concorde + (cplex and qsopt)
Solution Time:  14 years, AMD Athlon 1900+

History

Date	Gap	Lower Bound	Tour
4.1.02			557,315 - found by running Keld Helsgaun's LKH code 106 times, each with 16,862 trials, and merging the 106 tours using tmerge. The 106 LKH runs took a total of approximately 6 million seconds on a 500 MHz EV6 Alpha and the tmerge run took an additional 306.1 seconds. The best of the LKH tours had length 557,368.
4.23.02	0.007%	557,274 - Established by Concorde with -C 24 and LP solver QSopt; used 5,423 nodes in the branch-and-bound tree, 15,505,782 seconds on an Athlon 1900+ (run on a network of 14 workstations). The root LP used -C 48.
12.9.02	Optimal	557,315 - Established by Concorde and the LP solvers CPplex and QSopt; used 50,703 nodes in the branch-and-bound tree, 14 years on a network of Athlon 1900+ workstations at Princeton University and a network of Alpha EV6/500 processors at Rice University. The root LP used repeated runs with up to -C 52.

Notes

1. Concorde is our linear-programming based TSP solver.

2. linkern is an implementation of Martin, Otto, and Felten's Chained Lin-Kernighan heuristic. It is included in the Concorde code.

3. LKH is Keld Helsgaun's powerful implementation of the Lin-Kernighan heuristic.

Back to TSP home.