Instance Created:  April 26, 2002
Number of Cities:  21215
Status:  OPEN
Best Tour:  63517
Best Lower Bound:  63501

History

Date	Gap	Lower Bound	Tour
10.6.02			63531 - Best of 10 runs of LKH, each with n trials. Total running time 487468 seconds on an AMD Althlon 1900+ processor (1.6 GHz).
3.3.03			63522 - Found by Hung Dinh Nguyen using a parallel hybrid genetic algorithm. The running time was 84456 seconds on a Sun Ultra 80 with four 450-MHz processors (taking the best of five runs).
3.3.03			63519 - Found by running Keld Helsguan's LKH (version 1.3, default setting) 100 times, each with 21215 trials, and using tmorph+tmerge to merge the 10 best tours. The 100 LKH runs took approximately 4.6 million seconds on Athlon 1900+ processors. The best tour among the 100 LKH tours had length 63,528. The union of the 10 tours contained 25,557 edges, and tmorph reduced this to a total of 23,393 edges; the running time was 47 seconds on an EV6, 500 MHz AlphaServer. The best tour in the tmorphed set of edges was found by tmerge in 89 seconds (on the AlphaServer).
16.3.03	0.028%	63501 - Established by Concorde with -C 32 (used 2,143 in the branch-and-cut tree, 31,121,619 total seconds on a cluster of 2.4 GHz Xeon linux workstations).
2.4.08			63518 - Found by Changxing Dong, Gerold Jaeger, Paul Molitor, Dirk Richter by a variant of LKH based an backbone contraction. The running time was 99480 seconds on an AMD Opteron (2.6 GHz).
23.6.08			63517 - Found by Changxing Dong, Gerold Jaeger, Paul Molitor, Dirk Richter by a variant of LKH based an backbone contraction.

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.