Optimization Online


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

Thomas Kleinert (thomas.kleinert***at***fau.de)
Martine Labbé (martine.labbe***at***ulb.ac.be)
Fränk Plein (frank.plein***at***ulb.ac.be)
Martin Schmidt (martin.schmidt***at***uni-trier.de)

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.

Keywords: Bilevel optimization, Valid inequalities, Branch-and-cut, Computational analysis.

Category 1: Integer Programming ((Mixed) Integer Linear Programming )

Category 2: Complementarity and Variational Inequalities

Category 3: Integer Programming (Cutting Plane Approaches )


Download: [PDF]

Entry Submitted: 06/05/2020
Entry Accepted: 06/05/2020
Entry Last Modified: 09/16/2020

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society