Instance Created:  July 29, 2001
Number of Cities:  33,708
Status:  OPEN
Best Tour:  959,289
Best Lower Bound:  959,011

History

Date	Gap	Lower Bound	Tour
8.24.01			959,569 - Found by LKH (n trials, 575,697 seconds on a 500 MHz EV6 Alpha).
8.26.01	0.058%	959,011 - Established by Concorde with -C 20 (used 55 nodes in the branch-and-cut tree, 111,824 seconds on a 500 MHz EV6 Alpha).
9.20.01	0.031%		959,313 - Found by Keld Helsgaun using variants of his LKH code. The running time was approximately 2 days on a 400 MHz PowerMac G4.
9.30.01	0.031%		959,304 - Found by Keld Helsgaun using variants of his LKH code. The running time was approximately 1 day on a 400 MHz PowerMac G4.
3.27.06	0.029%		959,291 - Found by Yuichi Nagata.
7.10.07	0.029%		959,289 - Found by Yuichi Nagata. Link to tour in TSPLIB format: bm33708.959289.tour

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.

Back to TSP home.