Robust Dynamic Edge Service Placement Under Spatio-Temporal Correlated Demand Uncertainty

Edge computing enables Service Providers (SPs) to enhance user experience by placing services closer to the network edge. However, cost-effectively provisioning edge resources to meet uncertain and varying demand is a critical challenge. This paper introduces a novel two-stage, multi-period robust optimization model for edge service placement and workload allocation, aiming to minimize SPs' operating costs while ensuring service quality. The salient feature of this model is its ability to leverage dynamic service placement and spatio-temporal correlations in demand uncertainties to mitigate the conservatism of traditional robust approaches optimized for worst-case scenarios. In our model, resource reservation is determined preemptively in the first stage, while dynamic service placement and workload allocation are adaptively optimized in the second stage after uncertainties are revealed. To address the computational challenges posed by integer recourse variables in the resulting tri-level adjustable robust optimization problem, we develop a novel iterative decomposition-based approach with guaranteed finite convergence to an exact optimal solution. Extensive numerical results validate the efficacy of the proposed model and approach.