.... Solving TSPs

Back to Argentina

World TSP

National TSPs

TSP Home Page


TSP Links


Home page

AR9152 - Argentina Computation Log

Instance Created:  July 29, 2001
Number of Cities:  9,152
Status:  OPEN
Best Tour:  837,479
Best Lower Bound:  837,377


Date Gap Lower Bound Tour
8.23.01 837,583 - Merging 10 linkerh tours. The 10 linkern runs took a total of 460,058 seconds on a 500 MHz EV6 Alpha, merging took an additional 194.11 seconds. The best of the 10 linkerh tours had length 837,794.
8.23.01 0.025% 837,377 - Established by Concorde with -C 20 (used 227 nodes in the branch-and-cut tree, 324,453 seconds on a 500 MHz EV6 Alpha).
9.01.01 0.021% 837,556 - Merged 40 LKH tours (n trials per run). The 40 LKH runs took a total of 1,474,264 seconds on a 500 MHz EV6 Alpha, merging took an additional 532.78 seconds. The best of the 40 LKH tours had length 837,635.
10.15.01 0.017% 837,520 - - Found by Keld Helsgaun using variants of his LKH code. The running time was approximately 2 days on a 400 MHz Macintosh PowerBook G3.
16.3.03 0.012% 837,479 - - Found by Hung Dinh Nguyen using a hybrid genetic algorithm, starting from the 837,583 tour described above. The running time was 24301 seconds on a single processor of a Sun Ultra 80 (450 MHz).


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.
4. linkerh is an implementation of the Lin-Kernighan heuristic, making use of a number of the ideas introduced in Keld Helsgaun's LKH code.

Back to TSP home.

Last Updated:  March 16, 2003.