GES-TSP: Graph Edge Sparsification for TSP
06:00 · July 14, 2026 · arXiv cs.AI RSS
Solving large-scale instances of the Traveling Salesman Problem (TSP) exactly is computationally expensive. Researchers often employ graph sparsification methods to improve computational efficiency. Traditional sparsification methods typically rely on fixed heuristics and fail to fully exploit instance-specific structural information. In this paper, we propose Graph Edge Sparsification (GES), a learning-based sparsification approach for Euclidean TSP. By incorporating geometric structural information and combinatorial optimization technology, our proposed method adaptively generates a sparsification graph for different instances, significantly reducing the graph size and accelerating the solving process. Experimental results demonstrate that our sparsification method can prune up to 95% of edges on the MATILDA dataset, while keeping the solution gap within 1% of the optimal value. Moreover, our approach exhibits strong generalization capability on the TSPLIB benchmark.In some large-scale instances, the pruning rate exceeds 99%, while the optimality gap remains below 1%.
Summary
The article introduces Graph Edge Sparsification (GES), a learning-based method that reduces the size of Euclidean TSP instances before they are passed to exact solvers. Standard TSP formulations operate on complete graphs whose edge count grows quadratically with the number of cities, rendering exact branch-and-cut procedures such as SCIP impractical for large point sets. GES therefore constructs a much smaller candidate graph while preserving edges that belong to near-optimal tours.
The pipeline begins with a geometric coarse sparsification step that replaces the complete graph by its Delaunay triangulation, which already contains only a linear number of edges and retains many tour edges. A Graph Attention Network is then trained to assign importance scores to these remaining edges. The attention mechanism incorporates both node embeddings derived from coordinates and explicit edge features such as Euclidean length, allowing the model to adapt its pruning decisions to the specific instance distribution. After scoring, low-ranked edges are discarded, yielding a final sparse graph that is supplied to the solver.
On the MATILDA benchmark the method removes up to 95 percent of edges while keeping the optimality gap below one percent; on selected large TSPLIB instances the pruning rate exceeds 99 percent under the same quality constraint. Because the resulting graphs remain connected and contain high-quality tour edges, exact solvers converge substantially faster than when run on either the original complete graph or graphs produced by fixed heuristics such as k-nearest-neighbor or plain Delaunay triangulation. The approach also shows competitive generalization when transferred from synthetic training data to real-world TSPLIB instances.
Why it matters
This research is highly relevant for AI researchers and operations research practitioners in the Netherlands, particularly those optimizing logistics, supply chain, and routing systems. The integration of Graph Neural Networks with classical combinatorial optimization offers actionable, scalable methodologies for Dutch enterprises dealing with complex transportation networks.
