Kleinert T, Schmidt M, Labbé M, Plein F (2020)
Publication Status: Submitted
Publication Type: Journal article, Original article
Future Publication Type: Journal article
Publication year: 2020
URI: https://link.springer.com/article/10.1007/s11590-020-01660-6
DOI: 10.1007/s11590-020-01660-6
Linear bilevel optimization problems are often tackled by replacing the linear lower-level problem with its Karush–Kuhn–Tucker (KKT) 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.
APA:
Kleinert, T., Schmidt, M., Labbé, M., & Plein, F. (2020). Closing the Gap in Linear Bilevel Optimization: A New Valid Primal-Dual Inequality. Optimization Letters. https://dx.doi.org/10.1007/s11590-020-01660-6
MLA:
Kleinert, Thomas, et al. "Closing the Gap in Linear Bilevel Optimization: A New Valid Primal-Dual Inequality." Optimization Letters (2020).
BibTeX: Download