Bilevel stochastic linear programming with integer variables in the lower level problem
Bilevel models in the presence of stochastic uncertainty are among the newer research objects in leader-follower optimization. An extension to a scheme of alternating decision and observation seems obvious against the background of traditional two-stage stochastic problems. Thus, bilevel stochastic problems arise from the interaction of two decision makers on different levels of hierarchy and the realization of a random vector before the follower makes a choice (data uncertainty). While the optimal objective value of the recourse problem is returned to the first stage in a two-stage stochastic optimization problem, the set of optimal lower level solutions is returned to the leader in a bilevel (stochastic) problem.
In the present work, we add lower level (equal to second stage) integrality constraints to a bilevel stochastic problem. This model extension is known to have drastic consequences for the analytical properties of the upper level objective function as a function of the leader's decision, even in the optimistic formulation of a bilevel linear problem. For example, the lower semicontinuity of this mapping cannot be maintained in general, and the existence of an optimal solution cannot be guaranteed under standard assumptions.
These consequences are the subject of this thesis, which examines the optimistic (as well as the pessimistic) formulation of a bilevel stochastic linear model whose lower level solutions may not be unique. In addition, only the right-hand side of the system of lower level constraints is affected by both the decision of the leader and the realization of a random vector. Prior to this, we study the function obtained by optimizing a linear function over the set of minimizers of an integer linear problem, and characterize the set of its discontinuity points. Assuming that the follower is the only one acting with complete information, a convex risk measure is used to estimate and evaluate the upper level (equal to first stage) outcome. Sufficient conditions for the (local) Hölder continuity of the leader's risk functional are established, and conclusions on the existence of optimal solutions are drawn. Then, the qualitative stability of the model under weak convergence of the underlying probability measure is investigated. The joint continuity of the leader's risk functional in dependence on the upper level decision and the probability measure is verified.
In the analysis, two types of ground sets of the lower level feasibility set are treated with different assumptions and using different techniques: Initially the set is finite, later the convex hull of the set is a polyhedron with integer vertices.
Zwei-Ebenen-Modelle in der Gegenwart von stochastischer Unsicherheit gehören zu den neueren Forschungsobjekten in der Optimierung von Leader-Follower-Beziehungen. Vor dem Hintergrund von traditionellen zweistufigen stochastischen Problemen erscheint eine Erweiterung zu einem Schema von abwechselnder Entscheidung und Beobachtung als naheliegend. Stochastische Zwei-Ebenen-Probleme ergeben sich damit aus dem Zusammenspiel zweier Entscheidungstragenden auf verschiedenen Hierarchieebenen sowie der Realisierung eines Zufallsvektors bevor die zweite Person auf der unteren Ebene eine Entscheidung trifft (Unsicherheit der Daten). Während im zweistufigen stochastischen Optimierungsproblem der optimale Zielfunktionswert des Rekursproblems an die erste Stufe zurückgegeben wird, ist es die Menge der optimalen Lösungen der unteren Ebene, die in einem (stochastischen) Zwei-Ebenen-Problem an die Person auf der oberen Ebene zurückgeführt wird.
In der vorliegenden Arbeit fügen wir der unteren Ebene (gleich zweiter Stufe) eines stochastischen Zwei-Ebenen-Problems Ganzzahligkeitsbedingungen hinzu. Es ist bekannt, dass diese Modellerweiterung bereits in der optimistischen Formulierung eines linearen Zwei-Ebenen-Problems drastische Konsequenzen für die analytischen Eigenschaften der Zielfunktion der oberen Ebene in Abhängigkeit von der Entscheidung der ersten Person hat. Beispielsweise kann die Unterhalbstetigkeit dieser Abbildung im Allgemeinen nicht aufrechterhalten werden und die Existenz einer optimalen Lösung kann unter Standardannahmen nicht garantiert werden.
Um diese Folgen geht es in der vorliegenden Arbeit, in der die optimistische (sowie die pessimistische) Formulierung eines stochastischen linearen Zwei-Ebenen-Modells, dessen Lösungen der unteren Ebene nicht eindeutig sein müssen, untersucht wird. Zusätzlich wird ausschließlich die rechte Seite des Systems an Nebenbedingungen der unteren Ebene sowohl von der Wahl der Person auf der oberen Ebene als auch von der Realisierung eines Zufallsvektors beeinflusst. Grundlegend dafür untersuchen wir zuvor die Funktion, die wir durch die Optimierung einer linearen Funktion über der Menge der Minimierer eines ganzzahligen linearen Problems erhalten, und charakterisieren die Menge ihrer Unstetigkeitsstellen.
Unter der Annahme, dass die Person auf der unteren Ebene die Einzige ist, die auf Basis vollständiger Information handelt, wird ein konvexes Risikomaß zur Abschätzung und Bewertung des Ergebnisses der oberen Ebene (gleich erster Stufe) verwendet. Es werden hinreichende Bedingungen für die (lokale) Hölderstetigkeit des Risikofunktionals der oberen Ebene aufgestellt und Schlussfolgerungen zur Existenz optimaler Lösungen gezogen. Anschließend wird die qualitative Stabilität des Modells unter schwacher Konvergenz des zugrunde liegenden Wahrscheinlichkeitsmaßes untersucht. Zu diesem Zweck wird die gemeinsame Stetigkeit des Risikofunktionals der oberen Ebene als Funktion in der Entscheidung der oberen Ebene und des Wahrscheinlichkeitsmaßes verifiziert.
In der Analyse werden mit unterschiedlichen Annahmen und unter Verwendung unterschiedlicher Techniken zwei verschiedene Typen der zugrunde liegenden Menge der Zulässigkeitsmenge der unteren Ebene behandelt: Im ersten Fall ist die Menge endlich, im zweiten Fall ist die konvexe Hülle der Menge ein Polyeder mit ganzzahligen Eckpunkten.