Sampling-based Approximation Algorithms for Multi-stage Stochastic
Authors:
- 15 November 2005
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 357-366
Abstract
Stochastic optimization problems provide a means to model uncertainty in the input data where the uncertainty is modeled by a probability distribution over the possible realizations of the actual data. We consider a broad class of these problems in which the realized input is revealed through a series of stages, and hence are called multi-stage stochastic programming problems. Our main result is to give the first fully polynomial approximation scheme for a broad class of multi-stage stochastic linear programming problems with any constant number of stages. The algorithm analyzed, known as the sample average approximation (SAA) method, is quite simple, and is the one most commonly used in practice. The algorithm accesses the input by means of a "black box" that can generate, given a series of outcomes for the initial stages, a sample of the input according to the conditional probability distribution (given those outcomes). We use this to obtain the first polynomial-time approximation algorithms for a variety of k-stage generalizations of basic combinatorial optimization problems.Keywords
This publication has 10 references indexed in Scilit:
- On complexity of multistage stochastic programsOperations Research Letters, 2006
- What About Wednesday? Approximation Algorithms for Multistage Stochastic Optimization2005
- Sampling Bounds for Stochastic Optimization2005
- Stochastic Optimization is (Almost) as easy as Deterministic Optimization2004
- On a New Collection of Stochastic Linear Programming Test ProblemsINFORMS Journal on Computing, 2004
- Boosted sampling2004
- Hedging Uncertainty: Approximation Algorithms for Stochastic Optimization ProblemsLecture Notes in Computer Science, 2004
- The stochastic single resource service‐provision problemNaval Research Logistics (NRL), 2003
- Monte Carlo Sampling Methods2003
- The Sample Average Approximation Method for Stochastic Discrete OptimizationSIAM Journal on Optimization, 2002