Certified Single-Level Reformulation for Tri-Level Cyber-Physical Grid Security

Modern power grids are increasingly exposed to coordinated cyber-physical disruptions, where the outage of a small number of transmission components can trigger severe post-contingency load shedding. Designing proactive _security defense_ against such adversarial contingencies is naturally modeled as a tri-level Defender-Attacker-Operator (DAO) problem: the defender allocates limited hardening resources, the attacker selects worst-case line outages, and the operator solves a post-attack DC/AC-optimal power flow (OPF). However, the resulting tri-level program is computationally prohibitive even for moderate network sizes. We develop a certified four-step reformulation pipeline that converts this intractable tri-level DAO problem into a tractable single-level optimization, yielding a Single-Level Mixed-Integer Linear Program (SL-MILP) under DC-OPF and a Single-Level Mixed-Integer Conic Program (SL-MICP) under AC-OPF. The construction combines exact dualization, exact Big-$M$ linearization, and a single controlled attacker relaxation. We prove that the resulting single-level optimum provides a conservative upper bound on the true worst-case load shedding and, more importantly, yields a robustness certificate for the deployed defense: no feasible binary attack can induce damage exceeding the reported single-level value. Extensive experiments on IEEE benchmark systems demonstrate substantial runtime improvements while maintaining strong worst-case security guarantees.