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