# Neural Improvement Heuristics for Graph Combinatorial Optimization Problems

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 26 of its 52 references that are in the map.
- First posted on arXiv 1 Jun 2022.

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

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [Graph Attention Networks](https://mlsanity.com/paper/1710.10903/) (2017)
- [Curiosity-driven Exploration by Self-supervised Prediction](https://mlsanity.com/paper/1705.05363/) (2017)
- [Pointer Networks](https://mlsanity.com/paper/1506.03134/) (2015)
- [Benchmarking Graph Neural Networks](https://mlsanity.com/paper/2003.00982/) (2020)
- [Attention, Learn to Solve Routing Problems!](https://mlsanity.com/paper/1803.08475/) (2018)
- [Machine Learning for Combinatorial Optimization: a Methodological Tour d'Horizon](https://mlsanity.com/paper/1811.06128/) (2018)
- [Neural Combinatorial Optimization with Reinforcement Learning](https://mlsanity.com/paper/1611.09940/) (2016)
- [POMO: Policy Optimization with Multiple Optima for Reinforcement Learning](https://mlsanity.com/paper/2010.16011/) (2020)
- [Agent57: Outperforming the Atari Human Benchmark](https://mlsanity.com/paper/2003.13350/) (2020)
- [An Efficient Graph Convolutional Network Technique for the Travelling Salesman Problem](https://mlsanity.com/paper/1906.01227/) (2019)
- [Combinatorial optimization and reasoning with graph neural networks](https://mlsanity.com/paper/2102.09544/) (2021)
- [Reinforcement Learning for Combinatorial Optimization: A Survey](https://mlsanity.com/paper/2003.03600/) (2020)
- [Learning to Perform Local Rewriting for Combinatorial Optimization](https://mlsanity.com/paper/1810.00337/) (2018)
- [Learning Improvement Heuristics for Solving Routing Problems](https://mlsanity.com/paper/1912.05784/) (2019)
- [Generalize a Small Pre-trained Model to Arbitrarily Large TSP Instances](https://mlsanity.com/paper/2012.10658/) (2020)
- [Neural Large Neighborhood Search for the Capacitated Vehicle Routing Problem](https://mlsanity.com/paper/1911.09539/) (2019)
- [Learning to Iteratively Solve Routing Problems with Dual-Aspect Collaborative Transformer](https://mlsanity.com/paper/2110.02544/) (2021)
- [Learning the Travelling Salesperson Problem Requires Rethinking Generalization](https://mlsanity.com/paper/2006.07054/) (2020)
- [Matrix Encoding Networks for Neural Combinatorial Optimization](https://mlsanity.com/paper/2106.11113/) (2021)
- [Approximate Ranking from Pairwise Comparisons](https://mlsanity.com/paper/1801.01253/) (2018)
- [Edge-Featured Graph Attention Network](https://mlsanity.com/paper/2101.07671/) (2021)
- [Guidelines for the Computational Testing of Machine Learning approaches to Vehicle Routing Problems](https://mlsanity.com/paper/2109.13983/) (2021)
- [On the Linear Ordering Problem and the Rankability of Data](https://mlsanity.com/paper/2104.05816/) (2021)
- [Neural Combinatorial Optimization: a New Player in the Field](https://mlsanity.com/paper/2205.01356/) (2022)
- [A Diversity-Aware Memetic Algorithm for the Linear Ordering Problem: Improving Best-Known Solutions for Standard Benchmarks](https://mlsanity.com/paper/2106.02696/) (2021)

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

- [MARCO: A Memory-Augmented Reinforcement Framework for Combinatorial Optimization](https://mlsanity.com/paper/2408.02207/) (2024)
- [Unrealized Expectations: Comparing AI Methods vs Classical Algorithms for Maximum Independent Set](https://mlsanity.com/paper/2502.03669/) (2025)
- [Learning Memory-Enhanced Improvement Heuristics for Flexible Job Shop Scheduling](https://mlsanity.com/paper/2603.02846/) (2026)
- [Projecting Latent RL Actions: Towards Generalizable and Scalable Graph Combinatorial Optimization](https://mlsanity.com/paper/2605.19721/) (2026)

## Abstract (arXiv)

Recent advances in graph neural network architectures and increased computation power have revolutionized the field of combinatorial optimization (CO). Among the proposed models for CO problems, Neural Improvement (NI) models have been particularly successful. However, existing NI approaches are limited in their applicability to problems where crucial information is encoded in the edges, as they only consider node features and node-wise positional encodings. To overcome this limitation, we introduce a novel NI model capable of handling graph-based problems where information is encoded in the nodes, edges, or both. The presented model serves as a fundamental component for hill-climbing-based algorithms that guide the selection of neighborhood operations for each iteration. Conducted experiments demonstrate that the proposed model can recommend neighborhood operations that outperform conventional versions for the Preference Ranking Problem with a performance in the 99th percentile. We also extend the proposal to two well-known problems: the Traveling Salesman Problem and the Graph Partitioning Problem, recommending operations in the 98th and 97th percentile, respectively.