Exact Combinatorial Optimization with Graph Convolutional Neural Networks
Maxime Gasse · Didier Chetelat · Nicola Ferroni · Laurent Charlin · Andrea Lodi

Tue Dec 10th 10:45 AM -- 12:45 PM @ East Exhibition Hall B + C #176

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

Author Information

Maxime Gasse (Polytechnique Montréal)
Didier Chetelat (Polytechnique Montreal)
Nicola Ferroni (University of Bologna)
Laurent Charlin (MILA / U.Montreal)
Andrea Lodi (École Polytechnique Montréal)

More from the Same Authors