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

协作研究：大规模多阶段随机程序的分布式求解算法

• 批准号: 1435771
• 负责人: Burhaneddin Sandikci
• 金额: $ 12万
• 依托单位: University of Chicago
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2014
• 资助国家: 美国
• 起止时间: 2014-08-01 至 2017-07-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1435771&HistoricalAwards=false
• 关键词: Collaborative; Research; Distributed; Solution; Algorithms

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.

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