Thursday, 13:15 - 13:40 h, Room: MA 004


Jan Wolf
Accelerating nested Benders decomposition with game-tree search techniques to solve quantified linear programs

Coauthor: Ulf Lorenz


Quantified linear programs (QLPs) are linear programs with variables being either existentially or universally quantified. The problem is similar to two-person zero-sum games with perfect information, like, e.g., chess, where an existential and a universal player have to play against each other. At the same time, a QLP is a variant of a linear program with a polyhedral solution space. On the one hand it has strong similarities to multi-stage stochastic linear programs with variable right-hand side. On the other hand it is a special case of a multi-stage robust optimization problem where the variables that are affected by uncertainties are assumed to be fixed. In this paper we show how the problem's ambiguity of being a two-person zero-sum game, and simultaneously being a convex multistage decision problem, can be used to combine linear programming techniques with solution techniques from game theory. Therefore, we propose an extension of the Nested Benders Decomposition algorithm with two techniques that are successfully used in game-tree search - the αβ-heuristic and move-ordering.


Talk 1 of the invited session Thu.2.MA 004
"Multistage robustness" [...]
Cluster 20
"Robust optimization" [...]


  personal loans. This pill gives a hand to thousands who suffer from erectile dysfunction. People who take Viagra Super Active can forget about their impotence and have a normal intimate life.