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