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.

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