CAREER: Large Scale Stochastic Control: A Math Programming and Discrete Optimization Lens

点击翻译按钮获取中文摘要

The research objective of this Faculty Early Career Development (CAREER) project seeks to deliver new, approximate approaches for large-scale stochastic control that are easy to implement `out of the box' with little or no expert tuning. At a high level, the research will leverage algorithmic techniques and modes of analysis developed for deterministic optimization problems, in the design of algorithms for large-scale stochastic control. The project consists of two complementary thrusts. The first concerns deriving new math programming formulations for Approximate Dynamic Programming (ADP) via non-standard characterizations of optimal control. ADP algorithms constitute a general approach to large-scale control. These new math programming formulations promise simplicity and robustness, while potentially admitting strong theoretical performance guarantees. The second thrust concerns identifying classes of stochastic control problems wherein one may combat uncertainty with frequent re-optimization and limited `lookahead'. One avenue will consist of developing an abstract modeling framework for a large class of stochastic control problems analogous to that for discrete optimization problems over matroids - an eminently well-studied and relatively tractable class of discrete optimization problems. A second avenue will consist of analyzing dynamic `allocation' or `packing' problems whose deterministic analogues are simple linear programs; such models arise in settings as diverse as revenue management, healthcare and queueing. The goal is to pursue the analysis and development of extremely simple, easy to implement, re-optimization based schemes. The tool facilitating this analysis will consist of a characterization of the dynamics of `basis changes' in such problems.The research agenda above is rooted in real world applications. ADP algorithms have proven to be valuable tools in areas as far ranging as oil exploration to option pricing; the agenda above will potentially bring these schemes closer to being `technologies'. The matroid-like framework mentioned captures features of non-standard processing systems that arise ubiquitously in critical healthcare delivery settings among other applications. The dynamic allocation problems we focus on form the core computational routine in decisions made in online advertising systems, revenue management system and even internet switches, frequently at sub milli-second timescales. As such, the algorithms developed as part of this research will potentially be deployed in several manufacturing, healthcare and e-commerce related settings. In summary, if successful, this research will provide fundamental and practically relevant new tools for stochastic control at both the `generic' and `highly suctured' ends of the problem spectrum.