# Learning to Sparsify Travelling Salesman Problem Instances

arXiv: https://arxiv.org/abs/2104.09345 · HTML: https://mlsanity.com/paper/2104.09345/

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- Builds on 10 of its 33 references that are in the map.
- First posted on arXiv 19 Apr 2021.

## Builds on (most cited first, 10 of 10)

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [Pointer Networks](https://mlsanity.com/paper/1506.03134/) (2015)
- [Attention, Learn to Solve Routing Problems!](https://mlsanity.com/paper/1803.08475/) (2018)
- [Neural Combinatorial Optimization with Reinforcement Learning](https://mlsanity.com/paper/1611.09940/) (2016)
- [Reinforcement Learning for Solving the Vehicle Routing Problem](https://mlsanity.com/paper/1802.04240/) (2018)
- [Hybrid Models for Learning to Branch](https://mlsanity.com/paper/2006.15212/) (2020)
- [Generalization of Machine Learning for Problem Reduction: A Case Study on Travelling Salesman Problems](https://mlsanity.com/paper/2005.05847/) (2020)
- [Fine-grained Search Space Classification for Hard Enumeration Variants of Subset Problems](https://mlsanity.com/paper/1902.08455/) (2019)
- [Learning Multi-Stage Sparsification for Maximum Clique Enumeration](https://mlsanity.com/paper/1910.00517/) (2019)
- [Edge Elimination in TSP Instances](https://mlsanity.com/paper/1402.7301/) (2014)

## Built on by (most cited first, 9 of 9)

- [Revisit the Algorithm Selection Problem for TSP with Spatial Information Enhanced Graph Neural Networks](https://mlsanity.com/paper/2302.04035/) (2023)
- [COMBHelper: A Neural Approach to Reduce Search Space for Graph Combinatorial Problems](https://mlsanity.com/paper/2312.09086/) (2023)
- [A New Constructive Heuristic driven by Machine Learning for the Traveling Salesman Problem](https://mlsanity.com/paper/2108.10224/) (2021)
- [Learning to Prune Instances of Steiner Tree Problem in Graphs](https://mlsanity.com/paper/2208.11985/) (2022)
- [Machine Learning Constructives and Local Searches for the Travelling Salesman Problem](https://mlsanity.com/paper/2108.00938/) (2021)
- [The (Un)Scalability of Heuristic Approximators for NP-Hard Search Problems](https://mlsanity.com/paper/2209.03393/) (2022)
- [Imitation Learning for Combinatorial Optimisation under Uncertainty](https://mlsanity.com/paper/2601.05383/) (2026)
- [Machine Learning-based Two-Stage Graph Sparsification for the Travelling Salesman Problem](https://mlsanity.com/paper/2604.20236/) (2026)
- [GES-TSP: Graph Edge Sparsification for TSP](https://mlsanity.com/paper/2607.09708/) (2026)

## Abstract (arXiv)

In order to deal with the high development time of exact and approximation algorithms for NP-hard combinatorial optimisation problems and the high running time of exact solvers, deep learning techniques have been used in recent years as an end-to-end approach to find solutions. However, there are issues of representation, generalisation, complex architectures, interpretability of models for mathematical analysis etc. using deep learning techniques. As a compromise, machine learning can be used to improve the run time performance of exact algorithms in a matheuristics framework. In this paper, we use a pruning heuristic leveraging machine learning as a pre-processing step followed by an exact Integer Programming approach. We apply this approach to sparsify instances of the classical travelling salesman problem. Our approach learns which edges in the underlying graph are unlikely to belong to an optimal solution and removes them, thus sparsifying the graph and significantly reducing the number of decision variables. We use carefully selected features derived from linear programming relaxation, cutting planes exploration, minimum-weight spanning tree heuristics and various other local and statistical analysis of the graph. Our learning approach requires very little training data and is amenable to mathematical analysis. We demonstrate that our approach can reliably prune a large fraction of the variables in TSP instances from TSPLIB/MATILDA (>85%) while preserving most of the optimal tour edges. Our approach can successfully prune problem instances even if they lie outside the training distribution, resulting in small optimality gaps between the pruned and original problems in most cases. Using our learning technique, we discover novel heuristics for sparsifying TSP instances, that may be of independent interest for variants of the vehicle routing problem.