Combinatorial Optimization with Graph Convolutional Networks and Guided Tree Search

Abstract

We present a learning-based approach to computing solutions for certain NP-hard problems. Our approach combines deep learning techniques with useful algorithmic elements from classic heuristics. The central component is a graph convolutional network that is trained to estimate the likelihood, for each vertex in a graph, of whether this vertex is part of the optimal solution. The network is designed and trained to synthesize a diverse set of solutions, which enables rapid exploration of the solution space via tree search. The presented approach is evaluated on four canonical NP-hard problems and five datasets, which include benchmark satisfiability problems and real social network graphs with up to a hundred thousand nodes. Experimental results demonstrate that the presented approach substantially outperforms recent deep learning work, and performs on par with highly optimized state-of-the-art heuristic solvers for some NP-hard problems. Experiments indicate that our approach generalizes across datasets, and scales to graphs that are orders of magnitude larger than those used during training.

To appear in NIPS 2018

References in corpus (2)

• Neural Message Passing for Quantum Chemistry
• Learning a SAT Solver from Single-Bit Supervision

Cited by in corpus (67)

• Graph Neural Networks: A Review of Methods and Applications
• Learning to schedule job-shop problems: Representation and policy learning using graph neural network and reinforcement learning
• Learning to Dispatch for Job Shop Scheduling via Deep Reinforcement Learning
• Benchmarking Graph Neural Networks
• Combinatorial Optimization with Physics-Inspired Graph Neural Networks
• HyperGCN: A New Method of Training Graph Convolutional Networks on Hypergraphs
• An Efficient Graph Convolutional Network Technique for the Travelling Salesman Problem
• Deep Reinforcement Learning for Electric Vehicle Routing Problem with Time Windows
• Learning Combinatorial Optimization on Graphs: A Survey with Applications to Networking
• Deep Learning on Graphs: A Survey
• Graph Neural Networks Meet Neural-Symbolic Computing: A Survey and Perspective
• Deep Reinforcement Learning for Combinatorial Optimization: Covering Salesman Problems
• Advances of Machine Learning in Materials Science: Ideas and Techniques
• Learning to Optimize: A Primer and A Benchmark
• A Survey on The Expressive Power of Graph Neural Networks
• Reinforcement Learning for Integer Programming: Learning to Cut
• Factorizable Graph Convolutional Networks
• Learning Heuristics over Large Graphs via Deep Reinforcement Learning
• Graph Neural Ordinary Differential Equations
• A Survey on Influence Maximization: From an ML-Based Combinatorial Optimization
• Link Scheduling using Graph Neural Networks
• Learning Scheduling Algorithms for Data Processing Clusters
• Solving Mixed Integer Programs Using Neural Networks
• Learning the Travelling Salesperson Problem Requires Rethinking Generalization
• Coloring Big Graphs with AlphaGoZero
• Hypergraph Convolution and Hypergraph Attention
• Reinforced Genetic Algorithm Learning for Optimizing Computation Graphs
• Learning Variable Ordering Heuristics for Solving Constraint Satisfaction Problems
• Efficient Active Search for Combinatorial Optimization Problems
• Solving Optimization Problems through Fully Convolutional Networks: an Application to the Travelling Salesman Problem
• What graph neural networks cannot learn: depth vs width
• Exploratory Combinatorial Optimization with Reinforcement Learning
• CLDG: Contrastive Learning on Dynamic Graphs
• Building powerful and equivariant graph neural networks with structural message-passing
• Solving NP-Hard Problems on Graphs with Extended AlphaGo Zero
• Optimal Robustness-Consistency Trade-offs for Learning-Augmented Online Algorithms
• Approximation Ratios of Graph Neural Networks for Combinatorial Problems
• Accelerating Primal Solution Findings for Mixed Integer Programs Based on Solution Prediction
• Erdos Goes Neural: an Unsupervised Learning Framework for Combinatorial Optimization on Graphs
• Optimal Solving of Constrained Path-Planning Problems with Graph Convolutional Networks and Optimized Tree Search
• Learning to design without prior data: Discovering generalizable design strategies using deep learning and tree search
• Meta-Learning with Graph Neural Networks: Methods and Applications
• Learning to simulate and design for structural engineering
• From Local Structures to Size Generalization in Graph Neural Networks
• Graph Neural Networks for Maximum Constraint Satisfaction
• Network Calculus with Flow Prolongation -- A Feedforward FIFO Analysis enabled by ML
• Graph Learning for Combinatorial Optimization: A Survey of State-of-the-Art
• Smart Feasibility Pump: Reinforcement Learning for (Mixed) Integer Programming
• From Shallow to Deep Interactions Between Knowledge Representation, Reasoning and Machine Learning (Kay R. Amel group)
• AdarGCN: Adaptive Aggregation GCN for Few-Shot Learning
• Graph Neural Networks for Scalable Radio Resource Management: Architecture Design and Theoretical Analysis
• Reinforcement Learning Enhanced Quantum-inspired Algorithm for Combinatorial Optimization
• A Fast Graph Neural Network-Based Method for Winner Determination in Multi-Unit Combinatorial Auctions
• Maximum Entropy Weighted Independent Set Pooling for Graph Neural Networks
• Get Rid of Suspended Animation Problem: Deep Diffusive Neural Network on Graph Semi-Supervised Classification
• Reversible Action Design for Combinatorial Optimization with Reinforcement Learning
• Curriculum learning for multilevel budgeted combinatorial problems
• Learning Combinatorial Node Labeling Algorithms
• Adversarial Deep Learning for Online Resource Allocation
• Learning Markov Random Fields for Combinatorial Structures via Sampling through Lovász Local Lemma
• Maximizing Influence with Graph Neural Networks
• Multi-fidelity Stability for Graph Representation Learning
• Vulcan: Solving the Steiner Tree Problem with Graph Neural Networks and Deep Reinforcement Learning
• Gumbel-softmax Optimization: A Simple General Framework for Combinatorial Optimization Problems on Graphs
• Graph Convolutional Policy for Solving Tree Decomposition via Reinforcement Learning Heuristics
• Time-based Dynamic Controllability of Disjunctive Temporal Networks with Uncertainty: A Tree Search Approach with Graph Neural Network Guidance
• Learning to Accelerate Heuristic Searching for Large-Scale Maximum Weighted b-Matching Problems in Online Advertising