In this paper, we investigate the integrality gap of the Asymmetric Traveling Salesman Problem (ATSP) with respect to the linear relaxation given by the Asymmetric Subtour Elimination Problem (ASEP) for instances with n nodes, where n is small. In particular, we focus on the geometric properties and symmetries of the ASEP polytope (PASEPn) and its vertices. The polytope's symmetries are exploited to design a heuristic pivoting algorithm to search vertices where the integrality gap is maximized. Furthermore, a general procedure for the extension of vertices from PASEPn to PASEPn+1 is defined. The generated vertices improve the known lower bounds of the integrality gap for 16≤n≤22 and, provide small hard-to-solve ATSP instances.
On the integrality gap of small Asymmetric Traveling Salesman Problems: A polyhedral and computational approach
Vercesi, Eleonora
;Gualandi, Stefano;
2025-01-01
Abstract
In this paper, we investigate the integrality gap of the Asymmetric Traveling Salesman Problem (ATSP) with respect to the linear relaxation given by the Asymmetric Subtour Elimination Problem (ASEP) for instances with n nodes, where n is small. In particular, we focus on the geometric properties and symmetries of the ASEP polytope (PASEPn) and its vertices. The polytope's symmetries are exploited to design a heuristic pivoting algorithm to search vertices where the integrality gap is maximized. Furthermore, a general procedure for the extension of vertices from PASEPn to PASEPn+1 is defined. The generated vertices improve the known lower bounds of the integrality gap for 16≤n≤22 and, provide small hard-to-solve ATSP instances.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
