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 10^27. 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.


Files contained in this data set: 

Tnm.cpp :  A C++-program to generate the Tnm-instances.
Tnm_instances.zip :  All Tnm-instances with 52 to 199 vertices.
Tnm_logfiles.zip log :  files of all Concorde runs on the Tnm-instances as described in our paper.
TSPLIB_logfiles.zip :  log files of all Concorde runs on the TSPLIB instances as described in our paper.