Presolve of Linear Bilevel Programs

  • Bilevel programs are complex optimization problems that can be used to model hierarchical decision processes, which occur e.g. in energy markets, critical infrastructure defense or pricing models. Even the most simple bilevel programs, where only linear objective functions and constraints appear, are non-convex optimization problems and equivalent single level formulations replace the lower level problem by its non-convex optimality constraints. This makes linear bilevel programs inherently difficult so solve. The simplification of mixed-integer linear programs before solving them, called presolve, significantly accelerated the solving of these problems. However, there is only very few literature on the topic of presolve of bilevel programs. In this thesis we review said literature on presolve of bilevel programs in the context of linear bilevel programming, derive new theoretical foundations for presolve of linear bilevel programs and then apply these results to analyze how common presolve techniques for linear and mixed integer programs can be used to presolve linear bilevel programs.

Download full text files

Export metadata

Additional Services

Share in Twitter Search Google Scholar
Metadaten
Author:Julian Manns
Document Type:Master's Thesis
Language:English
Date of Publication (online):2020/08/13
Date of first Publication:2020/08/13
Granting Institution:Friedrich-Alexander-Universität Erlangen-Nürnberg
Date of final exam:2020/03/02
Release Date:2020/08/13
Institutes:Friedrich-Alexander-Universität Erlangen-Nürnberg
Subprojects:B08
Licence (German):License LogoCreative Commons - CC BY - Namensnennung 4.0 International