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.