Conference 2020
Top image

 
Home
Program LNMB conference
Registration LNMB conference
Invited Speakers LNMB Conference
Program PhD presentations
Abstracts PhD presentations
Announcement NGB/LNMB Seminar
Abstracts/Bios NGB/LNMB Seminar
Registration NGB/LNMB Seminar
Conference Office
How to get there
 
Return to LNMB Site
 

Andrea Lodi: 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.