Online Stochastic Combinatorial Optimization

在线随机组合优化

• 批准号: 0600384
• 负责人: Pascal Van Hentenryck
• 金额: $ 42.45万
• 依托单位: Brown University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2006
• 资助国家: 美国
• 起止时间: 2006-07-01 至 2010-06-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0600384&HistoricalAwards=false
• 关键词: Online; Stochastic; Combinatorial; Optimization

This grant provides funding for research on a novel paradigm for on-line, adaptive scheduling and resource allocation. This work envisions a new era in which optimization systems will not only allocate resources optimally: they will react and adapt to external events effectively under time constraints, anticipating the future and learning from the past to produce more robust and effective solutions. These systems will deal simultaneously with planning, scheduling, and control, complementing a priori optimization with integrated online decision making. The focus of this research is the concept of online stochastic combinatorial optimization that unifies stochastic optimization (from operations research) with online algorithms (from computer science). By moving from a priori to online optimization, this research will be able to provide adaptive algorithms focusing on the current data and uncertainty, and will make it possible to learn, and use, the uncertainty models online, which is critical in many applications such as pandemic containment. This framework naturally leverages progress in offline optimization.If successful, the results of this research will have a profound impact on time critical applications such as emergency response systems, pandemic containment, and power grid failure management. This research aims at developing systematically the theoretical foundations, the algorithms, the software infrastructure, and the applications of online stochastic combinatorial optimization. It will develop frameworks and algorithms for online stochastic combinatorial optimization that are general enough to model a wide variety of significant applications, and yet would provide quality guarantees with high probability and exhibit significant computational benefits. The research performed under this grant is likely to have significant impact on both undergraduate and graduate students at Brown, producing a stream of students with a broader perspective on decision making under uncertainty, and will lead to new courses and textbooks.

该补助金为在线，自适应调度和资源分配的新范式的研究提供资金。这项工作设想了一个新的时代，在这个时代，优化系统不仅可以最佳地分配资源：它们还可以在时间限制下有效地对外部事件做出反应和适应，预测未来并从过去学习，以产生更强大和有效的解决方案。这些系统将同时处理规划、调度和控制，通过集成的在线决策来补充先验优化。这项研究的重点是在线随机组合优化的概念，统一随机优化（从运筹学）与在线算法（从计算机科学）。通过从先验转向在线优化，这项研究将能够提供专注于当前数据和不确定性的自适应算法，并将使在线学习和使用不确定性模型成为可能，这在流行病遏制等许多应用中至关重要。如果成功的话，这项研究的结果将对紧急响应系统、流行病遏制和电网故障管理等时间关键型应用产生深远的影响。本研究旨在系统地发展在线随机组合优化的理论基础、算法、软件架构和应用。它将为在线随机组合优化开发框架和算法，这些框架和算法足够通用，可以模拟各种各样的重要应用，但仍将提供高概率的质量保证，并表现出显着的计算优势。在该资助下进行的研究可能会对布朗大学的本科生和研究生产生重大影响，培养出一批对不确定性下的决策有更广泛视角的学生，并将带来新的课程和教科书。