Research Initiation Award: Conditional Stochastic Decomposition - An Algorithmic Interface for Optimization/Simulation

本研究解决了优化和仿真程序之间的算法接口的设计、开发和分析。本文提出的算法条件随机分解（CSD）是基于随机分解的一种新引入的求解带追索权的两阶段随机线性规划的算法。虽然随机分解本质上是嵌入随机化代理的Bender分解的一个版本，但CSD是一种最大限度地利用随机元素的每个可用观察的算法。这项研究包括两个主要任务。第一个涉及CSD的分析验证，并将导致计算权宜之计的发展，包括切割/变量消除和聚合技术。第二部分涉及对算法性能特征的实证研究，并且必然包括测试问题的开发。用基本版随机分解进行的初步测试表明，它非常适合求解有追索权的大规模两阶段随机优化问题。当问题的随机性质足够复杂，以致无法用封闭形式的分布来描述时，CSD作为优化/模拟界面的发展应允许解决此类问题。

This research addresses the design, development, and analysis of algorithmic interfaces between optimization and simulation procedures. The proposed algorithm, Conditional Stochastic Decomposition (CSD), is based on stochastic decomposition, a newly introduced algorithmic concept for the solution of two stage stochastic linear programs with recourse. While stochastic decomposition is essentially a version of Bender's decomposition with an embedded randomizing agent, CSD is an algorithm that makes maximal use of each available observation of the random element. The research includes two major tasks. The first involves analytic verification of CSD, and will lead to the development of computational expedients, including cut/variable elimination and aggregation techniques. The second involves an empirical investigation of the algorithms performance characteristics, and will necessarily include the development of test problems. As preliminary tests with a basic version of stochastic decomposition suggest that it is ideally suited for the solution of large scale two stage stochastic optimization problems with recourse, the development of CSD as an optimization/simulation interface should allow for the solution of such problems when the stochastic nature of the problem is sufficiently complex to preclude its description with closed form distributions.