Exact Combinatorial Optimization with Graph Convolutional Neural Networks

Code

• github.com/ds4dm/learn2branch
  OfficialIn papertf★ 404
• github.com/ds4dm/branch-search-trees
  pytorch★ 68
• github.com/isotlaboratory/ml4vrp
  pytorch★ 16
• github.com/sclbd/accelerated-lpbox-admm
  pytorch★ 6
• github.com/whuang-io/Distributional_MIPLIB_eval
  tf★ 1
• github.com/audreyanneguindon/NeurIPS_2019
  tf★ 0

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. Code for reproducing all the experiments can be found at https://github.com/ds4dm/learn2branch.

Tasks

Reproductions