Algorithms for Mixed-Integer Bilevel Problems with Convex Followers

Language
en
Document Type
Doctoral Thesis
Issue Date
2021-04-19
Issue Year
2021
Authors
Kleinert, Thomas
Editor
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.

Abstract

Einstufige Optimierungsprobleme dienen in der Regel der Entscheidungsfindung eines einzelnen Akteurs oder Systems. In vielen praktischen Optimierungsproblemen, beispielsweise aus der Ökonomie, können Entscheidungen verschiedener Akteure jedoch nicht isoliert voneinander betrachtet werden, da sich ihre Entscheidungen gegenseitig beeinflussen. Haben die Akteure gegensätzliche Ziele, so führt dies zwangsläufig zu suboptimalen Ergebnissen für einen oder mehrere Akteure. Solche Strukturen mit gegenseitigen Abhängigkeiten können mit einstufigen Optimierungsproblemen nicht adäquat abgebildet werden. Gibt es eine feste Hierarchie in der Abfolge der Entscheidungen, können diese mit mehrstufigen Optimierungsproblemen, also mit ineinander geschachtelten Optimierungsproblemen, modelliert werden. Im Fall zweier Akteure bzw. Optimierungsstufen nennt man solche Probleme auch Bilevelprobleme. Diese Probleme haben die Eigenschaft, dass ein Teil der Optimierungsvariablen der oberen Stufe eine optimale Lösung des Problems der unteren Stufe sein müssen. Aus diesem Grund sind zweistufige Optimierungsprobleme sowohl aus theoretischer als auch aus praktischer Sicht sehr schwer zu lösen. So ist sogar die zulässige Menge der “einfachsten” Bilevelprobleme mit linearen Funktionen und kontinuierlichen Variablen nicht konvex und oftmals nicht zusammenhängend. In den letzten Jahren hat das Interesse an der rechnergestützten Bileveloptimierung stark zugenommen und es wurden viele Methoden entwickelt, die sich an bekannten Konzepten der gemischt-ganzzahligen einstufigen Optimierung orientieren. Dazu zählen beispielsweise Dekompositions-, Branch-and-Bound-, oder Schnittebenenverfahren. Die vorliegende kumulative Dissertation befasst sich mit solchen Techniken für zweistufige Optimierungsprobleme, bei denen das Optimierungsproblem der unteren Stufe konvex ist. Insbesondere fassen wir im ersten Teil der Dissertation verschiedene Algorithmen, die wir in den letzten Jahren entwickelt und publiziert haben, zusammen. Außerdem demonstrieren wir in numerischen Studien den großen Fortschritt, den diese Methoden liefern. Der zweite Teil der Dissertation enthält Abdrucke der originalen Publikationen und Vorveröffentlichungen, die dem ersten Teil der Arbeit zugrunde liegen. Die Beiträge des Autors dieser Dissertation zu jedem der Artikel sind in englischer Sprache im Abschnitt “Author’s Contributions” ab Seite ix dargelegt. Im Folgenden beschreiben wir kurz den Inhalt des ersten Teils der Dissertation. Zunächst beleuchten wir zwei aus der Literatur bekannte Branch-and-Bound-Methoden für lineare Bilevelprobleme und diskutieren kritisch ihre Anwendbarkeit aus praktischer Sicht. Dann leiten wir gültige Ungleichungen für lineare Bilevelprobleme her, die sich als sehr effektiv herausstellen, wenn sie im Wurzelknoten der Branch-and-Bound-Verfahren angewendet werden. Außerdem zeigen wir anhand einer großen Sammlung von Instanzen, dass man nicht mehr auf die etablierte, aber fehlerbehaftete Big-M-Methode angewiesen ist, um lineare Bilevelprobleme zu lösen. Als nächstes stellen wir eine Bilevel-spezifische Heuristik vor, die auf einer Penalty-Alternating-Direction Methode basiert. Diese Heuristik ist auf eine breite Klasse von zweistufigen Optimierungsproblemen anwendbar, beispielsweise auch auf gemischt-ganzzahlige, quadratische Bilevelprobleme. In einer rechnergestützten Studie zeigen wir, dass die Methode in sehr kurzer Zeit zulässige Punkte bestimmt, die sehr nahe an der optimalen Lösung sind. Wir zeigen auch, dass dieses Verfahren einem klassischen Verfahren aus der Literatur deutlich überlegen ist. Schließlich wenden wir uns globalen Verfahren für gemischt-ganzzahlige quadratische Bilevelprobleme zu. Neben einem Dekompositionsverfahren stellen wir auch Outer-Approximation-Verfahren vor, die von Algorithmen aus der konvexen, gemischt-ganzzahligen und nichtlinearen Optimierung inspiriert sind. In einer numerischen Studie zeigen wir, dass diese Verfahren schneller und robuster sind als aus der Literatur bekannte Benchmark-Algorithmen.

DOI
Faculties & Collections
Zugehörige ORCIDs