Methods for off-line/on-line optimization under uncertainty

Methods for off-line/on-line optimization under uncertainty

Allegra De Filippo, Michele Lombardi, Michela Milano

Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence
Main track. Pages 1270-1276. https://doi.org/10.24963/ijcai.2018/177

In this work we present two general techniques to deal with multi-stage optimization problems under uncertainty, featuring off-line and on-line decisions. The methods are applicable when: 1) the uncertainty is exogenous; 2) there exists a heuristic for the on-line phase that can be modeled as a parametric convex optimization problem. The first technique replaces the on-line heuristics with an anticipatory solver, obtained through a systematic procedure. The second technique consists in making the off-line solver aware of the on-line heuristic, and capable of controlling its parameters so as to steer its behavior. We instantiate our approaches on two case studies: an energy management system with uncertain renewable generation and load demand, and a vehicle routing problem with uncertain travel times. We show how both techniques achieve high solution quality w.r.t. an oracle operating under perfect information, by obtaining different trade-offs in terms of computation time.
Keywords:
Constraints and SAT: Constraint Optimisation
Heuristic Search and Game Playing: Combinatorial Search and Optimisation
Uncertainty in AI: Uncertainty in AI