The Cloven Traveling Salesman: Cycle Covers and the Integrality Gap of Small ATSP Instances

Alessandro Sosso, Ambrogio Maria Bernardelli, Stefano Gualandi

This work proposes a novel enumeration algorithm for computing the integrality gap of small instances of the subtour elimination formulation for the Asymmetric Traveling Salesman P…