GES-TSP: Learning-Based Graph Sparsification for Efficient TSP Solving

Jul 14, 2026

Researchers have introduced Graph Edge Sparsification (GES), a learning-based method for the Euclidean Traveling Salesman Problem (TSP) that adaptively prunes up to 95% of edges on the MATILDA dataset while maintaining a solution gap within 1% of optimal. The method significantly reduces graph size and accelerates solving, and on large-scale TSPLIB instances, pruning rates can exceed 99% with optimality gaps below 1%.

Why it matters: This approach could enable exact TSP solvers to efficiently handle much larger problems by dramatically reducing computational costs while maintaining near-optimal solutions.

Full story at: arXiv AI/ML ↗