.... Solving TSPs

Back to Greece

World TSP

National TSPs

TSP Home Page


TSP Links


Home page

GR9882 - Greece Computation Log

Instance Created:  July 29, 2001
Number of Cities:  9,882
Optimal Value:  300,899
Solved:  March 22, 2002
Solution Method:  Concorde -C 24, QSopt LP solver, LKH+tmerge tour
Solution Time:  7.9 million seconds, AMD Athlon 1900+


Date Gap Lower Bound Tour
8.23.01 300,899 - Best of 40 LKH tours (n trials per run). The 40 LKH runs took a total of 415,948 seconds on a 500 MHz EV6 Alpha. Merging the tours (49.72 seconds) did not make an improvement.
8.27.01 0.0076% 300,876 - Established by Concorde with -C 20 (used 535 nodes in the branch-and-cut tree, 774,679 seconds on a 500 MHz EV6 Alpha).
3.22.02 Optimal 300,899 - Established by Concorde with -C 24 (root node was run with -C 36). The run used 5,455 nodes in the branch-and-cut tree and 7.9 million seconds on an AMD Athlon 1900+ (ran in parallel on a network of 15 workstations). The LP solver was QSopt.


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:  April 10, 2002.