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.

Name

Nodes in Search Tree

Running Time (seconds)

burma14 1   0.06 
ulysses16 1   0.22 
gr17 1   0.08 
gr21 1   0.03 
ulysses22 1   0.53 
gr24 1   0.07 
fri26 1   0.07 
bayg29 1   0.09 
bays29 1   0.13 
dantzig42 1   0.23 
swiss42 1   0.13 
att48 1   0.56 
gr48 1   0.67
hk48 1   0.17 
eil51 1   0.73 
berlin52 1   0.29 
brazil58 1   0.68 
st70 1   0.50 
eil76 1   0.30 
pr76 1   1.86 
gr96 1   6.71 
rat99 1   0.95 
kroA100 1   1.00 
kroB100 1   2.36 
kroC100 1   0.96 
kroD100 1   1.00 
kroE100 1   2.44 
rd100 1   0.67 
eil101 1   0.74 
lin105 1   0.59 
pr107 1   1.03 
gr120 1   2.23 
pr124 1   3.64 
bier127 1   1.65 
ch130 1   2.13 
pr136 1   3.97 
gr137 1   3.42 
pr144 1   2.58 
ch150 1   3.03 
kroA150 1   5.00 
kroB150 1   4.23 
pr152 1   7.93 
u159 1   1.00 
si175 3   13.09 
brg180 1   1.46 
rat195 5   22.23 
d198 3   11.82 
kroA200 1   6.59 
kroB200 1   3.91 
gr202 1   5.01 
ts225 1   20.52 
tsp225 1   15.01 
pr226 1   4.35 
gr229 3   38.61 
gil262 1   13.06 
pr264 1   2.67 
a280 3   5.37 
pr299 3   17.49 
lin318 1   9.74 
rd400 15   148.42 
fl417 5   57.75 
gr431 13   133.29 
pr439 15   216.75 
pcb442 9   49.92 
d493 5   113.32 
att532 7   109.52 
ali535 3   53.14 
si535 3   43.13 
pa561 17   246.82 
u574 1   23.04 
rat575 25   363.07 
p654 3   26.52 
d657 13   260.37 
gr666 3   49.86 
u724 11   225.44 
rat783 1   37.88 
dsj1000 7   410.32 
pr1002 1   34.30 
si1032 1   25.47 
u1060 21   571.43 
vm1084 11   604.78 
pcb1173 19   468.27 
d1291 45 27393.72 
rl1304 1   189.20 
rl1323 25   3742.25 
nrw1379 19   578.42 
fl1400 5   1548.51 
u1432  3   223.70 
fl1577 7   6705.04 
d1655 5   263.03 
vm1748 17   2223.65 
u1817 887 449230.55 
rl1889 83 10023.02 
d2103 169 11179253.91 (2)
u2152 309 45204.53 
u2319 13   7067.93 
pr2392 1   116.86 
pcb3038 313 80828.87 
fl3795 21 69886.48 
fnl4461 213 53420.13 (2)
rl5915 161 2319671.71 (2)
rl5934 205 588936.85 (1)
pla7397 101 428996.2 (3)
rl11849 431 ~155 days (4)
usa13509 9539 ~4 years (5)
brd14051 -- OPEN 
d15112 164569 ~22.6 years (6)
d18512 -- OPEN 
pla33810 -- OPEN 
pla85900 -- OPEN 

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).

Machine Type

Operating System

Total Time (seconds)

Compaq XP1000 (500 MHz) True64 Unix 5901
AMD Athlon (800 MHz) FreeBSD 9214
AMD Athlon (550 MHz) FreeBSD 11782
Intel Pentium III (600 MHz) Redhat Linux 6.1 11935
AlphaServer 4100 (400 MHz, EV56) Digital Unix 14676
Intel Pentium II (300 MHz) Solaris 2.6 20431
UltraSparc 30 (300 MHz) Solaris 2.6 21056
Intel Pentium Pro (200 MHz) Solaris 2.6 31551
Sun Ultra 1 (167 MHz) Solaris 2.6 42833