Predicting Accurate Lagrangian Multipliers for Mixed Integer Linear
  Programs
Francesco Demelas Joseph Le Roux Mathieu Lacroix Axel Parmentier
Lagrangian relaxation stands among the most efficient approaches for solving
a Mixed Integer Linear Programs (MILP) with difficult constraints. Given any
duals for these constraints, called Lagrangian Multipliers (LMs), it returns a
bound on the optimal value of the MILP, and Lagrangian methods seek the LMs
giving the best such bound. But these methods generally rely on iterative
algorithms resembling gradient descent to maximize the concave piecewise linear
dual function: the computational burden grows quickly with the number of
relaxed constraints. We introduce a deep learning approach that bypasses the
descent, effectively amortizing the local, per instance, optimization. A
probabilistic encoder based on a graph convolutional network computes
high-dimensional representations of relaxed constraints in MILP instances. A
decoder then turns these representations into LMs. We train the encoder and
decoder jointly by directly optimizing the bound obtained from the predicted
multipliers. Numerical experiments show that our approach closes up to 85~\% of
the gap between the continuous relaxation and the best Lagrangian bound, and
provides a high quality warm-start for descent based Lagrangian methods.