A Novel Approach to Multistage Decision Making under Uncertainty

不确定性下多阶段决策的新方法

• 批准号: 1642531
• 负责人: Andrew Schaefer
• 金额: $ 24.89万
• 依托单位: William Marsh Rice University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2015
• 资助国家: 美国
• 起止时间: 2015-12-01 至 2018-07-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1642531&HistoricalAwards=false
• 关键词: Novel; Approach; Multistage; Decision; Making

Management in most practical settings involves a series of decisions that must be made repeatedly under uncertainty over a long period of time. Many of these decisions involve yes/no decisions, as well as decisions regarding appropriate levels of various factors. For many such problems, stochastic mixed-integer programming (SMIP) provides a powerful modeling framework. Unfortunately, state-of-the-art SMIP algorithms cannot solve realistic-sized problems that arise in real-world contexts. This award supports fundamental research aimed at investigating novel approaches that can form a framework for a general-purpose multistage SMIP solver. The broader impacts of this work will be felt in multiple domains. Should this approach prove successful, a much richer set of models can be solved in a variety of applications arising in healthcare, energy, manufacturing, and so on. The educational impacts will be felt by graduate and undergraduate students.In this research, which is known as scenario-tree decomposition, a novel method will be developed for decomposing the scenario tree of a multistage SMIP, rather than its extensive form. One major advantage of such approach is that it will not require any particular structure. Based on preliminary results and prior work on establishing bounds for two-stage SMIPs, it will be shown that cuts of the scenario tree can generate lower and upper bounds on a multistage SMIP. Moreover, it is hypothesized that a hierarchy among such bounds can be established. These bounds will be incorporated into a global branch-and-bound framework. Furthermore, this approach may be generalized beyond the standard stochastic programming paradigm. For example, it may be amenable to certain classes of nonlinear SMIPs. This method is highly amenable to high-performance computing, and will provide users with an explicit tradeoff between the quality of the bounds and the requisite computational effort.

在大多数实际情况下，管理涉及一系列决策，这些决策必须在长期不确定的情况下反复作出。其中许多决定涉及是/否决定，以及关于各种因素的适当水平的决定。对于许多此类问题，随机混合整数规划(SMIP)提供了一个强大的建模框架。不幸的是，最先进的SMIP算法不能解决现实世界中出现的实际大小的问题。该奖项支持旨在研究新方法的基础研究，这些方法可以形成通用多级SMIP解算器的框架。这项工作的更广泛影响将在多个领域感受到。如果这种方法被证明是成功的，则可以在医疗保健、能源、制造等领域的各种应用中解决更丰富的模型集。在这项被称为情景树分解的研究中，将开发一种新的方法来分解多级SMIP的情景树，而不是其扩展形式。这种方法的一个主要优点是，它不需要任何特定的结构。基于初步结果和先前关于建立两阶段SMIP边界的工作，将证明对情景树的切割可以产生多阶段SMIP的上下界。此外，还假设可以在这些界限之间建立一个等级。这些界限将被纳入一个全球分支和界限框架。此外，这种方法可以推广到超越标准的随机编程范例。例如，它可能服从于某些类型的非线性SMIP。这种方法非常适合于高性能计算，并将为用户提供边界质量和必要的计算工作量之间的明确折衷。