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

随机混合整数优化：多面体理论、大规模算法和计算

• 批准号: 1100383
• 负责人: Simge Kucukyavuz
• 金额: $ 23万
• 依托单位: Ohio State University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2011
• 资助国家: 美国
• 起止时间: 2011-07-01 至 2014-06-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1100383&HistoricalAwards=false
• 关键词: Stochastic; Mixed; Integer; Optimization; Polyhedral

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.

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