Abstract
Sampling-based anticipatory algorithms can be
very effective at solving online optimization problems under uncertainty, but their computational
cost may be prohibitive in some cases. Given an
arbitrary anticipatory algorithm, we present three
methods that allow to retain its solution quality at
a fraction of the online computational cost, via a
substantial degree of offline preparation. Our approaches are obtained by combining: 1) a simple
technique to identify likely future outcomes based
on past observations; 2) the (expensive) offline
computation of a “contingency table”; and 3) an
efficient solution-fixing heuristic. We ground our
techniques on two case studies: an energy management system with uncertain renewable generation
and load demand, and a traveling salesman problem with uncertain travel times. In both cases, our
techniques achieve high solution quality, while substantially reducing the online computation time