Machine Learning for Two-Stage Graph Sparsification for the Travelling Salesman Problem

arXiv:2604.20236v1 Announce Type: new Abstract: 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: Stage1 takes the union of alpha-Nearest and POPMUSIC to maximise recall; Stage2 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.

Related

• Improved large-scale graph learning through ridge spectral sparsification
• Empowering Targeted Neighborhood Search via Hyper Tour for Large-Scale TSP
• Accelerating Optimization and Machine Learning through Decentralization
• Graph Transformer-Based Pathway Embedding for Cancer Prognosis

Source: arXiv cs.LG | 2026-04-23