Hard
to Solve Instances of the Euclidean Traveling Salesman Problem
Stefan Hougardy and
Xianghui Zhong
Research
Institute for Discrete Mathematics, University of Bonn
September 2018
In our paper Hard to Solve
Instances of the Euclidean Traveling Salesman Problem we
construct a family of Euclidean instances for the Traveling Salesman
Problem for which the integrality ratio of the subtour LP converges to
4/3. These instances turn out to be very hard to solve with exact TSP
solvers. On a 200 vertex instance from our family, Concorde, the
fastest known exact TSP solver, needs more than 1,000,000 times the
runtime it needs for TSPLIB instances of similar size. On a 1000 vertex
instance the runtime factor is already about 1027. Here we
provide instances with up to 200 vertices from our family in TSPLIB
format. We also provide code for generating these instances for an
arbitrary number of vertices. Finally we make all the .log-files
available of the runs of Concorde we describe in our paper.
Tnm.cpp A
C++-program to generate the Tnm-instances.
Tnm_instances.zip All
Tnm-instances listed in the table below.
number of vertices
|
filename
|
integrality gap
|
optimum tour length
|
Concorde runtime in seconds*
|
52
|
Tnm52.tsp
|
1.1207
|
551,609
|
12
|
55
|
Tnm55.tsp
|
1.1265
|
605,778
|
17
|
58
|
Tnm58.tsp
|
1.1313 |
660,687
|
21
|
61
|
Tnm61.tsp
|
1.1350 |
716,131
|
30
|
64
|
Tnm64.tsp
|
1.1383
|
770,162
|
33
|
67
|
Tnm67.tsp
|
1.1420 |
825,328
|
47
|
70
|
Tnm70.tsp
|
1.1453
|
881,036
|
68
|
73
|
Tnm73.tsp
|
1.1587 |
893,843
|
84
|
76
|
Tnm76.tsp
|
1.1619 |
949,961
|
103
|
79
|
Tnm79.tsp
|
1.1648
|
1,006,535
|
152
|
82
|
Tnm82.tsp
|
1.1665
|
1,062,686
|
190
|
85
|
Tnm85.tsp
|
1.1663
|
1,117,381
|
164
|
88
|
Tnm88.tsp
|
1.1673 |
1,172,734
|
196
|
91
|
Tnm91.tsp
|
1.1697
|
1,228,726
|
275
|
94
|
Tnm94.tsp
|
1.1724
|
1,285,416
|
397
|
97
|
Tnm97.tsp
|
1.1747 |
1,342,086 |
566
|
100
|
Tnm100.tsp
|
1.1762
|
1,398,070
|
664
|
103
|
Tnm103.tsp
|
1.1845
|
1,412,229
|
478
|
106
|
Tnm106.tsp
|
1.1867
|
1,469,617
|
761
|
109
|
Tnm109.tsp
|
1.1893
|
1,527,709 |
1068
|
112
|
Tnm112.tsp
|
1.1911
|
1,585,157
|
1721
|
115
|
Tnm115.tsp
|
1.1921 |
1,641,752
|
1523
|
118
|
Tnm118.tsp
|
1.1931 |
1,698,486
|
2261
|
121
|
Tnm121.tsp
|
1.1943
|
1,755,689 |
2329
|
124
|
Tnm124.tsp
|
1.1957 |
1,813,276
|
3082
|
127
|
Tnm127.tsp
|
1.1971
|
1,871,162
|
3787
|
130
|
Tnm130.tsp
|
1.1982
|
1,928,734
|
4332
|
133
|
Tnm133.tsp
|
1.2059 |
1,944,317
|
6254
|
136
|
Tnm136.tsp
|
1.2070
|
2,002,445 |
6912
|
139
|
Tnm139.tsp
|
1.2082 |
2,060,637
|
9347
|
142
|
Tnm142.tsp
|
1.2092
|
2,118,758
|
9980
|
145
|
Tnm145.tsp
|
1.2102
|
2,177,169
|
12990
|
148
|
Tnm148.tsp
|
1.2113
|
2,235,669
|
18144
|
151
|
Tnm151.tsp
|
1.2124
|
2,293,265
|
18866
|
154
|
Tnm154.tsp
|
1.2132
|
2,350,345
|
24972
|
157
|
Tnm157.tsp
|
1.2137 |
2,407,153
|
29190
|
160
|
Tnm160.tsp
|
1.2141
|
2,463,857 |
34022
|
163
|
Tnm163.tsp
|
1.2214
|
2,485,463
|
56671
|
166
|
Tnm166.tsp
|
1.2223
|
2,543,466
|
53752
|
169
|
Tnm169.tsp
|
1.2227
|
2,600,546
|
72038
|
172
|
Tnm172.tsp
|
1.2229 |
2,657,369 |
61625
|
175
|
Tnm175.tsp
|
1.2233
|
2,714,530
|
80703
|
178
|
Tnm178.tsp
|
1.2237 |
2,771,953
|
110158
|
181
|
Tnm181.tsp
|
1.2242 |
2,829,701
|
117373
|
184
|
Tnm184.tsp
|
1.2248 |
2,887,675 |
191357
|
187
|
Tnm187.tsp
|
1.2255
|
2,945,939
|
249657
|
190
|
Tnm190.tsp
|
1.2261 |
3,004,259
|
337307
|
193
|
Tnm193.tsp
|
1.2316 |
3,023,551
|
263334
|
196
|
Tnm196.tsp
|
1.2320
|
3,081,566
|
300945
|
199
|
Tnm199.tsp
|
1.2325 |
3,139,778 |
411222
|
*Average runtime of 10 independent runs on a 2.2GHz Intel Xeon
E5-2699. For details see the paper.
Tnm_logfiles.zip (174MB)
log files of all Concorde runs on the Tnm-instances as described
in our paper.
TSPLIB_logfiles.zip (32MB)
log files of all Concorde runs on the TSPLIB instances as
described in our paper.
Stefan Hougardy's
homepage