Skip to Main content Skip to Navigation
Preprints, Working Papers, ...

Closing the Gap in Linear Bilevel Optimization: A New Valid Primal-Dual Inequality

Thomas Kleinert 1 Martine Labbé 2 Fränk Plein 2 Martin Schmidt 3
2 INOCS - Integrated Optimization with Complex Structure
Inria Lille - Nord Europe, ULB - Université libre de Bruxelles, CRIStAL - Centre de Recherche en Informatique, Signal et Automatique de Lille (CRIStAL) - UMR 9189
Abstract : 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.
Document type :
Preprints, Working Papers, ...
Complete list of metadatas

Cited literature [28 references]  Display  Hide  Download

https://hal.inria.fr/hal-02889276
Contributor : Fränk Plein <>
Submitted on : Wednesday, September 16, 2020 - 10:54:42 AM
Last modification on : Thursday, September 17, 2020 - 3:36:50 AM

File

PreprintVersion-2020-09-16.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-02889276, version 2

Collections

Citation

Thomas Kleinert, Martine Labbé, Fränk Plein, Martin Schmidt. Closing the Gap in Linear Bilevel Optimization: A New Valid Primal-Dual Inequality. 2020. ⟨hal-02889276v2⟩

Share

Metrics

Record views

18

Files downloads

22