This Article Full Text (PDF) References Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Download to citation manager Citing Articles Citing Articles via Google Scholar Google Scholar Articles by Casey, M. S. Articles by Sen, S. Search for Related Content

The Scenario Generation Algorithm for Multistage Stochastic Linear Programming

407 North Broadway, Apt. 14, Redondo Beach, California 90277
SIE Department, University of Arizona, Tucson, Arizona 85721-0001
msc.sedcontra{at}gmail.com
sen{at}sie.arizona.edu

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.

Key Words: multistage stochastic linear program; stochastic optimization; scenario tree generation; finite element methods
History: Received: October 29, 2002; revision received: November 24, 2003;revision received: October 20, 2004;