Instance Created:  July 29, 2001
Number of Cities:  24,978
Optimal Value:  855,597
Solution Method:  Concorde, CPlex 6.5 LP Solver, LKH
Solution Time:  84.8 years, Intel Xeon 2.8 GHz

History

Date	Gap	Lower Bound	Tour
24.8.01			855,683 - Found by merging 3 LKH tours (each with n trials). The total time to find the tours was 465,529 seconds on a 500 MHz EV6 Alpha; merging required an additional 447.58 seconds). The best LKH tour had length 855,751.
26.8.01	0.041%	855,331 - Established by Concorde with -C 20 (used 31 nodes in the branch-and-cut tree, 113,553 seconds on a 500 MHz EV6 Alpha).
4.9.01	0.034%		855,618 - Merging 10 LKH tours (each with n trials). The total time to find the 10 tours was 1,505,455 seconds on a 500 MHz EV6 Alpha; merging required an additional 2025.87 seconds). The best LKH tour had length 855,735.
20.9.01	0.033%		855,612 - Found by Keld Helsgaun using variants of his LKH code. The running time was approximately 2 days on a 400 MHz PowerMac G4.
30.9.01	0.033%		855,610 - Found by Keld Helsgaun using LKH, working with the 855,612 and 855,618 tours. The running time was approximately 30 minutes on a 400 MHz PowerBook G3.
16.3.03	0.032%		855,602 - Found by Hung Dinh Nguyen using a hybrid genetic algorithm, starting with the 855,610 tour described above. The running time was 19034 seconds on a single processor of a Sun Ultra 80 (450 MHz)
18.3.03	0.031%		855,597 - Found by Keld Helsgaun using a new variant of his LKH heuristic.
24.3.03	0.012%	855,493 - Established by Concorde with -C 32 (used 2,011 nodes in the branch-and-cut tree; 34,585,460 total seconds on a cluster of 2.4 GHz Xeon linux workstations).
2.6.03	0.009%	855,528 - Established by Concorde with -C 36 starting with an LP obtained using cutting planes from the final pool of cuts from the 3.24.03 branching run. This run used 2,965 nodes in the branch-and-cut tree and a total of 138,864,296 seconds on a cluster of 2.4 GHz Xeon linux workstations.
20.5.04	Optimal	855,597 - Established by Concorde. The total CPU time was approximately 84.8 years on a 2.8GHz Intel Xeon linux workstation. Detailed information about the run can be found on the Sweden TSP Page.

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.