David S. Johnson - Obtaining Test Instances

1. Optimization by Simulated Annealing: An Experimental Evaluation; Part I, Graph Partitioning, D. S. Johnson, C. R. Aragon, L. A. McGeoch and C. Shevon, Operations Research, 37:6 (1989), 865-892.

All the graphs used as test instances in this paper are located in directory pub/dsj/partition at dimacs.rutgers.edu. The graphs with G as the first character are random graphs: G1000.01 is the 1000-vertex graph with p=.01, etc. Graphs starting with U are geometric graphs: U500.10 is the 500-vertex geometric graph with "expected degree" 10, etc. The format for the test graphs is as follows:

Vertex Name (Coordinates) Degree Names of adjacent vertices

(the coordinates are 0.000000,0.000000 for random graphs and are the actual coordinates of the geometric model for geometric graphs.

Go there now.

2. Optimization by Simulated Annealing: An Experimental Evaluation; Part II, Graph Coloring and Number Partitioning, C. R. Aragon, D. S. Johnson, L. A. McGeoch and C. Schevon, Operations Research, 39:3 (1991), 378-406.

All the graphs used as test instances for graph coloring in this paper are located in directory pub/dsj/chrom at dimacs.rutgers.edu. Names can be decrypted as follows. The first character represents the type of graph, C for random graph, R for geometric graph. For random graphs, the suffix ".n" indicates the edge probability p=.n. The suffix ".5x" indicates s low chromatic number graph "cooked" to look like a p=.5 random graph. For geometric graphs, the suffix .n indicates that d=.n, the suffix .1c indicates the complement of a d=.1 graph. The graphs with prefixes B,D,E,F are additionan 1000-vertex p=.5 random graphs mentioned in Section 2.4.1 of the paper.

IMPORTANT NOTE: The files in this directory are in a different format from that used for the graph partitioning instances. Here because of the higher density of many of the graphs, we represent them by their incidence matrices, stored in bit vector form. A README file in the directory gives some sample C code for decoding them.

Go there now.

3. The Traveling Salesman Problem.

The testbed of instances used in the DIMACS Implementation Challenge on the TSP can be downloaded from the Challenge Website.

These include both randomly generated instances (C programs and seeds are provided to generate them) and the larger instances in Gerd Reinelt's popular TSPLIB database of (mostly) real-world instances. For the full set of TSPLIB instances, visit the TSPLIB website.

Last Updated: 8/24/2000