.... Solving TSPs

Back to Italy

World TSP

National TSPs

TSP Home Page


TSP Links


Home page

IT16862 - Italy Computation Log

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+


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.


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.

Last Updated:  May 1, 2005