Online stochastic optimization without distributions
Russell W. Bent, Pascal Van Hentenryck · 2005
This paper considers online stochastic scheduling prob-lems where time constraints severely limit the number of optimizations which can be performed at decision time and/or in between decisions. Prior research has demonstrated that, whenever a distribution of the in-puts is available for sampling, online stochatic algo-rithms may produce significant improvements in solu-tion quality over oblivious approaches. However, the availability of an input distribution, although reason-able in many contexts, is too strong a requirement in a variety of applications. This paper broadens the ap-plicability of online stochastic algorithms by relaxing this requirement and using machine learning techniques or historical data instead. In particular, it shows that machine learning techniques can be engineered to learn the distribution online, when its underlying structure is not available. Moreover, the paper presents the idea of historical sampling which provides a simple and effec-tive way to leverage historical data in continuous and periodic online optimization. Experimental results on packet scheduling and vehicle routing indicate the po-tential of machine learning and historical sampling for online scheduling.