A Novel Approach to Multistage Decision Making under Uncertainty

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

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.