 |


Back to Tanzania

World TSP

National TSPs

TSP Home Page




TSP Links
|
 |

TZ6117 - Tanzania Computation Log
Instance Created: July 29, 2001
Number of Cities: 6,117
Status: OPEN
Best Tour: 394,718
Best Lower Bound: 394,609
History
Date |
Gap |
Lower Bound |
Tour |
8.15.01 |
|
|
394,742 - found by running linkerh to produce 10 tours, and then merging the tours using tmerge.
The 10 linkerh runs took a total of 30,079.59 seconds on a 500 MHz EV6 Alpha and the tmerge run took an additional 24.10 seconds.
The best of the linerh tours had length 394,797. |
8.15.01 |
|
|
394,726 - found by running Keld Helsgaun's LKH code 10 times, each with 6117 trials, and choosing the best tour. The total running time was 35,787.17 seconds on a 1.33 GHz AMD Athlon processor. |
8.16.01 |
0.046% |
394,543 - Concorde -C 24, with Cplex 6.5 LP solver, 351 hours, 500 MHz EV6 Alpha processor, the branch-and-cut run created 631 nodes in the search tree |
|
8.17.01 |
0.044% |
|
394,718 - found by running LKH to produce 10 tours, and then merging the tours using tmerge.
The 10 LKH runs took a total of 52,196.23 seconds on a 500 MHz EV6 Alpha and the tmerge run took an additional 17.63 seconds.
The best of the LKH tours had length 394,730. |
3.13.02 |
0.027% |
394,609 - Concorde -C 24, with QSopt LP solver, 1,556 hours, AMD Athlon 1900+ processor, the branch-and-cut run created 2,369 nodes in the search tree. The root LP was run with -C 40; the branching was carried out in parallel on a network of 15 AMD workstations |
|
Notes
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 13, 2002.
|