Closing the gap in linear bilevel optimization: a new valid primal-dual inequality

Linear bilevel optimization problems are often tackled by replacing the linear lower-level problem with its Karush-Kuhn-Tucker conditions. The resulting single-level problem can be solved in a branch-and-bound fashion by branching on the complementarity constraints of the lower-level problem's optimality conditions. While in mixed-integer single-level optimization branch-and-cut has proven to be a powerful extension of branch-and-bound, in linear bilevel optimization not too many bilevel-tailored valid inequalities exist. In this paper, we briefly review existing cuts for linear bilevel problems and introduce a new valid inequality that exploits the strong duality condition of the lower level. We further discuss strengthened variants of the inequality that can be derived from McCormick envelopes. In a computational study, we show that the new valid inequalities can help to close the optimality gap very effectively on a large test set of linear bilevel instances.

Automated summary

The paper explores linear bilevel optimization problems, introducing a new valid inequality that exploits the strong duality condition of the lower level and discussing strengthened variants derived from McCormick envelopes. Computational experiments demonstrate that the new valid inequalities can effectively close the optimality gap on a large test set of linear bilevel instances.