Large-Scale Online and Real-Time Optimization Problems under Uncertainty

摘要

The main focus of our research is on the fundamental aspects of decision making in the context of uncertain (and possibly very large) data sets revealed in an online fashion. More specifically, we are interested in the intersection and interplay of three main phenomena -- incomplete and uncertain data, online decisions with or without real-time restrictions, and extremely large data sets -- and the corresponding fundamental questions when facing a problem exhibiting one or more of these phenomena. These questions are as follows: (1) How to properly model and quantify the degree of uncertainty in such a problem and its impact on our ability to 'solve' it; (2) How to quantify the value of additional (deterministic and/or probabilistic) information for solving such problems. Is it worth it to seek additional information; and (3) How to design provably good algorithms for such problems. There are many motivating examples for such problems. In the proposal that led to this funded research, we listed examples in routing and scheduling as well as applications in which the basic decisions were to assign goods, items, or requests to clients, bins, or servers (assignment or allocation problems). In a recent internal ONR white paper we highlighted applications associated with the deployment of autonomous multiagent systems for spatial exploration and information harvesting. The major objectives of this long-ranging research involve the definition and rigorous mathematical analysis of canonical models which would capture the essence of this new class of problems. The overall purpose is to systematically analyze and integrate the most promising paradigms/solution strategies for dealing with these problems; formulate adequate corresponding models; and develop, analyze, and implement algorithms for solving them.