Collaborative Research: Distributed Solution Algorithms for Large-Scale Multi-Stage Stochastic Programs

能源、金融、制造、电信、运输、物流和卫生保健等领域的许多重要决策问题难以解决，因为这些问题的特点是决策时的结果不确定，而且决策和随后的结果在多个阶段反复出现。解决如此复杂的问题轻而易举地超出了当前台式计算机的最先进的能力。为了克服这个问题，典型的方法会丢弃或聚合问题数据，从而丢失可能至关重要的信息。该奖项支持基础研究，以开发、评估和实施一种综合方法，通过使用分布式计算环境来优化不确定性下的大规模多阶段问题。对于这类问题缺乏普遍适用的有效解决方法，这就表明了这项研究的必要性。该项目的成果将直接适用于公共和私营部门广泛遇到的不确定性下的顺序决策问题，从而使美国经济和社会受益。这项研究将通过促进代表性不足的群体参与研究，对工程教育产生积极影响。本研究包括解决大规模多阶段随机规划的理论和方法上的进步。具体来说，它涉及到以分布式方式设计边界方案和精确解算法来解决此类问题。缺乏有效的求解方法，特别是当涉及混合整数决策变量时。现有的方法通常会做出限制性的假设，比如凸性。这种方法是广泛适用的，因为它不假设任何特殊的问题结构。此外，这种方法的一个固有特征是它非常适合分布式计算环境，这使得它能够解决真正大规模的实例。除了开发方法之外，研究团队还将在最先进的高性能计算集群上使用大规模实例来实现和评估它们的性能。

Many important decision problems in areas such as energy, finance, manufacturing, telecommunication, transportation, logistics, and health care are difficult to solve because they are characterized by uncertain outcomes when decisions are made, and furthermore the decisions and subsequent outcomes occur repeatedly, in multiple stages over time. Solving such complex problems easily exceeds the state-of-the-art capabilities of current desktop computers. To overcome this issue, typical methods discard or aggregate problem data, thereby losing information that may be critical. This award supports fundamental research to develop, evaluate, and implement a comprehensive methodology for optimizing such large-scale multi-stage problems under uncertainty by using a distributed computing environment. The need for this research is evident from the lack of generally applicable efficient solution methods for such problems. The results of this project will be directly applicable to sequential decision-making problems under uncertainty that are widely encountered in public and private sectors, therefore benefiting the U.S. economy and society. This research will positively impact engineering education by promoting the participation of underrepresented groups in research. This research consists of theoretical and methodological advancements for solving large-scale multi-stage stochastic programs. Specifically, it involves designing bounding schemes and exact solution algorithms to solve such problems in a distributed fashion. There is a lack of efficient solutions methods, particularly when mixed-integer decision variables are involved. Existing methods typically make restrictive assumptions such as convexity. This methodology is broadly applicable, as it does not assume any special problem structure. Moreover, an inherent feature of this approach is its natural fit into a distributed computing environment, which makes it amenable to solving truly large-scale instances. In addition to developing methods, the research team will implement and evaluate their performance using large-scale instances on a state-of-the-art high-performance computing cluster.