TU Darmstadt / ULB / TUprints

Quantified linear programming

Wolf, Jan (2022)
Quantified linear programming.
doi: 10.26083/tuprints-00021382
Book, Secondary publication, Postprint

[img] Text
diss_2015_Wolf.pdf
Copyright Information: CC BY-NC 4.0 International - Creative Commons, Attribution NonCommercial.

Download (2MB)
Item Type: Book
Type of entry: Secondary publication
Title: Quantified linear programming
Language: English
Date: 2022
Place of Publication: Darmstadt
Publisher: Shaker
Series: Forschungsberichte zur Fluidsystemtechnik
Series Volume: 7
Collation: 222 Seiten
DOI: 10.26083/tuprints-00021382
Corresponding Links:
Origin: Secondary publication service
Abstract:

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.

Alternative Abstract:
Alternative AbstractLanguage

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.

German
Status: Postprint
URN: urn:nbn:de:tuda-tuprints-213826
Additional Information:

Zugl.: Darmstadt, Techn. Univ., Diss. 2014

Classification DDC: 000 Generalities, computers, information > 004 Computer science
500 Science and mathematics > 500 Science
Divisions: 16 Department of Mechanical Engineering > Institute for Fluid Systems (FST) (since 01.10.2006)
Date Deposited: 20 May 2022 12:21
Last Modified: 03 Apr 2023 13:27
URI: https://tuprints.ulb.tu-darmstadt.de/id/eprint/21382
PPN: 495533661
Export:
Actions (login required)
View Item View Item