Wolf, Jan (2022)
Quantified linear programming.
doi: 10.26083/tuprints-00021382
Buch, Zweitveröffentlichung, Postprint

Kurzbeschreibung (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.

Typ des Eintrags:	Buch
Erschienen:	2022
Autor(en):	Wolf, Jan
Art des Eintrags:	Zweitveröffentlichung
Titel:	Quantified linear programming
Sprache:	Englisch
Publikationsjahr:	2022
Ort:	Darmstadt
Publikationsdatum der Erstveröffentlichung:	2015
Verlag:	Shaker
Reihe:	Forschungsberichte zur Fluidsystemtechnik
Band einer Reihe:	7
Kollation:	222 Seiten
DOI:	10.26083/tuprints-00021382
URL / URN:	https://tuprints.ulb.tu-darmstadt.de/21382
Zugehörige Links:	Verlags-DOI
Herkunft:	Zweitveröffentlichungsservice
Kurzbeschreibung (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.
Alternatives oder übersetztes Abstract:	Alternatives Abstract Sprache 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. Deutsch
Status:	Postprint
URN:	urn:nbn:de:tuda-tuprints-213826
Zusätzliche Informationen:	Zugl.: Darmstadt, Techn. Univ., Diss. 2014
Sachgruppe der Dewey Dezimalklassifikatin (DDC):	000 Allgemeines, Informatik, Informationswissenschaft > 004 Informatik 500 Naturwissenschaften und Mathematik > 500 Naturwissenschaften
Fachbereich(e)/-gebiet(e):	16 Fachbereich Maschinenbau 16 Fachbereich Maschinenbau > Institut für Fluidsystemtechnik (FST) (seit 01.10.2006)
Hinterlegungsdatum:	20 Mai 2022 12:21
Letzte Änderung:	23 Mai 2022 05:20
PPN:
Export:	Simple MetadataDublin CoreIBW_RDAEP3 XMLAtomJSONHTML CitationRDF+XMLT2T_XMLASCII CitationMODSBibTeXEndNoteMultiline CSV
Suche nach Titel in:	TUfind oder in Google

Verfügbare Versionen dieses Eintrags

• Quantified linear programming. (deposited 20 Mai 2022 12:21) [Gegenwärtig angezeigt]
  • Quantified linear programming. (deposited 31 Jul 2015 13:30)

Frage zum Eintrag

Optionen (nur für Redakteure)

Redaktionelle Details anzeigen