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

1. Introduction

Transmission switching, with its inception in the 1980s (Glavitsch 1985), has gained considerable attention in both industry and academia in recent years (Hedman et al. 2008, Kocuk et al. 2017). The optimal transmission switching (OTS) problem studies how to switch on or off certain transmission lines to modify the network topology in the real-time operation of transmission power grids. Solving the OTS problem brings several benefits that the traditional optimal power flow (OPF) problem solution cannot offer, such as reducing the total operational cost, mitigating transmission congestion, clearing contingencies, and improving engineering limits (Hedman et al. 2011). Thus, as the modern transmission control and relay technologies evolve, transmission line switching has become an important option in power system operators’ toolkits.

Previous literature on OTS mainly relies on the direct current (DC) approximation of the power flow model to avoid the mathematical complexity of the nonconvex alternating current (AC) power flow equations. The first formal mathematical model for the OTS problem, proposed by Fisher et al. (2008), relies on this DC approximation. Kocuk et al. (2016b) develop a cycle-induced relaxation for a DCOTS model and characterize its convex hull.

The drawback of DCOTS approximation is that the optimal decisions may not accurately represent power flows or may even be infeasible in the AC setting (Coffrin et al. 2014). This drawback motivates the adoption of ACOTS. The ACOTS problem can be formulated as a nonconvex mixed-integer nonlinear program (MINLP), which is challenging to solve. Moreover, even in the DC setting, the OTS problem is known to be NP-hard (Lehmann et al. 2014). Several heuristics are proposed for solving the ACOTS problem, for example, by Barrows et al. (2014) and Goldis et al. (2013). Separately, convex relaxations for ACOTS have gained significant attention in recent years.

The convex relaxations of the ACOTS problem, of which the literature is quite scarce, are built upon the rich literature on ACOPF convex relaxations, such as the second order cone (SOC) relaxation (Jabr 2006), the quadratic convex (QC) relaxation (Coffrin et al. 2016), and the semidefinite programming (SDP) relaxation (Bai et al. 2008). For the ACOPF problem, both standard SDP and QC relaxations are at least as strong as the SOC relaxation, whereas the SDP and QC relaxation strengths are not directly comparable. Computationally, the SOC and QC relaxations are faster and more reliable than the SDP relaxation (Coffrin et al. 2016). In the ACOTS setting, Hijazi et al. (2017) and Bestuzheva et al. (2020) propose a QC relaxation that incorporates on/off decision variables, and it provides a tight lower bound to the generation–cost minimization objective. We further tighten this on/off version of the QC relaxation with a much stronger linearization and additional valid inequalities with some of the latter being novel.

In particular, one type of valid inequality we incorporate is cycle-based polynomial constraints (lifted cycle constraints for short). The lifted cycle constraints are first proposed by Kocuk et al. (2016a) as a relaxation to the arc-tangent constraints in ACOPF. Their work provides a reformulated SOC relaxation for ACOPF, strengthened by the McCormick relaxation of the lifted cycle constraints, and it is shown to be incomparable to the SDP relaxation. Further, these cycle-based valid inequalities are generalized for the ACOTS problem by Kocuk et al. (2017), which is derived in the rectangular coordinates. However, in our work, we develop a new type of lifted cycle constraint based on the QC relaxation of the ACOPF problem written in polar coordinates. Our method takes advantage of the direct access to auxiliary variables representing the trigonometric functions in the QC relaxation. Then, we reformulate the on/off version of those lifted cycle constraints for the ACOTS problem, which is new in the literature. In our strengthened formulation, we combine those new constraints and the lifted cycle constraints from Kocuk et al. (2017). Further, we linearize these on/off polynomial constraints with the tightest extreme-point representation, and this captures the convex hull of the on/off lifted cycle constraints for a given cycle. Because adding all constraints at the same time can make the problem challenging to solve, we derive novel cutting planes and incorporate lifted cycle constraints via a branch-and-cut scheme.

We further improve the bounds using an optimization-based bound tightening (OBBT) technique. OBBT is often used in MINLPs to tighten relaxation bounds (Nagarajan et al. 2019b). It is shown to be an effective bound-tightening method in nonlinear AC power flow models. Sundar et al. (2023) use OBBT to tighten an ACOPF-QC relaxation, whereas Bestuzheva et al. (2020) use OBBT for an ACOTS-QC relaxation with nonlinear terms linearized using weaker recursive McCormick relaxations. Additionally, Fattahi et al. (2018) employ bound-tightening methods for the simpler DCOTS model, testing them on large-scale networks. In our work, we incorporate all the proposed tightening valid inequalities and the ones from the literature within OBBT to achieve a very tight lower bound for the ACOTS problem.

Our main contributions can be summarized as follows:

1. We strengthen the ACOTS-QC relaxation with several techniques. First, we linearize the summation of two on/off trilinear terms with the tight extreme-point representation and prove such a linearization captures its convex hull. To the best of our knowledge, we are the first to develop this linearization method for ACOTS. We also reformulate several ACOPF-QC strengthening constraints for the OTS setting, some of which are novel. Compared with the state-of-the-art on/off QC relaxation formulation (Coffrin et al. 2018), our strengthened relaxation is shown to provide better lower bounds for many test cases, and some of those improvements are substantial. It can also solve several large-scale power grid library (PGLib) instances with 500 to 2,312 buses, which, to the best of our knowledge, have not been previously solved by the ACOTS-QC relaxation.

2. We derive a new lifted cycle constraint that strengthens the QC relaxations of both ACOPF and ACOTS. We linearize those constraints with the extreme-point representation, which is always tighter than the recursive McCormick relaxation in the literature. Also, to separate lifted cycle constraints with discrete decisions, we develop novel cutting planes by reformulating Benders cuts via disjunctive programming. We incorporate those cutting planes in a branch-and-cut framework, and this leads to significant solution time reductions. The lifted cycle constraints are also useful for obtaining solutions of large-scale PGLib instances.

3. We combine strengthening methods listed in (i) and (ii) with OBBT and obtain the tightest QC-based ACOTS relaxation in the literature to the best of our knowledge.

4. We propose a novel heuristic that solves a restricted ACOTS-QC model by fixing a maximum spanning tree of the network to remain switched on. This approach significantly improves computational performance on medium-scale networks, enables the solution of large-scale instances that were previously unsolved, and provides near-optimal solutions.

2. The ACOTS Problem

Before describing the model for the ACOTS problem, we first introduce some notation. Throughout, constants are typeset in boldface to make it easier to distinguish between decision variables and parameters. In the AC power flow equations, uppercase letters represent complex quantities. $\mathfrak{R}(·)$ and $\mathfrak{T}(·)$, respectively, denote the real and imaginary parts of a complex number. Given any two complex numbers (variables/constants) $z_1$ and $z_2$, the relationship $z_1⩾z_2$ implies $\mathfrak{R}(z_1)⩾\mathfrak{R}(z_2)$ and $\mathfrak{T}(z_1)⩾\mathfrak{T}(z_2)$. $|·|$ and ${(·)}^{*}$ represent the magnitude and Hermitian conjugate of a complex number, respectively. When applied on a real-valued number, $|·|$ represents its absolute value. The notation for sets, parameters, and variables is summarized in Table 1.

Table 1. Notation

The power network can be represented with the graph $G=(\mathcal{N},\mathcal{A})$, where $\mathcal{N}$ corresponds to the set of buses, whereas the set of arcs $\mathcal{A}$ corresponds to the set of lines. Note that we assume that lines in the network are directed with designated from/to buses as indicated by the data. This assumption is conventional, and it is necessary because the data contains asymmetric shunt conductance and transformers.

The ACOTS problem minimizes the total production cost of generators such that all the demands at the buses, the physical constraints (e.g., Ohm’s and Kirchoff’s law), and engineering limit constraints (e.g., transmission line flow limits) are satisfied. In this work, for the purpose of the QC relaxation (see Section 3), we model the AC power flow equations in polar coordinates (Taylor 2015) and, thus, the following ACOTS formulation:

where $z_{\{ft|(f,t)\in \mathcal{A},f=i \text{or} \text{t}=\text{i}\}}$ is the switch on/off variable for a line having either end connected to a leaf node with zero load. When such a line is switched off, the generators on the leaf node are disconnected from the network, and thus, we do not need to pay the fixed cost $c_{0k}$.

The convex quadratic objective (1a) minimizes total generator dispatch cost. Constraints (1b) correspond to the power balance at each bus, that is, Kirchoff’s current law. Constraints (1c)–(1f) model the power flow on each line. Note that Constraints (1c) and (1d) ensure that the power flow over line $(i,j)$ is zero if the line is switched off; Constraints (1f) ensure that $W_{ij}=0$ when line $(i,j)$ is switched off. Constraints (1g) connect voltage angle and voltage difference variables.

Constraints (1h) limit the phase angle difference on each line. We define ${\mathit{\theta }}_{ij}^{\mathbf{u}}=\max (|{\underset{¯}{\mathit{\theta }}}_{ij}|,|{\overline{\mathit{\theta }}}_{ij}|)$. Let ${\mathit{\theta }}_{ij,k}^{\mathit{u},\max }$ be the kth largest value in $\{{\mathit{\theta }}_{ij}^{\mathbf{u}}|(i,j)\in \mathcal{A}\}$ and ${\mathit{\theta }}^{\mathbf{M}}={\sum }_{k=1}^{|\mathcal{N}|-1}{\mathit{\theta }}_{ij,k}^{\mathit{u},\max }$ be a big-M constant for phase angle difference. This big-M constant enables us to provide proper bounds for ${\theta }_{ij}$ in Constraints (1h).

Constraints (1i) set the voltage angles of reference buses to zero. Constraints (1j) restrict the apparent power output of each generator. Constraints (1k) are thermal limit constraints that restrict the total electric power transmitted on each line. Note that, in these constraints, a squared form of $z_{ij}$ is used instead of the linear form as it produces a tighter formulation (Hijazi et al. 2017). Constraints (1l) limit the voltage magnitude at each bus.

This ACOTS model is a nonconvex MINLP, and it contains nonlinear Constraints (1c) through (1f). An easy method to linearize Constraints (1c) and (1d) is to introduce a lifted variable $w_{ij}^z$ per line, and this equals $w_i$ when $z_{ij}=1$ and 0 otherwise; then, Constraints (1c) and (1d) can be replaced with the following linear constraints for every line $(i,j)\in \mathcal{A}$:

Constraints (2a)–(2d) are from Hijazi et al. (2017), whereas Constraints (2e) and (2f) are new and provide tighter bounds for $w_{ij}^z$ and $w_{ji}^z$. Tractable convex relaxations for Constraints (1e) and (1f) are described in the next section.

3. On/Off Quadratic Convex Relaxation

The on/off version of the QC relaxation for the ACOTS model relaxes nonlinear Constraints (1e) and (1f). Let $w_{ij}^R≔\mathfrak{R}(W_{ij})$ and $w_{ij}^I≔\mathfrak{T}(W_{ij})$; then, (1f) can be equivalently written as follows $(\forall (i,j)\in \mathcal{A})$:

A key feature of the QC relaxation is the use of polar coordinates, and this has direct access to voltage magnitude $v_i$ and voltage angle ${\theta }_i$ variables. This enables stronger links between voltage variables. In what follows, we list the QC relaxation constraints, some of which are based on previous works (Coffrin et al. 2016, Hijazi et al. 2017), whereas others are newly derived, and we specify.

1. Quadratic function relaxation ($\forall i\in \mathcal{N}$): We can formulate the convex-hull envelope for Constraints (1e) by relaxing every equality to a quadratic inequality Constraint (4a) as is done in (Hijazi et al. 2017) and providing upper bounds via linear McCormick relaxation constraints in (4b):

   $$w_i⩾v_i^2,$$(4a)
   $$w_i⩽({\underset{¯}{\mathit{v}}}_i+{\overline{\mathit{v}}}_i)v_i-{\underset{¯}{\mathit{v}}}_i{\overline{\mathit{v}}}_i.$$(4b)

2. Cosine and sine function relaxations $(\forall (i,j)\in \mathcal{A})$: The trigonometric term $\cos ({\theta }_{ij})$ in (3a) is nonconvex. We define a lifted variable $c_{ij}$ that captures the convex envelope of $\cos ({\theta }_{ij})$. We assume ${\mathit{\theta }}_{ij}^{\mathbf{u}}⩽\pi /2$, which is reasonable as the absolute value of the phase angle differences across the lines is usually under 15° in practice (Purchala et al. 2005). We define the following constants for every line $(i,j)\in \mathcal{A}$, and these are necessary for the relaxation constraints:

   $${\mathit{\theta }}_{ij}^{\mathit{c}}=\frac{\cos ({\overline{\mathit{\theta }}}_{ij})-\cos ({\underset{¯}{\mathit{\theta }}}_{ij})}{{\overline{\mathit{\theta }}}_{ij}-{\underset{¯}{\mathit{\theta }}}_{ij}},\hspace{1em}{\mathit{\theta }}_{ij}^{\mathit{s}}=\frac{\sin ({\overline{\mathit{\theta }}}_{ij})-\sin ({\underset{¯}{\mathit{\theta }}}_{ij})}{{\overline{\mathit{\theta }}}_{ij}-{\underset{¯}{\mathit{\theta }}}_{ij}}.$$

   Following the disjunctive programming method in Hijazi et al. (2017), an on/off version of the convex relaxation of the cosine function is as follows:

   $$-c_{ij}+{\mathit{\theta }}_{ij}^{\mathit{c}}{\theta }_{ij}⩽({\mathit{\theta }}_{ij}^{\mathit{c}}{\underset{¯}{\mathit{\theta }}}_{ij}-\cos ({\underset{¯}{\mathit{\theta }}}_{ij}))z_{ij}+|{\mathit{\theta }}_{ij}^{\mathit{c}}|{\mathit{\theta }}^{\mathbf{M}}(1-z_{ij}),$$(5a)
   $$c_{ij}⩽z_{ij}-\frac{1-\cos ({\mathit{\theta }}_{ij}^{\mathbf{u}})}{{({\mathit{\theta }}_{ij}^{\mathbf{u}})}^2}{\theta }_{ij}^2+\frac{1-\cos ({\mathit{\theta }}_{ij}^{\mathbf{u}})}{{({\mathit{\theta }}_{ij}^{\mathbf{u}})}^2}{({\mathit{\theta }}^{\mathbf{M}})}^2(1-z_{ij}),$$(5b)
   $${\underset{¯}{\mathit{c}}}_{ij}{z}_{ij}⩽c_{ij}⩽{\overline{\mathit{c}}}_{ij}{z}_{ij}.$$(5c)

   Constraints (5a) and (5b) are big-M constraints. When $z_{ij}=1$, they represent quadratic convex relaxations of $\mathit{\text{cos}}({\theta }_{ij})$ derived from trigonometric identities and properties of quadratic functions, and those convex relaxations are not valid when the line $(i,j)$ is switched off as we have $c_{ij}=0$. Therefore, big-M parameter ${\mathit{\theta }}^{\mathbf{M}}$ is used to ensure that, when $z_{ij}=0$, those constraints are valid for $c_{ij}=0$ and ${\theta }_{ij}\in [{\underset{¯}{\mathit{\theta }}}_{ij},{\overline{\mathit{\theta }}}_{ij}]$. Constraint (5c) provides bounds for $c_{ij}$ and ensures that $c_{ij}=0$ when the line $(i,j)$ is switched off. Note that Constraint (5a) is a new constraint that is not in Hijazi et al. (2017) or Bestuzheva et al. (2020).

   Similarly, we define a lifted variable $s_{ij}$ that captures the convex envelope of $\sin ({\theta }_{ij})$. When ${\mathit{\theta }}_{ij}^{\mathbf{u}}⩽\pi /2$, a disjunctive relaxation of the sine function is as follows:

   $$s_{ij}-\cos \left(\frac{{\mathit{\theta }}_{ij}^{\mathbf{u}}}{2}\right){\theta }_{ij}⩽\left(\sin \left(\frac{{\mathit{\theta }}_{ij}^{\mathbf{u}}}{2}\right)-\cos \left(\frac{{\mathit{\theta }}_{ij}^{\mathbf{u}}}{2}\right)\frac{{\mathit{\theta }}_{ij}^{\mathbf{u}}}{2}\right)z_{ij}+\cos \left(\frac{{\mathit{\theta }}_{ij}^{\mathbf{u}}}{2}\right){\mathit{\theta }}^{\mathbf{M}}(1-z_{ij}), \text{if} {\overline{\mathit{\theta }}}_{\text{ij}}⩾0,$$(6a)
   $$-s_{ij}+\cos \left(\frac{{\mathit{\theta }}_{ij}^{\mathbf{u}}}{2}\right){\theta }_{ij}⩽\left(\sin \left(\frac{{\mathit{\theta }}_{ij}^{\mathbf{u}}}{2}\right)-\cos \left(\frac{{\mathit{\theta }}_{ij}^{\mathbf{u}}}{2}\right)\frac{{\mathit{\theta }}_{ij}^{\mathbf{u}}}{2}\right)z_{ij}+\cos \left(\frac{{\mathit{\theta }}_{ij}^{\mathbf{u}}}{2}\right){\mathit{\theta }}^{\mathbf{M}}(1-z_{ij}), \text{if} {\underset{¯}{\mathit{\theta }}}_{\text{ij}}⩽0,$$(6b)
   $$s_{ij}-{\mathit{\theta }}_{ij}^{\mathit{s}}{\theta }_{ij}⩽(-{\mathit{\theta }}_{ij}^{\mathit{s}}{\underset{¯}{\mathit{\theta }}}_{ij}+\sin ({\underset{¯}{\mathit{\theta }}}_{ij}))z_{ij}+{\mathit{\theta }}_{ij}^{\mathit{s}}{\mathit{\theta }}^{\mathbf{M}}(1-z_{ij}), \text{if} {\overline{\mathit{\theta }}}_{\text{ij}}⩽0,$$(6c)
   $$-s_{ij}+{\mathit{\theta }}_{ij}^{\mathit{s}}{\theta }_{ij}⩽({\mathit{\theta }}_{ij}^{\mathit{s}}{\underset{¯}{\mathit{\theta }}}_{ij}-\sin ({\underset{¯}{\mathit{\theta }}}_{ij}))z_{ij}+{\mathit{\theta }}_{ij}^{\mathit{s}}{\mathit{\theta }}^{\mathbf{M}}(1-z_{ij}), \text{if} {\underset{¯}{\mathit{\theta }}}_{\text{ij}}⩾0,$$(6d)
   $${\underset{¯}{\mathit{s}}}_{ij}{z}_{ij}⩽s_{ij}⩽{\overline{\mathit{s}}}_{ij}{z}_{ij},$$(6e)
   where Constraints (6a)–(6d) are derived from the linear outer approximation of the $\sin ({\theta }_{ij})$ function (Hijazi et al. 2017).

3. Extreme-point representation for summation of on/off trilinear terms $(\forall (i,j)\in \mathcal{A})$: Next, we develop a novel extreme-point representation to linearize the sum of two on/off trilinear terms and theoretically prove its tightness. We first substitute the nonconvex functions $\cos ({\theta }_{ij})$ and $\sin ({\theta }_{ij})$ in Constraints (3) with lifted variables $c_{ij}$ and $s_{ij}$ and their convex envelopes, respectively. The remaining nonlinearities reduce to trilinear terms $v_i{v}_j{c}_{ij}$ and $v_i{v}_j{s}_{ij}$, which are further controlled by the status of the on/off variable $z_{ij}$. To linearize these terms, we generalize the convex hull representation of the extreme-point formulation (Lu et al. 2018) to incorporate on/off variables as discussed below.

Let the extreme points of the domain $[{\underset{¯}{\mathit{v}}}_i,{\overline{\mathit{v}}}_i]\times [{\underset{¯}{\mathit{v}}}_j,{\overline{\mathit{v}}}_j]\times [{\underset{¯}{\mathit{c}}}_{ij},{\overline{\mathit{c}}}_{ij}]$ be denoted by ${\mathit{\xi }}^k$ with $k=1,\dots ,8$ and the extreme points of the domain $[{\underset{¯}{\mathit{v}}}_i,{\overline{\mathit{v}}}_i]\times [{\underset{¯}{\mathit{v}}}_j,{\overline{\mathit{v}}}_j]\times [{\underset{¯}{\mathit{s}}}_{ij},{\overline{\mathit{s}}}_{ij}]$ be denoted by ${\mathit{\gamma }}^k,k=1,\dots ,8$. We relax Constraints (3) as follows:

where ${\mathit{\xi }}_1^k$ is the value of $v_i$ in the extreme point ${\mathit{\xi }}^k$. The constants ${\mathit{\xi }}_2^k$, ${\mathit{\xi }}_3^k$, ${\mathit{\gamma }}_1^k$, ${\mathit{\gamma }}_2^k$, and ${\mathit{\gamma }}_3^k$ are similarly defined. ${\lambda }_{ij,k}^c$ and ${\lambda }_{ij,k}^s$ are auxiliary multiplier variables for representing a linear combination of the extreme points. When $z_{ij}=1$, Constraints (7a) connect values of $w_{ij}^R$ and $w_{ij}^I$ with convex combinations of extreme points for trilinear terms; Constraints (7b)–(7f) equate the values of $v_i$, $v_j$, $c_{ij}$, and $s_{ij}$ to convex combinations of their respective extreme points in $[{\underset{¯}{\mathit{v}}}_i,{\overline{\mathit{v}}}_i]\times [{\underset{¯}{\mathit{v}}}_j,{\overline{\mathit{v}}}_j]\times [{\underset{¯}{\mathit{c}}}_{ij},{\overline{\mathit{c}}}_{ij}]$. When $z_{ij}=0$, Constraints (7a)–(7f) enforce $w_{ij}^R=w_{ij}^I=c_{ij}=s_{ij}=0$ and impose no constraints on $v_i$ and $v_j$. Constraints (7g) ensure that the summations of convex combination coefficients equal to one when line $(i,j)$ is switched on, and all the coefficients become zero when the line is switched off. Linking Constraints (7h) connect the shared bilinear term $v_i{v}_j$ that appears in both trilinear terms $v_i{v}_j\cos ({\theta }_{ij})$ and $v_i{v}_j\sin ({\theta }_{ij})$.

Note that, when $z_{ij}=1$, Constraints (7b)–(7e) and (7g) reduce to the following constraints:

We next formally show that Constraints (7) form the tightest, or the convex hull, relaxation for the summation of nonlinear terms of the form

Note that this form appears in Constraints (1c) and (1d), where ${\mathit{a}}_1$ and ${\mathit{a}}_2$ represent coefficients that are functions of ${\mathit{g}}_{ij}$, ${\mathit{b}}_{ij}$, ${\mathit{t}}_{ij}^R$, and ${\mathit{t}}_{ij}^I$. For this purpose, we define the following: let $\eta =$ $(w_{ij}^R,$ $w_{ij}^I,$ $c_{ij},$ $s_{ij},$ ${\lambda }_{ij,1}^c,$ $\dots ,$ ${\lambda }_{ij,8}^c,$ ${\lambda }_{ij,1}^s,$ $\dots ,$ ${\lambda }_{ij,8}^s,$ $z_{ij},$ $v_i,$ $v_j)$ and define the set $H=\{\eta |\eta \text{satisfies} (7),z_{ij}\in [0,1]\}$. When $z_{ij}=0$ and $z_{ij}=1$, H becomes $H^0$ and $H^1$, respectively:

Sundar et al. (2023) show, for a simpler case in which $z_{ij}=1$, that the linearization defined by $H^1$ is the convex hull of the summation terms in (9) because of the addition of equality Constraints (7h). However, to understand the tightness (convex hull property) of the linearization (7) for the generalized ACOTS model, we present the following theorem, based on the literature of perspective formulations for disjunctive programming (Ceria and Soares 1999, Nagarajan et al. 2019a):

Theorem 1.

The set $H=\text{conv}(H^0\cup H^1)$.

Proof.

First, we prove that $\text{conv}(H^0\cup H^1)\subseteq H$. For any ${\eta }^0\in H^0$, ${\eta }^0$ satisfies constraints in (7) when $z_{ij}=0$. Similarly, for any ${\eta }^1\in H^1$, ${\eta }^1$ satisfies constraints in (7) when $z_{ij}=1$. Thus, $H^0\cup H^1\subseteq H$. Because H contains only linear constraints and is, thus, convex, we have $\text{conv}(H^0\cup H^1)\subseteq H$.

Next, we prove that $H\subseteq \text{conv}(H^0\cup H^1)$. Let ${\eta }^{*}\in H$. If $z_{ij}^{*}=0$, then ${\eta }^{*}\in H^0$, and if $z_{ij}^{*}=1$, then ${\eta }^{*}\in H^1$. When $z_{ij}^{*}\in (0,1)$, we define the following variables:

$$\begin{array}{l}{\eta }_0^{*}=\left(0,0,\dots ,0,\frac{v_i^{*}-\sum _{k=1}^8{\lambda }_{ij,k}^{c*}{\mathit{\xi }}_1^k}{1-z_{ij}^{*}},\frac{v_j^{*}-\sum _{k=1}^8{\lambda }_{ij,k}^{c*}{\mathit{\xi }}_2^k}{1-z_{ij}^{*}}\right)\\ {\eta }_1^{*}=(\frac{w_{ij}^{R*}}{z_{ij}^{*}},\frac{w_{ij}^{I*}}{z_{ij}^{*}},\frac{c_{ij}^{*}}{z_{ij}^{*}},\frac{s_{ij}^{*}}{z_{ij}^{*}},\frac{{\lambda }_{ij,1}^{c*}}{z_{ij}^{*}},\dots ,\frac{{\lambda }_{ij,8}^{c*}}{z_{ij}^{*}},\frac{{\lambda }_{ij,1}^{s*}}{z_{ij}^{*}},\dots ,\frac{{\lambda }_{ij,8}^{s*}}{z_{ij}^{*}},1,{\displaystyle \sum _{k=1}^8\frac{{\lambda }_{ij,k}^{c*}}{z_{ij}^{*}}}{\mathit{\xi }}_1^k,{\displaystyle \sum _{k=1}^8\frac{{\lambda }_{ij,k}^{c*}}{z_{ij}^{*}}}{\mathit{\xi }}_2^k)\end{array}.$$

Next, we prove that ${\eta }_0^{*}\in H^0$ and ${\eta }_1^{*}\in H^1$. Because of (7b), we have $(1-z_{ij}^{*}){\underset{¯}{\mathit{v}}}_i⩽v_j^{*}-{\sum }_{k=1}^8{\lambda }_{ij,k}^{c*}{\mathit{\xi }}_2^k⩽(1-z_{ij}^{*}){\overline{\mathit{v}}}_i$. Thus, ${(v}_i^{*}-{\sum }_{k=1}^8{\lambda }_{ij,k}^{c*}{\mathit{\xi }}_1^k)/(1-z_{ij}^{*})\in [{\underset{¯}{\mathit{v}}}_i,{\overline{\mathit{v}}}_i]$. Similarly, $(v_j^{*}-{\sum }_{k=1}^8{\lambda }_{ij,k}^{c*}{\mathit{\xi }}_2^k)/(1-z_{ij}^{*})\in [{\underset{¯}{\mathit{v}}}_j,{\overline{\mathit{v}}}_j]$. Therefore, ${\eta }_0^{*}\in H^0$.

For ${\eta }_1^{*}$, $\frac{w_{ij}^{R*}}{z_{ij}^{*}}={\sum }_{k=1}^8\frac{{\lambda }_{ij,1}^{c*}}{z_{ij}^{*}}({\mathit{\xi }}_1^k,{\mathit{\xi }}_2^k,{\mathit{\xi }}_3^k)$ because $w_{ij}^{R*}={\sum }_{k=1}^8{\lambda }_{ij,1}^{c*}({\mathit{\xi }}_1^k,{\mathit{\xi }}_2^k,{\mathit{\xi }}_3^k)$ and $z_{ij}^{*}\in (0,1)$. Similarly, it can be proved that ${\eta }_1^{*}$ satisfies Constraints (7a), (7f), (7h), and (8c). For Constraint (8a), the first equation follows directly from the definition of ${\eta }_1^{*}$, and the second equality is correct because the validity of (7b) and (7c) for ${\eta }^{*}$ indicates that ${\sum }_{k=1}^8{\lambda }_{ij,k}^{s*}{\mathit{\gamma }}_1^k+(1-z_{ij}^{*}){\underset{¯}{\mathit{v}}}_i⩽{\sum }_{k=1}^8{\lambda }_{ij,k}^{c*}{\mathit{\xi }}_1^k+(1-z_{ij}^{*}){\underset{¯}{\mathit{v}}}_i$ and ${\sum }_{k=1}^8{\lambda }_{ij,k}^{s*}{\mathit{\gamma }}_1^k+(1-z_{ij}^{*}){\overline{\mathit{v}}}_i\ge {\sum }_{k=1}^8{\lambda }_{ij,k}^{c*}{\mathit{\xi }}_1^k+(1-z_{ij}^{*}){\overline{\mathit{v}}}_i$; thus, ${\sum }_{k=1}^8{\lambda }_{ij,k}^{c*}{\mathit{\xi }}_1^k={\sum }_{k=1}^8{\lambda }_{ij,k}^{s*}{\mathit{\gamma }}_1^k\Rightarrow {\sum }_{k=1}^8({\lambda }_{ij,k}^{c*}{/z}_{ij}^{*}){\mathit{\xi }}_1^k={\sum }_{k=1}^8({\lambda }_{ij,k}^{s*}{/z}_{ij}^{*}){\mathit{\gamma }}_1^k$, which means ${\eta }_1^{*}$ satisfies the second equality in (8a). With similar arguments, ${\eta }_1^{*}$ is also feasible for (8b). Therefore, ${\eta }_1^{*}\in H^1$.

Now, note that ${\eta }^{*}=(1-z_{ij}^{*}){\eta }_0^{*}+z_{ij}^{*}{\eta }_1^{*}$, which means $H\subseteq \text{conv}(H^0\cup H^1)$. □

To the best of our knowledge, this is the first attempt at applying the convex hull–based extreme-point formulation for the ACOTS QC relaxation. Previous works (Hijazi et al. 2017, Lu et al. 2017, Bestuzheva et al. 2020) utilize recursive McCormick-based relaxations, which are not as tight as the above formulation, as the former relaxation when applied to (9) is not as tight as $H^1$.

1. Other valid constraints for strengthening the on/off QC relaxation $(\forall (i,j)\in \mathcal{A})$: We also add the following constraints to strengthen the on/off QC relaxation:

   $$\begin{array}{l}\tan ({\underset{¯}{\mathit{\theta }}}_{ij})w_{ij}^R⩽w_{ij}^I⩽\tan ({\overline{\mathit{\theta }}}_{ij})w_{ij}^R\hfill \end{array},$$(10a)
   $$\begin{array}{l}{\mathit{v}}_i^{\sigma }{\mathit{v}}_j^{\sigma }(\cos ({\mathit{\varphi }}_{ij})w_{ij}^R+\sin ({\mathit{\varphi }}_{ij})w_{ij}^I)-{\overline{\mathit{v}}}_j\cos ({\mathit{\delta }}_{ij}){\mathit{v}}_i^{\sigma }{w}_{ij}^z\\ -{\overline{\mathit{v}}}_i\cos ({\mathit{\delta }}_{ij}){\mathit{v}}_i^{\sigma }{w}_{ji}^z\ge {\overline{\mathit{v}}}_i{\overline{\mathit{v}}}_j\cos ({\mathit{\delta }}_{ij})({\underset{¯}{\mathit{v}}}_i{\underset{¯}{\mathit{v}}}_j-{\overline{\mathit{v}}}_i{\overline{\mathit{v}}}_j)z_{ij},\end{array}$$(10b)
   $$\begin{array}{l}{\mathit{v}}_i^{\sigma }{\mathit{v}}_j^{\sigma }(\cos ({\mathit{\varphi }}_{ij})w_{ij}^R+\sin ({\mathit{\varphi }}_{ij})w_{ij}^I)-{\underset{¯}{\mathit{v}}}_j\cos ({\mathit{\delta }}_{ij}){\mathit{v}}_i^{\sigma }{w}_{ij}^z\\ -{\underset{¯}{\mathit{v}}}_i\cos ({\mathit{\delta }}_{ij}){\mathit{v}}_i^{\sigma }{w}_{ji}^z\ge {\underset{¯}{\mathit{v}}}_i{\underset{¯}{\mathit{v}}}_j\cos ({\mathit{\delta }}_{ij})({\overline{\mathit{v}}}_i{\overline{\mathit{v}}}_j-{\underset{¯}{\mathit{v}}}_i{\underset{¯}{\mathit{v}}}_j)z_{ij},\end{array}$$(10c)
   $$|S_{ij}{|}^2⩽\frac{w_i}{|{\mathit{T}}_{ij}{|}^2}{l}_{ij},$$(10d)
   $$\begin{array}{l}{l}_{ij}=|{\mathit{Y}}_{ij}{|}^2\left(\frac{w_{ij}^z}{|{\mathit{T}}_{ij}{|}^2}+w_{ji}^z-2({\mathit{t}}_{ij}^R{w}_{ij}^R+{\mathit{t}}_{ij}^I{w}_{ij}^I)/|{\mathit{T}}_{ij}{|}^2\right)\\ -\frac{|{\mathit{Y}}_{ij}^c{|}^2}{|{\mathit{T}}_{ij}{|}^2}{w}_{ij}^z+2({\mathit{g}}_{ij}^c{p}_{ij}-{\mathit{b}}_{ij}^c{q}_{ij}),\end{array}$$(10e)
   $$0⩽l_{ij}⩽{\overline{\mathit{l}}}_{ij}{z}_{ij},$$(10f)

where ${\mathit{v}}_i^{\sigma }={\underset{¯}{\mathit{v}}}_i+{\overline{\mathit{v}}}_i$, ${\mathit{\varphi }}_{ij}=({\overline{\mathit{\theta }}}_{ij}+{\underset{¯}{\mathit{\theta }}}_{ij})/2$, ${\mathit{\delta }}_{ij}=({\overline{\mathit{\theta }}}_{ij}-{\underset{¯}{\mathit{\theta }}}_{ij})/2$, and ${\overline{\mathit{l}}}_{ij}={|{\mathit{T}}_{ij}|}^2{\left({\overline{\mathit{s}}}_{ij}^a\right)}^2/{\underset{¯}{\mathit{v}}}_i^2$. Constraint (10a) is the phase angle difference constraint, which is a relaxation of the equality $\tan ({\mathit{\theta }}_{ij})=w_{ij}^R/w_{ij}^I$. Constraints (10b) and (10c) are the lifted nonlinear cuts from Bestuzheva et al. (2020), derived using trigonometric identities. Constraints (10d) and (10e) use the relationship between current magnitude and power flow to tighten the QC relaxation. Constraint (10f) bounds the squared current magnitude. Note that, whereas (10a), (10d), and (10f) are the same as their counterparts in the ACOPF model, they are still valid for the ACOTS setting. On the other hand, (10b), (10c), and (10e) are modified under the ACOTS case so that, when line $(i,j)$ is switched off, Constraints (10b) and (10c) become redundant, whereas Constraints (10e) and (10f) ensure that $l_{ij}$ goes to zero. The use of (10e) is new for the ACOTS QC relaxation.

Putting all the constraints together, we obtain the following QC relaxation for the ACOTS problem:

The relationship between the solution sets of different formulations is simplified and shown in Figure 1. Here, ACOPF is the nonconvex polar formulation, which is equivalent to the ACOTS model with all the lines switched on; ACOPF-QC is the QC relaxation for ACOPF from Coffrin et al. (2016).

Tight convex relaxations for ACOTS such as (ACOTS-QC) can serve several purposes. The solution to a tight relaxation problem is a good approximation for optimal ACOTS decisions. Also, they provide tight lower bounds for evaluating the quality of a feasible ACOTS solution and can be used to prove the global optimality of a feasible solution when the optimality gap is zero. In addition, the convex relaxation can be used in a two-stage process for minimizing the cost of ACOPF, in which we first change the network topology using line-switching solutions from the relaxation and then solve the ACOPF problem on the updated network. In what follows, we show how to further tighten (ACOTS-QC) with lifted cycle constraints and OBBT.

4. Cycle-Based On/Off Polynomial Constraints

In this section, we present a novel type of lifted cycle constraints based on lifted trigonometric auxiliary variables $c_{ij}$ and $s_{ij}$. We use both these new lifted cycle constraints and lifted cycle constraints with voltage product variables $w_{ij}^R$, $w_{ij}^I$, and $w_i$ from Kocuk et al. (2016a) to strengthen the on/off QC relaxation for ACOTS. Because those constraints are polynomial functions in multilinear terms, we linearize them with the extreme-point representation. We also develop novel cutting planes to incorporate those constraints more efficiently via a branch-and-cut framework.

4.1. Formulating Lifted Cycle Constraints

The lifted cycle constraints are formulated based on the fact that, for any given cycle $\mathcal{C}$ in the transmission network, the voltage angle differences of all lines in $\mathcal{C}$ sum up to zero. More formally, let $({\widehat{v}}_1,{\widehat{v}}_2,\dots ,{\widehat{v}}_n,{\widehat{v}}_1)$ be a vertex sequence for the cycle $\mathcal{C}$ of length n and let the cycle be represented by its lines: $\mathcal{C}=\{({\widehat{v}}_1,{\widehat{v}}_2),({\widehat{v}}_2,{\widehat{v}}_3),\dots ,({\widehat{v}}_n,{\widehat{v}}_1)\}$; then, we have ${\sum }_{(i,j)\in \mathcal{C}}{\theta }_{ij}=0$.

The method we use to derive lifted cycle constraints for the QC relaxation is similar to that of Kocuk et al. (2016a) in which lifted cycle constraints for the SOC relaxation are derived. However, unlike in the SOC relaxation, the main advantage of the QC relaxation is that we have direct access to both $(c_{ij}$, $s_{ij})$ and $(w_{ij}^R,w_{ij}^I)$ variables, enabling us to formulate additional lifted cycle constraints that could further enhance the relaxation quality.

In what follows, we derive lifted cycle constraints for cycles with three and four nodes. We call the resulting constraints three-cycle constraints and four-cycle constraints, respectively. We first develop those constraints without considering switching (on/off) decisions and then demonstrate how to reformulate them to include those decisions using a tight big-M formulation.

4.1.1. Three-Cycle Constraints.

For a cycle of three nodes i, j, and k, we have ${\theta }_{ij}+{\theta }_{jk}+{\theta }_{ki}=0$ or, equivalently, ${\theta }_{ik}={\theta }_{ij}+{\theta }_{jk}$, which indicates that $\cos ({\theta }_{ik})=\cos ({\theta }_{ij}+{\theta }_{jk})$ and $\sin ({\theta }_{ik})=\sin ({\theta }_{ij}+{\theta }_{jk})$. Expanding the right-hand sides and replacing the trigonometric functions with their corresponding lifted variables, we get the following nonlinear three-cycle constraints:

where, though simple, these are novel and applicable to both ACOPF and ACOTS problems. We can then obtain the lifted cycle constraints in Kocuk et al. (2016a) by multiplying both sides of (12a) and (12b) with $v_i{v}_j^2{v}_k$ and using the relationships in (1e) and (3) (ignoring switching decisions in (3) for now):

Alternatively, Constraints (13) can also be derived from minor-based reformulation as in Kocuk et al. (2018).

For brevity, in the following, we call lifted cycle constraints with $c_{ij}$ and $s_{ij}$ variables lifted cycle constraints in the c–s space and lifted cycle constraints with $w_{ij}^R$, $w_{ij}^I$, and $w_i$ variables lifted cycle constraints in the w space.

We also derive two more sets of lifted cycle constraints by considering other permutations of the equality ${\theta }_{ij}+{\theta }_{jk}+{\theta }_{ki}=0$, including ${\theta }_{jk}+{\theta }_{ki}={\theta }_{ji}$ and ${\theta }_{ki}+{\theta }_{ij}={\theta }_{kj}$. Though they look equivalent in the nonlinear forms, the linearized versions (see Section 4.2) of these permutated constraints do not necessarily dominate one another, and we add all of them to tighten the relaxation.

Another type of lifted cycle constraint can be derived from the equality ${\theta }_{ij}+{\theta }_{jk}-{\theta }_{ik}=0$, which leads to the following constraints in the c–s space:

The following proposition shows the equivalence between Constraints (12) and (14). This proposition is similar to proposition 4.1 in Kocuk et al. (2016a), but our result is in the c–s space rather than the w space, and we simplify the presentation of the result. Also, we provide a new way to prove this result.

Proposition 1.

For all $(i,j)\in \mathcal{A}$, if $c_{ij}$ and $s_{ij}$ satisfy $c_{ij}^2+s_{ij}^2=1$, then $\{(c,s):(12) \text{holds}\}=\{(c,s):(14) \text{holds}\}$.

Proof.

We first prove that $\{(c,s):(12) \text{holds}\}\subseteq \{(c,s):(14) \text{holds}\}$. If the variables c and s satisfy (12a) and (12b), we multiply both sides of (12a) with $c_{ik}$ and both sides of (12b) with $s_{ik}$ and then sum up those two equations:

$$c_{ik}^2+s_{ik}^2=c_{ik}{c}_{ij}{c}_{jk}-c_{ik}{s}_{ij}{s}_{jk}+s_{ik}{c}_{ij}{s}_{jk}+s_{ik}{s}_{ij}{c}_{jk}.$$

Because the left-hand side is equal to one, this equation is equivalent to Constraint (14a). Similarly, we obtain Constraint (14b) by multiplying both sides of (12a) with $s_{ik}$ and both sides of (12b) with $c_{ik}$ and deduct the second equation from the first.

For the reverse direction, if c and s satisfy (14), let $a=c_{ij}{c}_{jk}-s_{ij}{s}_{jk}$ and $b=c_{ij}{s}_{jk}+s_{ij}{c}_{jk}$, and we can rewrite (14a) and (14b) as $c_{ik}a+s_{ik}b=1$ and $c_{ik}b-s_{ik}a=0$, respectively. Solving for a and b, we get $a=c_{ik}$ and $b=s_{ik}$, which are equivalent to Constraints (12a) and (12b). □

4.1.2. Four-Cycle Constraints.

For a four-cycle with nodes $\{i,j,k,l\}$, we similarly derive lifted cycle constraints based on the equality ${\theta }_{ij}+{\theta }_{jk}+{\theta }_{kl}+{\theta }_{li}=0$. More specifically, for the permutation ${\theta }_{ij}+{\theta }_{kl}={\theta }_{il}-{\theta }_{jk}$, we derive the following lifted cycle constraints:

For the other two permutations, that is, ${\theta }_{ij}+{\theta }_{jk}={\theta }_{il}-{\theta }_{kl}$ and ${\theta }_{jk}+{\theta }_{kl}={\theta }_{il}-{\theta }_{ij}$, we can derive similar lifted cycle constraints. Note that, for those permutations, the lifted cycle constraints in the w space contain trilinear terms; thus, we do not include those constraints in our implementation for efficiency purposes.

4.1.3. On/Off Cycle Constraints for ACOTS.

To reformulate lifted cycle constraints for ACOTS and include switching decisions, we use the big-M formulation. As an example, we demonstrate the formulation on Constraints (12), that is, the three-cycle constraints in the c–s space. Constraints (12) are only valid when all lines in the three-cycle $\mathcal{C}$ are switched on, which is ensured by the following big-M constraints:

Here, $\widehat{z}={\sum }_{(l,m)\in \mathcal{C}}(1-z_{lm})$ and we use “3” as the big-M constant. It is valid because $c_{ij}\in [0,1]$ and $s_{ij}\in [-1,1]$ for the worst case bounds of ${\theta }_{ij}\in [-\pi /2,\pi /2]$ although this could be further improved if the angle-difference bounds are tighter. We also include similar on/off constraints for all four-cycles with appropriate big-M constants.

4.2. Extreme-Point Representation

The lifted cycle constraints contain bilinear terms, which are usually linearized with McCormick relaxation in the literature (Kocuk et al. 2016b, 2018). We instead use the extreme-point representation to linearize those constraints, which is guaranteed to capture the convex hull of the lifted cycle constraints for a given cycle (including all permutations in the c–s or w space).

For example, let $x_i^{\mathbf{c}}\hspace{0.17em}\forall i=1,\dots ,6$ represent variables $c_{ij},c_{jk},c_{ik},s_{ij},s_{jk},s_{ik}$, respectively. We first rewrite three-cycle Constraints (12) and their counterparts by permutation as follows:

Let binary variable $y_{\mathcal{C}}$ equal one if and only if all lines in the cycle $\mathcal{C}=\{(i,j),(j,k),(k,i)\}$ are switched on. $x_{j_1{j}_2}^{\mathbf{c}}$ is a lifted variable for $x_{j_1}^{\mathbf{c}}{x}_{j_2}^{\mathbf{c}}$. We can linearize the constraint $x_3^{\mathbf{c}}=x_1^{\mathbf{c}}{x}_2^{\mathbf{c}}-x_4^{\mathbf{c}}{x}_5^{\mathbf{c}}$ and connect the constraint with line-switching decisions as follows:

We explain this constraint in more detail at the end of this section after introducing Constraints (19). Other constraints in (17) can be linearized in a similar way.

In addition to the linearization above, we have the following constraints in the extreme-point representation for Constraints (17) (with switching decisions added):

where ${\lambda }_i^{cs}$ is an auxiliary variable. $\mathcal{P}=$ {(1,2), (1,3), (1,5), (1,6), (2,3), (2,4), (2,6), (3,4), (3,5), (4,5), (4,6), (5,6)}. $\mathcal{X}$ can be viewed as a matrix of size $2^6\times 6$ such that every row represents all possible combinations of the lower and upper bounds of variables $x_j^{\mathbf{c}}\in [{\underset{¯}{\mathit{x}}}_j^{\mathbf{c}},{\overline{\mathit{x}}}_j^{\mathbf{c}}]\hspace{0.17em}\forall j=1,\dots ,6$. Constraints (19a) and (19b) set bounds for auxiliary multiplier variables. When $y_{\mathcal{C}}=1$, Constraints (19c)–(19e) represent the convex hull consisting of variables $x_j^{\mathbf{c}} (\forall j)$ and $x_{j_1{j}_2}^{\mathbf{c}} (\forall (j_1,j_2))$; when $y_{\mathcal{C}}=0$, Constraints (19c) and (19d) become redundant. Constraint (19f) connects $y_{\mathcal{C}}$ and $z_{ij}$: when all lines are switched on, (19f) fixes $y_{\mathcal{C}}$ to one. If any line is switched off, $1-{\sum }_{(i,j)\in \mathcal{C}}(1-z_{ij})⩽0$ and $(1/|\mathcal{C}|){\sum }_{(i,j)\in \mathcal{C}}{z}_{ij}\in [0,1)$, which enforce $y_{\mathcal{C}}=0$. Also note that, when $y_{\mathcal{C}}=0$, (19a), (19b), and (19e) ensure that $x_{12}^{\mathbf{c}}=x_{45}^{\mathbf{c}}=0$, and Constraint (18) becomes redundant. We can similarly derive the convex hull formulation for three-cycle constraints in the w space and for four-cycle constraints.

To show the tightness of extreme-point formulation compared with McCormick relaxation, we use the scatterplot method, similar to that of Luedtke et al. (2012). We apply the two different relaxation methods for the summation of bilinear terms ${\sum }_{(j_1,j_2)\in \mathcal{P}}{x}_{j_1}^{\mathbf{c}}{x}_{j_2}^{\mathbf{c}}$. Without loss of generality, we set the domain of $x_i^{\mathbf{c}},i=1,\dots ,6$ as $[-1,1]$, which includes both positive and negative numbers. We randomly generate 5,000 samples of those points, following a uniform distribution in their domain. For each sample, we then obtain the difference between upper and lower bounds of the summation with the two relaxation methods and obtain the scatterplot in Figure 2. In the scatterplot, each point corresponds to the result of one sample. All the points are above the (gray) diagonal line, which implies that the extreme-point representation is either tighter or as tight as the McCormick relaxation.

4.3. Branch-and-Cut Algorithm for Lifted Cycle Constraints

The size of extreme-point formulation for lifted cycle constraints grows quickly with the number of cycles in the network. Therefore, instead of adding all of those constraints at once, we use a separation scheme that generates cutting planes only when the linearized lifted cycle constraints are violated.

Because of binary line-switching decisions in the linearized lifted cycle constraints, the separation problem is not a linear program (LP). To generate cutting planes that separate infeasible solutions, we first ignore the line-switching decisions in the linearized lifted cycle constraints and generate Benders feasibility cuts if those constraints are violated. We then incorporate binary variables into the Benders cuts via disjunctive programming.

First, we describe how to generate Benders cuts without considering line-switching decisions. At the start of the cutting-plane algorithm, we solve the ACOTS-QC model without any lifted cycle constraints and obtain optimal solutions for c–s and w variables. Then, for each cycle, we solve a feasibility problem consisting of all the lifted cycle constraints (within the c–s or w space) in the extreme-point formulation without line-switching decisions, fixing c–s or w variables to their optimal values. If this feasibility problem is feasible, then none of the linearized lifted cycle constraints is violated, so we do not need to add any cut; otherwise, we generate a Benders feasibility cut and add this cut back to the ACOTS-QC model and solve it again. The algorithm terminates if, at one iteration, the ACOTS-QC model solution is feasible to the lifted cycle constraints for all cycles.

For example, for a three-cycle with nodes i, j, and k, let $x^{\mathbf{c}}=(c_{ij},c_{jk},c_{ik},s_{ij},s_{jk},s_{ik})$ and let ${\mathit{x}}^{\mathbf{c}*}$ be an optimal solution of the ACOTS-QC model. We solve the following separation problem:

If this problem is infeasible, we can generate a Benders feasibility cut in the following form:

where $\mathit{\beta }$ and $\mathit{b}$ are the coefficient vector and the constant in the Benders cut, respectively. Now, we consider the impact of line-switching decisions. The Benders cut should be redundant when any line in a cycle is turned off. To ensure this, we reformulate Benders cuts via disjunctive programming. Again, we use the three-cycle constraints in the c–s space to demonstrate how this works. Remember the binary variable $y_{\mathcal{C}}$ that equals one if and only if all lines in the cycle $\mathcal{C}$ are turned on. The Benders cut (21) should only be active when $y_{\mathcal{C}}=1$. In other words, the feasible region defined by the reformulated Benders cut is a union of the following two sets:where ${\underset{¯}{\mathit{x}}}^{\mathbf{c}}$ and ${\overline{\mathit{x}}}^{\mathbf{c}}$ are lower and upper bounds of $x^{\mathbf{c}}$. Using disjunctive programming, the following constraint is valid for the convex hull of ${\mathrm{\Gamma }}_0\cup {\mathrm{\Gamma }}_1$:where $\mathcal{N}$ is the set of indices for $\mathit{\beta }$ and $x^{\mathbf{c}}$. Intuitively, when $y_{\mathcal{C}}=1$, (22) is exactly the Benders cut (21); when $y_{\mathcal{C}}=0$, (22) is always satisfied and, thus, becomes redundant.

The separation scheme needs to solve the mixed-integer quadratic ACOTS-QC model at each iteration, which is very inefficient. This is why we use a branch-and-cut method, in which the mixed-integer quadratic ACOTS-QC model is only solved once with the branch-and-bound algorithm, and the Benders cuts are added at integral nodes of the branch-and-bound tree. More specifically, at each integral node, we obtain the optimal values of trigonometric terms $x^{\mathbf{c}}$ and switching decisions $z_{ij}$ and denote them, respectively, by ${\mathit{x}}^{\mathbf{c}*}$ and ${\mathbf{z}}_{ij}^{*}$. For any cycle $\mathcal{C}$ with all lines turned on (i.e., when ${\sum }_{(i,j)\in \mathcal{C}}{\mathbf{z}}_{ij}^{*}=|\mathcal{C}|$), we solve the separation problem (20). If the problem is infeasible, we add Constraints (19f), (19g), and (22).

5. Optimization-Based Bound Tightening

The OBBT method is a technique in nonconvex optimization, and it aims to improve the convex relaxation bound by tightening the bounds of certain variables. OBBT is often used to improve bounds and obtain near global optimal solutions for ACOPF problems (Chen et al. 2015, Cengil et al. 2022), and it has the benefit of being massively parallelizable (Gopinath et al. 2020). In our work, we implement OBBT to tighten the bounds of $v_i$, ${\theta }_{ij}$, $z_{ij}$, and $y_C$ variables before solving the relaxations of ACOTS.

To formulate bound-tightening optimization models for any variable x, we replace the objective of an ACOTS relaxation (e.g., ACOTS-QC) with $\max x$ or $\min x$. To avoid solving time-consuming MINLPs in OBBT, we linearly relax all integer variables. We denote the optimal objectives of the bound-tightening maximization and minimization problems $\overline{x}$ and $\underset{¯}{x}$. If x is a binary variable (such as $z_{ij}$ and $y_C$), we can further tighten their bounds by fixing x to 1 if $\underset{¯}{x}>0$ and to 0 if $\overline{x}<1$ within the OBBT iteration. The OBBT algorithm terminates when the bounds of all variables stop improving or when the algorithm reaches its time/iteration limit.

6. Maximum Spanning Tree Heuristic

Heuristics have been developed to quickly find good feasible solutions for the OTS problem, prioritizing speed over optimality (Barrows et al. 2012, Fuller et al. 2012, Soroush and Fuller 2013, Hinneck and Pozo 2022). These approaches typically reduce the solution space by fixing a set of candidate lines based on objective sensitivities. However, they often apply heuristics to the simpler, less accurate DCOTS model for large-scale networks or focus on quantifying the accuracy of such decisions. None has explored the problem using more accurate ACOTS relaxations, particularly for large-scale networks.

In this section, we propose a heuristic to accelerate the solution of the (ACOTS-QC) formulation in (11), in which we find a maximum spanning tree in the network, and keep all lines in the spanning tree switched on. Note that a maximum spanning tree is a spanning tree of a weighted graph with the maximum total weight.

Based on empirical observations, most transmission lines remain switched on in the optimal solution. Inspired by this observation, we heuristically identify the lines that are likely the most essential for transmission and that maintain network connectivity, keeping these lines switched on to reduce the number of binary variables. Specifically, we assign the weight $\max ({|{\widehat{S}}_{ij}|}^2/{\left({\overline{\mathit{s}}}_{ij}^a\right)}^2,{|{\widehat{S}}_{ji}|}^2/{\left({\overline{\mathit{s}}}_{ij}^a\right)}^2)$ to each line $(i,j)$, where ${\widehat{S}}_{ij}$ is the locally optimal solution corresponding to the AC power flow variable, $S_{ij}$, in the ACOPF problem (e.g., obtained using Ipopt) based on the original topology with all lines active. Intuitively, lines with higher weights exhibit lower slack. We then find a maximum spanning tree for the network and allow only lines outside the tree to be switched off.

This heuristic restricts the solution space of switching variables, potentially leading to suboptimal solutions for (11). However, even suboptimal line-switching can reduce grid operating costs. Our numerical experiments in Section 8.2 demonstrate that the heuristic can quickly find near-optimal solutions for many instances, particularly larger ones. Additionally, in Section 8.3, we show that the heuristic obtains results for several large instances with 500 to 2,312 buses, which, to our knowledge, have not been previously explored for ACOTS with tight convex relaxations.

7. Overview of Proposed Algorithm

In this section, we provide a summary of our algorithm with all proposed improvements (with lifted cycle constraints added in branch-and-cut fashion).

We start the algorithm by preprocessing variable bounds via OBBT as described in Section 5. Those bounds are added to (ACOTS-QC), which is then solved via branch-and-bound. Inside the branch-and-bound search, lifted cycle constraints are generated as described in Section 4.3 and added at integral nodes via lazy callback of the solver. The algorithm terminates when the gap between the upper and lower bounds of the branch-and-bound search is below a small tolerance. Finally, if we opt to use the maximum spanning tree heuristic, it can be incorporated before OBBT. We summarize the implementation of the algorithm in Figure 3.

Combining all strengthening techniques in Figure 3 provides the tightest QC-based ACOTS relaxation in the literature. Note that, when strengthening the ACOTS relaxations, two factors are crucial: (i) tightness of the MINLP convexification and (ii) tightness of the corresponding ACOPF relaxation. The latter is important because, if the binary variables are known, then the ACOTS problem simplifies to an ACOPF problem. In our work, several approaches, such as disjunctive programming–based lifted cycle constraints, are employed to strengthen the MINLP bound. Whereas some of our proposed methods, such as the lifted cycle constraints, can also improve the ACOPF relaxation, as shown in Section 8.5, our main focus is not on improving the ACOPF bound, which remains challenging on a large scale and warrants further exploration.

8. Numerical Experiments

This section presents the numerical efficacy of the proposed ACOTS-QC and ACOPF-QC relaxations with lifted cycle constraints and an analysis for ACOTS with different load profiles. Our experiments are conducted on the PGLib-OPF v20.07 benchmark library (Babaeinejadsarookolaee et al. 2019). For medium-scale instances, we use a Linux workstation with 3.6 GHz Intel Core i9-9900K CPUs and 128 GB memory. For large-scale instances in Section 8.3, we use Linux workstations with Intel CPUs and 250 GB memory. The programming language is Julia v1.6. We locally solve all nonconvex MINLP (ACOTS) formulations with both Juniper.jl (v0.7.0) (Kroger et al. 2018) and Knitro (v.13.0.1) (Byrd et al. 2006). Nonconvex NLP (ACOPF) formulations are solved locally using Ipopt (v3.13.4) (Wachter and Biegler 2006). All relaxation formulations (ACOTS-QC, ACOPF-QC, and OBBT iterations) are solved using the Gurobi (v9.0.0) solver. The branch-and-cut framework for cycle constraints is implemented using Gurobi’s lazy-constraint callback. The code for our experiments is available in the INFORMS Journal on Computing GitHub software repository (Guo et al. 2025).

8.1. Relaxations for ACOTS

We compare five different types of relaxations for ACOTS:

1. “P”: The on/off QC relaxation implemented in PowerModels.jl (Coffrin et al. 2018) is used as the state of the art to benchmark ACOTS relaxations. Formulation within “P” is based on (Hijazi et al. 2017), which uses on/off trigonometric function relaxations and recursive McCormick linearization of trilinear terms without additional cycle constraints or the OBBT algorithm.

2. “E”: Proposed ACOTS-QC relaxation with extreme-point representation for linearizing $z_{ij}{v}_i{v}_j{c}_{ij}$ and $z_{ij}{v}_i{v}_j{s}_{ij}$ in (3).

3. “EC”: Tightened “E” with lifted cycle constraints. The lifted cycle constraints are included in (ACOTS-QC) at the start of the algorithm.

4. “ECB”: Includes all proposed improvements (extreme-point representation, lifted cycle constraints, and OBBT). The lifted cycle constraints are included in (ACOTS-QC) at the start of the algorithm (Compare this with “ECB*” below).

5. “ECB*”: The same as “ECB” except the lifted cycle constraints are added via a branch-and-cut framework as in Section 4.3. The number of added cuts is bounded at 200.

We also provide initial feasible solutions as warm-start solutions, and these are helpful to speed up the convergence for many of the large instances. Those initial feasible solutions are obtained by solving the ACOPF-QC relaxation with recursive McCormick linearization for trilinear terms (for “P”), ACOPF-QC (with extreme-point linearization for “E”), or ACOPF-QC with lifted cycle constraints (for “EC”), and those solutions are valid when all lines in the network are switched on.

We run PGLib instances with up to 300 buses under typical operating conditions (TYP), as well as cases with small angle-difference conditions (SAD) and congested operating conditions (API), all of which are created by Babaeinejadsarookolaee et al. (2019). More specifically, the TYP cases are base cases with no change in the standard PGLib-OPF networks. The SAD cases modify the TYP cases by reducing the voltage angle difference on all branches of the standard networks, whereas the API cases modify the TYP cases by increasing active power demand throughout the standard networks.

In Table 2, we present results for cases that are solved in the two-hour time limit (within 0.1% optimality tolerance) for “E.” As shown in Online Table 1, which provides the relative gap at termination for all PGLib instances up to 300 buses, instances not solved by “E” are also unsolved by other methods. The performance measures we use for comparison include optimality gap and runtime. We put “ns.” for the optimality gaps of cases that are not solved to 0.1% optimality tolerance within the time limit and “tl.” for the runtime of test cases that hit the time limit.

Table 2. Optimality Gap and Runtime of ACOTS Relaxations

The optimality gap is calculated by (UB − LB)/UB × 100, where LB is the optimal value from relaxations of ACOTS and UB is an upper bound for ACOTS. For UB, we take the minimum of local optimal values of the following four types of methods:

• Nonconvex ACOTS Model (1) with the Knitro solver.

• Nonconvex ACOTS Model (1) with the Juniper solver.

• Nonconvex ACOPF model with all lines switched on.

• Nonconvex ACOPF model with the set of lines switched off as indicated by the ACOTS-QC solutions.

We highlight with boldface the optimality gaps improved after the relaxations are tightened. All comparisons are between two adjacent columns in the table. We also highlight the reduced runtimes of our branch-and-cut algorithm (in “ECB*”).

The runtimes of “ECB” and “ECB*” are the runtimes of the ACOTS-QC relaxation problems and do not include the runtimes of OBBT. This is because OBBT time is a constant factor inclusion irrespective of whether the cycle constraints are added to LP-relaxed models ($z_{ij},y_C\in [0,1])$ directly or in a branch-and-cut fashion within the OBBT algorithm. Moreover, these times are not as significant when compared with the ACOTS-QC relaxation problems as the OBBT’s LP-relaxed models, at every iteration, can be solved in parallel. We also exclude the model-building time of separation problems in “ECB*” within the branch-and-cut algorithm (we separately provide the separation problem–building time in Online Table 2) as any overhead in such time is an artifact of the mathematical modeling package within Julia. We set the feasibility tolerance for “EC” and “ECB*” to ${10}^{-4}$ instead of Gurobi’s default of ${10}^{-6}$ because, with a smaller tolerance, the solver may incorrectly reject feasible warm-start solutions for some instances. In addition, we set the upper bound on the number of added cuts at 200 as adding too many cuts could slow down the performance. We observe that those added cuts are able to significantly improve the bounds as shown in Table 2.

In Table 2, compared with “P,” our tightened “E” reduces the optimality gap for many benchmark instances, especially for the SAD and API ones. For example, it yields 3.4% gap improvement for case3_lmbd_api and 2.9% improvement for case24_ieee_rts_sad. It also solves several instances to optimality that “P” is not able to solve within the time limit. The benefit of the lifted cycle constraints (“EC”) is most apparent for “SAD” with case14_ieee_sad closing 6.2%.

Combining the extreme point formulation, OBBT algorithm, and the lifted cycle constraints, we obtain the tightest QC-based ACOTS relaxation in the literature as highlighted in the optimality gap columns of “ECB” and “ECB*” (see Table 2). Note that “ECB*” may not be as tight as “ECB” because “ECB” includes all cycle constraints, whereas “ECB*” adds up to 200 cycle constraints via cutting planes. However, when “ECB*” is not as tight, the difference is only 0.1%, indicating that “ECB*” remains relatively strong. Because of the efficient implementation of the branch-and-cut framework, “ECB*” reduces the solution time significantly in many instances. It is clear from the table that the OBBT algorithm in conjunction with all the proposed enhancements in this paper can provide significant improvements in closing the gap for several benchmark cases. For example, in case14_ieee_sad, “ECB” closes as much as 17.6% of the gap when compared with “E” and proves global optimality for case3_lmbd_api. Compared with “E,” “ECB” and the faster “ECB*” reduce the gap of nine instances to below 1.0%. In fact, with “ECB” and “ECB*,” we close the optimality gaps to less than 1.0% for ≈75% of all instances; these improvements are also significant when compared with state-of-the-art implementation in “P” and the results in Bestuzheva et al. (2020). Note that, if the optimality gap equals zero, then the corresponding ACOTS relaxation provides a globally optimal solution to the nonconvex ACOTS problem.

Note that there are a few instances that are not solved because of no feasible solution found within the time limit. In particular, for the instances with 89 buses, we do not provide warm-start solutions when cycle constraints are included as these instances have a large number of cycles, resulting in large warm-start files that cause a stack overflow error in the solver. In addition, the warm-start solution is incorrectly rejected by the solver when solving case200_activ with “ECB*.” Without warm start, these instances struggle to find a feasible solution.

We also check the tightness of the root node relaxation. To find the values of the root node relaxation, we set the Gurobi “NodeLimit” parameter to zero and obtain the optimal objective bound. In Online Table 3, we present the optimality gaps at the root node for the ACOTS relaxations, which equals 100 × (UB − root node relaxation value)/UB. In contrast to the results in Table 2, the improvement of “E” is relatively small at the root node, indicating that “E” closes more gap during branch and bound. “EC” provides tight root relaxations for several SAD instances. The “ECB” relaxation provides tighter root node relaxations for many instances, in particular for SAD and API ones, which possibly explains the reduced final optimality gaps in Table 2. Note that, unlike “ECB,” the bound-tightening optimization models for “ECB*” are not strengthened by cycle constraints, leading to potentially weaker bounds after OBBT and weaker root node relaxations. In fact, “ECB*” shows weaker root relaxations than “ECB” in several instances, suggesting that the tighter root relaxation of “ECB” is a result of both bound tightening and cycle constraints.

In addition, we include the results for the “PB” and “EB” relaxations (i.e., tightened “P” and “E,” respectively, with OBBT) in Online Table 4. We highlight with boldface italic the optimality gaps that can be further improved by “EB” (for “PB”) and by “ECB” (for “EB”). The difference between “PB” and “EB” shows that our extreme-point representation is useful for tightening many instances even after OBBT is implemented. Also, adding lifted cycle constraints (“ECB”) tightens “EB” for many instances.

To summarize, our basic relaxation with extreme-point representation (i.e., “E”) provides improvements over many of the instances compared with the state-of-the-art benchmark with comparable computational time. Both the lifted cycle constraints and OBBT provide enhancements to the basic relaxation. Combining all the improvements provides the tightest QC-based ACOTS relaxation in the literature with the runtime comparable to the basic relaxation when implemented in the branch-and-cut format.

Note that, for obtaining the UB, Juniper fails to find feasible solutions for many instances within the time limit (two hours), whereas Knitro found feasible solutions for all instances. On the other hand, for the instances that Juniper can solve, it sometimes provides better solutions. We provide a comparison of the results from the two solvers in Online Table 5.

Although not shown in the result table, it is worth mentioning that tightening the ACOTS relaxations does lead to different line-switching decisions. For example, in case24_ieee_rts_api, 13.9% of the lines have different switching decisions between “E” and “ECB.” If we fix the on/off statuses of the lines based on the solution of “E” and then solve the problem with “ECB,” the cost increases by 4.5%. Similarly, in case30_as_api, 7.3% of the lines have different switching decisions, leading to a 79.0% cost increase when using the “E” solution. Therefore, by tightening the relaxation, we make better decisions and obtain better approximations of the true cost after line switching.

8.2. Results with the Maximum Spanning Tree Heuristic

Table 3 compares results of our ACOTS relaxations with and without the maximum spanning tree heuristic proposed in Section 6. We include PGLib instances with up to 300 buses, which are solved with the same setups as in Section 8.1. In addition, when using the heuristic, we solve one “ECB” instance (case30_as_api) and the three 200-bus “ECB*” instances with Gurobi’s presolve disabled and with one thread. This is necessary to avoid the solver either incorrectly terminating with a locally optimal solution or incorrectly reporting infeasibility.

Table 3. Comparing the Objective Difference and Saved Runtime of ACOTS Relaxations with and Without the Spanning Tree Heuristic

The objective difference values are calculated by 100 × (LB₂ − LB₁)/LB₁, where LB₁ and LB₂ are, respectively, the optimal value with and without the heuristic. We use “s.” for cases solved with the heuristic but not without it, “ws.” for cases solved without the heuristic but not with it, and “ns.” for cases not solved by either method. “Runtime saved” shows the saved runtime by using the heuristic.

With the heuristic, we can solve many instances significantly faster and solve 12 more instances within the 0.1% tolerance. The heuristic can lead to higher optimal values for some instances. The objective difference is generally smaller for larger cases, suggesting that their accuracy is less affected by the heuristic. This is probably because larger networks tend to have more flexibility even after the heuristic fixes some lines to be switched on. There are three instances that can be solved without the heuristic, whereas the heuristic leads to relative gaps larger than 0.1% (and below 0.5%) at termination.

We also tested with assigning the same weight to all lines, but this approach does not lead to as much improvement as shown in Table 3.

8.3. Performance on Large-Scale ACOTS Instances

In this section, we present experimental results for large-scale PGLib instances with 500 to 2,312 buses. Note that, to the best of our knowledge, the largest ACOTS-QC instances investigated in the literature are up to 300 buses (Hijazi et al. 2017, Bestuzheva et al. 2020). However, with our proposed relaxations and heuristic, we are able to obtain results for some of these larger instances.

In Table 4, we present results for the upper bound and the relaxations of ACOTS-QC. Here, we include instances for which a feasible solution is found by either “P,” “E,” or “EC” and provide the results for all instances in Online Table 6. The “UB” and relaxation results are obtained with a similar method as in Section 2 with the following adjustment: solver time limits are set to three hours, and solver feasibility tolerances for the relaxations are set to ${10}^{-3}$ to reduce the likelihood of incorrectly rejecting warm-start solutions. Note that, when using Gurobi’s default feasibility tolerance of ${10}^{-6}$, none of the instances is solved. We include results for “P,” “E,” and “EC” relaxations. None of the “ECB” and “ECB*” relaxation instances is solved within the time limit. The performance measures we use include the objective value and runtime (or the relative gap at termination for cases hit the time limit). We use “nf.” as the objective value if no feasible solution is found within the time limit.

Table 4. Objective Value, Runtime, and Relative Gap of ACOTS Relaxations for Instances with 500 to 2,312 Buses

The state-of-the-art “P” relaxation solves three cases with at most 793 buses. In comparison, the “E” relaxation solves more cases to a below 0.5% relative gap, including some cases with more than 1,000 buses, such as case1354_pegase_sad and case1951_rte. In particular, the objective value of case1951_rte is within 0.1% of “UB,” suggesting it is very close to the global optimal solution. The “EC” relaxation solves case1354_pegase_api within a 0.1% relative gap, whereas this case is not solved by “E.”

In Table 5, we also present results with the maximum spanning tree heuristic. Here, we include instances that obtain a feasible solution from any one of the ACOTS-QC relaxations and present the results for all instances in Online Table 7. This method enables us to heuristically solve more large instances to either optimality or within a 0.5% relative gap. Interestingly, “EC” can sometimes solve cases that “E” cannot solve, such as case1354_pegase_api and case2000_goc_api. This is likely because the cycle constraints reduce the search space. The “ECB” and “ECB*” relaxations solve fewer instances compared with “E” and “EC,” and this is possibly because of more warm-start solutions being incorrectly rejected after the bounds are tightened.

Table 5. With the Spanning Tree Heuristic: The Objective Value, Runtime, and Relative Gap of ACOTS Relaxations for Instances with 500 to 2,312 Buses

In sum, the “E” and “EC” relaxations with the max spanning tree heuristic are very useful in obtaining results for larger PGLib cases. Given the critical role of warm-start solutions in performance, it is promising that more large cases can be handled once the solver can effectively adopt feasible warm-start solutions.

8.4. Analysis for Varying Load Profiles

We uniformly increase the loading condition, starting from the nominal value of the case30_ieee instance, and observe the number of lines that are switched off. As shown in Figure 4, the number of off lines first decreases and then increases. This is because, when the load is at the lower levels, some lines are redundant and are switched off to save costs. However, when the load is very high and the network is congested, lines are switched off to avoid congestion. As suggested by Fisher et al. (2008), it is beneficial to solve the ACOTS problem frequently to obtain optimal line-switching decisions for different load profiles.

8.5. Lifted Cycle Constraints for ACOPF-QC

We also add the linearized lifted cycle constraints (including the novel ones we derive) to the ACOPF-QC relaxation. This happens to be the special case of the ACOTS-QC with all the lines of the network switched on. These cycle constraints are linearized using the strong extreme-point representation, which is also new. We experiment with “TYP,” “SAD,” and “API” cases with up to 2,869 buses (102 cases in total) and observe improvements of optimality gaps in several instances. We report cases with greater than 0.03% improvement in objectives in Table 6 and include the results for all tested cases in Online Table 6. The results show that, for ACOPF-QC, the lifted cycle constraints are more useful in tightening “SAD” and “API” instances and for smaller size test cases.

Table 6. Comparing Optimality Gaps (Percentage) for “E” and “EC” Relaxations for ACOPF-QC, Including All Cases with Improvement Greater Than 0.03%

9. Conclusion

In this paper, we strengthen the on/off QC relaxation of the ACOTS model by the extreme-point representation technique, several valid inequalities added via branch and cut, and the OBBT algorithm. We also speed up the solution with a maximum spanning tree–based heuristic. Experiments on PGLib instances show that the strengthened ACOTS-QC formulation significantly improves lower bounds in several instances, especially for small angle–difference instances and congested instances. We also experiment with large-scale instances that are unexplored in the literature, demonstrating the usefulness of our relaxations and heuristic. Our proposed lifted cycle constraints improve the bounds of ACOTS-QC as well as ACOPF-QC relaxations and are helpful for solving more large-scale instances. We believe that our methods and findings make an important contribution toward solving ACOTS problems of more practical scale.

Considering large-scale grids, operated in a close-to-real-time fashion, ACOTS is still a very hard problem to solve with optimality guarantees. As the line-switching decisions are sensitive to load changes, it would be helpful to develop stochastic programming models that provide more robust solutions. It would also be interesting to improve the maximum spanning tree heuristic, further reducing binary switching decisions, maintaining high accuracy. To address scaling issues, it would be useful to (i) balance the trade-off between runtime and tighter formulations, (ii) develop faster decomposition-based distributed algorithms, and (iii) study more scalable ACOPF relaxations.