Data to 7 Oct 2026

Learning Combinatorial Optimization Algorithms over Graphs

arXiv 1704.01665 ↗First posted 5 Apr 2017cs.LG stat.MLcited by 557

Not on the map. Why?

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.

Key facts. Cited by 557 papers in the map (data through 7 Oct 2026). First posted on arXiv 5 Apr 2017.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 129; 2022: 105; 2023: 102; 2024: 90; 2025: 72; 2026: 59.

557 papers.

Sort:

By area:

2022What Can Transformers Learn In-Context? A Case Study of Simple Function Classescited by 700
2021Combinatorial optimization and reasoning with graph neural networkscited by 267
2023DIFUSCO: Graph-based Diffusion Solvers for Combinatorial Optimizationcited by 216
2021Learning to Optimize: A Primer and A Benchmarkcited by 206
2021End-to-End Constrained Optimization Learning: A Surveycited by 154
2021Graph Learning: A Surveycited by 140
2022DIMES: A Differentiable Meta Solver for Combinatorial Optimization Problemscited by 127
2022Sym-NCO: Leveraging Symmetricity for Neural Combinatorial Optimizationcited by 118
2021Learning to Delegate for Large-scale Vehicle Routingcited by 108
2021Learning to Iteratively Solve Routing Problems with Dual-Aspect Collaborative Transformercited by 108
2021Combinatorial Optimization with Physics-Inspired Graph Neural Networkscited by 107
2022The CLRS Algorithmic Reasoning Benchmarkcited by 103

38 more

2021NeuroLKH: Combining Deep Learning Model with Lin-Kernighan-Helsgaun Heuristic for Solving the Traveling Salesman Problemcited by 102
2021Efficient Active Search for Combinatorial Optimization Problemscited by 99
2021Matrix Encoding Networks for Neural Combinatorial Optimizationcited by 89
2021Learning Collaborative Policies to Solve NP-hard Routing Problemscited by 86
2022Simulation-guided Beam Search for Neural Combinatorial Optimizationcited by 84
2022Tutorial on amortized optimizationcited by 83
2023Learning to Search Feasible and Infeasible Regions of Routing Problems with Flexible Neural k-Optcited by 81
2023BQ-NCO: Bisimulation Quotienting for Efficient Neural Combinatorial Optimizationcited by 80
2023DeepACO: Neural-enhanced Ant Systems for Combinatorial Optimizationcited by 77
2021Machine Learning for Electronic Design Automation: A Surveycited by 71
2021Graph Neural Network Guided Local Search for the Traveling Salesperson Problemcited by 70
2023RL4CO: an Extensive Reinforcement Learning for Combinatorial Optimization Benchmarkcited by 70
2023Towards Omni-generalizable Neural Methods for Vehicle Routing Problemscited by 68
2022Learning Generalizable Models for Vehicle Routing Problems via Knowledge Distillationcited by 61
2023Towards Generalizable Neural Solvers for Vehicle Routing Problems via Ensemble with Transferrable Local Policycited by 61
2022Theory of Graph Neural Networks: Representation and Learningcited by 60
2022Self-Supervised Primal-Dual Learning for Constrained Optimizationcited by 60
2021The Transformer Network for the Traveling Salesman Problemcited by 59
2022A Generalist Neural Algorithmic Learnercited by 58
2024A Diffusion Model Framework for Unsupervised Neural Combinatorial Optimizationcited by 58
2022GraphFramEx: Towards Systematic Evaluation of Explainability Methods for Graph Neural Networkscited by 57
2022Winner Takes It All: Training Performant RL Populations for Combinatorial Optimizationcited by 57
2022Pareto Set Learning for Neural Multi-objective Combinatorial Optimizationcited by 56
2021Graph Coarsening with Neural Networkscited by 55
2021Ordering-Based Causal Discovery with Reinforcement Learningcited by 55
2022Boosting the Cycle Counting Power of Graph Neural Networks with I2-GNNscited by 55
2024Ant Colony Sampling with GFlowNets for Combinatorial Optimizationcited by 53
2021Learning to schedule job-shop problems: Representation and policy learning using graph neural network and reinforcement learningcited by 52
2021CombOptNet: Fit the Right NP-Hard Problem by Learning Integer Programming Constraintscited by 49
2023Pointerformer: Deep Reinforced Multi-Pointer Transformer for the Traveling Salesman Problemcited by 49
2022MIP-GNN: A Data-Driven Framework for Guiding Combinatorial Solverscited by 48
2024GraphArena: Evaluating and Exploring Large Language Models on Graph Computationcited by 48
2023H-TSP: Hierarchically Solving the Large-Scale Travelling Salesman Problemcited by 43
2024INViT: A Generalizable Routing Problem Solver with Invariant Nested View Transformercited by 43
2025Fast T2T: Optimization Consistency Speeds Up Diffusion-Based Training-to-Testing Solving for Combinatorial Optimizationcited by 43
2024Can Graph Learning Improve Planning in LLM-based Agents?cited by 42
2021Learning a Large Neighborhood Search Algorithm for Mixed Integer Programscited by 41
2022Equivariant quantum circuits for learning on weighted graphscited by 41

50 most cited of 557 All 557 (JSON)