Exact Combinatorial Optimization with Graph Convolutional Neural Networks

Abstract

Combinatorial optimization problems are typically tackled by the branch-and-bound paradigm. We propose a new graph convolutional neural network model for learning branch-and-bound variable selection policies, which leverages the natural variable-constraint bipartite graph representation of mixed-integer linear programs. We train our model via imitation learning from the strong branching expert rule, and demonstrate on a series of hard problems that our approach produces policies that improve upon state-of-the-art machine-learning methods for branching and generalize to instances significantly larger than seen during training. Moreover, we improve for the first time over expert-designed branching rules implemented in a state-of-the-art solver on large problems. Code for reproducing all the experiments can be found at https://github.com/ds4dm/learn2branch.

Accepted paper at the NeurIPS 2019 conference

References in corpus (3)

• Neural Message Passing for Quantum Chemistry
• Cuts, Primal Heuristics, and Learning to Branch for the Time-Dependent Traveling Salesman Problem
• Learning Heuristics for Quantified Boolean Formulas through Deep Reinforcement Learning

Cited by in corpus (45)

• Graph Neural Networks: A Review of Methods and Applications
• Operational Research: Methods and Applications
• A Survey on The Expressive Power of Graph Neural Networks
• Deep Graph Matching via Blackbox Differentiation of Combinatorial Solvers
• Learning Heuristics over Large Graphs via Deep Reinforcement Learning
• Graph Neural Ordinary Differential Equations
• Hybrid Models for Learning to Branch
• Neural Airport Ground Handling
• Solving Mixed Integer Programs Using Neural Networks
• Learning the Travelling Salesperson Problem Requires Rethinking Generalization
• Learning Variable Ordering Heuristics for Solving Constraint Satisfaction Problems
• Learning to Solve Network Flow Problems via Neural Decoding
• A Study of Learning Search Approximation in Mixed Integer Branch and Bound: Node Selection in SCIP
• Branch and Bound in Mixed Integer Linear Programming Problems: A Survey of Techniques and Trends
• Machine Learning for Cutting Planes in Integer Programming: A Survey
• Symmetric Tensor Networks for Generative Modeling and Constrained Combinatorial Optimization
• Erdos Goes Neural: an Unsupervised Learning Framework for Combinatorial Optimization on Graphs
• Accelerating Primal Solution Findings for Mixed Integer Programs Based on Solution Prediction
• A General Large Neighborhood Search Framework for Solving Integer Linear Programs
• A hybrid deep-learning-metaheuristic framework for bi-level network design problems
• Meta-Learning with Graph Neural Networks: Methods and Applications
• How to Evaluate Machine Learning Approaches for Combinatorial Optimization: Application to the Travelling Salesman Problem
• Towards VM Rescheduling Optimization Through Deep Reinforcement Learning
• Efficient Neural Network Verification via Order Leading Exploration of Branch-and-Bound Trees
• A Reinforcement-Learning-Based Multiple-Column Selection Strategy for Column Generation
• Learning a Large Neighborhood Search Algorithm for Mixed Integer Programs
• Towards Lower Bounds on the Depth of ReLU Neural Networks
• Learning Branching Heuristics for Propositional Model Counting
• Maximum Entropy Weighted Independent Set Pooling for Graph Neural Networks
• A Fast Graph Neural Network-Based Method for Winner Determination in Multi-Unit Combinatorial Auctions
• DClEVerNet: Deep Combinatorial Learning for Efficient EV Charging Scheduling in Large-scale Networked Facilities
• Learning to Pivot as a Smart Expert
• Optimizing Large-Scale Fleet Management on a Road Network using Multi-Agent Deep Reinforcement Learning with Graph Neural Network
• Continuous-Depth Neural Models for Dynamic Graph Prediction
• The deep learning and statistical physics applications to the problems of combinatorial optimization
• Lifelong Learning for Neural powered Mixed Integer Programming
• Curriculum learning for multilevel budgeted combinatorial problems
• An Efficient Hybridization of Graph Representation Learning and Metaheuristics for the Constrained Incremental Graph Drawing Problem
• Structured Convolutional Kernel Networks for Airline Crew Scheduling
• Fully Linear Graph Convolutional Networks for Semi-Supervised Learning and Clustering
• Time-based Dynamic Controllability of Disjunctive Temporal Networks with Uncertainty: A Tree Search Approach with Graph Neural Network Guidance
• Simplex Initialization: A Survey of Techniques and Trends
• Multi-fidelity Stability for Graph Representation Learning
• SeaPearl: A Constraint Programming Solver guided by Reinforcement Learning
• Learning to Solve Combinatorial Optimization under Positive Linear Constraints via Non-Autoregressive Neural Networks