Stochastic Decomposition: An Algorithm for Two-Stage Linear Programs with Recourse
Stochastic Decomposition: An Algorithm for Two-Stage Linear Programs with Recourse
复制标题
DOI：
10.1287/moor.16.3.650
复制
发表时间：
1991-08
期刊：
影响因子：
--
通讯作者：
J. Higle;S. Sen
中科院分区：
文献类型：
--
作者：
J. Higle;S. Sen
提出了一种带追索权的两阶段随机线性规划的切平面算法。受Benders分解的启发，我们的方法使用随机变量的随机生成观测值来构建目标函数支持度的统计估计。一般情况下，所得的分段线性近似在有限时间内与目标函数不一致。然而，估计支持的某些子序列在目标函数的支持处累积，概率为1。由此，我们在相对温和的假设下证明了算法的收敛性。
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.