Solving multistage quantified linear optimization problems with the alpha–beta nested Benders decomposition

Abstract

Quantified linear programs (QLPs) are linear programs with variables being either existentially or universally quantified. QLPs are convex multistage decision problems on the one side, and two-person zero-sum games between an existential and a universal player on the other side. Solutions of feasible QLPs are so-called winning strategies for the existential player that specify how to react on moves—fixations of universally quantified variables—of the universal player to certainly win the game. To find a certain best one among different winning strategies, we propose the extension of the QLP decision problem by an objective function. To solve the resulting QLP optimization problem, we exploit the problem’s hybrid nature and combine linear programming techniques with solution techniques from game-tree search. As a result, we present an extension of the nested Benders decomposition algorithm by the αβ-heuristic and move-ordering, two techniques that are successfully used in game-tree search to solve minimax trees. We furthermore exploit solution information from QLP relaxations obtained by quantifier shifting. The applicability is examined in an experimental evaluation.

Keywords

• 90C46
• 90C47