Ebook: Hybrid Offline/Online Methods for Optimization Under Uncertainty

This work considers multi-stage optimization problems under uncertainty. In this context, at each stage some uncertainty is revealed and some decision must be made: the need to account for multiple future developments makes stochastic optimization incredibly challenging. Due to such a complexity, the most popular approaches depend on the temporal granularity of the decisions to be made. These approaches are, in general, sampling-based methods and heuristics. Long-term strategic decisions (which are often very impactful) are typically solved via expensive, but more accurate, sampling-based approaches. Short-term operational decisions often need to be made over multiple steps, within a short time frame: they are commonly addressed via polynomial-time heuristics, while more advanced sampling-based methods are applicable only if their computational cost is carefully managed. We will refer to the first class of problems (and solution approaches) as offline and to the second as online. These phases are typically solved in isolation, despite being strongly interconnected. Starting from the idea of providing multiple options to balance the solution quality/time trade-off in optimization problem featuring offline and online phases, we propose different methods that have broad applicability. These methods have been firstly motivated by applications in real-world energy problems that involve distinct offline and online phases: for example, in Distributed Energy Management Systems we may need to define (offline) a daily production schedule for an industrial plant, and then manage (online) its power supply on a hour by hour basis. Then we show that our methods can be applied to a variety of practical application scenarios in very different domains with both discrete and numeric decision variables.

In the first part of this work, we propose general methods based on a tighter integration between the two phases and we show that their applicability can lead to substantial improvements. Our methods are applicable under two (fairly general) conditions: 1) the uncertainty is exogenous; 2) it is possible to define a greedy heuristic for the online phase that can be modeled as a parametric convex optimization problem. We start with a baseline composed by a two-stage offline approach paired with an online greedy heuristic. We then propose multiple methods to tighten the offline/online integration, leading to significant quality improvements, at the cost of an increased computation effort either in the offline or the online phase.

The second part of this work focuses on how to manage the cost/quality trade-off of online stochastic anticipatory algorithms, taking advantage of some offline information. Sampling-based anticipatory algorithms can be very effective at solving online optimization problems under uncertainty, but their computational cost may be sometimes prohibitive. In many practical cases, some degree of information about future uncertainty is available significantly in advance. This provides an opportunity to exploit offline techniques to boost the performance of the online method. In this context, we present three methods that, given an arbitrary anticipatory algorithm, 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. Overall, all the methods proposed in this work provide multiple options to balance the solution quality/time trade-off in optimization problem featuring offline and online phases, suiting a variety of practical application scenarios. We ground our methods on two real case studies with both offline and online decisions: an energy management system with uncertain renewable generation and demand, and a routing problem with uncertain travel times. The application domain feature respectively continuous and discrete decisions. An extensive analysis of the experimental results shows that indeed offline/online integration may lead to substantial benefits by achieving high solution quality, while reducing the online computation time.