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.