Online Optimization for Dynamic Resource Allocation Problems

Massachusetts Institute Of Technology, Cambridge MA

Investigators

Abstract

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?