Learning Combinatorial Optimization Algorithms over Graphs

2017/04/05 by Hanjun Dai, Dai, Hanjun, Elias B. Khalil +7 · 2 voices · 43 citations
Computer Science · #Advanced Graph Neural Networks #Optimization and Search Problems #Reinforcement Learning in Robotics #cs.LG #stat.ML

paper · pdf · doi:10.48550/arxiv.1704.01665

openalex publication_date 2017/04/05 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

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.

Citations

• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• Inferring Networks of Diffusion and Influence
• Q-Prop: Sample-Efficient Policy Gradient with An Off-Policy Critic

Cited by

• One4Many-StablePacker: An Efficient Deep Reinforcement Learning Framework for the 3D Bin Packing Problem
• Automated Reinforcement Learning: An Overview
• TSP with Predictions: Heatmap to Tour with Provable Guarantees
• Learning to Optimize at Scale: A Benders Decomposition-TransfORmers Framework for Stochastic Combinatorial Optimization
• Linear Decision Tree Policies for Integer Linear Programs
• Learning to Design City-scale Transit Routes
• Delay-Oriented Distributed Scheduling with TransGNN
• Networked Restless Multi-Arm Bandits with Reinforcement Learning
• DQ4FairIM: Fairness-aware Influence Maximization using Deep Reinforcement Learning
• Neural Tractability via Structure: Learning-Augmented Algorithms for Graph Combinatorial Optimization
• Graph Neural Networks vs Convolutional Neural Networks for Graph Domination Number Prediction
• DLMMPR:Deep Learning-based Measurement Matrix for Phase Retrieval
• Graph-Based Imitation and Reinforcement Learning for Efficient Benders Decomposition
• Imitation Learning in the Deep Learning Era: A Novel Taxonomy and Recent Advances
• Probing Neural Combinatorial Optimization Models
• Empowering Targeted Neighborhood Search via Hyper Tour for Large-Scale TSP
• Demonstrating Real Advantage of Machine-Learning-Enhanced Monte Carlo for Combinatorial Optimization
• Multi-Action Self-Improvement for Neural Combinatorial Optimization
• A Denoising Diffusion-Based Evolutionary Algorithm Framework: Application to the Maximum Independent Set Problem
• Graph Optimization Foundation Model: Tokenizing Graph via A Language-Model Paradigm
• Tackling GNARLy Problems: Graph Neural Algorithmic Reasoning Reimagined through Reinforcement Learning
• Automated Cyber Defense with Generalizable Graph-based Reinforcement Learning Agents
• Large Language Models in Operations Research: Methods, Applications, and Challenges
• Data from Discrete Flow-Based Generative Models for Measurement Optimization in Quantum Computing
• Recurrent State Encoders for Efficient Neural Combinatorial Optimization
• Agentic AI Empowered Multi-UAV Trajectory Optimization in Low-Altitude Economy Networks
• Distributed Scheduling using Graph Neural Networks
• REFRAG: Rethinking RAG based Decoding
• Learning to Delegate for Large-scale Vehicle Routing
• Deep Learning on Attributed Graphs: A Journey from Graphs to Their Embeddings and Back
• An Efficient Hybridization of Graph Representation Learning and Metaheuristics for the Constrained Incremental Graph Drawing Problem
• A Deep Reinforcement Learning Algorithm Using Dynamic Attention Model for Vehicle Routing Problems
• Combinatorial Optimization by Graph Pointer Networks and Hierarchical Reinforcement Learning
• Constraint Matters: Multi-Modal Representation for Reducing Mixed-Integer Linear programming
• Optimizing Large-Scale Fleet Management on a Road Network using Multi-Agent Deep Reinforcement Learning with Graph Neural Network
• Nonlocal Monte Carlo via Reinforcement Learning
• Learning to Optimize: A Primer and A Benchmark
• A State Aggregation Approach for Solving Knapsack Problem with Deep Reinforcement Learning
• Learning Network Dismantling Without Handcrafted Inputs
• Learning Enhanced Optimisation for Routing Problems
• Optimal Robustness-Consistency Trade-offs for Learning-Augmented Online Algorithms
• Multi-fidelity Stability for Graph Representation Learning
• Accelerating Quadratic Optimization with Reinforcement Learning

Discussions

• Learning Combinatorial Optimization Algorithms Over Graphs [hn, 88 points, 1 comments]
• Learning Combinatorial Algorithms Over Graphs (2017) [lobsters, 1 points, 0 comments]

Related

• Learning to Solve Combinatorial Optimization Problems on Real-World\n Graphs in Linear Time
• Graph Reinforcement Learning for Combinatorial Optimization: A Survey and Unifying Perspective
• Reversible Action Design for Combinatorial Optimization with Reinforcement Learning
• Solving Dynamic Graph Problems with Multi-Attention Deep Reinforcement Learning
• On the Difficulty of Generalizing Reinforcement Learning Framework for Combinatorial Optimization