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.