|
 Concorde Home Documentation Download Benchmarks  TSP Links
| | Concorde Benchmarks We report below the running times for the Concorde TSP solver on all TSPLIB instances. Unless otherwise noted, the times are for the default 99.12.15 version of the code using 99 as the random number seed (that is, "concorde -s 99 xxx.tsp"). The tests were carried out on a 500 MHz Compaq XP1000 workstation. A comparison on a number of other machine types is given at the bottom of the page. TSPLIB Instances The TSPLIB is Gerhard Reinelt's library of 110 instances of the traveling salesman problem. Some of these instances arise from the task of drilling holes in printed circuit boards; others have been constructed artificially. (A popular way of constructing a TSP instance is to choose a set of actual cities and to define the cost of travel from X to Y as the distance between X and Y.) None of them (with a single exception) is contrived to be hard and none of them is contrived to be easy; their sizes range from 17 to 85,900 cities. Concorde's TSP solver has solved 106 instances from the library; the remaining four instances are still open problems. For several of the larger instances, links are given to detailed reports of the computations.
NOTES: (1) For the instance rl5934, the TSP solver was given the value of the optimal tour as an input parameter. (2) For the instances d2103, fnl4461, rl5915, and pla7397 the optimal value was given and the code was run with local cuts of size 24 (that is "-C 24") rather than the default. (3) The default code on pla7397 ran into difficulties with the LP solver, related to dual degeneracy in the LPs that were created. To solve this instance we ran the code with CCtsp_EDGE_DUST = 0.000001 and CCtsp_EDGE_LIFE = 50 (these settings cause the code to remove from the LP any column [edge] that has not been assigned an LP value greater than 0.000001 for 50 consecutive LPs). (4) The default options were not used on rl11849. Instead, several passes through the cutting plane routines were made before the branching process was initiated. (5) The running time for usa13509 is only a very rough estimate. The TSP solver was run in parallel on a network consisting of a wide variety of machine types. The run was made with an earlier (1998) version of Concorde's TSP solver, using multiple passes through the cutting plane routines. (6) The d15112 run was made with an updated version of Concorde. Like the usa13509 run, a large amount of CPU time was used in finding the initial LP relaxation. The final branching run was carried out on a network of 110 processors located at Rice and at Princeton. More information about the solution can be found on the d15112 page. (7) Some additional Concorde benchmarks can be found at Hans Mittelmann's TSP page. Machine Benchmarks To give an indication of the performance of Concorde on a variety of machine types, we ran a benchmark consisting of the 87 TSPLIB instances in the above table that solved in under 1,000 seconds on the XP1000. The total time to solve this set of instances is reported in the table given below. Note that this is only a rough measure of the performance of the machine types since the optimization algorithm will follow different paths on different machines (due to numerical issues in the linear programming solver).
Concorde Links
David Applegate, Robert Bixby, Vašek Chvátal, William Cook TSP home page. Last updated: July 5, 2001. |
