On complexity of stochastic programming problems. (English) Zbl 1115.90041

Jeyakumar, Vaithilingam (ed.) et al., Continuous optimization. Current trends and modern applications. New York, NY: Springer (ISBN 0-387-26769-7/hbk). Applied Optimization 99, 111-146 (2005).
Summary: The main focus of this paper is in a discussion of complexity of stochastic programming problems. We argue that two-stage (linear) stochastic programming problems with recourse can be solved with a reasonable accuracy by using Monte Carlo sampling techniques, while multi-stage stochastic programs, in general, are intractable. We also discuss complexity of chance constrained problems and multistage stochastic programs with linear decision rules.
For the entire collection see [Zbl 1078.90003].


90C15 Stochastic programming
90C60 Abstract computational complexity for mathematical programming problems