Tar and Zip files containing Makefile and C programs for the Greedy benchmark
algorithm and for generators of three types of random instances: uniform
points in the plan, clustered points, random distance matrices. They also
contain a README file that lists the commands for generating all the
randomly generated instances in the testbed, and a program for verifying
the length of the tour corresponding to a given permutation of the cities
( **tarfile**,
**zipfile** ).

All benchmark instances are in the standard TSPLIB format as specified
in the following documentation from the TSPLIB website
( postscript ).
The format and metric used for each instance is specified in the instance's header
in terms explained in the TSPLIB documentation.
The testbed uses only the following three types: two dimensional
Euclidean metric rounded to the nearest integer (`EUC_2D`),
two dimensional Euclidean metric rounded up (`CEIL_2D`),
and explicit distance matrix presented in upper diagonal form
(`UPPER_DIAG_ROW`).
To visit the TSPLIB website, click
here.

Benchmark TSPLIB Instances
( tarfile, zipfile )

Tar and Zip files containing all instances from TSPLIB with 1000 or more cities as of 1 January 2000.

Samples of Randomly Generated Instances
( tarfile, zipfile )

Tar file containing one 1000-city instance of each type
(E1k.1, C1k.1, M1k.1) from the
randomly generated instance testbed.
Use these to verify that the instance generator codes are working correctly.

Held-Karp Lower Bounds and Optimal Tour Lengths (where known)
(text, html )

Held-Karp lower bounds for E3M.0 and E10M.0 are estimated using the
formula from Johnson, McGeoch, and Rothberg, ``Asymptotic experimental analysis
for the Held-Karp traveling salesman bound,'' in *Proc. 7th ACM-SIAM Symp.
on Discrete Algorithms*, 1996, pp. 341-350
(pdf, 10 pages).
The remainder were computed
exactly using the `Concorde` program of Applegate, Bixby, Chvatal, and Cook
(webpage),
with the result for E1M.0 computed at Rice University on a bigger machine
by Applegate et al.
Exact values are included in the text file; entries in the html file are
rounded to the nearest integer.
Optimal tour lengths for `TSPLIB` instances courtesy of `TSPLIB`
(webpage).
Optimal values for the randomly generated instances
were computed using `Concorde`.
In the ``html'' summary, the ``percent excess'' is the amount by which
the optimal tour length (when known) exceeds the Held-Karp lower bound.

The postscript figures included in the book chapters based on this Challenge
and gifs produced by the Comparison page on this website were produced
using a set of programs that have been bundled together into a
downloadable package
(tarfile)(zipfile).
This package requires that `gnuplot` and `ppmtogif`
are installed on your machine, but otherwise should be usable on most
`UNIX` and `LINUX`.
More details can be in this README text file
(also included in the package).