  This paper introduces a computational method for generating metric Travelling
Salesman Problem (TSP) instances having a large integrality gap. The method is
based on the solution of an integer programming problem, called IH-OPT, that
takes as input a fractional solution of the Subtour Elimination Problem (SEP)
on a TSP instance and computes a TSP instance having an integrality gap larger
than or equal to the integrality gap of the first instance. The decision
variables of IH-OPT are the entries of the TSP cost matrix, and the constraints
are defined by the intersection of the metric cone with an exponential number
of inequalities, one for each possible TSP tour. Given the very large number of
constraints, we have implemented a branch-and-cut algorithm for solving IH-OPT.
Then, by sampling cost vectors over the metric polytope and by solving the
corresponding SEP, we can generate random fractional vertices of the SEP
polytope. If we solve the IH-OPT problem for every sampled vertex using our
branch-and-cut algorithm, we can select the generated TSP instance (i.e., cost
vector), yielding the longest runtime for Concorde, the state-of-the-art TSP
solver. Our computational results show that our method is very effective in
producing challenging instances. As a by-product, we release the Hard-TSPLIB, a
library of 41 small metric TSP instances which have a large integrality gap and
are challenging in terms of runtime for Concorde.
