On complexity of stochastic programming problems

Alexander Shapiro (ashapiroisye.gatech.edu)
Arkadi Nemirovski (nemirovsie.technion.ac.il)

Abstract: The main focus of this paper is 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 multi-stage stochastic programs with linear decision rules.

Keywords: stochastic programming, complete recourse, chance constraints, Monte Carlo sampling, SAA method, large deviations bounds, convex programming, multi-stage stochastic programming

Category 1: Stochastic Programming

Citation: School of Industrial and Systems Engineering, Georgia Institute of Technology, Atlanta, Georgia, USA

Download: [PDF]

Entry Submitted: 10/09/2004
Entry Accepted: 10/16/2004
Entry Last Modified: 01/15/2005

Modify/Update this entry