2018/06/25 by Pouya Baniasadi, Baniasadi, Pouya, Vladimir Ejov +5 · 2 citations
Computer Science · #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #cs.DS
paper · pdf · doi:10.48550/arxiv.1806.09285
21 pages, 11 tables
arxiv created 2018/06/25 · arxiv updated 2018/06/26
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.