Stochastic Decomposition for Two-Stage Stochastic Linear Programs with Random Cost Coefficients
Stochastic Decomposition for Two-Stage Stochastic Linear Programs with Random Cost Coefficients
复制标题
DOI：
10.1287/ijoc.2019.0929
复制
发表时间：
2021-12-01
影响因子：
2.1
通讯作者：
Sen, Suvrajeet
中科院分区：
文献类型：
--
作者：
Gangammanavar, Harsha;Liu, Yifan;Sen, Suvrajeet
随机分解（SD）是解决实际应用中出现的大规模随机规划（SP）问题的一种有效方法。通过使用增量采样，这种方法的目的是发现一个适当的样本大小为一个给定的SP实例，从而排除了需要的情况下减少或任意的样本大小，以创建样本平均近似值（SAA）。当与使用SAA程序获得的解决方案相比，SD提供了类似的质量的解决方案，在更少的计算时间，使用通常可用的计算资源。然而，以前版本的SD不适用于第二阶段成本系数的随机性问题。在本文中，我们扩展了它的能力，放宽这一假设的成本系数在第二阶段。除了实现这一目标所需的算法增强，我们还提出了实现这些扩展的细节，这些扩展保留了SD的计算边缘。最后，我们说明了从最新实施的SD各种测试实例中产生的问题，从文献中获得的计算结果。我们将这些结果与应用于不同样本量的这些问题的SAA函数的正则化L形方法所获得的结果进行了比较。
Stochastic decomposition (SD) has been a computationally effective approach to solve large-scale stochastic programming (SP) problems arising in practical applications. By using incremental sampling, this approach is designed to discover an appropriate sample size for a given SP instance, thus precluding the need for either scenario reduction or arbitrary sample sizes to create sample average approximations (SAA). When compared with the solutions obtained using the SAA procedure, SD provides solutions of similar quality in far less computational time using ordinarily available computational resources. However, previous versions of SD were not applicable to problems with randomness in second-stage cost coefficients. In this paper, we extend its capabilities by relaxing this assumption on cost coefficients in the second stage. In addition to the algorithmic enhancements necessary to achieve this, we also present the details of implementing these extensions, which preserve the computational edge of SD. Finally, we illustrate the computational results obtained from the latest implementation of SD on a variety of test instances generated for problems from the literature. We compare these results with those obtained from the regularized L-shaped method applied to the SAA function of these problems with different sample sizes.