Neur2BiLO: Neural Bilevel Optimization
Justin Dumouchelle Esther Julien Jannis Kurtz Elias B. Khalil
Bilevel optimization deals with nested problems in which a leader takes the
first decision to minimize their objective function while accounting for a
follower's best-response reaction. Constrained bilevel problems with integer
variables are particularly notorious for their hardness. While exact solvers
have been proposed for mixed-integer linear bilevel optimization, they tend to
scale poorly with problem size and are hard to generalize to the non-linear
case. On the other hand, problem-specific algorithms (exact and heuristic) are
limited in scope. Under a data-driven setting in which similar instances of a
bilevel problem are solved routinely, our proposed framework, Neur2BiLO, embeds
a neural network approximation of the leader's or follower's value function,
trained via supervised regression, into an easy-to-solve mixed-integer program.
Neur2BiLO serves as a heuristic that produces high-quality solutions extremely
fast for the bilevel knapsack interdiction problem, the "critical node game"
from network security, a donor-recipient healthcare problem, and discrete
network design from transportation planning. These problems are diverse in that
they have linear or non-linear objectives/constraints and integer or
mixed-integer variables, making Neur2BiLO unique in its versatility.