• search hit 2 of 12
Back to Result List

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 (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.

Download full text files

Export metadata

Metadaten
Author:Thomas Kleinert, Martine Labbé, Martin Schmidt, Fränk Plein
Parent Title (German):Optimization Letters
Document Type:Article
Language:German
Date of Publication (online):2020/06/05
Date of first Publication:2020/06/05
Release Date:2020/06/05
Issue:15
Page Number:14
First Page:1027
Last Page:1040
Institutes:Friedrich-Alexander-Universität Erlangen-Nürnberg
Universität Trier
Université libre de Bruxelles
Subprojects:B08
Licence (German):License LogoCreative Commons - CC BY - Namensnennung 4.0 International