Exact Combinatorial Optimization with Graph Convolutional Neural Networks
This addresses the problem of solving hard combinatorial optimization problems more efficiently for researchers and practitioners in operations research and AI.
The paper tackles combinatorial optimization by proposing a graph convolutional neural network model for learning branch-and-bound variable selection policies, demonstrating that it improves upon state-of-the-art machine-learning methods and expert-designed rules on large problems.
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.