Online Optimization for Dynamic Resource Allocation Problems

动态资源分配问题的在线优化

• 批准号: 1029603
• 负责人: Patrick Jaillet
• 金额: $ 29.5万
• 依托单位: Massachusetts Institute of Technology
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2010
• 资助国家: 美国
• 起止时间: 2010-09-01 至 2015-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1029603&HistoricalAwards=false
• 关键词: Online; Optimization; Dynamic; Resource; Allocation

The research objective of this project is for the development of general online optimization methodologies and algorithms for addressing resource allocation problems with the following combined characteristics: (i) dynamic input streams with significant uncertainty about their patterns and (ii) requirements for full or partial online decision making. A corresponding class of canonical problems of increasing complexity will be proposed. The mathematical tools for the analysis of these data-driven optimization problems will expand the competitive analysis proposed for online problems, by incorporating, when appropriate, stochastic information about future data and/or limited learning capabilities from past data. The design of the online algorithms will use greedy techniques as well as general principles from primal-dual concepts. It will incorporate probabilistic information when available. The analysis of the algorithms will be based on theoretical competitive analysis, including asymptotic consideration, and on empirical testing within a controlled numerical simulation framework.If successful, the results of this research will help understand how to tackle/solve complex new data-driven problems that have been made possible from continuing developments in telecommunication, computing, and other information technologies. While the basic technologies needed for the development of dynamic online systems are already available, the results of this research would provide algorithms that exploit the dynamic information supplied by these technologies and leverage processes to generate cost effective solutions. In addition we hope that this research will shed lights on the following basic questions: (i) How to quantify the degree of uncertainty in data-driven problems, and its impact on the ability to solve them? (ii) How to quantify the value of additional (deterministic and/or probabilistic) information for solving such problems?

该项目的研究目标是开发一般在线优化方法和算法，以解决以下组合特征来解决资源分配问题：（i）对其模式的不确定性以及（ii）全面或部分在线决策的需求的动态输入流。将提出一类相应的规范问题，即增加复杂性。用于分析这些数据驱动的优化问题的数学工具将扩大针对在线问题的竞争分析，并在适当的情况下合并有关未来数据和/或从过去数据中学习有限的学习能力的随机信息。在线算法的设计将使用贪婪的技术以及原始偶尔概念中的一般原则。可用时，它将包含概率信息。对算法的分析将基于理论竞争分析，包括渐近考虑，以及在受控的数值模拟框架内的经验测试。尽管已经可以使用动态在线系统所需的基本技术，但这项研究的结果将提供算法，以利用这些技术提供的动态信息并利用流程来生成成本有效的解决方案。此外，我们希望这项研究能够在以下基本问题上阐明：（i）如何量化数据驱动问题的不确定性程度及其对解决这些问题的影响？ （ii）如何量化解决此类问题的其他信息（确定性和/或概率）信息的价值？