Samplingbased Approximation Algorithms for Multistage Stochastic Optimization

Probabilistic Methods in the Design and Analysis of Algorithms

计算机科学;物理学

Chaitanya Swamy† David B. Shmoys‡

PID  :  81803

学科分类：计算机科学（综合）

来源: CEUR

【 摘 要 】

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, but 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 multi stage stochastic linear programming problems with any constant number of stages. The algorithm ana lyzed, 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 gener ate, 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 kstage generalizations of basic combinatorial optimization problems including the set