Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2511.05045 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909892252532736 |
|---|---|
| author | Sosso, Alessandro Bernardelli, Ambrogio Maria Gualandi, Stefano |
| author_facet | Sosso, Alessandro Bernardelli, Ambrogio Maria Gualandi, Stefano |
| contents | 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 Problem (ATSP). The core idea is to enumerate pairs of vertex-disjoint cycle covers that can be filtered and mapped to half-integer vertices of the subtour elimination polytope. The two-cycle covers are encoded as lexicographically ordered partitions of $n$ numbers, with an encoding that prevents the generation of several isomorphic vertices. However, since not every cycle cover pair can be mapped to a vertex of the subtour elimination polytope, we have designed an efficient property-checking procedure to control whether a given point is a vertex of the asymmetric subtour elimination polytope. The proposed approach turns upside down the algorithms presented in the literature that first generate every possible vertex and later filter isomorphic vertices. With our approach, we can replicate state-of-the-art results for n<=9 in a tiny fraction of time, and we compute for the first time the exact integrality gap of half-integer vertices of the asymmetric subtour elimination polytope for n=10, 11, 12. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2511_05045 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | The Cloven Traveling Salesman: Cycle Covers and the Integrality Gap of Small ATSP Instances Sosso, Alessandro Bernardelli, Ambrogio Maria Gualandi, Stefano Optimization and Control 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 Problem (ATSP). The core idea is to enumerate pairs of vertex-disjoint cycle covers that can be filtered and mapped to half-integer vertices of the subtour elimination polytope. The two-cycle covers are encoded as lexicographically ordered partitions of $n$ numbers, with an encoding that prevents the generation of several isomorphic vertices. However, since not every cycle cover pair can be mapped to a vertex of the subtour elimination polytope, we have designed an efficient property-checking procedure to control whether a given point is a vertex of the asymmetric subtour elimination polytope. The proposed approach turns upside down the algorithms presented in the literature that first generate every possible vertex and later filter isomorphic vertices. With our approach, we can replicate state-of-the-art results for n<=9 in a tiny fraction of time, and we compute for the first time the exact integrality gap of half-integer vertices of the asymmetric subtour elimination polytope for n=10, 11, 12. |
| title | The Cloven Traveling Salesman: Cycle Covers and the Integrality Gap of Small ATSP Instances |
| topic | Optimization and Control |
| url | https://arxiv.org/abs/2511.05045 |