Quantified Linear Programs: A Computational Study

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

Abstract

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.

Authors with CRIS profile

Involved external institutions

How to cite

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