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

研究启动奖：条件随机分解 - 用于优化/模拟的算法接口

• 批准号: 8910046
• 负责人: Julia Higle
• 金额: $ 6万
• 依托单位: University of Arizona
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 1989
• 资助国家: 美国
• 起止时间: 1989-11-01 至 1992-04-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=8910046&HistoricalAwards=false
• 关键词: Research; Initiation; Award; Conditional; Stochastic

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.

这项研究涉及设计，开发， 分析优化与 模拟程序 该算法，条件 随机分解（CSD），基于随机 分解，一个新引入的算法概念， 带补偿两阶段随机线性规划解 虽然随机分解本质上是一个版本的 具有嵌入随机化剂的Bender分解，CSD是 最大限度地利用每个可用观测值的算法 的随机元素。 研究包括两个主要任务。 第一个涉及CSD的分析验证，并将导致 计算经验的发展，包括 切割/变量消除和聚合技术。 第二 涉及算法性能的实证调查 特点，并将必然包括发展 测试问题。 作为初步测试， 随机分解表明它非常适合于 大规模两阶段随机优化问题解 资源问题，CSD的发展作为一个 优化/模拟界面应允许解决方案 当问题的随机性是 复杂到无法用封闭形式描述 分布。