Exact Combinatorial Optimization with Graph Convolutional Neural Networks

By Maxime Gasse, Didier Chételat, D. Chételat, Nicola Ferroni, Laurent Charlin, Andrea Lodi. 2019

647 citations recorded by the source corpus.

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 this https URL.

Subfields: Artificial Intelligence, Graph Learning, Optimization & Training

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Graph Learning

In Optimization & Training

Citations in the corpus

Structured Convolutional Kernel Networks for Airline Crew Scheduling (2021, background): “…to solve the optimization problem end-to-end (Khalil et al., 2017), or (3) to guide an optimization process (variable selection in branch-and-bound Gasse et al. (2019)), and ConvGNNs might appear to be a good candidate-solution for CPPs when coupled with a CRF layer to impose constraints on the…”
Solving Mixed Integer Programs Using Neural Networks (2020, methodology): “Most of the combined set of MIPs from all datasets have 103–106 variables and constraints after presolve (see figure 4 in section 4), which is significantly larger than earlier works (Gasse et al. 2019, Ding et al. 2020).”
A learning-based algorithm to quickly compute good primal solutions for Stochastic Integer Programs (2019, background): “It is well known that features describing the connection between variables, constraints and other interaction help ML to perform well rather than just providing plain data matrices [3, 5, 8, 12].”
Combinatorial optimization and reasoning with graph neural networks (2021, methodology): “Also, Sun et al. [2020] uses a GNN learned with evolution strategies to improve on the GNN of Gasse et al. [2019] on problems deﬁned on graphs sharing a common backbone.”
Machine Learning for Combinatorial Optimization: a Methodological Tour d'Horizon (2018, methodology): “This can generalize to MILPs, where the constraint matrix can be represented as the adjacency matrix of a bipartite graph on variables and constraints, as done in Gasse et al. (2019).”
Differentiation of Blackbox Combinatorial Solvers (2019, background): “Also, more general solvers received some attention; this includes SAT-solvers [42, 43], integer programming solvers [14] and SMT-solvers (satisfiability modulo theories)[4].”