Online stochastic optimization under time constraints (Q1958625)

In this paper the authors consider online stochastic combinatorial optimization problems (OSCO), that integrated online algorithms and stochastic optimization. In OSCO the uncertainties are characterized by distributions that can be sampled and where time constraints severely limit the number of offline optimizations which can be performed at decision time and/or in between decisions. This paper reviews recent developments in OSCO and presents new theoretical and experimental results. The authors propose three main algorithms: expectation \(E\), consensus \(C\), and reset \(R\). The algorithms were evaluated experimentally and theoretically. The experimental results were obtained on three applications of different nature: packet scheduling, multiple vehicle routing with time windows, and multiple vehicle dispatching. The theoretical results show that algorithm \(E\) has an expected constant loss compared to the offline optimal solution. Algorithm \(R\) has an expected \(\rho (1+o(1))\) loss (when the regret gives an \(\rho \)-approximation to the offline problem), but is significantly faster.