Integrated Offline and Online Decision Making under Uncertainty

Allegra De Filippo, Michele Lombardi, Michela Milano

TL;DR

This paper tackles the challenge of making optimal decisions in complex systems that involve both long-term strategic planning (offline) and short-term operational adjustments (online), all under uncertainty. The authors propose four novel methods that integrate these two phases, demonstrating significant improvements in solution quality and efficiency compared to treating them separately.

What Problem Does This Paper Address?

Many real-world applications, from energy management to vehicle routing, require a sequence of decisions made over time. Some decisions are "strategic" and can be made with more time and data (offline), while others are "operational" and must be made quickly as new information becomes available (online). The core challenge is that these two phases are often treated in isolation, leading to suboptimal outcomes. For instance, an offline plan might not be compatible with the capabilities of the online decision-maker, or an online solver might struggle to adapt to unexpected events because the offline plan didn't account for its limitations. This paper aims to bridge this gap by developing methods that allow the offline and online decision-making processes to work synergistically, leading to better overall performance.

Methods

The authors build upon a baseline approach that uses a two-stage stochastic optimization model for offline decisions and a greedy heuristic for online decisions. They then propose four methods to improve this integration:

  • ANTICIPATE: This method enhances the online solver by making it "anticipatory." Instead of a myopic greedy approach, it uses a sampling-based algorithm that considers future scenarios to make more informed online decisions. This increases the online phase's computational load.
  • TUNING: This approach focuses on improving the greedy heuristic by adjusting its parameters offline. This is achieved by incorporating the heuristic's optimality conditions (KKT conditions) into the offline optimization problem, effectively "tuning" the heuristic's behavior without increasing its online computation time.
  • ACKNOWLEDGE: Here, the offline solver is made aware of the online heuristic's limitations. This is done by injecting the KKT conditions of the online heuristic as constraints into the offline optimization problem. This forces the offline decisions to be compatible with the online solver's capabilities.
  • ACTIVE: This method combines the ideas of TUNING and ACKNOWLEDGE. It simultaneously optimizes offline decisions and the parameters for the online heuristic by incorporating KKT conditions into the offline problem. This offers the deepest integration but comes with the highest offline computational cost.

Datasets

The paper uses two case studies to test their methods:

  • Energy Management System (EMS): This case study uses data from a virtual power plant (VPP) scenario, drawing from public datasets for residential and industrial plants with varying renewable energy generation and market prices.
  • Vehicle Routing Problem (VRP): This case study uses instances from the Solomon's TSPTW benchmark dataset, specifically instances I1 through I6, with varying numbers of customers.

Key Insights and Ideas

  • Synergy is Key: Treating offline and online decision-making in isolation is a significant missed opportunity. Integrating them can lead to substantial improvements in solution quality and efficiency.
  • Anticipation vs. Awareness: The authors explore two main strategies for integration: making the online solver anticipatory (ANTICIPATE) or making the offline solver aware of the online solver's limitations (ACKNOWLEDGE, TUNING, ACTIVE). Both can be effective, but the choice depends on time constraints.
  • Bridging the Gap: The core idea behind TUNING, ACKNOWLEDGE, and ACTIVE is to use the mathematical formulation of the online heuristic (specifically, its KKT conditions) to guide or constrain the offline decisions. This allows the offline phase to "understand" how the online phase will behave.
  • Virtual Costs for Guidance: In the energy management case, the ACTIVE method introduces "virtual costs" for energy storage. This allows the offline phase to strategically encourage or discourage storage, guiding the online heuristic to make better decisions regarding energy market prices and renewable energy utilization.
  • Discrete vs. Continuous Decisions: The proposed methods are shown to be effective for both continuous (EMS) and discrete (VRP) decision variables, highlighting their generality.

Key Results

  • Significant Quality Improvement: All proposed methods (ANTICIPATE, TUNING, ACKNOWLEDGE, ACTIVE) consistently outperform the baseline approach in terms of solution quality (lower costs/travel times) across both case studies.
  • ANTICIPATE vs. EXPECTATION: For discrete problems like VRP, ANTICIPATE achieves comparable solution quality to EXPECTATION (an established anticipatory algorithm) but is more general and can handle continuous variables, which EXPECTATION cannot.
  • ACTIVE's Performance: The ACTIVE method often achieves the best solution quality, sometimes even surpassing ANTICIPATE, by deeply integrating offline and online optimization. However, this comes at the cost of significantly higher offline computation time.
  • Trade-offs: The methods offer different trade-offs between offline computation time, online computation time, and solution quality. For instance, TUNING provides a fast online heuristic with offline parameter tuning, while ACKNOWLEDGE makes the offline solver aware of online limitations.

Limitations and Future Work

  • Scalability: The authors acknowledge that the scalability of their methods, particularly those involving KKT conditions, can be adversely affected by the need for additional variables and constraints. Large scenario sets or long look-ahead horizons can also lead to larger, potentially NP-hard, problems.
  • Guidance for Method Selection: The paper suggests that defining clear guidelines for choosing among the proposed methods based on problem characteristics and time constraints would be very useful.
  • Improving Scalability: Future work includes exploring ways to improve scalability, such as replacing sampling with machine learning predictors.
  • Enhancing Efficiency: Further research is planned to improve the efficiency of the methods, similar to how EXPECTATION was improved in REGRET.
  • Broader Applications: The authors intend to apply their approaches to other problems, such as resource allocation and scheduling with Simple Temporal Networks under Uncertainty.

Summary updated

Abstract

This paper considers multi-stage optimization problems under uncertainty that involve distinct offline and online phases. In particular it addresses the issue of integrating these phases to show how the two are often interrelated in real-world applications. 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 the 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. Overall, our methods provide multiple options to balance the solution quality/time trade-off, suiting a variety of practical application scenarios. To test our methods, we ground our approaches on two real cases studies with both offline and online decisions: an energy management problem with uncertain renewable generation and demand, and a vehicle routing problem with uncertain travel times. The application domains feature respectively continuous and discrete decisions. An extensive analysis of the experimental results shows that indeed offline/online integration may lead to substantial benefits.
BibTeX
@article{filippo2021integrated,
  author = {Allegra De Filippo and Michele Lombardi and Michela Milano},
  title = {{Integrated Offline and Online Decision Making under Uncertainty}},
  journal = {J. Artif. Intell. Res.},
  year = {2021},
  doi = {10.1613/jair.1.12333},
}

Loading related content...

Figure