Algorithms for Mixed-Integer Bilevel Problems with Convex Followers

Kleinert T (2021)


Publication Language: English

Publication Type: Thesis

Publication year: 2021

URI: https://opus4.kobv.de/opus4-fau/frontdoor/index/index/docId/16225

Abstract

Bilevel problems are optimization problems for which a subset of variables is constrained to be an optimal solution of another optimization problem. As such, bilevel problems are capable of modeling hierarchical decision processes. This is required by many real-world problems from a broad spectrum of applications such as energy markets, traffic planning, or critical infrastructure defense, to name only a few. However, the hierarchy of decisions makes bilevel optimization problems also very challenging to solve—both in theory and practice. This cumulative PhD thesis is concerned with computational bilevel optimization. In the first part, we summarize several solution approaches that we developed over the last years and highlight the significant computational progress that these methods provide. For linear bilevel problems, we review branch-and-bound methods, critically discuss their practical use, and propose valid inequalities to extend the methods to branch-and-cut approaches. Further, we demonstrate on a large test set that it is no longer necessary to use the well-known but error-prone big-M reformulation to solve linear bilevel problems. We also present a bilevel-specific heuristic that is based on a penalty alternating direction method. This heuristic is applicable to a broad class of bilevel problems, e.g., linear or mixed-integer quadratic bilevel problems. In a computational study, we show that the method computes optimal or close-to-optimal feasible points in a very short time and that it outperforms a state-of-the-art local method from the literature. Finally, we review global approaches for mixed-integer quadratic bilevel problems. In addition to a Benders-like decomposition, we present a multi-tree and a single-tree outer-approximation approach. A computational evaluation demonstrates that both variants outperform known benchmark algorithms. The second part of this thesis consists of reprints of our original articles and preprints. These articles contain all details and are referenced throughout the first part of the thesis.

Authors with CRIS profile

How to cite

APA:

Kleinert, T. (2021). Algorithms for Mixed-Integer Bilevel Problems with Convex Followers (Dissertation).

MLA:

Kleinert, Thomas. Algorithms for Mixed-Integer Bilevel Problems with Convex Followers. Dissertation, 2021.

BibTeX: Download