Stochastic decomposition. A statistical method for large scale stochastic linear programming (Q2564096): Difference between revisions

A stochastic decomposition method for the approximate solution of stochastic linear programs with recourse is presented. Under the stochastic decomposition the authors keep in mind a cutting plane algorithm that, uses randomly generated observations of the random parameter \(\omega\) in order to construct cuts. Rather than optimizing the sample mean function, the stochastic decomposition develop lower bound piecewise linear approximations to the second stage correction function. These approximations bypass the need to solve a large number of second stage subproblems. In Chapter 1 properties and examples of two stage stochastic linear programs are presented. Chapter 2 describes the sample mean optimization algorithm for the approximate solution of stochastic linear programs with recourse. In Chapter 3 the basic stochastic decomposition algorithm is described and analyzed. Stochastic decomposition is a stochastic cutting plane algorithm that uses randomly generated observations of the random parameter \(\omega\) in order to construct approximate cutting planes for the second stage recourse function. Each cut is derived using a different number of observations of the random parameter \(\omega\). In Chapter 4 the algorithm is regularized by adding a quadratic term to the cost function, whereas the stopping rules for stochastic decomposition are discussed in Chapter 5. Guideliness for an eflicient computer implementation of stochastic decomposition algorithms are analyzed in Chapter 6.