\(\)
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 small-sized instances. In particular, we focus on the geometric properties and symmetries of the ASEP polytope ( \(P_{ASEP}^n\) ) and its vertices. The polytope's symmetries are exploited to design a heuristic pivoting algorithm for the search of vertices where the integrality gap is maximized.
Furthermore, a general procedure for the extension of vertices from \(P_{ASEP}^n\) to \(P_{ASEP}^{n+1}\) is defined. The generated vertices improve the known lower bounds of the integrality gap for \(16 \leq n \leq 22\) and, provide small hard-to-solve ATSP instances.