Timezone: »

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

Tue Dec 10 10:45 AM -- 12:45 PM (PST) @ East Exhibition Hall B + C #176
in Optimization -- Combinatorial Optimization »

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.

Keywords: Combinatorial Optimization · Decision and Control · Optimization · Deep Learning; Reinforcement Learning and Planning
[ Paper]  [ Slides] 

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