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.