Back to Italy
TSP 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+
||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.
||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.
||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