A note on exploiting the Hamiltonian cycle problem substructure of the Asymmetric Traveling Salesman Problem

The assignment problem is a well-known relaxation of the Asymmetric Traveling Salesman Problem (ATSP). Associated with every optimal dual solution to the assignment problem is a directed admissible graph. An ATSP solution is found if the admissible graph is Hamiltonian, otherwise the assignment problem bound may be strengthened. The exploitation of this result requires an exact algorithm for the directed Hamiltonian cycle problem. Computational results are presented for up to 3000 cities to show that determining the Hamiltonicity of admissible graphs improves the performance of an exact ATSP algorithm.