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

点击翻译按钮获取中文摘要

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.