Computational complexity of stochastic programming problems

M. Dyer, L. Stougie

Research output: Contribution to journalArticleAcademicpeer-review

118 Citations (Scopus)
1 Downloads (Pure)


Stochastic programming is the subfield of mathematical programming that considers optimization in the presence of uncertainty. During the last four decades a vast quantity of literature on the subject has appeared. Developments in the theory of computational complexity allow us to establish the theoretical complexity of a variety of stochastic programming problems studied in this literature. Under the assumption that the stochastic parameters are independently distributed, we show that two-stage stochastic programming problems are ¿P-hard. Under the same assumption we show that certain multi-stage stochastic programming problems are PSPACE-hard. The problems we consider are non-standard in that distributions of stochastic parameters in later stages depend on decisions made in earlier stages.
Original languageEnglish
Pages (from-to)423-432
JournalMathematical Programming
Issue number3
Publication statusPublished - 2006


Dive into the research topics of 'Computational complexity of stochastic programming problems'. Together they form a unique fingerprint.

Cite this