Instance Created:  July 29, 2001
Number of Cities:  9,882
Optimal Value:  300,899
Solved:  March 22, 2002
Solution Method:  Concorde -C 24, QSopt LP solver, LKH+tmerge tour
Solution Time:  7.9 million seconds, AMD Athlon 1900+

History

Date	Gap	Lower Bound	Tour
8.23.01			300,899 - Best of 40 LKH tours (n trials per run). The 40 LKH runs took a total of 415,948 seconds on a 500 MHz EV6 Alpha. Merging the tours (49.72 seconds) did not make an improvement.
8.27.01	0.0076%	300,876 - Established by Concorde with -C 20 (used 535 nodes in the branch-and-cut tree, 774,679 seconds on a 500 MHz EV6 Alpha).
3.22.02	Optimal	300,899 - Established by Concorde with -C 24 (root node was run with -C 36). The run used 5,455 nodes in the branch-and-cut tree and 7.9 million seconds on an AMD Athlon 1900+ (ran in parallel on a network of 15 workstations). The LP solver was QSopt.

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.