# Tight Big-Ms for Optimal Transmission Switching

Salvador Pineda, Juan Miguel Morales, Álvaro Porras, Concepción Domínguez
OASYS research group, University of Málaga, Spain
{spineda, juan.morales, alvaroporras<EMAIL_ADDRESS>
###### Abstract

This paper addresses the Optimal Transmission Switching (OTS) problem in
electricity networks, which aims to find an optimal power grid topology that
minimizes system operation costs while satisfying physical and operational
constraints. Existing methods typically convert the OTS problem into a Mixed-
Integer Linear Program (MILP) using big-M constants. However, the
computational performance of these approaches relies significantly on the
tightness of these big-Ms. In this paper, we propose an iterative tightening
strategy to strengthen the big-Ms by efficiently solving a series of bounding
problems that account for the economics of the OTS objective function through
an upper-bound on the generating cost. We also discuss how the performance of
the proposed tightening strategy is enhanced if reduced line capacities are
considered. Using the 118-bus test system we demonstrate that the proposed
methodology outperforms existing approaches, offering tighter bounds and
significantly reducing the computational burden of the OTS problem.

###### Index Terms:

Big-M tightening, Bounding problem, Mixed-integer optimization, Optimal
transmission switching, Topology control.

This work was supported in part by the European Research Council (ERC) under
the EU Horizon 2020 research and innovation program (grant agreement No.
755705), in part by the Spanish Ministry of Science and Innovation
(AEI/10.13039/501100011033) through project PID2020-115460GB-I00. Á. Porras is
also financially supported by the Spanish Ministry of Science, Innovation and
Universities through the University Teacher Training Program with fellowship
number FPU19/03053. Finally, the authors thankfully acknowledge the computer
resources, technical expertise, and assistance provided by the SCBI
(Supercomputing and Bioinformatics) center of the University of Málaga.

##  I Introduction

Traditionally, transmission lines in electricity networks have been regarded
as infrastructure devices that cannot be controlled, except during instances
of outages or maintenance. More recently, the possibility of flexibly
exploiting the topological configuration of the grid was first suggested in
[1] and later formalized in [2] into what we know today as the _Optimal
Transmission Switching_ (OTS) problem. The optimal transmission switching
problem refers to the task of determining the most efficient configuration of
transmission lines in a power system to achieve certain objectives. It
involves deciding which transmission lines should be open or closed to
optimize system performance in terms of factors such as minimizing
transmission losses, voltage deviations, or congestion. Even if the power flow
equations are simplified using the well-known _direct current_ (DC) linear
approximation of the power flow equations, the resulting formulation of the
OTS problem, known as DC-OTS, takes the form of a mixed-integer program, which
has been proven to be NP-hard for general network classes [3, 4].

Up until now, the resolution of the DC-OTS has been addressed using two
different methodological approaches. These approaches can be categorized as
exact methods and heuristics. The exact methods utilize techniques derived
from mixed-integer programming, such as bounding and generating valid cuts.
These methods aim to solve the DC-OTS with (certified) global optimality,
ensuring the best possible solution. On the other hand, heuristics aim to
rapidly identify good solutions for the problem, potentially sacrificing
optimality or even suggesting infeasible grid configurations.

Several heuristic methods have been proposed in the technical literature to
reduce the computational time in solving the OTS problem. Some of these
methods focus on decreasing the number of lines that can be switched off [5,
6, 7]. Other approaches maintain the original set of switchable lines but
determine their on/off status using greedy algorithms [8, 9]. In contrast, the
authors of [10] propose a parallel approach where heuristics generate
promising candidate solutions to expedite traditional MIP algorithms in
solving the OTS problem. Furthermore, certain data-based heuristic methods
utilize information from past OTS problems to improve efficiency. For example,
the authors of [11, 12] employ a $K$-nearest neighbor strategy to
significantly reduce the search space of the integer solution for the DC-OTS
problem. Similarly, references [13, 14] present more advanced methodologies
involving neural networks to learn the optimal status of switchable lines.

Within the exact methods, notable contributions can be found in references
[3], [4], and [15]. In particular, the authors of [3] present a cycle-based
formulation for the DC-OTS problem, which yields a mixed-integer linear
program. They also introduce sets of strong valid inequalities for a relaxed
version of their formulation that can be efficiently separated. In [4], the
authors focus on the mixed-integer linear formulation of the DC-OTS, utilizing
a big-M approach to handle the disjunctive relationship between the power flow
of switchable lines and the voltage angle differences. They prove the NP-
hardness of determining valid big-Ms and propose a methodology for setting the
appropriate values. Lastly, the authors of [15] develop a family of cutting
planes specifically tailored for the DC-OTS problem.

This paper introduces a new exact methodology to address the DC-OTS problem,
making significant contributions to the existing state-of-the-art. Our
approach determines suitable values for the big-M constants used in the mixed-
integer reformulation of the DC-OTS by solving the so-called bounding
problems. To obtain tighter big-M values, we impose an upper-bound on the
generating cost in these bounding problems. We also investigate the
synergistic effect between the big-M tightening and the reduction of the line
capacities. The performance of our methodology is then compared to the
approach proposed in [4] to determine big-M constants for the 118-bus test
system. In summary, the key contributions of this work can be summarized as
follows:

  * -

We propose a set of bounding problems to efficiently compute tight big-M
values to be used in the optimal transmission switching problem. Besides, we
enhance the performance of the bounding problems imposing a valid upper-bound
on the total generating cost.

  * -

We extend the use of the bounding problem to also compute the maximum feasible
power flow through the transmission lines. We demonstrate that using these
reduced capacities decrease even further the big-M values.

  * -

We use a 118-bus test system to prove that the proposed bound tightening
methodology clearly outperforms state-of-the-art approaches and general
purpose methods of optimization solvers in terms of the computational burden
required to solve the OTS problem.

The remainder of this paper is structured as follows. Section II introduces
the original formulation of the DC-OTS problem, its reformulation as a mixed-
integer linear program, and the existing methodologies to compute the required
big-M constants. The proposed cost-driven bound tightening approach is
presented in Section III, which concludes with the comparison procedure used
to assess its performance. Section IV discusses the computational results
obtained for the 118-bus test system. Finally, conclusions are drawn in
Section V.

##  II Optimal Transmission Switching

In this section we introduce the standard and well-known formulation of the
_Direct Current Optimal Transmission Switching_ problem (DC-OTS) which has
been considered in [2, 3, 4, 5, 6, 8, 10, 11, 12, 13, 15, 16, 17] among
others. Readers interested in exploring further details regarding the
additional complexity of the AC-OTS problem can refer to [7, 9, 18].

Consider a power network consisting of a set of nodes $\mathcal{N}$ and
transmission lines $\mathcal{L}$. For simplicity, we assume that there is one
generator and one power load per node $n\in\mathcal{N}$. Let $p_{n}$ and
$d_{n}$ denote the power dispatch of the generator and the power consumed by
the power load, respectively. Each generator is characterized by a minimum and
maximum power output, $\underline{p}_{n}$ and $\overline{p}_{n}$, and a
marginal production cost $c_{n}$. We represent the power flow through the line
$(n,m)\in\mathcal{L}$ connecting nodes $n$ and $m$ by $f_{nm}$. As customary,
$f_{nm}>0$ represents a power flow from node $n$ to node $m$, and $f_{nm}<0$ a
power flow in the opposite direction. The maximum power flow from node $n$ to
node $m$ is denoted by $F_{nm}$, and the power flow in the opposite direction
is limited by $F_{mn}$. The maximum flow through a line is constrained by
thermodynamics limitations and therefore, _physical_ line capacities are
always symmetric, i.e., $F_{nm}=F_{mn}$. However, depending on the location of
generators and loads in a network, the maximum _feasible_ flows through a line
may be different in each direction, which is the reason why we consider the
more general case of asymmetric line capacities. Besides, the set of
transmission lines that can be switched on/off is denoted by
$\mathcal{L}_{S}\subseteq\mathcal{L}$. If the line $(n,m)\in\mathcal{L}_{S}$,
the binary variable $x_{nm}$ determines its status, being equal to 1 if the
line is fully operational, and 0 when disconnected. Using the DC approximation
of the network equations, the flow $f_{nm}$ through an operational line is
given by the product of the susceptance of the line, $b_{nm}$, and the
difference of the voltage angles at nodes $n$ and $m$, i.e.,
$\theta_{n}-\theta_{m}$. We use bold symbols to define the vectors of
variables $\mathbf{p}=[p_{n},n\in\mathcal{N}]$,
$\boldsymbol{\theta}=[\theta_{n},n\in\mathcal{N}]$,
$\mathbf{f}=[f_{nm},(n,m)\in\mathcal{L}]$, and
$\mathbf{x}=[x_{nm},(n,m)\in\mathcal{L_{S}}]$. With this notation in place,
the DC-OTS problem can be formulated as follows:

$\displaystyle\min_{p_{n},f_{nm},\theta_{n},x_{nm}}\quad\sum_{n}c_{n}\,p_{n}$
(1a) s.t. $\displaystyle\quad
f_{nm}=x_{nm}b_{nm}(\theta_{n}-\theta_{m}),\quad\forall(n,m)\in\mathcal{L}_{S}$
(1b) $\displaystyle\quad
f_{nm}=b_{nm}(\theta_{n}-\theta_{m}),\quad\forall(n,m)\in\mathcal{L}\setminus\mathcal{L}_{S}$
(1c)
$\displaystyle\quad\sum_{m:(n,m)\in\mathcal{L}}f_{nm}-\sum_{m:(m,n)\in\mathcal{L}}f_{mn}=p_{n}-d_{n},\quad\forall
n\in\mathcal{N}$ (1d) $\displaystyle\quad\underline{p}_{n}\leq
p_{n}\leq\overline{p}_{n},\quad\forall n\in\mathcal{N}$ (1e)
$\displaystyle\quad-x_{nm}F_{mn}\leq f_{nm}\leq
x_{nm}F_{nm},\quad\forall(n,m)\in\mathcal{L}_{S}$ (1f) $\displaystyle\quad-
F_{mn}\leq f_{nm}\leq
F_{nm},\quad\forall(n,m)\in\mathcal{L}\setminus\mathcal{L}_{S}$ (1g)
$\displaystyle\quad\theta_{1}=0$ (1h) $\displaystyle\quad
x_{nm}\in\\{0,1\\},\quad\forall(n,m)\in\mathcal{L}_{S}$ (1i)

The objective function (1a) minimizes the total electricity generation cost.
The power flow through transmission lines is defined in (1b) and (1c). In the
case of a switchable line, constraint (1b) includes the binary variable
$x_{nm}$ to enforce this relationship only when the line is in service.
Naturally, $x_{nm}=0$ implies that $f_{nm}=0$. The nodal power balance
equation is ensured by (1d), while constraints (1e) impose that the power
output of generating units must lie within the interval
$[\underline{p}_{n},\overline{p}_{n}]$. Constraints (1f) and (1g) limit the
maximum power flow through switchable and non-switchable lines, respectively.
Equation (1h) arbitrarily sets one of the voltage angles to zero, while the
binary character of variables $x_{nm}$ is imposed by constraint (1i).

Problem (1) is a mixed-integer nonlinear programming problem due to the
product $x_{nm}(\theta_{n}-\theta_{m})$ in (1b). Even when the power network
includes a connected subgraph of non-switchable lines, this problem has been
proven to be NP-hard [4]. However, constraint (1b) can be linearized by
introducing a pair of large enough constants $M_{nm}$, $M_{mn}$ per switchable
line [16]. By doing so, equation (1b) can be replaced by the two following
inequalities:

$\displaystyle f_{nm}\geq b_{nm}(\theta_{n}-\theta_{m})-M_{nm}(1-x_{nm})$ (2a)
$\displaystyle f_{nm}\leq b_{nm}(\theta_{n}-\theta_{m})+M_{mn}(1-x_{nm})$ (2b)

where the large constants $M_{nm},M_{mn}$ are guaranteed to be upper bounds of
$b_{nm}(\theta_{n}-\theta_{m})$ and $b_{nm}(\theta_{m}-\theta_{n})$,
respectively, when the line $(n,m)$ is disconnected ($x_{nm}=0$). Under that
assumption, the DC-OTS is reformulated as the following mixed-integer linear
programming problem

$\displaystyle\min_{p_{n},f_{nm},\theta_{n},x_{nm}}$
$\displaystyle\quad\sum_{n}c_{n}\,p_{n}$ (3a) s.t.
$\displaystyle\quad\eqref{eq:OTS_NP_Flow_NS}-\eqref{eq:OTS_NP_binary},\eqref{eq:linear}$
(3b)

Although model (3) can be solved using off-the-shelf mixed-integer
optimization solvers, such as Gurobi [19], the choice of the bounds
$M_{nm},M_{mn}$ is of utmost importance. If these bounds are too loose, the
relaxations performed throughout the branch-and-bound or branch-and-cut
algorithms are too poor, and the total computational burden is expected to
increase significantly. In all existing works that reformulate the DC-OTS
problem as a mixed-integer program, these large enough constants are assumed
to be symmetric, i.e., $M_{nm}=M_{mn}$. The review paper [18] collects in
Table 1 a summary of all proposed symmetric big-M values used in the technical
literature. In particular, the authors of [17] propose a method to compute
big-M values based on the shortest and longest paths between two nodes. This
methodology has been recently revisited in [4], where the authors argue that
the lowest possible value of these bounds denoted by $M^{\rm OPT}_{nm}$ and
$M^{\rm OPT}_{mn}$ can be obtained by solving the following bounding problems

$\displaystyle M^{\rm
OPT}_{nm}:=b_{nm}\times\underset{\eqref{eq:OTS_NP_Flow_S}-\eqref{eq:OTS_NP_slack}\,\cap\,\mathcal{X}_{nm}}{\max}(\theta_{n}-\theta_{m})$
(4a) $\displaystyle M^{\rm
OPT}_{mn}:=b_{nm}\times\underset{\eqref{eq:OTS_NP_Flow_S}-\eqref{eq:OTS_NP_slack}\,\cap\,\mathcal{X}_{nm}}{\max}(\theta_{m}-\theta_{n})$
(4b)

where
$\mathcal{X}_{nm}:=\\{\mathbf{x}\in\mathbb{B}^{|\mathcal{L}_{\mathcal{S}}|}:x_{nm}=0\\}$
imposes that the binary variable associated with the switchable line $(n,m)$
is equal to 0. As illustrated in [4], problem (4) can be unbounded in power
systems where switching off lines can result in isolated subnetworks. However,
due to reliability and security standards, islanding in power grids is to be
avoided in general and therefore, we assume that the set of switchable lines
$\mathcal{L}_{\mathcal{S}}$ is such that the connectivity of the whole power
network is always guaranteed by means of a spanning subgraph. The authors in
[4] also show that, even when $M^{\rm OPT}_{nm}$ is finite, computing it is as
hard as solving the original DC-OTS problem. Therefore, they propose an
efficient methodology to find other valid bounds for (2) as follows:

$\displaystyle M_{nm}=b_{nm}\sum_{(i,j)\in{\rm
SP}_{nm}}\frac{F_{ij}}{b_{ij}},\quad\forall(n,m)\in\mathcal{L}_{\mathcal{S}}$
(5a) $\displaystyle M_{mn}=b_{nm}\sum_{(i,j)\in{\rm
SP}_{mn}}\frac{F_{ij}}{b_{ij}},\quad\forall(n,m)\in\mathcal{L}_{\mathcal{S}}$
(5b)

where ${\rm SP}_{nm}$ is the shortest path from $n$ to $m$, and ${\rm
SP}_{mn}$ the shortest path from $m$ to $n$. These shortest paths are
determined on a directed graph with edge costs $c_{nm}=F_{nm}/b_{nm}$ and
$c_{mn}=F_{mn}/b_{nm}$ for the lines that belong to the connected spanning
subgraph, and $c_{nm}=c_{mn}=\infty$ for the switchable lines. These shortest
paths can be efficiently computed using Dijkstra’s algorithm [20]. In
reference [4], line capacities are assumed symmetric and therefore, the big-M
values computed by (5) are also symmetric, that is, $M_{nm}=M_{mn}$. For given
line capacities $\mathbf{F}$, using equations (5) to obtain the bounds
$\mathbf{M}$ for all switchable lines is denoted as
$\mathbf{M}=\mathcal{SP}\left(\mathbf{F}\right)$. Among the references
reviewed in [18], the methodology proposed in [4] is the one that leads to
tighter big-M values and therefore, this approach is used here as a benchmark.

In the next section we propose a novel methodology to compute valid bounds
that are tighter than those described in [4] and therefore reduce the
computational burden of solving model (3). Conversely to all existing
methodologies, the one we propose in this paper allows us to compute
asymmetric big-M values that yield tighter mixed-integer reformulations of the
DC-OTS problem. Following the assumption in [4], the proposed tighter bounds
are derived under the premise that network connectivity is guaranteed by a set
of non-switchable lines forming a spanning subgraph. Interested readers are
referred to [21] to delve into how the complexity of the OTS problem increases
when all lines are switchable, and network connectivity is enforced through
additional constraints.

##  III Bound tightening methodology

###  III-A Big-M tightening

The methodology proposed in this paper to find the values of the large
constants $M_{nm},M_{mn}$ is based on the following relaxations of problems
(4)

$\displaystyle
M_{nm}=b_{nm}\times\underset{\mathcal{R}(\mathbf{F},\mathbf{M})\,\cap\,\mathcal{X}^{0}_{nm}}{\max}(\theta_{n}-\theta_{m})$
(6a) $\displaystyle
M_{mn}=b_{nm}\times\underset{\mathcal{R}(\mathbf{F},\mathbf{M})\,\cap\,\mathcal{X}^{0}_{nm}}{\max}(\theta_{m}-\theta_{n})$
(6b)

where the feasible region defined by (1b)-(1h) is replaced by the set
$\mathcal{R}(\mathbf{F},\mathbf{M}):=\\{(\mathbf{p},\mathbf{\theta},\mathbf{f},\mathbf{x})\in\mathbb{R}^{2|\mathcal{N}|+|\mathcal{L}|+|\mathcal{L}_{\mathcal{S}}|}:\eqref{eq:OTS_NP_Flow_NS}-\eqref{eq:OTS_NP_slack},\eqref{eq:linear}\\}$
based on the linearization (2). Note that the feasible region $\mathcal{R}$
depends on the parameter vectors
$\mathbf{F}=[(F_{nm},F_{mn}),(n,m)\in\mathcal{L}]$ and
$\mathbf{M}=[(M_{nm},M_{mn}),(n,m)\in\mathcal{L}_{S}]$. Besides, the set
$\mathcal{X}^{0}_{nm}:=\\{\mathbf{x}\in\mathbb{R}^{|\mathcal{L}_{\mathcal{S}}|}:\mathbf{0}\leq\mathbf{x}\leq\mathbf{1},x_{nm}=0\\}$
is a relaxation of the set $\mathcal{X}_{nm}$ in which variables $\mathbf{x}$
can take any continuous value between 0 and 1. Similar relaxed optimization
problems have been used in [22, 23] to screen out redundant constraints. For
valid bound values $\mathbf{M}$, it is guaranteed that
$\mathcal{X}_{nm}\subset\mathcal{X}^{0}_{nm}$ and therefore, $M_{nm}\geq
M^{\rm OPT}_{nm}$ and $M_{mn}\geq M^{\rm OPT}_{mn}$. Besides, since
optimization problems in (6) are linear, the proposed methodology to find
valid bounds for inequality constraints (2) is computationally efficient. For
the remaining of this paper, we denote problems (6) as bounding problems [24].

Although bounding problems (6) are easy to solve, the proposed relaxation can
yield too loose bounds such that $M_{nm}\gg M^{\rm OPT}_{nm}$ and/or
$M_{mn}\gg M^{\rm OPT}_{mn}$ and therefore, the computational burden of
solving (3) using these bounds can still be substantial. To avoid this issue,
we include additional constraints to the bounding problems (6) so that the
obtained big-M values are as tight as possible.

In reference [23] the authors use a constraint on the generation cost of the
network-constrained unit commitment problem to efficiently remove inactive
constraints of the optimization model. Inspired by this idea, one may wonder
whether it is necessary to choose big-M values that guarantee the feasibility
of all integer solutions, or whether it could be more effective if these
bounds were tuned to also remove some feasible but suboptimal integer
solutions. For the sake of intuition, let us assume that the solution of
problem (4) for a given switchable line indicates that the maximum angle
difference is reached when the most expensive generators are producing at
maximum capacity and the cheapest units are not generating anything. Most
likely, the dispatch that maximizes this angle difference is much more
expensive than that obtained by the the DC-OTS problem and therefore, the
actual angle difference at the optimal solution of (3) is probably much lower
than that computed by (4). Accordingly, we define in this paper the set
$\mathcal{C}:=\\{\mathbf{p}\in\mathbb{R}^{|\mathcal{N}|}:\sum_{n}c_{n}p_{n}\leq\overline{C}\\}$,
where $\overline{C}$ is an upper bound on the optimal generation cost of the
DC-OTS problem. The bounding problems that consider an upper bound on the
production cost are then formulated as follows:

$\displaystyle
M_{nm}=b_{nm}\times\underset{\mathcal{R}(\mathbf{F},\mathbf{M})\,\cap\,\mathcal{X}^{0}_{nm}\cap\,\mathcal{C}}{\max}(\theta_{n}-\theta_{m})$
(7a) $\displaystyle
M_{mn}=b_{nm}\times\underset{\mathcal{R}(\mathbf{F},\mathbf{M})\,\cap\,\mathcal{X}^{0}_{nm}\cap\,\mathcal{C}}{\max}(\theta_{m}-\theta_{n})$
(7b)

Since the feasible regions of bounding problems (7) are contained in the
feasible regions of (6), we can guarantee that the obtained bounds are tighter
than those determined in (6). Besides, by setting a cap on the operational
cost, the big-M values derived from (7) become tighter, leveraging the
economic insights embedded in the maximum cost $\overline{C}$. Obviously, the
tighter the value of the upper-bound cost $\overline{C}$, the smaller the
feasible regions of problems (7). This implies lower big-M values and the
consequent reduction of the computational burden of problem (3). For given
line capacities $\mathbf{F}$, big-M values $\mathbf{M}$ and upper-bound cost
$\overline{C}$, using the bounding problems (7) to update the big-M values for
all switchable lines is denoted as
$\mathbf{M}=\mathcal{BM}(\mathbf{F},\mathbf{M},\overline{C})$.

Importantly, while the bounds computed by (5) according to the method proposed
in [4] are symmetric, the big-M values obtained by the bounding problems (7)
are not symmetric in general. Another relevant point to consider is that a
decrease of the big-M values associated with a specific switchable line has an
impact on the feasible region $\mathcal{R}$ of the bounding problems related
to the other switchable lines. As a result, it may be necessary to solve the
proposed bounding problems multiple times for the entire set of switchable
lines. This approach ensures that with each iteration, the big-M values will
consistently decrease and lead to more refined solutions through successive
iterations.

###  III-B Line capacity tightening

As discussed in Subsection III-A, the feasible region of problems (7) is
reduced by imposing an upper bound on the optimal generation cost. Following
this line of thought, the feasible region $\mathcal{R}$ can also be shrunk by
tightening the line capacities $\mathbf{F}$. For instance, let us consider a
given transmission line through which the power flow cannot exceed 100MW due
to thermal limitations. However, given the location and capacity of the
generating units, the demand location and variability, the network topology
and parameters, and an upper bound on the generating cost, the power flow
through that line is guaranteed to be always below 80MW. In such a case, we
can tighten this line capacity with the following computational advantages. By
reducing the capacities of the lines in the connected spanning subgraph, the
big-Ms computed by (5) also decrease. Besides, since constraint (1f) includes
the product $x_{nm}F_{nm}$, reducing the capacity of switchable lines also
makes model (3) tighter. For these reasons, we also propose in this Section to
compute the maximum feasible flows through all transmission lines as follows:

$\displaystyle
F_{nm}=b_{nm}\times\underset{\mathcal{R}(\mathbf{F},\mathbf{M})\,\cap\,\mathcal{X}^{1}_{nm}\cap\,\mathcal{C}}{\max}(\theta_{n}-\theta_{m})$
(8a) $\displaystyle
F_{mn}=b_{nm}\times\underset{\mathcal{R}(\mathbf{F},\mathbf{M})\,\cap\,\mathcal{X}^{1}_{nm}\cap\,\mathcal{C}}{\max}(\theta_{m}-\theta_{n})$
(8b)

where
$\mathcal{X}^{1}_{nm}:=\\{\mathbf{x}\in\mathbb{R}^{|\mathcal{L}_{\mathcal{S}}|}:\mathbf{0}\leq\mathbf{x}\leq\mathbf{1}\\}$
if $(n,m)\in\mathcal{L}\setminus\mathcal{L}_{S}$, and
$\mathcal{X}^{1}_{nm}:=\\{\mathbf{x}\in\mathbb{R}^{|\mathcal{L}_{\mathcal{S}}|}:\mathbf{0}\leq\mathbf{x}\leq\mathbf{1},x_{nm}=1\\}$
if $(n,m)\in\mathcal{L}_{S}$. Obviously, the maximum flows determined by (8)
are always lower than or equal to the original capacities determined by
thermodynamic limitations. Updating the maximum power flows through all lines
in the network using the bound problems (8) is denoted as
$\mathbf{F}=\mathcal{BL}(\mathbf{F},\mathbf{M},\overline{C})$. Additionally,
it is worth mentioning that the reduced line capacities computed in (8) can
also be used in (5) to get tighter big-M values.

Algorithm 1 Cost-driven Bound Tightening Algorithm

Input: Original line capacities $F_{nm},F_{mn},\,\forall(n,m)\in\mathcal{L}$,
demands $d_{n},\,\forall n\in\mathcal{N}$, upper-bound cost $\overline{C}$,
and number of iterations $K$.

Initialization: Determine SPnm and SPmn
$\forall(n,m)\in\mathcal{L}_{\mathcal{S}}$. Set $k=0$,
$\mathbf{F}^{0}=[(F_{nm},F_{mn}),(n,m)\in\mathcal{L}]$, and
$\mathbf{M}^{0}=\mathcal{SP}(\mathbf{F}^{0})$.

  1. 1)

Update $k\leftarrow k+1$.

  2. 2)

Depending on the method, update big-M values as

    1. i)

$\mathbf{M}^{k}\leftarrow\mathcal{SP}(\mathbf{F}^{k-1})$

    2. ii)

$\mathbf{M}^{k}\leftarrow\mathcal{BM}(\mathbf{F}^{k-1},\mathbf{M}^{k-1},\overline{C})$

  3. 3)

Depending on the method, update line capacities as

    1. i)

$\mathbf{F}^{k}\leftarrow\mathbf{F}^{k-1}$

    2. ii)

$\mathbf{F}^{k}\leftarrow\mathcal{BL}(\mathbf{F}^{k-1},\mathbf{M}^{k-1},\overline{C})$

  4. 4)

If $k<K$, go to step 1). Otherwise, stop.

Output: Bounds $\mathbf{F}^{K}$ and $\mathbf{M}^{K}$.

###  III-C Comparison procedure

In summary, the method we propose in this paper starts by finding a tight
upper-bound on the generating cost $\overline{C}$. Then, the big-M values and
the line capacities are iteratively tightened by solving the bounding problems
(7) and (8), respectively. Finally, the reduced bounds are used to solve the
mixed-integer formulation of the DC-OTS problem (3). Algorithm 1 summarizes
the main steps of the proposed methodology. In order to investigate the
improvements derived from the proposed methodology, we compare the
computational performance of the following four variations of Algorithm 1:

  * •

Shortest-Path approach with Original line Capacities (SP-OC). This is the
benchmark strategy proposed in [4] and only includes the initialization step
of Algorithm 1. Thus, model (3) is solved with $\mathbf{F}^{0}$ and
$\mathbf{M}^{0}$.

  * •

Shortest-Path approach with Reduced line Capacities (SP-RC). This is an
improvement of the method proposed in [4] that uses the reduced line
capacities obtained by the bounding problems (8) and updates the big-M values
using (5). Thus, this approach runs steps 3ii) and 2i) in Algorithm 1, in that
order, and ignores 2ii) and 3i).

  * •

Bound Tightening approach with Original line Capacities (BT-OC). In this
strategy we propose the big-M values are obtained by solving the bounding
problems (7) with the original line capacities in all iterations. Thus, this
approach runs steps 2ii) and 3i) in Algorithm 1, and ignores 2i) and 3ii).

  * •

Bound Tightening approach with Reduced line Capacities (BT-RC). This approach
reduces the big-M values and the line capacities by solving the bounding
problems and then, it is expected to yield the tightest bounds. This approach
runs steps 2ii) and 3ii) in Algorithm 1, and ignores 2i) and 3i).

Furthermore, in order to analyze the impact of the upper-bound cost on the
proposed tightening methodology, we compare two different procedures to
compute the maximum cost $\overline{C}$ to be used in the bounding problems:

  * •

Naive approach. This approach computes an upper bound on the cost by
satisfying the total demand with the most expensive generators. By
disregarding the network constraints, this cost is the solution to the linear
problem:

$\displaystyle\overline{C}=\max_{p_{n}}\quad$
$\displaystyle\sum_{n}c_{n}\,p_{n}$ (9a) s.t.
$\displaystyle\sum_{n}p_{n}=\sum_{n}d_{n}$ (9b)

Obviously, this upper bound on the optimal generating cost does not reduce the
feasibility region of the bounding problems and is just considered here for
benchmarking purposes. If model (9) is used to compute the upper-bound cost,
the method is denoted as XX-XX-N, where XX-XX represents the bound tightening
procedure SP-OC, SP-RC, BT-OC or BT-RC.

  * •

Heuristic approach. The technical literature also proposes some heuristic
approaches to solve the DC-OTS problem, like the greedy algorithm described in
[8]. At each step, this algorithm disconnects one switchable line at a time,
computes the resulting operating cost by solving an OPF linear problem, and
fixes the status of the line that leads to the lowest cost to 0. The algorithm
continues until disconnecting any remaining switchable line leads to a cost
increase. Although this procedure does not lead to the optimal solution of the
DC-OTS, its objective function can be close enough depending on each
particular case. If this heuristic approach is used to compute the upper-bound
cost, the method is denoted as XX-XX-H.

Naturally, there are alternative strategies to compute an upper bound on the
operating cost other than the two discussed above. For instance, the cost that
is obtained by solving a DC-OPF problem assuming that all switchable lines are
connected is also a valid bound. However, this cost lies in between those
computed by way of the naive and heuristic approaches. Consequently, in the
numerical experiments presented in Section IV, we only test these two.
Besides, in the procedure proposed in this paper, we utilize a maximum cost
constraint $\overline{C}$ as we aim to determine the optimal topology for
minimizing the operational cost. Nevertheless, this methodology could be
adapted to address problems where line switching decisions aim to optimize
alternative objective functions, such as mitigating the risk of wildfires [25,
26].

In the next section, we compare the performance of the four strategies
described above for each upper-bound cost using different metrics. For
instance, for each switchable line we compute the big-M range relative to that
determined in [4] as follows:

$\delta^{M}_{nm}=100\frac{M_{nm}+M_{mn}}{2M^{0}_{nm}}$ (10)

where $M^{0}_{nm}$ are the big-M values computed by (5) with the original
capacities. For instance, in the SP-OC benchmark approach,
$\delta^{M}_{nm}=100\%$ for all switchable lines. In the remaining methods,
$\delta^{M}_{nm}=80\%$ means that the big-M range has been reduced a 20% for
that particular switchable line. We can also compute an average value over all
switchable lines as

$\Delta^{M}=\frac{\sum_{nm\in\mathcal{L}_{S}}\delta^{M}_{nm}}{|\mathcal{L}_{S}|}$
(11)

Similarly, we can define the relative range of the power flows through any
transmission line as:

$\delta^{L}_{nm}=100\frac{F_{nm}+F_{mn}}{2F^{0}_{nm}}$ (12)

where $F^{0}_{nm}$ is the original line capacity. The average value is
computed as

$\Delta^{L}=\frac{\sum_{nm\in\mathcal{L}}\delta^{L}_{nm}}{|\mathcal{L}|}$ (13)

Apart from parameters $\Delta^{M}$ and $\Delta^{L}$, we also compare the four
strategies in terms of the computational burden required to solve model (3)
using the bounds obtained by Algorithm 1. Notice that the feasible region
defined by the tighter bounds is guaranteed to include the optimal solution
and therefore, the optimal decisions and objective function are the same for
all the methods that yield a solution in less than one hour.

##  IV Case study

This section provides an overview of the computational findings obtained from
the various methodologies discussed in Section III when applied to a practical
network. Our focus is on comparing the different approaches using a realistic
118-bus network, which consists of 186 lines as documented in [27]. This
network’s scale is significant enough to pose challenges for current
algorithms, yet it remains manageable in terms of computational complexity.
Moreover, the 118-bus system is the paradigmatic network commonly employed in
numerous studies on optimal transmission switching in the technical literature
[2, 3, 4, 8, 9, 10, 11, 13, 15]. Since the choice of the spanning subgraph can
notably impact the computational load of the resulting OTS problem, we
evaluate the performance of the proposed methodology for 100 instances with
different subsets of switchable lines and demand levels $d_{n}$. More
specifically, the spanning subgraph of 117 non-switchable lines is randomly
chosen and therefore, the 69 switchable lines are different for each instance.
Likewise, the nodal demand is randomly sampled using independent uniform
distributions in the range $[0.9\widehat{d}_{n},1.1\widehat{d}_{n}]$, where
$\widehat{d}_{n}$ is the baseline demand. In this way, we guarantee that the
results reported in what follows cover a range of OTS instances of different
complexity. All optimization problems have been solved using GUROBI 9.1.2 [19]
on a Linux-based server with CPUs clocking at 2.6 GHz, 1 thread and 8 GB of
RAM. In all cases, the optimality gap has been set to $0.01\%$ and the time
limit to 1 hour. We used the gurobipy API for Python to solve the problems,
with all Gurobi options set to default values.

Before presenting the computational results of this case study we must clarify
an implementation detail of Algorithm 1. In steps 2) and 3) of this algorithm
the corresponding bounding problems can be solved in parallel, then reducing
the final computational burden of the bound tightening procedure. However, the
results of this section are obtained by solving all bounding problems
sequentially and adding up the required time to solve each linear optimization
model. By doing so, the comparison of the computational burden of the
different models is more informative, especially if the number of iterations
is high. Besides, this strategy allows a dynamic update of the line capacities
and the big-M values. That is, the bounding problem corresponding to the k-th
line can be solved using the updated line capacities of the (k-1)-th line, and
so on.

After that clarification, we start this numerical analysis by fixing the
number of iterations (indicated in parenthesis for each method) to 1 and
comparing the four methodologies described in Section III combined with the
two strategies to compute the upper-bound cost. Table I collects, for each
approach, the big-M and line capacity relative ranges and the computational
time averaged over the 100 random instances considered including the time of
solving all the bounding problems sequentially ($T^{bnd}$) and the time of
solving the resulting mixed-integer DC-OTS problem ($T^{ots}$). This table
also includes the number of instances that are not solved to optimality in
less than one hour ($\\#U$), and the maximum optimality gap among those
unsolved instances. This optimality gap is provided by the solver and computed
as the relative difference between the best known upper bound and the best
known lower bound on the optimal objective value of the mixed-integer
optimization problem.

Method | $\Delta^{M}$ | $\Delta^{L}$ | $T^{bnd}$ | $T^{ots}$ | $\\#U$ | Max gap
---|---|---|---|---|---|---
SP-OC | 100% | 100% | - | 672s | 14 | 0.69%
BT-OC-N(1) | 68% | 100% | 0s | 589s | 12 | 1.69%
SP-RC-N(1) | 86% | 77% | 1s | 480s | 9 | 0.69%
BT-RC-N(1) | 68% | 74% | 1s | 486s | 8 | 1.04%
BT-OC-H(1) | 64% | 100% | 2s | 298s | 5 | 0.20%
SP-RC-H(1) | 83% | 73% | 3s | 234s | 2 | 0.47%
BT-RC-H(1) | 64% | 68% | 3s | 167s | 1 | 0.03%
TABLE I: Impact of upper-bound cost on bound tightening performance

If we compare the benchmark SP-OC with BT-OC-N(1), we observe that the big-M
values are significantly tightened, the average time is reduced by 12%, and
the number of unsolved problems is also lower. On the contrary, the maximum
gap increases from 0.69% to 1.69%. If the line capacities are reduced using
the bounding problems, approaches SP-RC-N(1) and BT-RC-N(1) also involve
computational savings that amount to 28% approximately. In any case, it seems
that using the naive upper-bound cost leads to quite modest computational
improvements.

In order to improve the performance of the bound tightening proposed in this
paper, the last three rows of Table I provide the results if the upper-bound
cost is obtained by the heuristic approach described in [8]. For the 100
instances of this case study, the average and maximum error incurred by this
greedy approach amounts to 2% and 11%, respectively. Consequently, despite the
valuable insights into generating costs provided by this heuristic procedure,
the obtained solutions still exhibit a significant degree of suboptimality. By
analyzing these results, we realize that using a tighter upper-bound on the
operating cost has a more notable impact on the computational burden of the
DC-OTS problem. For instance, even if the original line capacities are
considered, the approach BT-OC-H(1) is able to halve the computational time
and the number of unsolved instances yielded by SP-OC. Besides, even with one
iteration, the approach BT-RC-H(1) strengthens both the line capacities and
big-M values by solving the proposed bounding problems and consequently
reduces the computational time by 75% and only reports one unsolved instance.

We continue this case study by analyzing the impact of the number of
iterations through a comparison of the results collected in Table II.
Naturally, increasing the iterations leads to tighter bounds. However, the
bound values seem to stabilize after three or four iterations. It is also
relevant to highlight that, for the same number of iterations, BT-RC always
outperforms SP-RC, which clearly indicates that the big-M values obtained by
the bounding problems (7) are tighter than those computed by (5), even if the
line capacities are adjusted to more realistic values. In fact, the approach
BT-RC-H with one iteration yields better computational results than SP-RC-H
with four iterations. It is also worth mentioning that although SP-RC-H(2) has
tighter bounds than SP-RC-H(1), the former involves longer computational times
and a higher number of unsolved problems. This counterintuitive result is
attributed to the presolving and heuristic routines integrated into the
optimization solver. Finally, it is shown that the best results are provided
by BT-RC-H(4), an approach that achieves a time reduction of 88% and is able
to solve all instances in less than one hour.

Method | $\Delta^{M}$ | $\Delta^{L}$ | $T^{bnd}$ | $T^{ots}$ | $\\#U$ | Max gap
---|---|---|---|---|---|---
SP-OC | 100% | 100% | - | 672s | 14 | 0.69%
SP-RC-H(1) | 83% | 73% | 3s | 234s | 2 | 0.47%
SP-RC-H(2) | 77% | 69% | 4s | 337s | 5 | 0.37%
SP-RC-H(3) | 76% | 68% | 5s | 266s | 4 | 0.54%
SP-RC-H(4) | 75% | 68% | 6s | 206s | 2 | 0.25%
BT-RC-H(1) | 64% | 68% | 3s | 167s | 1 | 0.03%
BT-RC-H(2) | 56% | 63% | 5s | 82s | 0 | -
BT-RC-H(3) | 52% | 61% | 7s | 74s | 0 | -
BT-RC-H(4) | 50% | 59% | 8s | 72s | 0 | -
TABLE II: Impact of iterations on bound tightening performance

To conclude this case study, Figure 1 illustrates the number of instances
solved as a function of the computational time for the following three
approaches:

  * -

Proposed: This is the cost-driven bound tightening approach proposed in this
paper. Among all investigated methods, we choose BT-RC-H(4) since it is the
one that presents the best performance in the previous analysis.

  * -

Fattahi: This methodology proposed by Fattahi et al. in [4] is based on
determining the shortest-path through the spanning subgraph that connects the
two nodes of every switchable line. This is the benchmark approach SP-OC that
represents the state-of-the-art in the technical literature.

  * -

Gurobi: This strategy consists in solving the nonlinear OTS problem (1)
directly with Gurobi. Gurobi is able to handle the product of binary and
continuous products by using a big-M linearization with bounds that are
internally computed by the solver or by adding SOS1 variables.

This figure allows us to draw the following conclusions. First, the 100
randomized instances with varying spanning subgraphs and demand levels exhibit
a broad spectrum of computational difficulty. It is notable that Gurobi solves
40 “easy” instances in less than 500 seconds, while another 20 instances
categorized as “medium difficulty” require computational times ranging from
500 seconds to one hour. However, 40 instances classified as “difficult” are
not solved to optimality within one hour by this solver. Second, that the
general-purpose procedure to linearize the product of binary and continuous
variables implemented in Gurobi can be improved by using specific knowledge
about the problem to be solved. For instance, using the power flow equations
involved in the DC-OTS problem and graph theory, the shortest-path approach
proposed in [4] provide tighter bounds than those determined internally by
Gurobi to linearize the product of binary and continuous variables. Third,
although the benchmark SP-OC outperforms Gurobi, the obtained big-M values can
still be loose and therefore, the computational time can still be substantial
for some instances. Finally, that the proposed cost-driven bound tightening
methodology remarkably improves existing approaches and is able to solve the
100 random DC-OTS instances in less than 800 seconds and to reduce the average
computational time by 88% with respect to the state-of-the-art methodology.

$0$$500$$1{,}000$$1{,}500$$2{,}000$$2{,}500$$3{,}000$$3{,}500$$0$$10$$20$$30$$40$$50$$60$$70$$80$$90$$100$Time
(s)# Problems solvedProposedFattahiGurobi Figure 1: Comparison of the proposed
methodology with existing benchmarks

Finally, Table III summarizes the computational results of the proposed
methodology and existing benchmarks. These results demonstrate the superiority
of the bound tightening procedure we propose, with an average computational
time of 80 seconds, representing a speedup of 22x and 8x compared to Gurobi or
the approach described in [4], respectively.

Method | Time | $\\#U$ | Max gap
---|---|---|---
Gurobi | 1739s | 38 | 2.03%
Fattahi | 672s | 14 | 0.69%
Proposed | 80s | 0 | -
TABLE III: Summary of the computational results of the proposed methodology.

##  V Conclusions

The optimal transmission switching (OTS) aims at determining the network
topology that minimizes the generating cost to satisfy a given demand. The OTS
has the potential to generate substantial cost savings, but its computational
requirements are high due to its typical formulation as a mixed-integer linear
problem that belongs to the NP-hard class. In particular, the MIP formulation
of the OTS includes big-M constants that can lead to poor relaxations if their
values are too large. In this paper we propose an iterative tightening
methodology that effectively reduces the big-M values, thereby alleviating the
computational burden associated with the OTS. The proposed approach requires
the solution of inexpensive bounding problems that account for economic
information about the operating cost. Furthermore, the big-M values can be
further tightened by incorporating reduced capacities of the transmission
lines, which are in turn obtained by solving similar bounding problems. Using
the 118-bus test system, we demonstrate that our methodology outperforms
existing approaches to find proper big-M values and is able to reduce the
computational of the OTS problem by 88% in average with respect to them.

The proposed approach is dependent on the existence of a spanning subgraph of
connected lines. Therefore, extending this approach to handle the general
case, where any line can be disconnected, represents a promising direction for
future research.

## References

  * [1] R. P. O’Neill, R. Baldick, U. Helman, M. H. Rothkopf, and W. Stewart, “Dispatchable transmission in rto markets,” _IEEE Transactions on Power Systems_ , vol. 20, no. 1, pp. 171–179, 2005.
  * [2] E. B. Fisher, R. P. O’Neill, and M. C. Ferris, “Optimal transmission switching,” _IEEE Transactions on Power Systems_ , vol. 23, no. 3, pp. 1346–1355, 2008.
  * [3] B. Kocuk, H. Jeon, S. S. Dey, J. Linderoth, J. Luedtke, and X. A. Sun, “A cycle-based formulation and valid inequalities for DC power transmission problems with switching,” _Operations Research_ , vol. 64, no. 4, pp. 922–938, 2016.
  * [4] S. Fattahi, J. Lavaei, and A. Atamtürk, “A bound strengthening method for optimal transmission switching in power systems,” _IEEE Transactions on Power Systems_ , vol. 34, no. 1, pp. 280–291, 2019.
  * [5] C. Liu, J. Wang, and J. Ostrowski, “Heuristic prescreening switchable branches in optimal transmission switching,” _IEEE Transactions on Power Systems_ , vol. 27, no. 4, pp. 2289–2290, 2012.
  * [6] C. Barrows, S. Blumsack, and R. Bent, “Computationally efficient optimal transmission switching: Solution space reduction,” in _2012 IEEE Power and Energy Society General Meeting_. IEEE, 2012, pp. 1–8.
  * [7] M. Flores, L. H. Macedo, and R. Romero, “Alternative mathematical models for the optimal transmission switching problem,” _IEEE Systems Journal_ , vol. 15, no. 1, pp. 1245–1255, 2020.
  * [8] J. D. Fuller, R. Ramasra, and A. Cha, “Fast heuristics for transmission-line switching,” _IEEE Transactions on Power Systems_ , vol. 27, no. 3, pp. 1377–1386, 2012.
  * [9] C. Crozier, K. Baker, and B. Toomey, “Feasible region-based heuristics for optimal transmission switching,” _Sustainable Energy, Grids and Networks_ , vol. 30, p. 100628, 2022.
  * [10] A. Hinneck and D. Pozo, “Optimal transmission switching: improving exact algorithms by parallel incumbent solution generation,” _IEEE Transactions on Power Systems_ , 2022.
  * [11] E. S. Johnson, S. Ahmed, S. S. Dey, and J.-P. Watson, “A k-nearest neighbor heuristic for real-time dc optimal transmission switching,” 2020. [Online]. Available: https://arxiv.org/abs/2003.10565
  * [12] S. Pineda, J. M. Morales, and A. Jiménez-Cordero, “Learning-assisted optimization for transmission switching,” _arXiv preprint arXiv:2304.07269_ , 2023.
  * [13] Z. Yang and S. Oren, “Line selection and algorithm selection for transmission switching by machine learning methods,” in _2019 IEEE Milan PowerTech_. IEEE, 2019, pp. 1–6.
  * [14] T. Han and D. Hill, “Learning-based topology optimization of power networks,” _IEEE Transactions on Power Systems_ , 2022.
  * [15] S. S. Dey, B. Kocuk, and N. Redder, “Node-based valid inequalities for the optimal transmission switching problem,” _Discrete Optimization_ , vol. 43, p. 100683, 2022.
  * [16] K. W. Hedman, S. S. Oren, and R. P. O’Neill, “Flexible transmission in the smart grid: optimal transmission switching,” _Handbook of networks in power systems I_ , pp. 523–553, 2012.
  * [17] L. S. Moulin, M. Poss, and C. Sagastizábal, “Transmission expansion planning with re-design,” _Energy systems_ , vol. 1, pp. 113–139, 2010.
  * [18] M. Numan, M. F. Abbas, M. Yousif, S. S. Ghoneim, A. Mohammad, and A. Noorwali, “The role of optimal transmission switching in enhancing grid flexibility: A review,” _IEEE Access_ , 2023.
  * [19] Gurobi Optimization, LLC, “Gurobi Optimizer Reference Manual,” 2022. [Online]. Available: https://www.gurobi.com
  * [20] T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, _Introduction to algorithms_. Cambridge, Massachusetts: MIT press, 2022.
  * [21] P. Li, X. Huang, J. Qi, H. Wei, and X. Bai, “A connectivity constrained milp model for optimal transmission switching,” _IEEE Transactions on Power Systems_ , vol. 36, no. 5, pp. 4820–4823, 2021.
  * [22] L. A. Roald and D. K. Molzahn, “Implied constraint satisfaction in power system optimization: The impacts of load variations,” in _2019 57th Annual Allerton Conference on Communication, Control, and Computing (Allerton)_. IEEE, 2019, pp. 308–315.
  * [23] Á. Porras, S. Pineda, J. M. Morales, and A. Jiménez-Cordero, “Cost-driven screening of network constraints for the unit commitment problem,” _IEEE Transactions on Power Systems_ , vol. 38, no. 1, pp. 42–51, 2022.
  * [24] C. Chen, A. Atamtürk, and S. S. Oren, “Bound tightening for the alternating current optimal power flow problem,” _IEEE Transactions on Power Systems_ , vol. 31, no. 5, pp. 3729–3736, 2015.
  * [25] N. Rhodes, L. Ntaimo, and L. Roald, “Balancing wildfire risk and power outages through optimized power shut-offs,” _IEEE Transactions on Power Systems_ , vol. 36, no. 4, pp. 3118–3128, 2020.
  * [26] A. Kody, A. West, and D. K. Molzahn, “Sharing the load: Considering fairness in de-energization scheduling to mitigate wildfire ignition risk using rolling optimization,” in _2022 IEEE 61st Conference on Decision and Control (CDC)_. IEEE, 2022, pp. 5705–5712.
  * [27] S. Blumsack, _Network topologies and transmission investment under electric-industry restructuring_. Pittsburgh, Pennsylvania: Carnegie Mellon University, 2006.