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 (5)

• Statistical mechanics of complex networks
• Playing Atari with Deep Reinforcement Learning
• Discriminative Embeddings of Latent Variable Models for Structured Data
• Inferring Networks of Diffusion and Influence
• Q-Prop: Sample-Efficient Policy Gradient with An Off-Policy Critic

Cited by in corpus (244)

• Graph Neural Networks: A Review of Methods and Applications
• Deep Reinforcement Learning: An Overview
• 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
• A Survey on Influence Maximization: From an ML-Based Combinatorial Optimization
• Learning the Multiple Traveling Salesmen Problem with Permutation Invariant Pooling Networks
• 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
• Reinforcement Learning Applications
• NeuroLKH: Combining Deep Learning Model with Lin-Kernighan-Helsgaun Heuristic for Solving the Traveling Salesman Problem
• Learning Collaborative Policies to Solve NP-hard Routing Problems
• A Multi-task Selected Learning Approach for Solving 3D Flexible Bin Packing Problem
• Solving Mixed Integer Programs Using Neural Networks
• 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
• Learning Variable Ordering Heuristics for Solving Constraint Satisfaction Problems
• The Expressive Power of Graph Neural Networks: A Survey
• Approximating Network Centrality Measures Using Node Embedding and Machine Learning
• Learning to Handle Parameter Perturbations in Combinatorial Optimization: an Application to Facility Location
• Machine Learning Methods for Management UAV Flocks -- a Survey
• Learning to Solve Network Flow Problems via Neural Decoding
• Efficient Active Search for Combinatorial Optimization Problems
• Solving the single-track train scheduling problem via Deep Reinforcement Learning
• Learning Space Partitions for Nearest Neighbor Search
• Learning to Iteratively Solve Routing Problems with Dual-Aspect Collaborative Transformer
• Deep learning-driven scheduling algorithm for a single machine problem minimizing the total tardiness
• 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
• An Overview of Healthcare Data Analytics With Applications to the COVID-19 Pandemic
• DISCO: Influence Maximization Meets Network Embedding and Deep Learning
• Heuristics for k-domination models of facility location problems in street networks
• ORL: Reinforcement Learning Benchmarks for Online Stochastic Optimization Problems
• Generalize a Small Pre-trained Model to Arbitrarily Large TSP Instances
• ScheduleNet: Learn to solve multi-agent scheduling problems with reinforcement learning
• Attention-based UAV Trajectory Optimization for Wireless Power Transfer-assisted IoT Systems
• LS-Net: Learning to Solve Nonlinear Least Squares for Monocular Stereo
• On Learning Paradigms for the Travelling Salesman Problem
• Building powerful and equivariant graph neural networks with structural message-passing
• Exploratory Combinatorial Optimization with Reinforcement Learning
• Solving NP-Hard Problems on Graphs with Extended AlphaGo Zero
• Accelerating Quadratic Optimization with Reinforcement Learning
• Hybrid Pointer Networks for Traveling Salesman Problems Optimization
• 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
• Approximation Ratios of Graph Neural Networks for Combinatorial Problems
• Cooperative data-driven modeling
• Recent Advances in Neural Program Synthesis
• Learning to Solve Vehicle Routing Problems with Time Windows through Joint Attention
• Matrix Encoding Networks for Neural Combinatorial Optimization
• Learning for routing: A guided review of recent developments and future directions
• Accelerating Primal Solution Findings for Mixed Integer Programs Based on Solution Prediction
• Goal-directed graph construction using reinforcement learning
• Erdos Goes Neural: an Unsupervised Learning Framework for Combinatorial Optimization on Graphs
• AliGraph: A Comprehensive Graph Neural Network Platform
• Computably Continuous Reinforcement-Learning Objectives are PAC-learnable
• 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
• 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
• Provably Good Solutions to the Knapsack Problem via Neural Networks of Bounded Size
• Graph Coarsening with Neural Networks
• A Deep Reinforcement Learning Algorithm Using Dynamic Attention Model for Vehicle Routing Problems
• Text Level Graph Neural Network for Text Classification
• Factor Graph Neural Network
• CombOptNet: Fit the Right NP-Hard Problem by Learning Integer Programming Constraints
• Scalable variational Monte Carlo with graph neural ansatz
• Evaluating Curriculum Learning Strategies in Neural Combinatorial Optimization
• How to Evaluate Machine Learning Approaches for Combinatorial Optimization: Application to the Travelling Salesman Problem
• Learning Large Neighborhood Search Policy for Integer Programming
• Dismantling Complex Networks by a Neural Model Trained from Tiny Networks
• Dynamic resource matching in manufacturing using deep reinforcement learning
• Dynamic Partial Removal: A Neural Network Heuristic for Large Neighborhood Search
• Melding the Data-Decisions Pipeline: Decision-Focused Learning for Combinatorial Optimization
• Deep Optimisation: Solving Combinatorial Optimisation Problems using Deep Neural Networks
• Efficient Neural Network Verification via Order Leading Exploration of Branch-and-Bound Trees
• Neural Stochastic Dual Dynamic Programming
• Graph Neural Network Guided Local Search for the Traveling Salesperson Problem
• From Local Structures to Size Generalization in Graph Neural Networks
• Toward an Automated Auction Framework for Wireless Federated Learning Services Market
• Graph Neural Networks for Maximum Constraint Satisfaction
• It's Not What Machines Can Learn, It's What We Cannot Teach
• Solving Continual Combinatorial Selection via Deep Reinforcement Learning
• Learning Heuristics for Quantified Boolean Formulas through Deep Reinforcement Learning
• Graph Neural Networks with Parallel Neighborhood Aggregations for Graph Classification
• Sequential Evaluation and Generation Framework for Combinatorial Recommender System
• Learning-based Support Estimation in Sublinear Time
• Influence maximization in unknown social networks: Learning Policies for Effective Graph Sampling
• Graph2Seq: Scalable Learning Dynamics for Graphs
• A Global Solution Method for Decentralized Multi-Area SCUC and Savings Allocation Based on MILP Value Functions
• PDP: A General Neural Framework for Learning Constraint Satisfaction Solvers
• LORM: Learning to Optimize for Resource Management in Wireless Networks with Few Training Samples
• Graph Learning for Combinatorial Optimization: A Survey of State-of-the-Art
• Topology Aware Deep Learning for Wireless Network Optimization
• Modeling Attention Flow on Graphs
• Generalization in Deep RL for TSP Problems via Equivariance and Local Search
• Set-to-Sequence Methods in Machine Learning: a Review
• A Two-stage Framework and Reinforcement Learning-based Optimization Algorithms for Complex Scheduling Problems
• Constraint-Guided Reinforcement Learning: Augmenting the Agent-Environment-Interaction
• Distributed Scheduling using Graph Neural Networks
• Nearly Horizon-Free Offline Reinforcement Learning
• Learning Coordination Policies over Heterogeneous Graphs for Human-Robot Teams via Recurrent Neural Schedule Propagation
• Sample Complexity Bounds for Recurrent Neural Networks with Application to Combinatorial Graph Problems
• Learning to Optimise General TSP Instances
• Smart Feasibility Pump: Reinforcement Learning for (Mixed) Integer Programming
• Learning Mixed-Integer Convex Optimization Strategies for Robot Planning and Control
• First-Order Problem Solving through Neural MCTS based Reinforcement Learning
• A Comprehensive Survey on the Ambulance Routing and Location Problems
• Levels of Analysis for Machine Learning
• Safeguarded Learned Convex Optimization
• Transfer Learning for Mixed-Integer Resource Allocation Problems in Wireless Networks
• Expert-Calibrated Learning for Online Optimization with Switching Costs
• TauRieL: Targeting Traveling Salesman Problem with a deep reinforcement learning inspired architecture
• Reinforcement Learning Enhanced Quantum-inspired Algorithm for Combinatorial Optimization
• Benders Cut Classification via Support Vector Machines for Solving Two-stage Stochastic Programs
• Automated Optical Multi-layer Design via Deep Reinforcement Learning
• Deep Reinforcement Learning for Crowdsourced Urban Delivery: System States Characterization, Heuristics-guided Action Choice, and Rule-Interposing Integration
• Generalizable Resource Allocation in Stream Processing via Deep Reinforcement Learning
• Graph Ordering: Towards the Optimal by Learning
• GLAD: Learning Sparse Graph Recovery
• Deep Policies for Online Bipartite Matching: A Reinforcement Learning Approach
• The Atlas for the Aspiring Network Scientist
• Learning Vehicle Routing Problems using Policy Optimisation
• Optimizing Large-Scale Fleet Management on a Road Network using Multi-Agent Deep Reinforcement Learning with Graph Neural Network
• Learning-Augmented $k$-means Clustering
• Learning Robust Algorithms for Online Allocation Problems Using Adversarial Training
• Co-training for Policy Learning
• FastCover: An Unsupervised Learning Framework for Multi-Hop Influence Maximization in Social Networks
• Optimal $k$-Coverage Charging Problem
• My Body is a Cage: the Role of Morphology in Graph-Based Incompatible Control
• Finding spin glass ground states through deep reinforcement learning
• Neural Network Branch-and-Bound for Neural Network Verification
• Learning Combined Set Covering and Traveling Salesman Problem
• Informative Path Planning for Mobile Sensing with Reinforcement Learning
• Learning to Delegate for Large-scale Vehicle Routing
• Planted Dense Subgraphs in Dense Random Graphs Can Be Recovered using Graph-based Machine Learning
• 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
• Active Screening for Recurrent Diseases: A Reinforcement Learning Approach
• 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
• 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
• Structured agents for physical construction
• A unified framework for manifold landmarking
• Maximizing Influence with Graph Neural Networks
• ReLU Neural Networks of Polynomial Size for Exact Maximum Flow Computation
• Bayes EMbedding (BEM): Refining Representation by Integrating Knowledge Graphs and Behavior-specific Networks
• Can Graph Neural Networks Learn to Solve MaxSAT Problem?
• Deep Learning on Attributed Graphs: A Journey from Graphs to Their Embeddings and Back
• Adversarial Deep Learning for Online Resource Allocation
• Frequency Estimation in Data Streams: Learning the Optimal Hashing Scheme
• Learning Enhanced Optimisation for Routing Problems
• Fine-grained Search Space Classification for Hard Enumeration Variants of Subset Problems
• Computing Steiner Trees using Graph Neural Networks
• CoCo: Online Mixed-Integer Control via Supervised Learning
• Structured Convolutional Kernel Networks for Airline Crew Scheduling
• Graph Partitioning and Sparse Matrix Ordering using Reinforcement Learning and Graph Neural Networks
• Learning Robust Representations with Graph Denoising Policy Network
• QROSS: QUBO Relaxation Parameter Optimisation via Learning Solver Surrogates
• MONSTOR: An Inductive Approach for Estimating and Maximizing Influence over Unseen Networks
• Learning Combinatorial Node Labeling Algorithms
• State-Aware Variational Thompson Sampling for Deep Q-Networks
• USCO-Solver: Solving Undetermined Stochastic Combinatorial Optimization Problems
• Learning on Random Balls is Sufficient for Estimating (Some) Graph Parameters
• Predictive Machine Learning of Objective Boundaries for Solving COPs
• Multi-fidelity Stability for Graph Representation Learning
• 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
• MODRL/D-EL: Multiobjective Deep Reinforcement Learning with Evolutionary Learning for Multiobjective Optimization
• Learning Based Distributed Tracking
• OrderNet: Ordering by Example
• Graph Convolutional Policy for Solving Tree Decomposition via Reinforcement Learning Heuristics
• Fractional order graph neural network
• Gumbel-softmax Optimization: A Simple General Framework for Combinatorial Optimization Problems on Graphs
• A General Framework for Charger Scheduling Optimization Problems
• Learning to Search for MIMO Detection
• Weighted Graph Nodes Clustering via Gumbel Softmax
• Similarity Modeling on Heterogeneous Networks via Automatic Path Discovery
• Zero Training Overhead Portfolios for Learning to Solve Combinatorial Problems
• SeaPearl: A Constraint Programming Solver guided by Reinforcement Learning
• Combining Propositional Logic Based Decision Diagrams with Decision Making in Urban Systems
• Learning to Initialize Gradient Descent Using Gradient Descent
• Automated Allocation of Detention Rooms Based on Inverse Graph Partitioning
• Towards Utilitarian Combinatorial Assignment with Deep Neural Networks and Heuristic Algorithms
• Learning Chebyshev Basis in Graph Convolutional Networks for Skeleton-based Action Recognition
• Can NetGAN be improved on short random walks?
• cube2net: Efficient Query-Specific Network Construction with Data Cube Organization
• Convolutions for Spatial Interaction Modeling
• Particle Flow Bayes' Rule
• Learning Algorithms for Regenerative Stopping Problems with Applications to Shipping Consolidation in Logistics
• Experiments with graph convolutional networks for solving the vertex $p$-center problem
• OpenGraphGym-MG: Using Reinforcement Learning to Solve Large Graph Optimization Problems on MultiGPU Systems