A Novel Approach to Multistage Decision Making under Uncertainty

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

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.