Using a Hamiltonian cycle problem algorithm to assist in solving difficult instances of Traveling Salesman Problem

Vladimir Ejov, Michael Haythorpe, Serguei Rossomakhine

We describe a hybrid procedure for solving the traveling salesman problem (TSP) to provable optimality. We first sparsify the instance, and then use a hybrid algorithm that combine…