Online Stochastic Combinatorial Optimization

Advances in telecommunication technologies, combined with the increasingly integrated nature of optimization applications, create a wealth of online optimization problems in scheduling, routing, and resource allocation. Moreover, in many applications, stochastic and simulation models, or massive amount of historical data, are typically available to the decision-maker.

This talk presents an overview of online anticipatory algorithms for addressing this new class of applications and reports on their performance in a variety of settings. Anticipatory algorithms make decisions online, by conditionally sampling a distribution and solving the resulting optimization problems. Interestingly, many of these algorithms features innovative integration of artificial intelligence, discrete optimization, and stochastic programming techniques.