Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2603.23290 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866917539659907072 |
|---|---|
| author | Ciacco, Alessia Pugliese, Luigi Di Puglia Guerriero, Francesca |
| author_facet | Ciacco, Alessia Pugliese, Luigi Di Puglia Guerriero, Francesca |
| contents | The Traveling Salesman Problem is a fundamental combinatorial optimization problem widely studied in operations research. Despite its simple formulation, it remains computationally challenging due to the exponential growth of the search space and the large number of constraints required to eliminate subtours. This paper introduces a preprocessing strategy that significantly reduces the size of the optimization model by restricting the set of candidate arcs and retaining only the lowest-cost neighbors for each vertex. Computational experiments on TSPLIB benchmark instances demonstrate that the proposed approach substantially reduces the number of decision variables. The method is evaluated using both classical and quantum optimization techniques, showing improvements in computational time and reductions in optimality gaps. Overall, the results indicate that the proposed preprocessing enhances the scalability of the formulations and makes them more suitable for both classical solvers and emerging quantum optimization frameworks. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2603_23290 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Traveling Salesman Problem with a preprocessing method for classical and quantum optimization Ciacco, Alessia Pugliese, Luigi Di Puglia Guerriero, Francesca Quantum Physics Computational Engineering, Finance, and Science Combinatorics The Traveling Salesman Problem is a fundamental combinatorial optimization problem widely studied in operations research. Despite its simple formulation, it remains computationally challenging due to the exponential growth of the search space and the large number of constraints required to eliminate subtours. This paper introduces a preprocessing strategy that significantly reduces the size of the optimization model by restricting the set of candidate arcs and retaining only the lowest-cost neighbors for each vertex. Computational experiments on TSPLIB benchmark instances demonstrate that the proposed approach substantially reduces the number of decision variables. The method is evaluated using both classical and quantum optimization techniques, showing improvements in computational time and reductions in optimality gaps. Overall, the results indicate that the proposed preprocessing enhances the scalability of the formulations and makes them more suitable for both classical solvers and emerging quantum optimization frameworks. |
| title | Traveling Salesman Problem with a preprocessing method for classical and quantum optimization |
| topic | Quantum Physics Computational Engineering, Finance, and Science Combinatorics |
| url | https://arxiv.org/abs/2603.23290 |