  We present a benchmark set for Traveling salesman problem (TSP) with
characteristics that are different from the existing benchmark sets. In
particular, we focus on small instances which prove to be challenging for one
or more state-of-the-art TSP algorithms. These instances are based on difficult
instances of Hamiltonian cycle problem (HCP). This includes instances from
literature, specially modified randomly generated instances, and instances
arising from the conversion of other difficult problems to HCP. We demonstrate
that such benchmark instances are helpful in understanding the weaknesses and
strengths of algorithms. In particular, we conduct a benchmarking exercise for
this new benchmark set totalling over five years of CPU time, comparing the TSP
algorithms Concorde, Chained Lin-Kernighan, and LKH. We also include the HCP
heuristic SLH in the benchmarking exercise. A discussion about the benefits of
specifically considering outlying instances, and in particular instances which
are unusually difficult relative to size, is also included.

Data Structures and Algorithms