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

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

基本信息

批准号：
1436177
负责人：
Osman Ozaltin
金额：
$ 14.19万
依托单位：
North Carolina State University
依托单位国家：
美国
项目类别：
Standard Grant
财政年份：
2014
资助国家：
美国
起止时间：
2014-08-01 至 2018-07-31
项目状态：
已结题

来源：
https://www.nsf.gov/awardsearch/showAward?AWD_ID=1436177&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.

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