Machine Learning for Two-Stage Graph Sparsification for the Travelling Salesman Problem
This work addresses the challenge of efficient TSP solving for computational optimization, offering a scalable method that improves over existing heuristics and neural methods, though it is incremental in combining known techniques.
The paper tackles the problem of graph sparsification for the Travelling Salesman Problem by proposing a two-stage approach that combines existing heuristics with machine learning to reduce candidate-graph density while maintaining high coverage, achieving substantial reductions across various distance types and problem sizes up to 500.
High-performance TSP solvers like LKH search within a sparsified candidate graph rather than over all possible edges. Graph sparsification is non-trivial: keep too many edges and the solver wastes time; cut too many and it loses edges that belong to the optimal tour. The two leading heuristic methods, $α$-Nearest and POPMUSIC, produce high-quality candidate graphs, but no single heuristic is both sparse and reliable across all instance sizes and distributions. Machine learning methods can potentially learn better sparsification models. However, existing approaches operate on the complete graph, which is expensive and mostly restricted to Euclidean distances. To address this issue, we propose a two-stage graph sparsification approach: Stage~1 takes the union of $α$-Nearest and POPMUSIC to maximise recall; Stage~2 trains a single model to reduce density. We conducted experiments across four TSPLIB distance types, five spatial distributions, and problem sizes from 50 to 500. The two-stage approach substantially reduces candidate-graph density while retaining high coverage, generalises across distance types and distributions, outperforms recent neural sparsification methods that are restricted to Euclidean distances, and becomes increasingly valuable at larger scales where single-stage heuristics degrade.