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

该奖项主要关注一类约束优化问题，其中数据是不确定的，需要在数据的不确定性消除之前做出一些决策（第一阶段）。一旦数据变得更加可靠（第二阶段），就会做出剩下的决定。此外，这些问题涉及离散和连续决策，因此被称为两阶段随机混合整数规划（SMIP）。本项目的目标是整合最近开发的基于多项析取的整数规划工具，以及基于分解和协调的随机规划思想。这些工具将为SMIP问题的顺序凸化提供基础，并允许通过有限序列的近似来解决这些问题。这些算法将在各种各样的实例上实现和严格测试。如果成功的话，该项目将允许工程师在工程设计、制造中的应急计划、军事行动计划等方面为软件添加更大的智能。对于这些和其他现实世界的工程问题，未来作业的准确设置是不可能准确预测的，而SMIP为应对不确定性提供了正式的基础。虽然这些问题在大多数操作中普遍存在，但能够解决此类计算问题的方法严重缺乏。所提出的方法的广泛适用性预计将改变在不确定环境中作出离散决策的方式。此外，该项目的结果将为不确定条件下的离散和连续优化建立一个统一的理论。

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.