Computational complexity of stochastic programming problems

M. Dyer, L. Stougie

    Research output: Contribution to JournalArticleAcademicpeer-review

    Abstract

    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
    Volume106
    Issue number3
    DOIs
    Publication statusPublished - 2006

    Fingerprint

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

    Cite this