Instance Created:  July 29, 2001
Number of Cities:  7,663
Optimal Value:  238,314
Solved:  January 24, 2009
Solution Method:  Concorde

History

Date	Gap	Lower Bound	Tour
8.10.01	0.126%	238,242 - Concorde -C 20, with Cplex 6.5 LP solver, 159 hours, 500 MHz EV6 Alpha, the branch-and-cut run created 631 nodes in the search tree	238,543 - found by a call to linkern during Concorde's branch-and-cut run
8.15.01	0.038%		238,333 - found by running linkerh to produce 10 tours, and then merging the tours using tmerge. The 10 linkerh runs took a total of 41,758 seconds on a 500 MHz EV6 Alpha and the tmerge run took an additional 17.41 seconds. The best of the linerh tours had length 238,337.
8.23.01	0.030%		238,314 - Merging 40 LKH tours (n trials each). The 40 LKH runs took a total of 236,494 seconds on a 500 MHz EV6 Alpha and the tmerge run took an additional 30.15 seconds. The best of the linerh tours had length 238,315.

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.
4. linkerh is an implementation of the Lin-Kernighan heuristic, making use of a number of the new ideas introduced in Keld Helsgaun's LKH code.

Back to TSP home.