Integer Programming Under Uncertainty

不确定性下的整数规划

• 批准号: 0758234
• 负责人: Shabbir Ahmed
• 金额: $ 38万
• 依托单位: Georgia Tech Research Corporation
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2008
• 资助国家: 美国
• 起止时间: 2008-05-15 至 2012-04-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0758234&HistoricalAwards=false
• 关键词: Integer; Programming; Under; Uncertainty

PROJECT ABSTRACT Integer Programming under Uncertainty This grant provides funding to develop effective solution schemes for various dynamic integer programming (IP) models under uncertainty, and to apply these schemes to optimize models that deal with time dependent, on-demand networks. The models of uncertainty to be studied are: stochastic IP, chance-constrained IP, and robust IP. These are three of the fundamental approaches for dealing with uncertain data in optimization models. The first two approaches require probability distributions while robust optimization only requires uncertainty intervals on the data. However, in each of the three approaches, the resulting discrete optimization models cannot be solved efficiently by existing methodology. Stochastic, time-dependent IP models are extremely large-scale even when the underlying deterministic counterpart is of reasonable size. Chance-constrained and robust IP models are highly nonlinear and typically non-convex. The challenge is to develop theory and algorithms to overcome these difficulties. Our approach is to apply polyhedral integer programming, specifically mixing theory, to develop cutting plane strategies for the integer programming structures that arise under uncertainty. These results will be integrated with novel decomposition and branch-and-cut approaches to develop computationally effective algorithms. If successful, the results of this project will significantly advance the state of the art in cutting plane theory and in solving integer programming problems under uncertainty. Consequently, the results of this research project could lead to the use of integer programming under uncertainty in a variety of engineering applications. Currently, the commercial software used for discrete optimization in practice is essentially limited to solving deterministic problems. This research will be a significant step in making it possible to develop commercial software for the optimization of discrete, dynamic, stochastic systems. There is a great need for such decision support tools in optimizing on-demand networks that arise in transportation, supply chain, communication and power networks.

项目摘要：不确定性下的整数规划该基金提供资金，用于开发不确定性下各种动态整数规划（IP）模型的有效解决方案，并应用这些方案来优化处理时间依赖的按需网络的模型。研究的不确定性模型有：随机IP、机会约束IP和鲁棒IP。这是在优化模型中处理不确定数据的三种基本方法。前两种方法需要概率分布，而鲁棒优化只需要数据上的不确定区间。然而，在这三种方法中，所得到的离散优化模型都不能用现有的方法有效地求解。随机的、时间依赖的IP模型是非常大规模的，即使潜在的确定性对应是合理的规模。机会约束和健壮的IP模型是高度非线性的，通常是非凸的。挑战在于发展理论和算法来克服这些困难。我们的方法是应用多面体整数规划，特别是混合理论，为不确定情况下出现的整数规划结构制定切割平面策略。这些结果将与新的分解和分支切断方法相结合，以开发计算有效的算法。如果成功，本项目的结果将显著推动切割平面理论和解决不确定情况下的整数规划问题的最新进展。因此，该研究项目的结果可能会导致在各种工程应用中使用不确定性下的整数规划。目前，用于实际离散优化的商业软件基本上局限于解决确定性问题。这项研究将是重要的一步，使开发用于离散、动态、随机系统优化的商业软件成为可能。在优化运输、供应链、通信和电力网络中出现的按需网络时，非常需要这种决策支持工具。