Zl. Chen et Wb. Powell, Convergent cutting-plane and partial-sampling algorithm for multistage stochastic linear programs with recourse, J OPTIM TH, 102(3), 1999, pp. 497-524
We propose an algorithm for multistage stochastic linear programs with reco
urse where random quantities in different stages are independent. The algor
ithm approximates successively expected recourse functions by building up v
alid cutting planes to support these functions from below. In each iteratio
n, for the expected recourse function in each stage, one cutting plane is g
enerated using the dual extreme points of the next-stage problem that have
been found so far. We prove that the algorithm is convergent with probabili
ty one.