# Learning to Solve Combinatorial Optimization Problems on Real-World Graphs in Linear Time

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

## Key facts

- Cited by 39 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 6 Jun 2020.

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

- [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)
- [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)
- [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)
- [RL4CO: an Extensive Reinforcement Learning for Combinatorial Optimization Benchmark](https://mlsanity.com/paper/2306.17100/) (2023)
- [Pareto Set Learning for Neural Multi-objective Combinatorial Optimization](https://mlsanity.com/paper/2203.15386/) (2022)
- [Let the Flows Tell: Solving Graph Combinatorial Optimization Problems with GFlowNets](https://mlsanity.com/paper/2305.17010/) (2023)
- [On Representing Linear Programs by Graph Neural Networks](https://mlsanity.com/paper/2209.12288/) (2022)
- [Challenges and Opportunities in Deep Reinforcement Learning with Graph Neural Networks: A Comprehensive review of Algorithms and Applications](https://mlsanity.com/paper/2206.07922/) (2022)
- [Neural Combinatorial Optimization Algorithms for Solving Vehicle Routing Problems: A Comprehensive Survey with Perspectives](https://mlsanity.com/paper/2406.00415/) (2024)
- [An Overview and Experimental Study of Learning-based Optimization Algorithms for Vehicle Routing Problem](https://mlsanity.com/paper/2107.07076/) (2021)
- [Pareto Set Learning for Multi-Objective Reinforcement Learning](https://mlsanity.com/paper/2501.06773/) (2025)
- [Reducing Collision Checking for Sampling-Based Motion Planning Using Graph Neural Networks](https://mlsanity.com/paper/2210.08864/) (2022)
- [Learning to Solve Vehicle Routing Problems: A Survey](https://mlsanity.com/paper/2205.02453/) (2022)
- [Learning to Solve Combinatorial Graph Partitioning Problems via Efficient Exploration](https://mlsanity.com/paper/2205.14105/) (2022)
- [Solve routing problems with a residual edge-graph attention neural network](https://mlsanity.com/paper/2105.02730/) (2021)
- [Learning Combinatorial Node Labeling Algorithms](https://mlsanity.com/paper/2106.03594/) (2021)
- [Graph Partitioning and Sparse Matrix Ordering using Reinforcement Learning and Graph Neural Networks](https://mlsanity.com/paper/2104.03546/) (2021)
- [Solving Dynamic Graph Problems with Multi-Attention Deep Reinforcement Learning](https://mlsanity.com/paper/2201.04895/) (2022)
- [Differentiable Constraint-Based Causal Discovery](https://mlsanity.com/paper/2510.22031/) (2025)
- [Optimal Solving of Constrained Path-Planning Problems with Graph Convolutional Networks and Optimized Tree Search](https://mlsanity.com/paper/2108.01036/) (2021)
- [Understanding Curriculum Learning in Policy Optimization for Online Combinatorial Optimization](https://mlsanity.com/paper/2202.05423/) (2022)
- [Solving the capacitated vehicle routing problem with timing windows using rollouts and MAX-SAT](https://mlsanity.com/paper/2206.06618/) (2022)
- [Q-Cogni: An Integrated Causal Reinforcement Learning Framework](https://mlsanity.com/paper/2302.13240/) (2023)
- [Structure-Aware Robustness Certificates for Graph Classification](https://mlsanity.com/paper/2306.11915/) (2023)
- [Evaluating the progress of Deep Reinforcement Learning in the real world: aligning domain-agnostic and domain-specific research](https://mlsanity.com/paper/2107.03015/) (2021)
- [Solving Disjunctive Temporal Networks with Uncertainty under Restricted Time-Based Controllability using Tree Search and Graph Neural Networks](https://mlsanity.com/paper/2203.15030/) (2022)
- [NeuroPrim: An Attention-based Model for Solving NP-hard Spanning Tree Problems](https://mlsanity.com/paper/2210.12453/) (2022)

## Abstract (arXiv)

Combinatorial optimization algorithms for graph problems are usually designed afresh for each new problem with careful attention by an expert to the problem structure. In this work, we develop a new framework to solve any combinatorial optimization problem over graphs that can be formulated as a single player game defined by states, actions, and rewards, including minimum spanning tree, shortest paths, traveling salesman problem, and vehicle routing problem, without expert knowledge. Our method trains a graph neural network using reinforcement learning on an unlabeled training set of graphs. The trained network then outputs approximate solutions to new graph instances in linear running time. In contrast, previous approximation algorithms or heuristics tailored to NP-hard problems on graphs generally have at least quadratic running time. We demonstrate the applicability of our approach on both polynomial and NP-hard problems with optimality gaps close to 1, and show that our method is able to generalize well: (i) from training on small graphs to testing on large graphs; (ii) from training on random graphs of one type to testing on random graphs of another type; and (iii) from training on random graphs to running on real world graphs.