 |


Back to Egypt

World TSP

National TSPs

TSP Home Page




TSP Links
|
 |

EG7146 - Egypt Computation Log
Instance Created: July 29, 2001
Number of Cities: 7,146
Status: OPEN
Best Tour: 172,386
Best Lower Bound: 172,350
History
Date |
Gap |
Lower Bound |
Tour |
8.12.01 |
0.098% |
172,350 - Concorde -C 20, with Cplex 6.5 LP solver, 124 hours, 500 MHz EV6 Alpha, the branch-and-cut run created a search tree with 431 nodes. |
172,519 - found
by a call to linkern during Concorde's branch-and-cut run |
8.14.01 |
0.021% |
|
172,387 - found by running linkerh to produce 10 tours, and then merging the tours using tmerge.
The 10 linkerh runs took a total of 46,249 seconds on a 500 MHz EV6 Alpha and the tmerge run took an additional 49.45 seconds.
The best of the linerh tours had length 172,396. |
5.3.03 |
0.021% |
|
172,386 - found by Keld Helsgaun running a variant of his LKH code. |
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: August 19, 2004.
|