Computational stochastic programming with stochastic decomposition

Stochastic Programming (SP) has long been considered as a well-justified yet computationally challenging paradigm for practical applications. Computational studies in the literature often involve approximating a large number of scenarios by using a small number of scenarios to be processed via deterministic solvers, or running Sample Average Approximation on some genre of high performance machines so that statistically acceptable bounds can be obtained. In this dissertation we show that for a class of stochastic linear programming problems, an alternative approach known as Stochastic Decomposition (SD) can provide solutions of similar quality, in far less computational time using ordinary desktop or laptop machines of today. In addition to these compelling computational results, we also provide a stronger convergence result for SD, and introduce a new solution concept which we refer to as the compromise decision. This new concept is attractive for algorithms which call for multiple replications in sampling-based convex optimization algorithms. For such replicated optimization, we show that the difference between an average solution and a compromise decision provides a natural stopping rule. ❧ SD is a sequential sampling scheme combined with Benders’ like decomposition method for solving two stage stochastic linear programs with recourse. It exploits the special structures of the recourse problem to generate function approximations in an efficient manner. However, randomness is only allowed in the second stage right hand side and technology matrix associated with the first stage decision variables. In the second part of this dissertation, we relax this assumption to accommodate randomness of the second stage cost coefficients. Finally our computational results cover a variety of instances from the literature, and we further scale some operations management applications up to a level that is previously considered out of bounds for stochastic programming.随机规划（Stochastic Programming, SP）长期以来被视为一种理论依据充分，但在实际应用中却面临计算挑战的范式。现有文献中的计算研究通常采用两种思路：一是通过少量场景近似大量场景，以借助确定性求解器进行处理；二是在各类高性能计算设备上运行样本平均近似（Sample Average Approximation），以获得统计上可接受的界值。在本学位论文中，我们针对一类随机线性规划问题，证明了一种名为随机分解（Stochastic Decomposition, SD）的替代方法，可在使用当代普通台式机或笔记本电脑的前提下，以远更短的计算时间获得质量相当的解。除上述极具吸引力的计算结果外，我们还为随机分解推导了更强的收敛性结论，并提出了一个全新的解概念——折中决策。该新概念对于采样类凸优化算法中需要多次重复的场景颇具吸引力：针对这类重复优化问题，我们证明了平均解与折中决策之间的差值可作为自然的停止准则。 随机分解是一种结合类Benders分解方法的序贯采样方案，用于求解带追索的两阶段随机线性规划问题。它利用追索问题的特殊结构，以高效方式生成函数近似。不过该方法仅允许在第二阶段的右端项以及与第一阶段决策变量相关联的技术矩阵中引入随机性。在本论文的第二部分，我们放宽了这一假设，以容纳第二阶段成本系数的随机性。最后，我们的计算测试覆盖了文献中的各类经典算例，并进一步将部分运营管理应用的规模提升至此前被认为超出随机规划处理边界的水平。