Name
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. |
Year | Venue | Keywords |
|---|---|---|
2019 | ADVANCES IN NEURAL INFORMATION PROCESSING SYSTEMS 32 (NIPS 2019) | art machine |
Field | DocType | Volume |
Graph,Feature selection,Combinatorial optimization problem,Convolutional neural network,Computer science,Bipartite graph,Theoretical computer science,Combinatorial optimization,Artificial intelligence,Solver,Machine learning,Branching (version control) | Journal | 32 |
ISSN | Citations | PageRank |
1049-5258 | 0 | 0.34 |
References | Authors | |
0 | 5 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Maxime Gasse | 1 | 22 | 4.87 |
| Didier Chételat | 2 | 0 | 0.34 |
| Nicola Ferroni | 3 | 0 | 0.34 |
| Laurent Charlin | 4 | 637 | 29.86 |
| Andrea Lodi | 5 | 2198 | 152.51 |