Multistage Optimization with the Help of Quantified Linear Programming

Quantified linear integer programs (QIPs) are linear integer programs (IPs) with variables being either existentially or universally quantified. They can be interpreted as two-person zero-sum games between an existential and a universal player on the one side, or multistage optimization problems under uncertainty on the other side. Solutions of feasible QIPs are so called winning strategies for the existential player that specify how to react on moves—certain fixations of universally quantified variables—of the universal player to certainly win the game. In order to solve the QIP optimization problem, where the task is to find an especially attractive winning strategy, we examine the problem’s hybrid nature and combine linear programming techniques with solution techniques from game-tree search.