Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2506.10671 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866916792035704832 |
|---|---|
| author | Vercesi, Eleonora Barta, Janos Gambardella, Luca Maria Gualandi, Stefano Mastrolilli, Monaldo |
| author_facet | Vercesi, Eleonora Barta, Janos Gambardella, Luca Maria Gualandi, Stefano Mastrolilli, Monaldo |
| contents | 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 ($P^{n}_{ASEP}$) 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 $P^{n}_{ASEP}$ to $P^{n + 1}_{ASEP}$ 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2506_10671 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | On the integrality Gap of Small Asymmetric Traveling Salesman Problems: A Polyhedral and Computational Approach Vercesi, Eleonora Barta, Janos Gambardella, Luca Maria Gualandi, Stefano Mastrolilli, Monaldo Optimization and Control Discrete Mathematics 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 ($P^{n}_{ASEP}$) 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 $P^{n}_{ASEP}$ to $P^{n + 1}_{ASEP}$ 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. |
| title | On the integrality Gap of Small Asymmetric Traveling Salesman Problems: A Polyhedral and Computational Approach |
| topic | Optimization and Control Discrete Mathematics |
| url | https://arxiv.org/abs/2506.10671 |