Quantified linear programming

In many real world problems, dealing with uncertainty is a significant challenge for mathematical programming and related areas, and typically, standard (mixed-integer) linear programming formulations are not well suited to model such problems. However, a powerful way to express uncertainty or adversarial situations is through the use of quantified variables. To pursue this approach, this thesis is concerned with quantified (integer) linear programming, a generalization of traditional (integer) linear programming. Whereas in traditional linear programs (LPs) and integer programs (IPs) all variables are implicitly existentially quantified, they can be either existentially or universally quantified in quantified (continuous) linear programs (QLPs) and quantified integer programs (QIPs). Explicit quantification of variables yields a considerable increase in expressive power, suitable to compactly represent many problems from the field of optimization under uncertainty, a topic that has engaged much attention in the mathematical programming com- munity and beyond in the last decade. In the context of optimization under uncertainty robust optimization and stochastic programming are currently the most prominent modeling paradigms. However, the abilities of linear programming extensions by variable quantification are relatively unexplored. The present thesis is subdivided into two parts and its aim is to study quantified linear programming as an independent mathematical programming paradigm. However, we mainly focus on the continuous case. In the first part we give a detailed introduction into the concept of quantified (integer) linear programming and highlight the strong similarities to two-person zero-sum games and related work in the context of optimization under uncertainty. We furthermore present some illustrating examples to demonstrate the modeling power and broad applicability of this methodology. After a survey of the basic results of current research in this field both theoretical and applied, we also provide a detailed study of the algorithmic properties of QLPs by a comprehensive geometric analysis. As a result we present a complete and thorough complexity analysis by using a polyhedral approach and further analytical insights. The second part of this thesis deals with the development and the implementation of an efficient algorithm to solve QLPs. We first review existing solution approaches and then develop an algorithm that exploits the problem’s hybrid nature of being a convex multistage decision problem on the one hand, and being a two-person zero-sum game on the other hand. Based on the results of the theoretical analysis we propose an algorithm that combines linear programming techniques with solution techniques from game-tree search. This thesis is supplemented by the software QlpOpt, which is a quantified linear and integer programming solver and framework that features different solution techniques and a variety of methods to work with QLPs and QIPs.

Bei klassischen Optimierungsproblemen wird häufig davon ausgegangen, dass die Eingabedaten für ein gegebenes Problem zum Planungszeitpunkt bekannt sind. In der Praxis stösst man jedoch häufig auf Situationen, bei denen ein Teil dieser Daten mit Unsicherheiten behaftet ist und klassische Modelle nicht mehr geeignet sind, diese Probleme adäquat abzubilden. Eine Möglichkeit um Unsicherheitsaspekte in herkömmlichen Modellen zu integrieren, ist mittels der expliziten Quantifizierung von Entscheidungsvariablen. Diesem Ansatz folgend beschäftigt sich die vorliegende Arbeit mit einer Erweiterung der klassischen (ganzzahligen) linearen Programmierung, bei der Entscheidungsvariablen nicht mehr wie im herkömmlichen Fall implizit existenzquantifiziert sind, sondern alternativ auch allquantifiziert sein können. Die vorliegende Arbeit ist in zwei Teile unterteilt und verfolgt das Ziel, die quantifizierte (ganzzahlige) lineare Programmierung als eigenständiges Modellierungsparadigma zu untersuchen. Das Hauptaugenmerk liegt dabei auf dem kontinuierlichen Fall. Im ersten Teil wird dazu eine detaillierte Einführung in die grundlegenden Konzepte gegeben. Es wird der Zusammenhang zu Zwei-Personen-Spielen hergestellt und anhand von Beispielen gezeigt, wie unterschiedliche reale Probleme modelliert werden können. Im Anschluss folgt eine ausführliche Untersuchung der theoretischen Eigenschaften von QLPs, welcher eine umfangreiche geometrische Betrachtung zu Grunde liegt. Als Ergebnis wird im zweiten Teil ein Lösungsalgorithmus präsentiert, der klassische LP-Lösungstechniken und Techniken aus der Spielbaumsuche kombiniert. Die im Rahmen dieser Arbeit vorgestellten Algorithmen wurden in dem QLP und QIP Framework QlpOpt implementiert und in einer detaillierten experimentellen Studie untersucht.