Stochastic Decomposition: An Algorithm for Two-Stage Linear Programs with Recourse

TLDR

Piecewise linear approximations of two‑stage stochastic linear programs with recourse generally fail to match the objective function in finite time. The study introduces a cutting‑plane algorithm for such problems. The method builds statistical estimates of the objective‑function supports from random observations, following a Benders‑decomposition framework. The authors show that subsequences of these estimates converge almost surely to the true supports, proving algorithm convergence under mild assumptions.

Abstract

We present a cutting plane algorithm for two-stage stochastic linear programs with recourse. Motivated by Benders' decomposition, our 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, we establish the convergence of the algorithm under relatively mild assumptions.