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?

本项目的研究目标是开发解决资源分配问题的一般在线优化方法和算法，这些方法和算法具有以下综合特征：(1)动态输入流，其模式具有重大不确定性；(2)对全部或部分在线决策的要求。将提出相应的一类日益复杂的正则问题。用于分析这些数据驱动的优化问题的数学工具将通过酌情纳入关于未来数据的随机信息和(或)从过去数据中有限的学习能力，扩大为在线问题提出的竞争性分析。在线算法的设计将使用贪婪技术以及原始-对偶概念的一般原理。它将在可用时纳入概率信息。算法的分析将基于理论竞争分析，包括渐近考虑，以及在受控数值模拟框架内的经验测试。如果成功，这项研究的结果将有助于理解如何处理/解决电信、计算和其他信息技术的持续发展带来的复杂的新数据驱动问题。虽然开发动态在线系统所需的基本技术已经可用，但这项研究的结果将提供利用这些技术提供的动态信息并利用过程产生具有成本效益的解决方案的算法。此外，我们希望这项研究将阐明以下基本问题：(I)如何量化数据驱动问题的不确定性程度，以及它对解决这些问题的能力的影响？(2)如何量化附加(确定性和/或概率性)信息对解决这类问题的价值？