Stochastic Mixed-Integer Optimization: Polyhedral Theory, Large-Scale Algorithms and Computations

点击翻译按钮获取中文摘要

This award focuses on a class of constrained optimization problems in which data are uncertain, and some decisions need to be made before uncertainty about the data clears (first-stage). The remaining decisions are made once the data becomes more reliable (second-stage). In addition, these problems involve both discrete and continuous decisions, and hence are referred to as Two-stage Stochastic Mixed-Integer Programs (SMIP). The goal of this project is to integrate recently developed integer programming tools based on multi-term disjunctions, and stochastic programming ideas based on decomposition and coordination. These tools will provide the basis for sequential convexification of SMIP problems, and will allow their solution via a finite sequence of approximations. These algorithms will be implemented and rigorously tested on a wide variety of instances.If successful, this project will allow engineers to add greater intelligence to software that is used in engineering design, contingency planning in manufacturing, military operations planning, and many more. For these and other real-world engineering problems, the exact setting of future operations is impossible to predict accurately, and SMIP provides a formal basis to cope with the uncertainty. While these issues are ubiquitous in most operations, there is a serious paucity of methodologies that can solve such computational problems. The widespread applicability of the proposed methodology is expected to transform the way in which discrete decisions are made in an uncertain environment. Moreover, results from this project will build a unifying theory for discrete and continuous optimization under uncertainty.