The Blind Men and the Elephant: Integrated Offline/Online Optimization Under Uncertainty

Allegra De Filippo, Michele Lombardi, Michela Milano

Introduction

Optimization under uncertainty is traditionally bifurcated into two distinct paradigms: slow, robust "offline" strategic planning and fast, reactive "online" operational execution. This survey argues that treating these phases in isolation is akin to the parable of the blind men touching different parts of an elephant—each perceives a portion of the truth but misses the holistic reality. To bridge this gap, the authors advocate for integrated offline/online optimization, a framework where offline models are designed specifically to synergize with the constraints and heuristics of real-time online solvers.

Problem Statement: The Offline-Online Gap

In real-world domains such as vehicle routing, energy management, and production scheduling, decisions are inherently multi-stage. A plan is formulated "offline" (e.g., day-ahead) and subsequently adjusted "online" as uncertainties like traffic congestion or demand spikes manifest.

The standard two-stage decision process under uncertainty.

The authors identify a critical disconnect in current research:

  1. Offline methods (e.g., Sample Average Approximation) generate high-quality strategic plans but often assume that the "recourse" (the online adjustment) will be optimal and unconstrained by time.
  2. Online methods (e.g., greedy heuristics) offer the necessary speed for real-time response but are typically "myopic," failing to leverage historical data or account for long-term downstream effects.

When these paradigms are decoupled, an "optimal" offline plan may prove impossible for a fast online heuristic to implement, resulting in suboptimal real-world performance.

Methodology and Taxonomy

The survey categorizes existing approaches into three primary frameworks:

1. Pure Offline Optimization

These methods focus on strategic planning using techniques like Sample Average Approximation (SAA) and Benders decomposition. While they use scenarios to represent uncertainty, they often neglect the computational bottlenecks of real-time execution.

2. Pure Online Optimization

This focuses on real-time reaction. Anticipatory algorithms (e.g., Consensus or Regret algorithms) utilize limited sampling at runtime to "look ahead" without the overhead of a massive search space.

Sequential decision-making process over time.

3. Integrated Approaches

The core of the paper explores methods that bridge the two phases:

  • Contingency-based methods: Pre-computing policy trees or lookup tables for anticipated disruptions.
  • Markov Decision Processes (MDPs) & DRL: Training a policy offline via Deep Reinforcement Learning for instantaneous online deployment.
  • Online-Aware Offline Optimization: Modifying offline models (e.g., via parameter tuning or KKT-based constraints) to ensure the resulting plan is "friendly" to the specific heuristic used by the online solver.

Key Insights

  • Recourse as Online Optimization: The "second stage" of a classic two-stage stochastic program is, in practice, an online problem. If an offline model assumes an exact solver for stage two while the reality allows only a 10ms greedy heuristic, the offline plan is fundamentally flawed.
  • The Role of Machine Learning: ML serves as a bridge, either by "distilling" complex offline knowledge into fast online predictors or by tuning the parameters of online heuristics to mimic global optimizers.

Applications and Results

The paper synthesizes findings across various domains including Vehicle Routing (VRP), Kidney Exchange, and Energy Management. Key results include:

  • Hybrid DRL: Approaches combining offline value function approximation with online "rollout" algorithms show superior scalability for stochastic routing.
  • Parameter Tuning: Learning "potentials" offline for myopic online matching algorithms significantly outperforms standard sampling in kidney exchange problems.
  • Computational Gains: Integrated approaches can achieve the solution quality of complex anticipatory algorithms at a fraction of the online computational cost.

Limitations and Future Work

Despite progress, several challenges remain. Most Deep RL approaches struggle with the hard combinatorial constraints common in optimization. The authors suggest "Differentiable Programming" to embed solvers directly into neural architectures. Furthermore, there is a lack of unified frameworks; most current "online-aware" models are highly domain-specific. Future research should focus on "strategic synergy" — designing offline decisions specifically to increase the flexibility and ease of the online solver's task.

Summary updated

Abstract

Optimization problems under uncertainty are traditionally solved either via offline or online methods. Offline approaches can obtain high-quality robust solutions, but have a considerable computational cost. Online algorithms can react to unexpected events once they are observed, but often run under strict time constraints, preventing the computation of optimal solutions. Many real world problems, however, have both offline and online elements: a substantial amount of time and information is frequently available (offline) before an online problem is solved (e.g. energy production forecasts, or historical travel times in routing problems); in other cases both offline (i.e. strategic) and online (i.e. operational) decisions need to be made. Surprisingly, the interplay of these offline and online phases has received little attention: like in the blind men and the elephant tale, we risk missing the whole picture, and the benefits that could come from integrated offline/online optimization. In this survey we highlight the potential shortcomings of pure methods when applied to mixed offline/online problems, we review the strategies that have been designed to take advantage of this integration, and we suggest directions for future research.
BibTeX
@inproceedings{filippo2020blind,
  author = {Allegra De Filippo and Michele Lombardi and Michela Milano},
  title = {{The Blind Men and the Elephant: Integrated Offline/Online Optimization Under Uncertainty}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2020},
  doi = {10.24963/ijcai.2020/674},
}
Figure