Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2509.13327 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866916955443691520 |
|---|---|
| author | Nakhle, Wissam |
| author_facet | Nakhle, Wissam |
| contents | We present a scalable, high-performance algorithm that deterministically solves large-scale instances of the Traveling Salesman problem (in its asymmetric version, ATSP) to optimality using commercially available computing hardware. By combining an efficient heuristic warm start, capable of achieving near-optimality within seconds in some cases, with a subtour elimination strategy that removes the need for traditional MTZ constraints, our approach consistently resolves instances up to 5,000 nodes (approximately 25 million binary variables) in record time on widely accessible computers, with eight logical processors. We demonstrate reproducible results with convergence rates comparable to those of high-performance computing frameworks. Real-time iteration tracking and an adaptable interface allow seamless integration into scheduling workflows in logistics, bioinformatics, and astronomy. Designed to streamline solutions to large-scale TSP problems across disciplines, our approach is benchmarked against widely used public datasets, offering a deterministic, resource-efficient alternative to conventional solvers that rely on supercomputing hardware. Our GTA (Gurobi Tabu Algorithm) algorithm is a fundamental shift of TSP solution bottleneck from algorithmic complexity to the underlying hardware (RAM and system memory), which is a highly desirable characteristic. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2509_13327 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | GTA -- An ATSP Method: Shifting the Bottleneck from Algorithm to RAM Nakhle, Wissam Data Structures and Algorithms We present a scalable, high-performance algorithm that deterministically solves large-scale instances of the Traveling Salesman problem (in its asymmetric version, ATSP) to optimality using commercially available computing hardware. By combining an efficient heuristic warm start, capable of achieving near-optimality within seconds in some cases, with a subtour elimination strategy that removes the need for traditional MTZ constraints, our approach consistently resolves instances up to 5,000 nodes (approximately 25 million binary variables) in record time on widely accessible computers, with eight logical processors. We demonstrate reproducible results with convergence rates comparable to those of high-performance computing frameworks. Real-time iteration tracking and an adaptable interface allow seamless integration into scheduling workflows in logistics, bioinformatics, and astronomy. Designed to streamline solutions to large-scale TSP problems across disciplines, our approach is benchmarked against widely used public datasets, offering a deterministic, resource-efficient alternative to conventional solvers that rely on supercomputing hardware. Our GTA (Gurobi Tabu Algorithm) algorithm is a fundamental shift of TSP solution bottleneck from algorithmic complexity to the underlying hardware (RAM and system memory), which is a highly desirable characteristic. |
| title | GTA -- An ATSP Method: Shifting the Bottleneck from Algorithm to RAM |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2509.13327 |