Integer Programming Under Uncertainty

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

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.