Paper accepted on Discrete Optimization

Our paper “On the Integrality Gap of Small Asymmetric Travelling Salesman Problems: A Polyhedral and Computational Approach” has been accepted at the journal Discrete Optimization.

Here, we proposed a new approach for enumerating vertices of the asymmetric subtour elimination problems polytope that keep into account symmetries and tries to avoid them.

This allows us to improve lower bound for the integrality gap of the asymmetric travelling salesman problem with triangle inequality for small instances, and to prove that the integrality gap is at least 1.5 when you have just 18 cities.

As by-product, we release the Hard-ATSLIB, a library of 13 small hard instances of the asymmetric travelling salesman problem with triangle inequality.