Sampling-Based Approximation Algorithms for Multistage Stochastic Optimization
Authors:
- Chaitanya SwamyCSChaitanya Swamy
- David B. ShmoysDSDavid B. Shmoys
- 1 January 2012
- journal article
- research article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Computing
- Vol. 41 (4) , 975-1004
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 multistage stochastic programming problems. Multistage stochastic programming and, in particular, multistage stochastic linear programs with full recourse, is a domain that has received a great deal of attention within the operations research community, mostly from the perspective of computational results in application settings. Our main result is to give the first fully polynomial approximation scheme for a broad class of multistage stochastic linear programming problems with any constant number of stages. The algorithm analyzed, known as the sample average approximation 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 approximation algorithms for a variety of $k$-stage generalizations of basic combinatorial optimization problems including the set cover, vertex cover, multicut on trees, facility location, and multicommodity flow problems.Keywords
This publication has 17 references indexed in Scilit:
- Provably Near-Optimal Sampling-Based Policies for Stochastic Inventory Control ModelsMathematics of Operations Research, 2007
- LP Rounding Approximation Algorithms for Stochastic Network DesignMathematics of Operations Research, 2007
- An approximation scheme for stochastic linear programming and its application to stochastic integer programsJournal of the ACM, 2006
- Stochastic Combinatorial Optimization with Controllable Risk Aversion LevelLecture Notes in Computer Science, 2006
- Hedging Uncertainty: Approximation Algorithms for Stochastic Optimization ProblemsMathematical Programming, 2005
- What About Wednesday? Approximation Algorithms for Multistage Stochastic Optimization2005
- Sampling Bounds for Stochastic Optimization2005
- On a New Collection of Stochastic Linear Programming Test ProblemsINFORMS Journal on Computing, 2004
- The stochastic single resource service‐provision problemNaval Research Logistics (NRL), 2003
- The Sample Average Approximation Method for Stochastic Discrete OptimizationSIAM Journal on Optimization, 2002