Ederer T, Lorenz U, Martin A, Wolf J (2011)
Publication Type: Conference contribution
Publication year: 2011
Series: Lecture Notes in Computer Science
Book Volume: 6942
Pages Range: 203 -- 214
Conference Proceedings Title: Algorithms - ESA 2011, 19th Annual European Symposium, Saarbrücken, Germany, September 5-9, 2011. Proceedings
ISBN: 978-3-642-23718-8
DOI: 10.1007/978-3-642-23719-5
Quantified linear programs (QLPs) are linear programs with variables being either existentially or universally quantified. The integer variant (QIP) is PSPACE-complete, and the problem is similar to games like chess, where an existential and a universal player have to play a two-person-zero sum game. At the same time, a QLP with n variables is a variant of a linear program living in , and it has strong similarities with multi-stage stochastic linear programs with variable right-hand side. Our interest in QLPs stems from the fact that they are LP-relaxations of QIPs, which themselves are mighty modeling tools. In order to solve QLPs, we apply a nested decomposition algorithm. In a detailed computational study, we examine, how different structural properties like the number of universal variables, the number of universal variable blocks as well as their positions in the QLP influence the solution process.
APA:
Ederer, T., Lorenz, U., Martin, A., & Wolf, J. (2011). Quantified Linear Programs: A Computational Study. In C. Demetrescu, M. Halldórsson (Eds.), Algorithms - ESA 2011, 19th Annual European Symposium, Saarbrücken, Germany, September 5-9, 2011. Proceedings (pp. 203 -- 214).
MLA:
Ederer, Thorsten, et al. "Quantified Linear Programs: A Computational Study." Proceedings of the Algorithms - ESA 2011, 19th Annual European Symposium, Saarbrücken, Germany, September 5-9, 2011. Proceedings Ed. C. Demetrescu, M. Halldórsson, 2011. 203 -- 214.
BibTeX: Download