The Scenario Generation Algorithm for Multistage Stochastic Linear Programming
Authors:
- 1 August 2005
- journal article
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in Mathematics of Operations Research
- Vol. 30 (3) , 615-631
Abstract
A multistage stochastic linear program (MSLP) is a model of sequential stochastic optimization where the objective and constraints are linear. When any of the random variables used in the MSLP are continuous, the problem is infinite dimensional. To numerically tackle such a problem, we usually replace it with a finite-dimensional approximation. Even when all the random variables have finite support, the problem is often computationally intractable and must be approximated by a problem of smaller dimension. One of the primary challenges in the field of stochastic programming deals with discovering effective ways to evaluate the importance of scenarios and to use that information to trim the scenario tree in such a way that the solution to the smaller optimization problem is not much different from the problem stated with the original tree. The scenario generation (SG) algorithm proposed in this paper is a finite-element method that addresses this problem for the class of MSLP with random right-hand sides.Keywords
This publication has 11 references indexed in Scilit:
- Generating Scenario Trees for Multistage Decision ProblemsManagement Science, 2001
- Scenario tree generation for multiperiod financial optimization by optimal discretizationMathematical Programming, 2001
- Stochastic Lagrangian Relaxation Applied to Power Scheduling in a Hydro-Thermal System under UncertaintyAnnals of Operations Research, 2000
- Duality and optimality in multistagestochastic programmingAnnals of Operations Research, 1999
- Bound‐based approximations in multistage stochasticprogramming: Nonanticipativity aggregationAnnals of Operations Research, 1999
- Concepts, Technical Issues, and Uses of the Russell-Yasuda Kasai Financial Planning ModelOperations Research, 1998
- Barycentric scenario trees in convex multistage stochastic programmingMathematical Programming, 1996
- Stochastic Programming1995
- Stochastic programming in production planning: a case with none‐simple recourseStatistica Neerlandica, 1977
- Discretizations of multistage stochastic programming problems1976