Tightening Quadratic Convex Relaxations for the Alternating Current Optimal Transmission Switching Problem

The alternating current optimal transmission switching (ACOTS) problem incorporates line switching decisions into the alternating current optimal power flow framework, offering well-known benefits in reducing operational costs and enhancing system reliability. ACOTS optimization models contain discrete variables and nonlinear, nonconvex constraints, which make them difficult to solve. In this work, we develop strengthened quadratic convex (QC) relaxations for ACOTS, in which we tighten the relaxation with several new valid inequalities, including a novel kind of on/off cycle–based polynomial constraints by taking advantage of the network structure. We linearize the sum of on/off trilinear terms in the relaxation using extreme-point representation, demonstrating theoretical tightness, and efficiently incorporate on/off cycle–based polynomial constraints through disjunctive programming–based cutting planes. Combined with an optimization-based bound-tightening algorithm, this results in the tightest QC-based ACOTS relaxation to date. We additionally propose a novel maximum spanning tree–based heuristic to improve the computational performance by fixing certain lines to be switched on. Our extensive numerical experiments on medium-scale power grid library instances show significant improvements on relaxation bounds, whereas tests on large-scale instances with up to 2,312 buses demonstrate substantial performance gains. To our knowledge, this is the first ACOTS relaxation-based approach to demonstrate near-optimal switching solutions on realistic large-scale power grid instances. History: Accepted by Pascal Van Hentenryck, Area Editor for Computational Modeling: Methods & Analysis. Funding: The authors gratefully acknowledge support from the U.S. Department of Energy through Los Alamos National Laboratory’s directed research and development program [Grant 20230091ER: Learning to Accelerate Global Solutions for Non-Convex Optimization]. Supplemental Material: The software that supports the findings of this study is available within the paper and its Supplemental Information ( https://pubsonline.informs.org/doi/suppl/10.1287/ijoc.2023.0236 ) as well as from the IJOC GitHub software repository ( https://github.com/INFORMSJoC/2023.0236 ). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/ .