# Learning Combinatorial Optimization Algorithms over Graphs

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

## Key facts

- Cited by 561 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 5 Apr 2017.

## Built on by (most cited first, 30 of 561)

- [What Can Transformers Learn In-Context? A Case Study of Simple Function Classes](https://mlsanity.com/paper/2208.01066/) (2022)
- [Combinatorial optimization and reasoning with graph neural networks](https://mlsanity.com/paper/2102.09544/) (2021)
- [DIFUSCO: Graph-based Diffusion Solvers for Combinatorial Optimization](https://mlsanity.com/paper/2302.08224/) (2023)
- [Learning to Optimize: A Primer and A Benchmark](https://mlsanity.com/paper/2103.12828/) (2021)
- [End-to-End Constrained Optimization Learning: A Survey](https://mlsanity.com/paper/2103.16378/) (2021)
- [Graph Learning: A Survey](https://mlsanity.com/paper/2105.00696/) (2021)
- [DIMES: A Differentiable Meta Solver for Combinatorial Optimization Problems](https://mlsanity.com/paper/2210.04123/) (2022)
- [Sym-NCO: Leveraging Symmetricity for Neural Combinatorial Optimization](https://mlsanity.com/paper/2205.13209/) (2022)
- [Learning to Delegate for Large-scale Vehicle Routing](https://mlsanity.com/paper/2107.04139/) (2021)
- [Combinatorial Optimization with Physics-Inspired Graph Neural Networks](https://mlsanity.com/paper/2107.01188/) (2021)
- [Learning to Iteratively Solve Routing Problems with Dual-Aspect Collaborative Transformer](https://mlsanity.com/paper/2110.02544/) (2021)
- [The CLRS Algorithmic Reasoning Benchmark](https://mlsanity.com/paper/2205.15659/) (2022)
- [NeuroLKH: Combining Deep Learning Model with Lin-Kernighan-Helsgaun Heuristic for Solving the Traveling Salesman Problem](https://mlsanity.com/paper/2110.07983/) (2021)
- [Efficient Active Search for Combinatorial Optimization Problems](https://mlsanity.com/paper/2106.05126/) (2021)
- [Matrix Encoding Networks for Neural Combinatorial Optimization](https://mlsanity.com/paper/2106.11113/) (2021)
- [Learning Collaborative Policies to Solve NP-hard Routing Problems](https://mlsanity.com/paper/2110.13987/) (2021)
- [Simulation-guided Beam Search for Neural Combinatorial Optimization](https://mlsanity.com/paper/2207.06190/) (2022)
- [Tutorial on amortized optimization](https://mlsanity.com/paper/2202.00665/) (2022)
- [BQ-NCO: Bisimulation Quotienting for Efficient Neural Combinatorial Optimization](https://mlsanity.com/paper/2301.03313/) (2023)
- [Learning to Search Feasible and Infeasible Regions of Routing Problems with Flexible Neural k-Opt](https://mlsanity.com/paper/2310.18264/) (2023)
- [DeepACO: Neural-enhanced Ant Systems for Combinatorial Optimization](https://mlsanity.com/paper/2309.14032/) (2023)
- [Machine Learning for Electronic Design Automation: A Survey](https://mlsanity.com/paper/2102.03357/) (2021)
- [RL4CO: an Extensive Reinforcement Learning for Combinatorial Optimization Benchmark](https://mlsanity.com/paper/2306.17100/) (2023)
- [Graph Neural Network Guided Local Search for the Traveling Salesperson Problem](https://mlsanity.com/paper/2110.05291/) (2021)
- [Towards Omni-generalizable Neural Methods for Vehicle Routing Problems](https://mlsanity.com/paper/2305.19587/) (2023)
- [Learning Generalizable Models for Vehicle Routing Problems via Knowledge Distillation](https://mlsanity.com/paper/2210.07686/) (2022)
- [Towards Generalizable Neural Solvers for Vehicle Routing Problems via Ensemble with Transferrable Local Policy](https://mlsanity.com/paper/2308.14104/) (2023)
- [Theory of Graph Neural Networks: Representation and Learning](https://mlsanity.com/paper/2204.07697/) (2022)
- [Self-Supervised Primal-Dual Learning for Constrained Optimization](https://mlsanity.com/paper/2208.09046/) (2022)
- [The Transformer Network for the Traveling Salesman Problem](https://mlsanity.com/paper/2103.03012/) (2021)

## Abstract (arXiv)

The design of good heuristics or approximation algorithms for NP-hard combinatorial optimization problems often requires significant specialized knowledge and trial-and-error. Can we automate this challenging, tedious process, and learn the algorithms instead? In many real-world applications, it is typically the case that the same optimization problem is solved again and again on a regular basis, maintaining the same problem structure but differing in the data. This provides an opportunity for learning heuristic algorithms that exploit the structure of such recurring problems. In this paper, we propose a unique combination of reinforcement learning and graph embedding to address this challenge. The learned greedy policy behaves like a meta-algorithm that incrementally constructs a solution, and the action is determined by the output of a graph embedding network capturing the current state of the solution. We show that our framework can be applied to a diverse range of optimization problems over graphs, and learns effective algorithms for the Minimum Vertex Cover, Maximum Cut and Traveling Salesman problems.