Search papers, labs, and topics across Lattice.
This paper introduces a two-stage graph sparsification method for the Traveling Salesman Problem (TSP) that combines heuristic pre-processing with a learned model for density reduction. The approach aims to balance candidate graph density and coverage, addressing limitations of existing single-stage heuristics and neural methods. Experiments across diverse TSP instances demonstrate that the two-stage method reduces graph density, maintains high coverage, and generalizes better than existing neural sparsification techniques, especially at larger scales.
Combining heuristics with learned models for graph sparsification yields significantly sparser and more reliable candidate graphs for TSP solvers, outperforming purely heuristic or learned approaches, especially as problem size increases.
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, $\alpha$-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 $\alpha$-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.
