Stochastic Decomposition A Statistical Method for Large Scale Stochastic Linear Programming

This book summarizes developments related to a class of methods called Stochastic Decomposition (SD) algorithms, which represent an important shift in the design of optimization algorithms. Unlike traditional deterministic algorithms, SD combines sampling approaches from the statistical literature with traditional mathematical programming constructs (e.g. decomposition, cutting planes etc.). This marriage of two highly computationally oriented disciplines leads to a line of work that is most definitely driven by computational considerations. Furthermore, the use of sampled data in SD makes it extremely flexible in its ability to accommodate various representations of uncertainty, including situations in which outcomes/scenarios can only be generated by an algorithm/simulation. The authors report computational results with some of the largest stochastic programs arising in applications. These results (mathematical as well as computational) are the `tip of the iceberg'. Further research will uncover extensions of SD to a wider class of problems. Audience: Researchers in mathematical optimization, including those working in telecommunications, electric power generation, transportation planning, airlines and production systems. Also suitable as a text for an advanced course in stochastic optimization.