One-sentence Summary

This paper presents a competitive randomized online algorithm that determines whether inelastic demands can be allocated over requested intervals under time-varying quadratic apparent power capacity constraints, introduces a nodal voltage constraint variant, and empirically evaluates both approaches through simulation studies.

Key Contributions

• A competitive randomized online algorithm is introduced to determine the allocation of sequential inelastic demands within requested intervals while satisfying time-varying apparent power capacity constraints.
• A variant of the algorithm is adapted to enforce nodal voltage limits under a relaxed path-topology model that assumes small transmission power losses.
• Simulation studies are provided to empirically evaluate both algorithms under the specified network constraints.

Introduction

Modern smart grids require real-time demand response management to balance intermittent renewable generation and maintain network stability. The authors address the practical challenge of scheduling inelastic, binary customer demands that arrive unpredictably without knowledge of future requests. While existing online optimization methods effectively handle linear constraints, power systems introduce non-linear quadratic limits on apparent power and strict nodal voltage bounds, leaving a gap in reliable, theoretically guaranteed scheduling solutions. To bridge this gap, the authors develop a competitive randomized online algorithm that dynamically allocates inelastic demands under time-varying apparent power constraints. They further adapt the framework to enforce nodal voltage limits and demonstrate that the approach supports both centralized and distributed control architectures while maintaining provable performance guarantees.

Dataset

• Dataset composition and sources: The authors construct a synthetic power system dataset using PSCAD simulation and CPLEX optimization. The data combines a custom microgrid environment with the standardized Canadian benchmark distribution system.
• Key details for each subset: The microgrid configuration features over 2000 sequentially arriving customers within a 4MVA capacity network, with arrival times following a uniform random distribution and demand durations sampled uniformly. The Canadian benchmark feeder is rated at 8.7MVA, 400A, and 12.47KV, utilizing 700MCM Cu XLPE cable with a fixed impedance of 0.1529 + J0.1406 Ω/km and assigning a 2MVA load to each node. The dataset also includes two utility models: a quadratic formulation with predetermined non-negative constants, and a random formulation capped at 1MVA for commercial customers and 20KVA for residential users.
• How the paper uses the data: The authors apply this dataset to the CSP_V problem to benchmark candidate algorithms. The CPLEX optimizer produces a baseline solution (OFL) that serves as a reference for performance comparison. Time-varying generation capacity is simulated using a Bernoulli process to reflect realistic grid fluctuations.
• Additional processing details: Customer preferences are structured through a probability preference model that governs utility generation. All demand profiles, capacity limits, and utility parameters are mathematically parameterized to ensure reproducible case studies and consistent algorithm evaluation.

Method

The authors present a competitive online algorithm, referred to as Online, designed to solve the complex-demand scheduling problem under generation capacity constraints (CSP_C) in a demand response (DR) framework. The overall framework is structured to handle the arrival of customers sequentially, making decisions online without knowledge of future demands, while ensuring feasibility with respect to time-varying generation capacity. The algorithm leverages a primal-dual (PD) schema as a core subroutine to obtain fractional solutions and employs a randomized rounding technique with correction to convert these fractional solutions into integral ones, thereby satisfying the binary decision variable constraints required for the problem.

The Online algorithm is initialized with global variables including fractional solutions $\widehat{x}$x and $\widetilde{x}$x, integral solution $x$x, and two sets $\mathcal{I}_S$IS​ and $\mathcal{I}_L$IL​ to categorize customers based on demand magnitude. The algorithm processes each arriving customer $k$k by first classifying it into one of the two sets: $\mathcal{I}_S$IS​ for small demands, defined as those satisfying $|S_k| \leq \delta \min_{t \in T_k}\{C_t\}$∣Sk​∣≤δmint∈Tk​​{Ct​}, or $\mathcal{I}_L$IL​ for large demands. For customers in $\mathcal{I}_S$IS​, the algorithm updates a fractional solution $\widehat{x}_s$xs​ using the PD subroutine, which operates on a linearly constrained packing problem derived from the original quadratically constrained problem via Lemma 3. For customers in $\mathcal{I}_L$IL​, a separate fractional solution $\widetilde{x}_l$xl​ is computed using the PD subroutine. The PD schema, detailed in Algorithm 2, iteratively increases the primal variable $x_k$xk​ while adjusting dual variables $y_t$yt​ to maintain feasibility and ensure the competitive ratio. After computing the fractional solutions, the algorithm applies randomized rounding: for a customer $k \in \mathcal{I}_L$k∈IL​, the decision $x_k$xk​ is set to 1 with probability $\alpha \tau \frac{\widetilde{x}_l}{u_k r_L}$ατuk​rL​xl​​, and for $k \in \mathcal{I}_S$k∈IS​, $x_k$xk​ is set to 1 with probability $(1-\tau) \frac{\widehat{x}_s}{2u_k r_S}$(1−τ)2uk​rS​xs​​. Finally, a correction step ensures feasibility by setting $x_k \leftarrow 0$xk​←0 if the resulting load exceeds the capacity constraint at any time slot $t$t. This process ensures that the algorithm produces a feasible solution while maintaining a theoretical competitive ratio, as analyzed in Theorem 1.

Experiment

The empirical evaluation compares the proposed Online algorithm against an offline optimal solution and a greedy first-come-first-serve benchmark across varying utility functions and operational constraints. Results demonstrate that the Online approach consistently achieves performance closely aligned with the offline optimum, whereas the FCFS method frequently deviates significantly from optimal outcomes. Additionally, the proposed algorithm successfully maximizes system objectives while maintaining end-of-feeder voltage levels within IEEE standards. These findings confirm the method's robustness and practical effectiveness for dynamic scheduling under realistic grid constraints.