November 19, 2013
Official site moves to http://dimacs.rutgers.edu/Challenges/TSP. Site at www.research.att.com is deactivated.
July 29, 2011
Corrected the lengths for the tours constructed by the Benchmark Greedy code on the four CEIL_2D instances in our test set (dsj1000, pla7397, pla33810, and pla85900). The code that generated these was a variant on the Benchmark version, and had an error when handling the ceiling metric. Thanks to "raoweizhen" for spotting this error.
December 11, 2008
Added optimal tour lengths for instances brd14051, d18512, pla33810, and pla85900, as computed in recent years by Bill Cook and collaborators - see http://www.tsp.gatech.edu/ and The Traveling Salesman Problem: A Computational Study, D.L. Applegate, R.E. Bixby, B. Chvatal, and W.J. Cook, Princeton University Press, Princeton, NJ, 2006. A citation to the latter book has also been added to the "About the Challenge" page.
November 26, 2008
Corrected Held-Karp Lower bound for E316k.0.
The previous value, 398582616.458995, was incorrect. Computations using Concorde on two separate machines confirms that the true value is roughly 398760104.63771. Thanks to Peter Merz for catching this error.
Also, the arrival date for the long awaited DIMACS Tech Report has now been postponed until Summer 2009. Added contributions still welcome.
November 16, 2004
Updated Fred Glover's affiliation.
It looks as if the long-awaited DIMACS Tech Report will now not appear until 2005, but we plan to get it done sometime in the first half of the year.
January 31, 2003
Corrected optimal value for dsj1000. The old entry was the optimal value under the ``rounded-to-nearest'' Euclidean metric, but the instance's prescribed metric is the ceiling metric. Thanks to Moshe Looks for catching this error.
August 22, 2002
Added new results for the Lin-Kernighan variants of Nguyen-Yosihara-Yamamori-Yasunaga and of David Neto. The latter help to better illustrate the effects of Neto's ``cluster compensation'' technique. Also corrected entries for the 10-neighbor Johnson-McGeoch Lin-Kernighan implementation, where the runs on random instances had mistakenly been performed with a depth bound of 50 rather than infinity.
Redesigned the Results page to make the presentations
more uniform and to include the abberviations used in
the Comparisons pages to
name the various algorithms/implementations. Visitors to the website
can now use their browser's
Extended the deadline for the DIMACS Tech Report to 1 September 2002, although the job of putting the report together has finally begun and so this may be the last extension.
August 16, 2002
Updated URL's for the Cook et al. Traveling Salesman Page and Bill Cook's homepage . Please inform dsj@research.att.com of any other outdated or inoperable links.
June 19, 2002
Added an Instance Comparison page, whereby one can see how all the implementations rank as to tour quality on a selected instance.
June 11, 2002
Added package for generating charts and comparisons using your own data, accessible through both the main and download pages (tarfile).
Updated Comparison and Results Pages so that data file names use the same abbreviations as were used in the TSP book chapter. (The book has now been published.) Added results for Walshaw's Multi-Level Helsgaun variant and Nguyen-Yoshihara-Yamamori-Yasunaga implementations of LK and ILK variants. Corrected typos in this page.
Fixed bug in instance generation code that on rare occasions could yield an incorrect "length" result for instance with the rounded-up Euclidean metric. (Thanks to Chris Walshaw for pointing out the error.)
Fixed bug in cgi-script that computed summary tables -- for TSPLIB instances it was only reporting the result for one of the listed instances. (Thanks to Nguyen Dinh Hung for pointing out the error.)
November 27, 2001
Replaced the drafts of STSP and ATSP chapters with new near-final versions that correct several typos and imprecisions.
Extended the deadline for the results if they are to be included in the DIMACS Tech Report until 28 February 2002.
October 1, 2001
Replaced the draft STSP chapter with a new version that corrects an error in the references (on page 77).
September 10, 2001
Replaced the draft STSP chapter with the "final" version.
August 28, 2001
Replaced the draft ATSP chapter with a "final" version that corrects typos and clarifies some of the writing.
August 6, 2001
Added a links to the postscript (80 pages) for a draft of the TSP book chapter summarizing the results of this Challenge as of 1 July 2001. Updated the about page to reflect a new planned deadline of 30 November 2001 for the multi-authored DIMACS Tech Report on the Challenge.
The chapter refers to a not-yet (but soon-to-be) implemented feature of the comparison page whereby one will be able to specify an instance and obtain a sorted summary of the results for all the heuristics in the Challenge on that instance. This will involve renaming many files to correspond to the new heuristic abbreviations specified in the chapter draft but should be implemented by the end of August.
July 25, 2001
Added a link on the ATSP page to the postscript for a draft chapter (45 pages) on experimental analysis of heuristics for the ATSP, to appear in the book The Traveling Salesman Problem and its Variations , G. Gutin and A. Punnen, editors, Kluwer Academic Publishers. A draft of a companion chapter on the symmetric TSP, summarizing results from the DIMACS Implementation Challenge on the TSP, should be posted in the next week or so, along with other updates to the Challenge website.
June 19, 2001
Replaced results for approximate Christofides with HK one-trees by ones for true Christofides using HK one-trees, true minimum matchings, and greedy shortcuts (Rohe). Also added results for Rohe's LK implementation using the above as starting tours.
June 17, 2001
Added ATSP page from which instances and instance generators for the Asymmetric TSP can be downloaded.
Added results for the best of ten runs of chained and iterated Lin-Kernighan, best of five tour merges, and for 10N-iteration Iterated Lin-Kernighan. Added results for Concorde's versions of 2-, 2.5-, and 3-Opt.
June 4, 2001
Fixed a bug present in some of our normalization codes that could cause
mis-estimates of 50% on selected
Added results for "Best of multiple runs" for Chained LK, Iterated
LK, and tourmerging, and 10N-iteration runs of the latter. Also
Added results for Nearest, Random, and Farthest Addition to the results for the
previously included "augmented addition" algorithms.
Added results for
May 17, 2001
Added runs of Jon Bentley's implementations of 2-Opt, 2.5-Opt, and 3-Opt, as well as runs of the Johnson-McGeoch implementations of 2-Opt, 3-Opt, and Lin-Kernighan on the MIPS processor for comparison purposes. Added additional text and pointers to help explain some of the algorithms on the results page.
Fixed a bug in the summary table generating script that underestimated
the tour quality for the 10,000-city Random Distance Matrix instance.
Revised results for the J-M implementations of 2-Opt etc. to fix a
bug that inflated running times for fractional-coordinate
May 9, 2001
Added additional running time normalization factor options on comparison page. Changed "Clarke-Wright" to "Clarke-Wright Savings Heuristic" to be more in line with the literature on that algorithm. Removed spurious data for Random Distance Matrix instances on several implementations (The only Concorde tour construction heuristic that actually handles these is Nearest Neighbor).
May 2, 2001
Added results for Concorde's Lin-Kernighan implementation, an augmented version of Lin-Kernighan by Harald Buesching, and Johnson-McGeoch's implementations of 2-Opt, 3-Opt, and Lin-Kernighan with 10 and 20 quadrant neighbors. (Previously results were only available for 40 quadrant neighbors.)
Made other minor corrections.
April 29, 2001
Added an algorithm that merely reads the instance to the second column of options on the Comparisons page. With this, one can determine what proportion of a heuristic's total time is spent on instance-reading. This was run on a 196 Mhz MIPS processor, and so yields the most accurate comparisons for heuristic results on the same processor. Charts and table for comparisons involving the "Reading algorithm" do not include Tour Quality comparisons.
Augmented the heuristic menus on the Comparison page to include all the heuristic runs covered on the Results page. From now on these two should be in sync. Added a few more references/algorithm explanations to the Results page.
April 26, 2001
Changed the format of the summary tables to increase clarity, and changed the TSPLIB entries in those tables to be averages over sets of instances, as specified on the generated page.
Rearranged the Results page to better mirror the algorithm grouping for the TSPbook Chapter on the Challenge, and linked in a description of the Stem-and-Cycle Ejection Chain algorithm.
April 25, 2001
Added a Comparison page so that visitors can compare the results for various algorithms based on online-generated charts and tables. Thanks to David Applegate for help with the online generation of charts, and to John Denker for general help with CGI-scripts.
Added results for the Applegate-Cook-Rohe implementation of N-iteration Chained Lin-Kernighan, for a stem-and-cycle ejection chain variant on LK due to Rego, Glover, and Gamboa, and for an implementation of Boruvka's algorithm due to the latter group.
March 30, 2001
Added results for the multi-trial version of Helsgaun's LKH variant on Lin-Kernighan.
Corrected bug in cgi-script for summary table that led to underestimates of average running times for random distance matrix instances. Also, modified this and the cgi-script for normalized data so that if the instance size exceeds the maximum size for which the benchmark was run on the given machine, the time is normalized based on the largest instance size for which the benchmark code WAS run.
March 28, 2001
Added results for Concorde's implementation of chained Lin-Kernighan as computed on two different machines.
Added results for Balas and Simonetti's dynamic programming based tour improvement heuristic, along with a text file of Simonetti's description of the algorithm and analysis of its results (more of these short descriptions from participants will be added in soon - if you haven't sent me one for your submission, please do so).
Added results for additional tour construction heuristics, including the GENI and GENIUS algorithms of Gendreau, Hertz, and Laporte (as modified by David Johnson for improved speed and memory usage without affecting solutions quality).
Added results for C316k.0 for several of the Johnson-McGeoch local optimization implementations.
Noted of home page that results are still being accepted for the DIMACS tech report, since it will be sometime yet before the editors have time to put it together.
Added an additional reason why normalized running times might be inaccurate to the discussion in norm.html
March 9, 2001
Introduced a cgi-script to automatically generate the normalized datafiles (previously simply referred to as html tables). Also added a cgi-script to automatically generate a summary table for each algorithm, so that results for similarly sized instances from each class can be more readily compared.
Added results for a variety of additional tour construction heuristics implemented by Bentley, Johnson, and McGeoch.
January 26, 2001
Added results from
Modified homepage and ``About'' page to reflect the fact that the initial deadline has now passed, but that submissions were still welcome (indefinitely) and that a new section devoted to the asymmetric TSP should be opened shortly.
October 30, 2000
Replaced homepage (index.html) with a simpler page including some
graphics and pointers to the other pages. Former homepage is now
about.html.
Extended the deadline for inclusion in the initial technical report until November 30, 2000.
September 5, 2000
Added Held-Karp bound for the new benchmark instances C316k.0
(and the time for computing it) to relevant tables.
Added .pdf version of the viewgraphs for David Johnson's talk about the Challenge at the 2000 International Symposium on Mathematical Programming. Link is on the bottom of the Challenge homepage (and here).
August 28, 2000
Added a 316,228-city random clustered instance to the test suite, which
can be generated by the command
If correctly generated, the instance should consist of 6459637 bytes. We will shortly add results for this instance to the data for Johnson-McGeoch codes that can handle instances this large. Participants who have already submitted data and want to include this instance as well can send results for the instance alone if run on the same machine as your other results, and we will add them to your data files.
August 21, 2000
Put link at the bottom of the homepage (and here)
to the postscript for the
viewgraphs for David Johnson's talk about
the Challenge at the 2000 International Symposium on Mathematical
Programming in Atlanta (August 7-11). There are 29 viewgraphs in
the file, including displays of some of the random instances in
the testbed and some early attempts at graphical comparisons of
algorithms. Some of these will soon appear in gif form in the
relevant results sections.
August 4, 2000
Replaced table illustrating imprecision of normalization process with
a more direct one containing data for Lin-Kernighan as well as the
Benchmark Greedy code.
August 2, 2000
Moved Machine Comparisons and Algorithm Results to a new ``Results'' page and
changed other pages to reflect this.
Reformatted the Download page adding some
extra explanatory remarks.
Resorted the machine speed table according to speed on small instances.
Reformatted results tables to give excess over optimal (where known) as well as excess of the Held-Karp bound, and to include a normalized running time (obtained by dividing by the benchmark greedy time for the machine used). Added a table illustrating the imprecision of the normalization process.
Added results for Applegate-Cook-Rohe Lin-Kernighan and Chained Lin-Kernighan, for Johnson-McGeoch Iterated Lin-Kernighan, and for Rohe's Lagrangean relaxation code for approximating the Held-Karp bound.
Added results for the Clarke-Wright tour construction algorithm and ran the benchmark greedy code on the full suite of testbed instances using a second machine, so as to provide an additional perspective on the accuracy of running time normalization.
July 24, 2000
Added IBM 595 to machine table, updated results for Concorde.
June 15, 2000
Added optimal tour length for the final 3162-city random Euclidean instance.
June 8, 2000
Updated tar and zip files for benchmark codes to correct problems pointed
out by David Applegate. Two of the included files have been changed:
June 1, 2000
Officially announced the Challenge