Learning Combinatorial Optimization Algorithms over Graphs

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.

NIPS 2017

References in corpus (1)

• Q-Prop: Sample-Efficient Policy Gradient with An Off-Policy Critic

Cited by in corpus (243)

• Graph Neural Networks: A Review of Methods and Applications
• Graph Learning: A Survey
• Learning to schedule job-shop problems: Representation and policy learning using graph neural network and reinforcement learning
• Attention-based Graph Neural Network for Semi-supervised Learning
• Learning to Dispatch for Job Shop Scheduling via Deep Reinforcement Learning
• Benchmarking Graph Neural Networks
• Combinatorial Optimization with Physics-Inspired Graph Neural Networks
• An Efficient Graph Convolutional Network Technique for the Travelling Salesman Problem
• Deep Reinforcement Learning for Electric Vehicle Routing Problem with Time Windows
• Learning a SAT Solver from Single-Bit Supervision
• Reinforcement Learning for Solving the Vehicle Routing Problem
• Learning Combinatorial Optimization on Graphs: A Survey with Applications to Networking
• Adversarial Attack on Graph Structured Data
• Learning to Perform Local Rewriting for Combinatorial Optimization
• Combinatorial Optimization by Graph Pointer Networks and Hierarchical Reinforcement Learning
• POMO: Policy Optimization with Multiple Optima for Reinforcement Learning
• Graph Neural Networks Meet Neural-Symbolic Computing: A Survey and Perspective
• Causal Discovery with Reinforcement Learning
• Deep Reinforcement Learning for Combinatorial Optimization: Covering Salesman Problems
• ToupleGDD: A Fine-Designed Solution of Influence Maximization by Deep Reinforcement Learning
• Machine Learning on Graphs: A Model and Comprehensive Taxonomy
• Learning to Optimize: A Primer and A Benchmark
• A Survey on The Expressive Power of Graph Neural Networks
• Representation Learning for Natural Language Processing
• Deep Graph Matching via Blackbox Differentiation of Combinatorial Solvers
• Reinforcement Learning for Integer Programming: Learning to Cut
• Learning 2-opt Heuristics for the Traveling Salesman Problem via Deep Reinforcement Learning
• Learning Heuristics over Large Graphs via Deep Reinforcement Learning
• Generative AI and Process Systems Engineering: The Next Frontier
• End to end learning and optimization on graphs
• Learning the Multiple Traveling Salesmen Problem with Permutation Invariant Pooling Networks
• A Survey on Influence Maximization: From an ML-Based Combinatorial Optimization
• Link Scheduling using Graph Neural Networks
• Graph neural network initialisation of quantum approximate optimisation
• Learning Scheduling Algorithms for Data Processing Clusters
• Learning Improvement Heuristics for Solving Routing Problems
• Neural Airport Ground Handling
• Reinforcement Learning with Combinatorial Actions: An Application to Vehicle Routing
• NeuroLKH: Combining Deep Learning Model with Lin-Kernighan-Helsgaun Heuristic for Solving the Traveling Salesman Problem
• Reinforcement Learning Applications
• Learning Collaborative Policies to Solve NP-hard Routing Problems
• Solving Mixed Integer Programs Using Neural Networks
• A Multi-task Selected Learning Approach for Solving 3D Flexible Bin Packing Problem
• Learning the Travelling Salesperson Problem Requires Rethinking Generalization
• Coloring Big Graphs with AlphaGoZero
• CLARE: A Semi-supervised Community Detection Algorithm
• Learning Permutations with Sinkhorn Policy Gradient
• An actor-critic algorithm with policy gradients to solve the job shop scheduling problem using deep double recurrent agents
• Reinforced Genetic Algorithm Learning for Optimizing Computation Graphs
• The Expressive Power of Graph Neural Networks: A Survey
• Learning Variable Ordering Heuristics for Solving Constraint Satisfaction Problems
• Approximating Network Centrality Measures Using Node Embedding and Machine Learning
• Machine Learning Methods for Management UAV Flocks -- a Survey
• Learning to Handle Parameter Perturbations in Combinatorial Optimization: an Application to Facility Location
• Learning to Solve Network Flow Problems via Neural Decoding
• Efficient Active Search for Combinatorial Optimization Problems
• Learning to Iteratively Solve Routing Problems with Dual-Aspect Collaborative Transformer
• Solving the single-track train scheduling problem via Deep Reinforcement Learning
• Learning Space Partitions for Nearest Neighbor Search
• Deep learning-driven scheduling algorithm for a single machine problem minimizing the total tardiness
• An Overview of Healthcare Data Analytics With Applications to the COVID-19 Pandemic
• What graph neural networks cannot learn: depth vs width
• Neural Graph Matching Network: Learning Lawler's Quadratic Assignment Problem with Extension to Hypergraph and Multiple-graph Matching
• DISCO: Influence Maximization Meets Network Embedding and Deep Learning
• ScheduleNet: Learn to solve multi-agent scheduling problems with reinforcement learning
• Generalize a Small Pre-trained Model to Arbitrarily Large TSP Instances
• LS-Net: Learning to Solve Nonlinear Least Squares for Monocular Stereo
• ORL: Reinforcement Learning Benchmarks for Online Stochastic Optimization Problems
• Attention-based UAV Trajectory Optimization for Wireless Power Transfer-assisted IoT Systems
• Heuristics for k-domination models of facility location problems in street networks
• Building powerful and equivariant graph neural networks with structural message-passing
• On Learning Paradigms for the Travelling Salesman Problem
• Exploratory Combinatorial Optimization with Reinforcement Learning
• Solving NP-Hard Problems on Graphs with Extended AlphaGo Zero
• Hybrid Pointer Networks for Traveling Salesman Problems Optimization
• Accelerating Quadratic Optimization with Reinforcement Learning
• Ecole: A Gym-like Library for Machine Learning in Combinatorial Optimization Solvers
• Optimal Robustness-Consistency Trade-offs for Learning-Augmented Online Algorithms
• Exploring search space trees using an adapted version of Monte Carlo tree search for combinatorial optimization problems
• Machine Learning for Electronic Design Automation: A Survey
• (Learned) Frequency Estimation Algorithms under Zipfian Distribution
• Multi-Vehicle Routing Problems with Soft Time Windows: A Multi-Agent Reinforcement Learning Approach
• Deep Reinforcement Learning and Transportation Research: A Comprehensive Review
• A Bi-Level Framework for Learning to Solve Combinatorial Optimization on Graphs
• Cooperative data-driven modeling
• Approximation Ratios of Graph Neural Networks for Combinatorial Problems
• Learning to Solve Vehicle Routing Problems with Time Windows through Joint Attention
• Matrix Encoding Networks for Neural Combinatorial Optimization
• Recent Advances in Neural Program Synthesis
• Accelerating Primal Solution Findings for Mixed Integer Programs Based on Solution Prediction
• AliGraph: A Comprehensive Graph Neural Network Platform
• Learning for routing: A guided review of recent developments and future directions
• Computably Continuous Reinforcement-Learning Objectives are PAC-learnable
• Erdos Goes Neural: an Unsupervised Learning Framework for Combinatorial Optimization on Graphs
• Goal-directed graph construction using reinforcement learning
• A State Aggregation Approach for Solving Knapsack Problem with Deep Reinforcement Learning
• A General Large Neighborhood Search Framework for Solving Integer Linear Programs
• Temporal Multimodal Multivariate Learning
• Provably Good Solutions to the Knapsack Problem via Neural Networks of Bounded Size
• Graph Coarsening with Neural Networks
• A hybrid deep-learning-metaheuristic framework for bi-level network design problems
• Meta-Learning with Graph Neural Networks: Methods and Applications
• DeepSoCS: A Neural Scheduler for Heterogeneous System-on-Chip (SoC) Resource Scheduling
• Text Level Graph Neural Network for Text Classification
• A Deep Reinforcement Learning Algorithm Using Dynamic Attention Model for Vehicle Routing Problems
• CombOptNet: Fit the Right NP-Hard Problem by Learning Integer Programming Constraints
• Factor Graph Neural Network
• Learning Large Neighborhood Search Policy for Integer Programming
• How to Evaluate Machine Learning Approaches for Combinatorial Optimization: Application to the Travelling Salesman Problem
• Dismantling Complex Networks by a Neural Model Trained from Tiny Networks
• Scalable variational Monte Carlo with graph neural ansatz
• Evaluating Curriculum Learning Strategies in Neural Combinatorial Optimization
• Efficient Neural Network Verification via Order Leading Exploration of Branch-and-Bound Trees
• Deep Optimisation: Solving Combinatorial Optimisation Problems using Deep Neural Networks
• Melding the Data-Decisions Pipeline: Decision-Focused Learning for Combinatorial Optimization
• Dynamic resource matching in manufacturing using deep reinforcement learning
• Dynamic Partial Removal: A Neural Network Heuristic for Large Neighborhood Search
• Neural Stochastic Dual Dynamic Programming
• From Local Structures to Size Generalization in Graph Neural Networks
• Graph Neural Network Guided Local Search for the Traveling Salesperson Problem
• Toward an Automated Auction Framework for Wireless Federated Learning Services Market
• Graph Neural Networks with Parallel Neighborhood Aggregations for Graph Classification
• It's Not What Machines Can Learn, It's What We Cannot Teach
• Learning-based Support Estimation in Sublinear Time
• Sequential Evaluation and Generation Framework for Combinatorial Recommender System
• Learning Heuristics for Quantified Boolean Formulas through Deep Reinforcement Learning
• Graph Neural Networks for Maximum Constraint Satisfaction
• Influence maximization in unknown social networks: Learning Policies for Effective Graph Sampling
• Solving Continual Combinatorial Selection via Deep Reinforcement Learning
• PDP: A General Neural Framework for Learning Constraint Satisfaction Solvers
• Graph2Seq: Scalable Learning Dynamics for Graphs
• A Global Solution Method for Decentralized Multi-Area SCUC and Savings Allocation Based on MILP Value Functions
• Nearly Horizon-Free Offline Reinforcement Learning
• A Two-stage Framework and Reinforcement Learning-based Optimization Algorithms for Complex Scheduling Problems
• Topology Aware Deep Learning for Wireless Network Optimization
• Learning Coordination Policies over Heterogeneous Graphs for Human-Robot Teams via Recurrent Neural Schedule Propagation
• Graph Learning for Combinatorial Optimization: A Survey of State-of-the-Art
• Modeling Attention Flow on Graphs
• LORM: Learning to Optimize for Resource Management in Wireless Networks with Few Training Samples
• Constraint-Guided Reinforcement Learning: Augmenting the Agent-Environment-Interaction
• Distributed Scheduling using Graph Neural Networks
• Set-to-Sequence Methods in Machine Learning: a Review
• Generalization in Deep RL for TSP Problems via Equivariance and Local Search
• Learning to Optimise General TSP Instances
• Sample Complexity Bounds for Recurrent Neural Networks with Application to Combinatorial Graph Problems
• Smart Feasibility Pump: Reinforcement Learning for (Mixed) Integer Programming
• First-Order Problem Solving through Neural MCTS based Reinforcement Learning
• Learning Mixed-Integer Convex Optimization Strategies for Robot Planning and Control
• Benders Cut Classification via Support Vector Machines for Solving Two-stage Stochastic Programs
• TauRieL: Targeting Traveling Salesman Problem with a deep reinforcement learning inspired architecture
• Transfer Learning for Mixed-Integer Resource Allocation Problems in Wireless Networks
• A Comprehensive Survey on the Ambulance Routing and Location Problems
• Generalizable Resource Allocation in Stream Processing via Deep Reinforcement Learning
• Deep Reinforcement Learning for Crowdsourced Urban Delivery: System States Characterization, Heuristics-guided Action Choice, and Rule-Interposing Integration
• Levels of Analysis for Machine Learning
• Reinforcement Learning Enhanced Quantum-inspired Algorithm for Combinatorial Optimization
• Safeguarded Learned Convex Optimization
• Automated Optical Multi-layer Design via Deep Reinforcement Learning
• Expert-Calibrated Learning for Online Optimization with Switching Costs
• Co-training for Policy Learning
• Learning Vehicle Routing Problems using Policy Optimisation
• The Atlas for the Aspiring Network Scientist
• Optimizing Large-Scale Fleet Management on a Road Network using Multi-Agent Deep Reinforcement Learning with Graph Neural Network
• Finding spin glass ground states through deep reinforcement learning
• GLAD: Learning Sparse Graph Recovery
• Learning Robust Algorithms for Online Allocation Problems Using Adversarial Training
• Graph Ordering: Towards the Optimal by Learning
• Neural Network Branch-and-Bound for Neural Network Verification
• Optimal $k$-Coverage Charging Problem
• My Body is a Cage: the Role of Morphology in Graph-Based Incompatible Control
• Deep Policies for Online Bipartite Matching: A Reinforcement Learning Approach
• Learning-Augmented $k$-means Clustering
• FastCover: An Unsupervised Learning Framework for Multi-Hop Influence Maximization in Social Networks
• Learning Combined Set Covering and Traveling Salesman Problem
• Active Screening for Recurrent Diseases: A Reinforcement Learning Approach
• Planted Dense Subgraphs in Dense Random Graphs Can Be Recovered using Graph-based Machine Learning
• Learning to Delegate for Large-scale Vehicle Routing
• A Game-Theoretic Approach for Improving Generalization Ability of TSP Solvers
• HR-RCNN: Hierarchical Relational Reasoning for Object Detection
• A deep learning guided memetic framework for graph coloring problems
• Skeleton-based Hand-Gesture Recognition with Lightweight Graph Convolutional Networks
• Snowflake: Scaling GNNs to High-Dimensional Continuous Control via Parameter Freezing
• Reversible Action Design for Combinatorial Optimization with Reinforcement Learning
• Revocable Deep Reinforcement Learning with Affinity Regularization for Outlier-Robust Graph Matching
• Locality Preserving Dense Graph Convolutional Networks with Graph Context-Aware Node Representations
• Curriculum learning for multilevel budgeted combinatorial problems
• Optimizing Memory Placement using Evolutionary Graph Reinforcement Learning
• Learning Objective Boundaries for Constraint Optimization Problems
• A unified framework for manifold landmarking
• Learning to Dynamically Coordinate Multi-Robot Teams in Graph Attention Networks
• Learning-Accelerated ADMM for Distributed Optimal Power Flow
• Data-driven Policy on Feasibility Determination for the Train Shunting Problem
• MODRL/D-AM: Multiobjective Deep Reinforcement Learning Algorithm Using Decomposition and Attention Model for Multiobjective Optimization
• Informative Path Planning for Mobile Sensing with Reinforcement Learning
• Structured agents for physical construction
• State-Aware Variational Thompson Sampling for Deep Q-Networks
• Learning Combinatorial Node Labeling Algorithms
• USCO-Solver: Solving Undetermined Stochastic Combinatorial Optimization Problems
• CoCo: Online Mixed-Integer Control via Supervised Learning
• Frequency Estimation in Data Streams: Learning the Optimal Hashing Scheme
• Maximizing Influence with Graph Neural Networks
• Deep Learning on Attributed Graphs: A Journey from Graphs to Their Embeddings and Back
• ReLU Neural Networks of Polynomial Size for Exact Maximum Flow Computation
• Bayes EMbedding (BEM): Refining Representation by Integrating Knowledge Graphs and Behavior-specific Networks
• Learning Enhanced Optimisation for Routing Problems
• Fine-grained Search Space Classification for Hard Enumeration Variants of Subset Problems
• Learning Robust Representations with Graph Denoising Policy Network
• Adversarial Deep Learning for Online Resource Allocation
• MONSTOR: An Inductive Approach for Estimating and Maximizing Influence over Unseen Networks
• Can Graph Neural Networks Learn to Solve MaxSAT Problem?
• Structured Convolutional Kernel Networks for Airline Crew Scheduling
• QROSS: QUBO Relaxation Parameter Optimisation via Learning Solver Surrogates
• Computing Steiner Trees using Graph Neural Networks
• Graph Partitioning and Sparse Matrix Ordering using Reinforcement Learning and Graph Neural Networks
• Learning Algorithms for Regenerative Stopping Problems with Applications to Shipping Consolidation in Logistics
• Multi-fidelity Stability for Graph Representation Learning
• MODRL/D-EL: Multiobjective Deep Reinforcement Learning with Evolutionary Learning for Multiobjective Optimization
• Towards Utilitarian Combinatorial Assignment with Deep Neural Networks and Heuristic Algorithms
• OpenGraphGym-MG: Using Reinforcement Learning to Solve Large Graph Optimization Problems on MultiGPU Systems
• Solving Graph-based Public Good Games with Tree Search and Imitation Learning
• Learning to Solve Combinatorial Optimization under Positive Linear Constraints via Non-Autoregressive Neural Networks
• Fractional order graph neural network
• OrderNet: Ordering by Example
• Gumbel-softmax Optimization: A Simple General Framework for Combinatorial Optimization Problems on Graphs
• Graph Convolutional Policy for Solving Tree Decomposition via Reinforcement Learning Heuristics
• Weighted Graph Nodes Clustering via Gumbel Softmax
• Learning to Search for MIMO Detection
• Zero Training Overhead Portfolios for Learning to Solve Combinatorial Problems
• SeaPearl: A Constraint Programming Solver guided by Reinforcement Learning
• Learning Based Distributed Tracking
• Learning to Initialize Gradient Descent Using Gradient Descent
• A General Framework for Charger Scheduling Optimization Problems
• Learning on Random Balls is Sufficient for Estimating (Some) Graph Parameters
• Predictive Machine Learning of Objective Boundaries for Solving COPs
• Similarity Modeling on Heterogeneous Networks via Automatic Path Discovery
• Combining Propositional Logic Based Decision Diagrams with Decision Making in Urban Systems
• Can NetGAN be improved on short random walks?
• Automated Allocation of Detention Rooms Based on Inverse Graph Partitioning
• Learning Chebyshev Basis in Graph Convolutional Networks for Skeleton-based Action Recognition
• cube2net: Efficient Query-Specific Network Construction with Data Cube Organization
• Particle Flow Bayes' Rule
• Convolutions for Spatial Interaction Modeling
• Experiments with graph convolutional networks for solving the vertex $p$-center problem