Stochastic decomposition: An algorithm for two-stage linear programs with recourse

The authors present a cutting plane algorithm for two-stage stochastic linear programs with recourse. Motivated by Benders’ decomposition, the present method uses randomly generated observations of random variables to construct statistical estimates of supports of the objective function. In general, the resulting piecewise linear approximations do not agree with the objective function in finite time. However, certain subsequences of the estimated supports are shown to accumulate at supports of the objective function, with probability one. From this, the authors establish the convergence of the algorithm under relatively mild assumptions.