Learning Combinatorial Optimization Algorithms over Graphs
arXiv:1704.01665
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.
arXiv commentNIPS 2017
References in corpus (5)
Cited by in corpus (245)
- 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
- 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
- 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
- Enhanced MRI brain tumor detection using deep learning in conjunction with explainable AI SHAP based diverse and multi feature analysis
- Learning to Solve Network Flow Problems via Neural Decoding
- Efficient Active Search for Combinatorial Optimization Problems
- Learning Space Partitions for Nearest Neighbor Search
- Solving the single-track train scheduling problem via Deep Reinforcement Learning
- Deep learning-driven scheduling algorithm for a single machine problem minimizing the total tardiness
- Learning to Iteratively Solve Routing Problems with Dual-Aspect Collaborative Transformer
- What graph neural networks cannot learn: depth vs width
- An Overview of Healthcare Data Analytics With Applications to the COVID-19 Pandemic
- DISCO: Influence Maximization Meets Network Embedding and Deep Learning
- Neural Graph Matching Network: Learning Lawler's Quadratic Assignment Problem with Extension to Hypergraph and Multiple-graph Matching
- Attention-based UAV Trajectory Optimization for Wireless Power Transfer-assisted IoT Systems
- 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
- Heuristics for k-domination models of facility location problems in street networks
- 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
- Accelerating Quadratic Optimization with Reinforcement Learning
- Solving NP-Hard Problems on Graphs with Extended AlphaGo Zero
- Hybrid Pointer Networks for Traveling Salesman Problems Optimization
- Optimal Robustness-Consistency Trade-offs for Learning-Augmented Online Algorithms
- Ecole: A Gym-like Library for Machine Learning in Combinatorial Optimization Solvers
- 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
- Deep Reinforcement Learning and Transportation Research: A Comprehensive Review
- Multi-Vehicle Routing Problems with Soft Time Windows: A Multi-Agent Reinforcement Learning Approach
- Cooperative data-driven modeling
- Learning to Solve Vehicle Routing Problems with Time Windows through Joint Attention
- A Bi-Level Framework for Learning to Solve Combinatorial Optimization on Graphs
- Matrix Encoding Networks for Neural Combinatorial Optimization
- Approximation Ratios of Graph Neural Networks for Combinatorial Problems
- Recent Advances in Neural Program Synthesis
- Learning for routing: A guided review of recent developments and future directions
- Goal-directed graph construction using reinforcement learning
- AliGraph: A Comprehensive Graph Neural Network Platform
- Erdos Goes Neural: an Unsupervised Learning Framework for Combinatorial Optimization on Graphs
- Accelerating Primal Solution Findings for Mixed Integer Programs Based on Solution Prediction
- Computably Continuous Reinforcement-Learning Objectives are PAC-learnable
- A General Large Neighborhood Search Framework for Solving Integer Linear Programs
- A State Aggregation Approach for Solving Knapsack Problem with Deep Reinforcement Learning
- Temporal Multimodal Multivariate Learning
- Provably Good Solutions to the Knapsack Problem via Neural Networks of Bounded Size
- A hybrid deep-learning-metaheuristic framework for bi-level network design problems
- DeepSoCS: A Neural Scheduler for Heterogeneous System-on-Chip (SoC) Resource Scheduling
- Graph Coarsening with Neural Networks
- Meta-Learning with Graph Neural Networks: Methods and Applications
- CombOptNet: Fit the Right NP-Hard Problem by Learning Integer Programming Constraints
- 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
- How to Evaluate Machine Learning Approaches for Combinatorial Optimization: Application to the Travelling Salesman Problem
- Evaluating Curriculum Learning Strategies in Neural Combinatorial Optimization
- Scalable variational Monte Carlo with graph neural ansatz
- Learning Large Neighborhood Search Policy for Integer Programming
- Dismantling Complex Networks by a Neural Model Trained from Tiny Networks
- Melding the Data-Decisions Pipeline: Decision-Focused Learning for Combinatorial Optimization
- Dynamic Partial Removal: A Neural Network Heuristic for Large Neighborhood Search
- Deep Optimisation: Solving Combinatorial Optimisation Problems using Deep Neural Networks
- Efficient Neural Network Verification via Order Leading Exploration of Branch-and-Bound Trees
- Dynamic resource matching in manufacturing using deep reinforcement learning
- Toward an Automated Auction Framework for Wireless Federated Learning Services Market
- 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
- Graph Neural Networks for Maximum Constraint Satisfaction
- Influence maximization in unknown social networks: Learning Policies for Effective Graph Sampling
- Graph Neural Networks with Parallel Neighborhood Aggregations for Graph Classification
- It's Not What Machines Can Learn, It's What We Cannot Teach
- Sequential Evaluation and Generation Framework for Combinatorial Recommender System
- Solving Continual Combinatorial Selection via Deep Reinforcement Learning
- Learning Heuristics for Quantified Boolean Formulas through Deep Reinforcement Learning
- Learning-based Support Estimation in Sublinear Time
- Graph2Seq: Scalable Learning Dynamics for Graphs
- PDP: A General Neural Framework for Learning Constraint Satisfaction Solvers
- A Global Solution Method for Decentralized Multi-Area SCUC and Savings Allocation Based on MILP Value Functions
- Distributed Scheduling using Graph Neural Networks
- Generalization in Deep RL for TSP Problems via Equivariance and Local Search
- Constraint-Guided Reinforcement Learning: Augmenting the Agent-Environment-Interaction
- Topology Aware Deep Learning for Wireless Network Optimization
- A Two-stage Framework and Reinforcement Learning-based Optimization Algorithms for Complex Scheduling Problems
- LORM: Learning to Optimize for Resource Management in Wireless Networks with Few Training Samples
- Modeling Attention Flow on Graphs
- Nearly Horizon-Free Offline Reinforcement Learning
- Learning Coordination Policies over Heterogeneous Graphs for Human-Robot Teams via Recurrent Neural Schedule Propagation
- Set-to-Sequence Methods in Machine Learning: a Review
- Graph Learning for Combinatorial Optimization: A Survey of State-of-the-Art
- Learning Mixed-Integer Convex Optimization Strategies for Robot Planning and Control
- First-Order Problem Solving through Neural MCTS based Reinforcement Learning
- 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
- Safeguarded Learned Convex Optimization
- A Comprehensive Survey on the Ambulance Routing and Location Problems
- TauRieL: Targeting Traveling Salesman Problem with a deep reinforcement learning inspired architecture
- Generalizable Resource Allocation in Stream Processing via Deep Reinforcement Learning
- Expert-Calibrated Learning for Online Optimization with Switching Costs
- Benders Cut Classification via Support Vector Machines for Solving Two-stage Stochastic Programs
- Automated Optical Multi-layer Design via Deep Reinforcement Learning
- Transfer Learning for Mixed-Integer Resource Allocation Problems in Wireless Networks
- Levels of Analysis for Machine Learning
- Reinforcement Learning Enhanced Quantum-inspired Algorithm for Combinatorial Optimization
- Deep Reinforcement Learning for Crowdsourced Urban Delivery: System States Characterization, Heuristics-guided Action Choice, and Rule-Interposing Integration
- GLAD: Learning Sparse Graph Recovery
- The Atlas for the Aspiring Network Scientist
- Learning Vehicle Routing Problems using Policy Optimisation
- Optimal -Coverage Charging Problem
- Finding spin glass ground states through deep reinforcement learning
- FastCover: An Unsupervised Learning Framework for Multi-Hop Influence Maximization in Social Networks
- Learning-Augmented -means Clustering
- Graph Ordering: Towards the Optimal by Learning
- Learning Combined Set Covering and Traveling Salesman Problem
- Learning Robust Algorithms for Online Allocation Problems Using Adversarial Training
- Neural Network Branch-and-Bound for Neural Network Verification
- Co-training for Policy Learning
- Deep Policies for Online Bipartite Matching: A Reinforcement Learning Approach
- My Body is a Cage: the Role of Morphology in Graph-Based Incompatible Control
- Optimizing Large-Scale Fleet Management on a Road Network using Multi-Agent Deep Reinforcement Learning with Graph Neural Network
- Informative Path Planning for Mobile Sensing with Reinforcement Learning
- A unified framework for manifold landmarking
- Data-driven Policy on Feasibility Determination for the Train Shunting Problem
- 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
- Active Screening for Recurrent Diseases: A Reinforcement Learning Approach
- 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
- Learning to Dynamically Coordinate Multi-Robot Teams in Graph Attention Networks
- Learning-Accelerated ADMM for Distributed Optimal Power Flow
- MODRL/D-AM: Multiobjective Deep Reinforcement Learning Algorithm Using Decomposition and Attention Model for Multiobjective Optimization
- Learning to Delegate for Large-scale Vehicle Routing
- Structured agents for physical construction
- Maximizing Influence with Graph Neural Networks
- Can Graph Neural Networks Learn to Solve MaxSAT Problem?
- Adversarial Deep Learning for Online Resource Allocation
- Deep Learning on Attributed Graphs: A Journey from Graphs to Their Embeddings and Back
- Learning Robust Representations with Graph Denoising Policy Network
- QROSS: QUBO Relaxation Parameter Optimisation via Learning Solver Surrogates
- Frequency Estimation in Data Streams: Learning the Optimal Hashing Scheme
- Structured Convolutional Kernel Networks for Airline Crew Scheduling
- Fine-grained Search Space Classification for Hard Enumeration Variants of Subset Problems
- Learning Enhanced Optimisation for Routing Problems
- Computing Steiner Trees using Graph Neural Networks
- ReLU Neural Networks of Polynomial Size for Exact Maximum Flow Computation
- Graph Partitioning and Sparse Matrix Ordering using Reinforcement Learning and Graph Neural Networks
- Bayes EMbedding (BEM): Refining Representation by Integrating Knowledge Graphs and Behavior-specific Networks
- State-Aware Variational Thompson Sampling for Deep Q-Networks
- CoCo: Online Mixed-Integer Control via Supervised Learning
- Learning Combinatorial Node Labeling Algorithms
- USCO-Solver: Solving Undetermined Stochastic Combinatorial Optimization Problems
- MONSTOR: An Inductive Approach for Estimating and Maximizing Influence over Unseen Networks
- Learning on Random Balls is Sufficient for Estimating (Some) Graph Parameters
- Predictive Machine Learning of Objective Boundaries for Solving COPs
- 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
- Experiments with graph convolutional networks for solving the vertex -center problem
- Solving Graph-based Public Good Games with Tree Search and Imitation Learning
- OpenGraphGym-MG: Using Reinforcement Learning to Solve Large Graph Optimization Problems on MultiGPU Systems
- OrderNet: Ordering by Example
- Graph Convolutional Policy for Solving Tree Decomposition via Reinforcement Learning Heuristics
- 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
- Fractional order graph neural network
- Similarity Modeling on Heterogeneous Networks via Automatic Path Discovery
- Learning Based Distributed Tracking
- Weighted Graph Nodes Clustering via Gumbel Softmax
- Zero Training Overhead Portfolios for Learning to Solve Combinatorial Problems
- Combining Propositional Logic Based Decision Diagrams with Decision Making in Urban Systems
- SeaPearl: A Constraint Programming Solver guided by Reinforcement Learning
- Automated Allocation of Detention Rooms Based on Inverse Graph Partitioning
- 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
- Towards Utilitarian Combinatorial Assignment with Deep Neural Networks and Heuristic Algorithms
- Learning to Initialize Gradient Descent Using Gradient Descent
- Multi-fidelity Stability for Graph Representation Learning