The Cloven Travelling Salesman: a new Approach to the ATSP Integrality Gap Estimation

The Travelling Salesman Problem (TSP) is a long-established combinatorial optimization problem, with a classic integer linear programming formulation by Dantzig, Fulkerson, and Johnson [10]. Due to its NP-hardness, approximation algorithms are of key importance, and so is the research on the TSP linear programming relaxation known as the Subtour Elimination Problem (SEP). The study of the integrality gap of the metric TSP, measuring the approximation accuracy of SEP as a ratio between the exact solution of TSP and the SEP relaxation, remains an open question as no definitive upper bound on it is known. The computation of the gap upper bound is generally achieved by enumerating the SEP polytope vertices and is thus practicable only for very small TSP instances, though estimates are obtained by restricting to subsets of high-gap vertices such as half-integer vertices. In this work, an alternative method for estimating the asymmetric TSP integrality gap is presented, where half-integer candidate instances are generated and then checked with efficient and original algorithms for their feasibility and extremality in the ASEP polytope. An implementation of the method was able to exhaustively determine the integrality gap of half-integer instances for n≤11, proving in a fraction of the runtime that the best-known estimates in the literature (by Elliott-Magwood [13]) are in fact the highest gaps attainable over half-integers.