extfieldsofstudy:
Mathematics
Computer Science

text:
Fair and Reliable Reconnections for Temporary Disruptions in Electric Distribution Networks using Submodularity

Increasing reliability and reducing disruptions in supply networks are of increasing importance; for example, power outages in electricity distribution networks cost \$35-50 billion annually in the US. Motivated by the operational constraints of such networks and their rapid adoption of decentralized paradigms and self-healing components, we introduce the"minimum reconnection time"(MRT) problem. MRT seeks to reduce outage time after network disruptions by programming reconnection times of different edges (i.e., switches), while ensuring that the operating network is acyclic. We show that MRT is NP-hard and is a special case of the well-known minimum linear ordering problem (MLOP) in the submodular optimization literature. MLOP is a special case of a broader class of ordering problems that often admit polynomial time approximation algorithms. We develop the theory of kernel-based randomized rounding approaches to give a tight polynomial-time approximation for MRT, improving the state-of-the-art approximation factor for a broad class of MLOP instances. Further, motivated by the reliability incentive structure for utility companies and operational energy losses in distribution networks, we propose local search over spanning trees to balance multiple objectives simultaneously. We computationally validate our reconfiguration methods on the NREL SMART-DS Greensboro synthetic network, and show that this improves service equity by a factor of four, across industrial and residential areas.

Introduction
Improvements in distribution network reconfiguration are motivated by the high societal cost of electricity interruptions. Despite investments from utility companies in improving reliability, service disruptions remain challenging [29], with the economic costs of power outages estimated between $35 billion and $50 billion annually in the United States [27]. Related studies on the Value of Lost Load (VOLL) give per-kilowatt-hour estimates ranging from several dollars to several hundred dollars, depending on the underlying methodology, customer type, and assumptions, and the Midcontinent Independent System Operator, one of the largest power system operators in the United States, uses a VOLL of $3.50 per kilowatt-hour [44,35]. These values are an order of magnitude larger than typical costs (around 10.5 cents per kilowatt-hour in the United States [47]), reflecting the importance of providing reliable electricity.
Since reliability is so valuable, industry groups recognize utilities using reliability metrics such as the System Average Interruption Duration Index (SAIDI), e.g., the ReliabilityOne Award and the American Public Power Association's Certificate of Excellence Award [39,1]. Some regulators implement explicit financial incentives. For example, the California Public Utilities Commission set a SAIDI target of 60 minutes for San Diego Gas & Electric [6]. Overperforming or underperforming this target beyond ±2 minutes was rewarded or penalized by $375,000 per minute up to a maximum of $3 million. Similar incentives exist in Great Britain, Italy, etc. [22,20]. Reducing outage time is an important way to improve a network's reliability metrics. After an isolated fault occurs in a system, causing an outage downstream in the network, it is crucial to quickly reconfigure the network to reroute power to the affected areas. Reconfiguration can potentially be executed long before the fault is manually repaired, reducing the outage duration for many customers. Much of the existing work in the academic literature focuses on centralized approaches for distribution network reconfiguration. In centralized approaches, information regarding distribution system operations, such as the location of a fault that is causing a power outage, is communicated to a central substation or control center which computes an appropriate switching configuration that is then communicated to each switch. In contrast, decentralized approaches have local controllers that operate solely based on local information. Solving a reconfiguration problem centrally with full information and control is simpler, but has speed, robustness, and security disadvantages [51,26]. For these reasons, protection and reconfiguration systems are moving towards an adaptive paradigm where components of the distribution system work together to detect and characterize failures and then restore the supply of power as quickly as possible, e.g., [36,34,50].
To this end, we propose a decentralized approach for automatically reconfiguring radial distribution networks to quickly restore power after a fault. Such models are classified as Fault Location, Isolation, and Service Restoration applications that embed "self-healing" features within Advanced Distribution Management Systems [46]. A variety of self-healing approaches use decentralized schemes; e.g., [31] isolate faults onto "islands" and use alternate paths to restore service, and [45] employ an internal timer for each switch, as in our model. We assume a network is given as a graph G = (V, E) with an initial radial tree T ⊆ E. We employ edges (e.g., switches in an electrical network) s ∈ S = E \ T that are not in the base radial network, each of which can detect abnormal flow patterns on its endpoints, and then activate to reconnect the network. Our decentralized approach operates by preassigning an ordering to the edges in S that describes how long each edge waits before attempting to activate. This formulation leads to a novel connection of network reliability to linear ordering problems from the submodular optimization literature.
Contributions. We summarize our contributions next. In section 2, we present our general graphical model for network flow and network disruptions. We give a novel system for reconnecting the network after a disruptive event by activating edges in a decentralized manner, according to a preprogrammed order. This model is based on the challenges seen in fault detection and protection systems in electricity distribution networks. We define the Minimum Reconnection Time (MRT) problem of finding the best activation order of edges. Different fine-based structures imposed on utility companies, such as SAIDI, can be written as objectives of instances of MRT.
We show in section 3 that MRT is in fact NP-hard, using a reduction from the tree augmentation problem (TAP) of selecting a minimum-cardinality subset F of a set of edges E such that T ∪ F is 2-edge-connected, where T is a given tree [9]. Next, we show that the MRT problem is connected to the field of submodular optimization (e.g., [32,13]), and in particular is a special case of the Min Sum Set Cover (MSSC) problem [14]. Submodular functions are a discrete analog of convexity and capture the property of diminishing returns, and so are widely used in applications such as scheduling [18] and network topology [38].
In section 4, we give an improved approximation factor of (2c/(c + 1)) 2 for MRT instances which are c-uniform, i.e., for each initial radial tree edge e ∈ T , there are at most c non-tree edges s ∈ S = E \ T such that T − e + s is connected. This improves on the best known approximation factor of 4 for c-uniform instances [14]. To achieve this improvement, we use fractional kernels within a kernel-based randomized rounding approach [42,17], which may be of independent interest. These kernels are based on discrete analogs of negative power functions, and are used to spread the weight of the relaxed optimal solutions across time. Since our kernel is fractional, the analysis of our method is more intricate and uses discrete calculus-like manipulations. We further show that the (2c/(c + 1)) 2 approximation ratio is tight (Theorem 4) for all c-uniform MSSC instances, with respect to the natural LP relaxation.
Given a network, the choice of tree T can have a large impact on the reconnection metrics and losses due to energy dissipation. For example, Figure 1 shows two different spanning trees on the 7-vertex wheel graph. The "spoke" network (left) achieves an objective value 3 2 for both R-Time (an outage metric we introduce) and SAIDI, while the "wheel" network (right) achieves objective value 1 for R-Time and 7 2 for SAIDI. Moreover, the choice of the initial tree determines the energy loss in the network, which can be as large as 5-10% of the total energy generation [48,54]. Energy loss is 6 in the "spoke" and 91 in the "wheel," where we assume each bus has a demand of one unit, lines have uniform resistance, and losses are proportional to the square of the power flow through each line. Moreover, we find that on the NREL SMART-DS Greensboro synthetic network, optimizing for R-Time induces an expected outage time for medium voltage buses that is 50% longer than when optimizing for SAIDI. Therefore, even the choice of objectives can have a non-negligible disparate impact on service for different "groups" in the network. Therefore, to optimize multiple metrics simultaneously, in section 5 we use local search techniques over the set of spanning trees with a multi-criteria objective that involves all three metrics of interest (SAIDI, R-Time, and energy losses). We show that the choice of optimization metric results in varying outage times for consumers at low and medium-voltage buses. Finally, in section 6, we test our methods on the NREL SMART-DS Greensboro synthetic network. By adding relatively few edges to the network (less than .2% of the number in the original network), prioritizing the heaviest-load areas, we show that we can improve connectivity to cover over 90% of load in the network. After adding edges, our local search methods significantly improve outage and energy metrics, with up to a 95% reduction in the product of R-Time, SAIDI, and energy loss and a nearly 60% reduction on average. As a byproduct, we show that the equity of service between industrial and residential areas (i.e., medium and low voltage buses) improves by a factor of at least 4. We believe that next-generation networks with self-healing capabilities will benefit from decentralized approaches, as well as multi-criteria optimization to balance various reliability metrics. Figure 2: An example of a network comprising a spanning tree (solid edges) and inactive edges (dashed edges).
Consider a network represented as a graph G = (V, E), with vertex set V and edges e ∈ E. Each edge can be active (allows flow) or inactive (no flow allowed, e.g., an open switch). We assume that there is a given initial configuration of active edges T ⊆ E which is a spanning tree on V and meets the flow demands in the network. Let r ∈ V be a designated root vertex (e.g., an electrical substation) which supplies the demand in the network to the other vertices. Initially, the network operates using edges in T , but once a disconnecting "event" occurs, e.g., a fault in an electricity distribution network caused by an isolated event [28], an edge goes from being active to being inactive. As a result, the set of active edges becomes a disconnected union of two trees.
When an event occurs at edge e ∈ T , causing it to become inactive, all vertices that receive flow via e will become disconnected from the root vertex r. Let R ⊆ V be the reachable set of vertices, i.e., those in the same connected component as r in the subgraph of G comprising the active edges. Activating an edge s ∈ S = E \ T could allow flow through s from R to V \ R. This is feasible if and only if e is in the unique cycle of T + s; in other words, T − e + s is a tree. In this case, we say that s covers e. To maximize service availability (for instance, before potentially time-consuming repairs necessary to reactivate e are completed), we would like to activate such an edge to restore flow as quickly as possible. We must do so while respecting the requirement that the connected component containing r is radial (i.e., has no cycles), which is an operational requirement often seen in electricity and gas networks [10].
Example. Consider the network in Figure 2. Vertex r is the root. Edges in T are solid and edges in S are dashed. Suppose an event occurs on edge e, deactivating it. Vertices v 2 , v 3 , v 4 , and v 5 will be without flow since they are no longer in the same component as the root r. If s 1 or s 2 are activated, then the flow would be restored. Activating s 3 would not restore flow, and activating both s 1 and s 2 simultaneously would violate the radial constraint.
In our model, choosing an edge to activate would be straightforward given perfect information on the status of the network and the ability to activate edges through a central planner. However, there is an increasing push in many settings for decentralized operations, where cheap components such as sensors can detect local changes to the operability of the network (e.g., an edge can detect whether it has flow going through itself). Based on this information, an automatic self-healing operation can be performed, such as activating an edge. Therefore, we consider the following localized and decentralized reconnection process. Each non-tree edge s ∈ E \ T has a sensor which can detect whether each of its incident vertices is receiving flow (i.e., is in the reachable set R). Upon detecting that exactly one of its incident vertices is in R, it waits for a preprogrammed number σ(s) of time steps. If during that period of time that status of its incident vertices with respect to R does not change, the edge activates itself.
To define the preprogrammed waiting times for each self-healing edge, we select a permutation . . , |S|}. If necessary, we choose time steps to be long enough that any changes in the network due to other edges activating, flow being restored, etc. will be detected by the sensors within one unit of time. This ensures that multiple edges do not activate in such quick succession that a cycle forms in the set of active edges. Note that any ordering σ will yield feasible values for σ(s) and eventually reconnect the network and restore flow safely if it is possible to do so (i.e., without creating a cycle), but we would like to do so as quickly as possible so as to minimize network reconnection fines and other operational objectives such as energy losses (as explained in the next section). We next discuss metrics for measuring network design and the effectiveness of a reconnection method.

Definition of metrics
To define metrics for reliability and self-healing capabilities in a network G = (V, E), we use additional data about the demand and flow in G. Each vertex v ∈ V has a demand w(v) ∈ R + . For each e ∈ E, let p(e) be the probability of an event which causes edge e to become inactive. Given a starting tree T which connects the vertices in the network to the supply vertex (root) r ∈ V , for all e ∈ T let D(e) be the set of vertices downstream of e, i.e., all v such that the unique path in T between r and v includes e. For all e ∈ T , let the total flow f (e) ∈ R + through e be the total demand of the vertices in D(e). Let the set of non-tree edges, that are initially inactive (e.g., switches), be S = E \ T . Finally, let t(e) = min s∈S:s covers e σ(s) be the time taken to reconnect the network and restore flow after e becomes inactive, where σ : S −→ [|S|] defines the waiting times for each non-tree edge s ∈ S. Note that w, p, D, and f are functions of the network configuration, while t depends on the network restoration methods, i.e., the choice of σ.
We define the reconnection time metric R-Time to be the expected time between an event and the reconnection of the network, without considering the demand at each vertex: .
We also define a metric weighted by the demand w(v) of the affected vertices, which recovers the commonly used System Average Interruption Duration Index (SAIDI) reliability index for power systems [19]: .
For instance, if the weight w(v) represents the number of consumers at vertex v, then SAIDI is the expected duration of time that an average consumer is without flow. Finally, we consider a base measure of loss in the network, which is not affected by the reconnection methods but can be a substantial operational cost and is a critical factor in network design. Each edge e ∈ E has a quantity r(e) ∈ R + , which depends on the physical properties of the corresponding object in the network (e.g., the electrical resistance of a wire). Then the total loss in the network is the quantity For example, in an electrical network, if we assume that vertex weight is proportional to power consumption, by Ohm's law the energy loss in any edge e ∈ T is r(e)f (e) 2 . (We do not consider more complex nonlinearities, e.g., AC power flow in an electric distribution network.) Similar concerns arise in gas and water networks, where when using the classical Darcy-Weisbach equation, the pressure loss for liquid flow in pipes is proportional to the length of the pipe and to the square of the velocity of flow [37,12]. 1

The Min Reconnection Time (MRT) problem
SAIDI and R-Time can be viewed as special instances of the objective of a new problem, Min Reconnection Time (MRT). The goal of MRT is to find an ordering of the inactive edges that minimizes a weighted expected time for T to be reconnected after an edge becomes inactive. That is, given a network G = (V, E), a spanning tree T over V with edge weights b : T −→ R + , and a set of inactive edges S = E \ T , the MRT problem is to find an ordering σ : S −→ [|S|] that minimizes We set the tree edge weights b(e) to reflect our choice of instance and metric. Setting b(e) = p(e), the resulting objective is the expected length of time to network reconnection, while setting b(e) = p(e)f (e) yields SAIDI (up to the constant factor of the denominator of those objectives). Therefore, any methods and results for solving MRT apply to the specific problems of finding a reconnection order to minimize either of these metrics.

Connections to the Minimum Linear Ordering Problem
In this section, we show that MRT is a special case of the Min Sum Set Cover problem, itself a special case of the Minimum Linear Ordering Problem on supermodular functions. We show that MRT is NP-hard using a reduction from the Tree Augmentation Problem. For ease and clarity of language, throughout the remainder of the paper we refer to the initial non-tree self-healing edges in S = E \ T as "switches," following the terminology for electricity distribution networks.

Notation and Preliminaries
We begin by reviewing some preliminaries needed for this section. A set function f : is a pair of a vertex set V and a hyperedge set E, where each hyperedge e ∈ E is a nonempty subset (of any size) of V . This generalizes the notation of graphs G = (V, E) where each edge e ∈ E is a subset of V containing exactly two vertices, i.e., e = (u, v) for u, v ∈ V . A hypergraph is said to be c-uniform if each hyperedge contains exactly c vertices. We denote linear orderings of a finite set V by σ : We show that MRT is an instance of the Minimum Linear Ordering Problem (MLOP) on supermodular functions, in particular the Min Sum Set Cover (MSSC) problem introduced by [14]. We first define the general form of MLOP: Definition 1. Given a ground set S and a function f : 2 S −→ R + , the MLOP is to find a linear ordering σ of S that minimizes To see how MRT can be viewed as a special case of MLOP, consider a spanning tree T of the underlying network G = (V, E). The goal is to order the ground set of switches S = E \ T to minimize the time for edges in T to be covered. For each switch s, let U s be the set of tree edges covered by s. Given a set of switches W ⊆ S, let f (W ) be the cardinality of the set of tree edges not covered by W , i.e., f (W ) = |T \ ∪ s∈W U s |. This function can be shown to be supermodular. At each time t = i, any edge not covered by the first i − 1 switches adds 1 unit to the objective function. As in MRT, the value of the set function f can be weighted by b(e), thus recovering R-Time or SAIDI as the objective. Any ordering that minimizes the MLOP objective also minimizes MRT. 2 Another special case of the MLOP is the Min Sum Set Cover (MSSC) problem, in which given a set of subsets S 1 , . . . , S k ⊆ S, we find an ordering of the S i such that the total waiting time for each element of the ground set S to be covered is minimized. As an instance of the MLOP, this problem uses the function f (U ) = |S \ ∪ i∈U S i | for U ⊆ V , which again is supermodular. We may view this instance using the hyperedges of a hypergraph H = (V, E), where each hyperedge e ∈ E is a nonempty subset (of any size) of the vertex set V . Taking the ground set to be the edge set E, the MSSC problem is formally stated as: The MSSC problem, given a hypergraph H = (V, E), is to find a linear ordering σ of the vertices V so that the total waiting time for each edge to be covered is minimized, i.e., Again, note that one can write an instance of MRT as an instance of MSSC by taking H to be the hypergraph with a vertex for each switch s ∈ S = E \ T and a hyperedge {s ∈ S : T − e + f is connected} for each tree edge e ∈ T . However, MRT instances form a strict subset of MSSC instances, so showing MRT is NP-hard requires additional argument.
. Then in any corresponding instance of MRT, for a set of switches S corresponding to the hyperedges of H to exist, tree edges e 1 , e 2 , e 3 must lie on a path, with a fourth tree edge e 4 incident to each of them. However, this is impossible.
NP-hardness also may not hold in special cases of MRT, for instance if G is planar. 3 There may also be more effective heuristics or stronger approximation guarantees if G is planar [53].

NP-hardness of Min Reconnection Time
To show the NP-hardness of the Min Reconnection Time problem (MRT), we show a reduction from another NP-hard problem called the Tree Augmentation problem, or TAP [9]. Given G = (V, E) and a spanning tree T ⊆ E on V , the objective of TAP is to find a minimum-cardinality set of edges F ⊆ E such that T ∪ F is 2-edge-connected. Compare this to MRT, in which an ordering σ (a solution to MRT) is guaranteed to restore power by time k if the subgraph of G containing the edges of T ∪ {s ∈ S : σ(s) ≤ k} is a 2-edge-connected graph. Thus MRT can be viewed as a timed version of TAP, much as MSSC is the timed version of ordinary Set Cover: the latter seeks to find the minimum number of subsets to cover a given set of elements [21]. Theorem 1. The tree augmentation problem can be reduced in polynomial time to the Min Reconnection Time problem, and the latter problem is therefore NP-hard.
Proof. Let G = (V, E) with spanning tree T be an instance of TAP, and let n = |V |, m = |E|.
We modify the instance to create a new graph G = (V , E ) with a new spanning tree T . Add 1 , v mn,2 }} be a set of edges which constitute mn disjoint 2-paths. Let P S = {{v, v 1,2 }, . . . , {v, v mn,2 }} be a set of mn edges, and note that for and give all edges e ∈ T weight b(e) = 1 and all edges e ∈ P T weight b(e) = 1/2.
Let σ be an optimum solution to MRT on G = (V , E ) with tree T . The newly added switches {v, v 1,2 }, . . . , {v, v mn,2 } are the only switches that cover edges in P T . Furthermore, these switches each cover tree edges of total weight 1, and since all edges in T have weight 1, without loss of generality we may assume that the switches in P S are the last mn switches in σ that contribute a positive quantity to the objective OBJ(σ) of σ as a solution to MRT. Let the switches chosen before those mn switches be s 1 , . . . , Then the objective value of σ is We construct another solution σ * to MRT on G and T as follows.
Without loss of generality, assume that (if not, we can permute the indices of the f i to make this so). Let σ * be a permutation of E \ T such that Therefore, which would contradict the optimality of σ. Therefore, there is no such solution {f 1 , . . . , f k * } to TAP on G and T using k * < k edges, and so {s 1 , . . . , s k } is an optimum solution to the original TAP instance. Since G and T have size polynomial in the size of G and T , this gives a polynomial-time reduction of TAP to MRT, and thus MRT is NP-hard.

Approximation algorithms for MRT
We next discuss methods for solving MSSC and MRT with provable approximation guarantees. We first show that the greedy algorithm is not optimal for MRT, and then develop new fractional kernels for extending the alpha-point rounding method for MSSC introduced in [2].

The greedy algorithm
Since an instance of MRT is an instance of MSSC, a natural question is to ask if the greedy algorithm [14] gives a good approximation factor for the MRT as well. For each i from 1 to |S|, the greedy algorithm chooses σ −1 (i) = argmax s∈S e∈T s covers e σ j does not cover e,∀j<i b(e); that is, σ −1 (i) is the edge in S which covers the uncovered tree edges with greatest total weight. [14] showed that the greedy algorithm is a 4-approximation for general MSSC, and that this bound is tight.
There exist instances of MRT where the greedy algorithm does not find an optimal solution, and we construct instances with a gap of 4/3. We suspect that the greedy algorithm achieves an approximation ratio of strictly less than 4 on MRT instances.
Example 1: Consider the leftmost network in Figure 3. Edges in T are shown solid, while edges in S are dashed. Let ε = 1 and let p(e) = 1 for all e ∈ T . Then an optimal solution to MRT on this is to take the edges of S in order σ = (s 2 , s 3 , s 1 ), yielding objective value 3/2. However, the greedy algorithm, breaking ties lexicographically, will take σ = (s 1 , s 2 , s 3 ), yielding objective value 7/4, a multiplicative gap of 7/6. Example 2: Another instance when the greedy algorithm is not optimal is depicted in Figure 3 (right). Again, let ε = 1 and let p(e) = 1 for all e ∈ T . Then an optimal solution to MRT is σ = (s 4 , s 5 , s 2 , s 6 , s 7 , s 1 , s 3 ), yielding objective value 27/12. However, the greedy algorithm, breaking ties lexicographically, selects σ = (s 1 , s 2 , s 3 , s 4 , s 5 , s 6 , s 7 ), yielding an objective value of 36/12, a 4/3 multiplicative gap to the optimum. In this network, the edge e between v 3 and v 4 is covered only by edge s 7 , so any optimal ordering on S can take s 7 as the last edge σ −1 (i) that covers an edge not covered by σ −1 (1), . . . , σ −1 (i − 1). In this sense, the existence of e does not make solving the MRT problem any more difficult. However, if e is removed from G, the multiplicative gap shrinks to 29/22.

Kernel-based rounding for c -uniform MRT instances
We next show how to improve the approximation ratio for Min Sum Set Cover, including MRT, by extending a recent technique called kernel-based alpha-point rounding [2]. Unlike the approach taken by Bansal et. al, we use fractional kernels within a kernel-based randomized rounding approach [42,17], which may be of independent interest. In particular, we improve approximations for c-uniform instances of MSSC.
Given an MRT instance with every switch covering at most c edges of the underlying operational radial network, we first convert such an instance to a minimum sum set cover (MSSC) instance on a c-regular hypergraph (by analogy to the 3-layered zones of protection [3,15], we expect that tree edges are usually covered by a small number of switches). For these instances, our new kernels interpolate the above mentioned approximation factors from 16/9 ≈ 1.778 to 4, dependent on c. Therefore, these kernels strictly improve the state-of-the-art factors for MSSC instances. Figure 3: Two networks where the greedy algorithm for MRT does not achieve the optimum value.
The kernel-based α-point rounding method begins by finding a solution x to an LP relaxation of the following integer program. 4 The formulation encodes MSSC using binary variables x v,t to denote whether vertex v is chosen at time step t.
t u e,t = 1 ∀e edges, all u e,t , x v,t ≥ 0 for vertices v, time t and edges e.
If the variables u e,t , x v,t are binaries, then indices t ∈ [|V |] denote the index in the selection order σ, so that σ(v) = t if and only if x v,t = 1. Variables u e,t denote the time t at which edge e is covered.
Each edge e must be covered at some time t, and at each time t, at most one vertex can be chosen. The LP relaxation can be solved in polynomial time. We apply a kernel K(t, t ) to x to obtain new weights z. Applying α-point randomized rounding, we obtain a provisional schedule of selection times τ for all vertices v, then convert this list to our desired ordering σ by taking the vertices in the order in which they appear in τ , breaking ties at random. Pseudocode for this algorithm appears in Algorithm 1.
[2] obtained a 4-approximation for MSSC using K = 2/t · 1[t ≥ t ], and a 16/9-approximation for the minimum sum vertex cover problem (MSVC) using In contrast, to attain tight guarantees for MSSC on c-uniform hypergraphs, we consider a new kernel of the form K(t, t ) = 2c Algorithm 1 Kernel α-point Rounding for MSSC [2] 1: τv ← the earliest time t for which t ≤t z v,t ≥ αv 8: return an ordering σ of V , scheduling vertices according to τ and breaking ties at random. tentative schedule uses discrete calculus-like manipulations of the kernels, and requires close bounds on their sums. These are significantly more intricate when dealing with the fractional powers of t used in our kernels. Our bounds on the total cumulative weight assigned to the vertices of an edge e require additional convex analysis, including two more inequalities (Lemmas 2 and 3).
c+1 ) 2 approximation for the Min Sum Set Cover problem on H.
Proof. As defined in the algorithm, let z s,t = t K(t, t )x s,t be the weight assigned to any vertex s and time period t after rounding. Fix a hyperedge e ∈ E. Let e = {v 1 , . . . , v c }. Let z e,t = c i=1 z v i ,t be the total weight of vertices covering e at exactly time t, after applying the kernel K to the LP solution x, and let z e,<t = t <t z e,t . Let q t (e) = P [e is not scheduled before time t in τ ], and define p t (e) = ((1 − z e,<t /c) c ) + , which we will show is an upper bound on the former probability.
Define the cost of covering e ∈ E in the LP (c x (e)), a bound on the time e is scheduled in the tentative order τ (c z (e)), and the cost of covering e in the final order σ (c σ (e)) as:  The LP objective is e∈E c x (e) and the objective value of the ordering returned by α-point rounding is e∈T c σ (e). Therefore, it suffices to show that ( 2c c+1 ) 2 c x (e) ≥ c σ (e) for all e ∈ E. To do so, we separately show that ( 2c c+1 )c x (e) ≥ c z (e) and ( 2c c+1 )c z (e) ≥ c σ (e). Part A. We would like to show first that ( 2c c+1 )c z (e) ≥ c σ (e). The following argument can be generalized to a variety of kernels for α-point rounding. 5 We apply it with β = 2c c+1 . Claim 1. For the kernel K(t , t) = 2c Claim 2. The quantity p t (e) = ((1 − z e,<t /c) c ) + upper-bounds q t (e) and is 0 for sufficiently large t: For all v, we have that where (7) follows since without loss of generality we may assume that in the solution of the linear program for MSSC, each vertex v is selected with total weight 1 across all time steps.
so p t (e) = 0 for sufficiently large t. Moreover, by the arithmetic mean-geometric mean inequality, we have that q t (e) is bounded above by p t (e), since Each term of this sum corresponds to the event that e is scheduled at exactly time t in τ . This happens with probability q t (e) − q t+1 (e). The quantity S(t) = 1 + β(t − 1) − z e,<t + (β − z e,t )/2 is an upper bound on the expected number of vertices selected in σ before and including the one that covers e. By Claim 1, in this quantity: • 1 corresponds to the first vertex which covers e.
• β(t − 1) − z e,<t is an upper bound on the expected number of vertices scheduled in τ before e is covered. Indeed, that quantity is v ∈e z v,<t ≤ β(t − 1) − z e,<t .
• In expectation, at most β vertices are scheduled at exactly time t in τ , of which (β − z e,t ) do not cover e. In expectation, at most half of these vertices will be scheduled in σ before e is covered since ties are broken at random, yielding the bound of (β − z e,t )/2.

S(t)
is non-decreasing with respect to t. For each t, replacing q t (e) with p t (e) increases the right-hand side of Equation (8) by (p(t) − q(t))(S(t + 1) − S(t)) > 0. Therefore, since p t (e) is positive for a finite number of t (Claim 2), replacing all q t (e) with the corresponding p t (e) can only increase the sum, and therefore holds if and only if each of the following inequalities holds. We prove the last of these in Claim 4.
Part B. We would now like to show that (2c/(c + 1))c x (e) ≥ c z (e).
For all vertices v, we have that To analyze this sum, we use the following lemma, which we prove in Appendix B.
Examining the inner sum t−1 q=t K(q, t ) more closely and applying Lemma 2 with p = 2/(c − 1), we have that and so We now modify the LP solution x in order to bound c z (e). These modifications do not decrease our lower bound c z (e) and do not increase the LP cost c x (e). First, decrease x as necessary so that Second, for all t, replace each x v i ,t by their average value a t = c i=1 x v i ,t /c. As c z (e) depends only on the total c i=1 x v i ,t and not the distribution of weight between these vertices, this does not change c z (e). Then our goal is to show that for all nonnegative a with ||a|| 1 = 1, For each t, the corresponding summand (1 − d · a) c is positive and a convex function of a, since the vector d given by (d) t = t /t · 1[t < t] satisfies ||d|| ∞ ≤ 1. Therefore c z (e) is a convex function of a. Moreover, c x (e) is a linear function of a. Therefore, by Fact 8 of [2], the quotient c z (e)/c x (e) is maximized at an extreme point a of the positive simplex, i.e. for some u, a u = 1 and a u = 0 for u = u. At this point a, we have that 2c/(c + 1)c x (e) = 2c/(c + 1)u and Therefore, c z (e) ≤ 2c/(c + 1)c x (e) as desired.
We show that the approximation guarantee for c-uniform hypergraphs extend to all hypergraphs H in which each edge contains at most c vertices. In the MRT problem, this corresponds to networks in which each tree edge is covered by at most c switches. Proof. For each edge e with fewer than c vertices, modify H by adding additional dummy vertices belonging only to e, until e has exactly c vertices. Solve the LP on the resulting c-uniform hypergraph H . The objective value of the LP on H is the same as the objective value of the LP on the original hypergraph H, since assigning all weight given to a dummy vertex at a given time to a non-dummy vertex which covers the same edge cannot increase the LP objective. To obtain a solution σ , apply α-point rounding with kernel to the LP solution on H . By Theorem 2, or Theorem 22 of [2] if c = 2, the expected objective value of σ is at most ( 2c c+1 ) 2 times the LP objective. Finally, convert σ into an ordering σ of the vertices of H as follows. For each dummy vertex in σ , exchange its place in the ordering with a non-dummy vertex later in the ordering which covers the same edge. When no more such exchanges can be made, remove the dummy vertex from the ordering. This procedure cannot increase the time at which each edge e is covered, and hence cannot increase the objective. Therefore, the expected objective value of the resulting ordering σ of the vertex set V is at most ( 2c c+1 ) 2 times the LP objective. We further show that this approximation ratio is tight with respect to the natural LP relaxation, thus generalizing Lemmas 26 and 27 of [2]. Theorem 4. The integrality gap of the LP for MSSC on c-uniform hypergraphs (c ≥ 2) is at least ( 2c c+1 ) 2 . Therefore, if the LP relaxation is used as a lower bound for any approximation algorithm, one cannot hope to do better than ( 2c c+1 ) 2 . We include a detailed proof in Appendix C. The key idea of the proof is to construct a c-uniform instance out of the union of disjoint complete c-uniform hypergraphs of varying sizes. The LP relaxation can efficiently cover each hypergraph by assigning each vertex weight 1/c, thus covering each complete c-uniform hypergraph on n vertices in time n/c. In contrast, any integral solution must select all but (c − 1) vertices in each of the complete hypergraphs, which takes n − c + 1 time steps. By constructing instances from increasingly large numbers of increasingly large complete c-uniform hypergraphs, the ratio between the objective values of these two solutions approaches (2c/(c + 1)) 2 . This ratio matches the approximation guarantee of Theorem 2, and approaches the general approximation ratio of 4 as c → ∞. These guarantees are worst-case. Computationally (Section 6.3) we find that the greedy algorithm and the α-point rounding approaches are competitive, usually within 5% of the optimal solution as found by solving the IP.

Balancing multiple reliability and energy loss metrics
Different choices of the initial spanning tree T ⊆ E and reconnection order σ on S = E \ T can have widely diverging performance on R-Time and SAIDI, as well as energy costs dependent on the choice of the tree (see, for example, the system in Figure 1). Moreover, as we discuss in Section 6.1, the choice of optimization metric will affect the expected reconnection times of various types of buses (e.g. in residential or commercial area) differently.
In this section, we give a local search method for choosing a spanning tree T ⊆ E. The idea of local search for maximizing monotone submodular functions goes back to [7]. Our objectives require us to minimize a product of sums of supermodular functions over changing network topologies, thus making analysis of the process more difficult.

Branch exchange local search
Since we would like to simultaneously minimize all three objectives as best as possible to decrease loss of energy and improve service reliability across all customers, our goal is to find a single choice of T and σ that achieves strong performance on all three objectives. This becomes a multi-objective optimization problem, which we model as a composite objective SAIDI · R-Time · Energy = e∈T f (e)p(e)t(e) v∈V w(v) · e∈T p(e)t(e) e∈T p(e) · e∈T r(e)f (e) 2 , then apply the well-known spanning tree local search heuristic branch exchange.
The branch exchange search takes as input a network G with initial spanning tree T 0 and an objective function F (T, σ), which can be a combination of multiple metrics on T (such as energy) and σ (such as R-Time and SAIDI) [8]. In each iteration, the local search tests a random pair (e, s) ∈ T × S that is feasible (i.e., T = T − e + s is still connected). The algorithm then generates an order σ on the new set of switches S + e − s and compares the new objective value F (T , σ ) to the current value F (T, σ). If the objective is improved, the exchange is accepted; otherwise, sample another pair and repeat, until there is no improving step. The component of the composite product objective that depends on σ , SAIDI · R-Time, can no longer be written an instance of MRT. Therefore, we use a version of the greedy algorithm to choose σ , where at each step we choose the switch s achieving the greatest marginal increase in the product of the weights p(e)f (e) and p(e) used for SAIDI and R-Time, respectively.
A single local search step may check dozens or hundreds of possible branch exchanges, and for each possible exchange, the connectivity information needed for computing reconnection orders changes. Over networks of practical interest, existing methods for detecting cycles are very slow. In Appendix D, we give a method for updating connectivity which achieves a factor of Ω(min{|E −T |, |V |/d}) speedup, where d is the length of the longest cycle in G.
If the objective function is chosen to be linear in the weights b(e) of the edges, for instance a linear combination of the R-Time and SAIDI objectives, then it is possible to find an optimal spanning tree and reconnection order with an integer programming formulation (Appendix G). However, this program is large and solving it is intractable for larger networks.

Computations
In this section, we test our methods for improving outage metrics on the Greensboro, NC urbansuburban synthetic network from the NREL SMART-DS project to evaluate the performance of our α-point rounding and local search methods. All our code is available via github , where we have included the relevant data from NREL SMART-DS dataset in an accessible CSV format.

Greensboro dataset
The NREL SMART-DS synthetic network covers most of the Greensboro area, including residential, industrial, and other areas, and contains 145052 buses [40]. The network contains demand data for each bus, which we treat as the vertex weights w(v), and lines between buses. We take the failure probability p(e) of each line e to be proportional to the straight-line distance between its endpoints, as in practice, failure rates tend to be proportional to length [4]. The network contains 19 distinct connected components. Of these, 18 correspond to radial distribution networks, each with its own substation, while the other links the substations. We apply our methods to each of the 18 distribution networks, treating them as entirely separate and independent networks. Some components of the Greensboro network have over 10,000 vertices each. Before performing experiments, we preprocess the network to simplify and reduce its size while retaining key information about its structure. For instance, we remove low-demand degree-1 and degree-2 nodes by contracting incident edges and distributing their demands to neighboring vertices. These steps eliminate leaves and bridge vertices corresponding to buses with low weight. See Appendix E. Repeatedly applying these steps significantly reduces the size of the network. Using a threshold of W = 10 kW on the Greensboro network, the resulting contracted trees have an average of 17% of the the number of nodes of the original trees. These simplifications primarily consist of contracting leaves corresponding to low-demand buses in residential areas, and do not significantly change the network topology.

Adding switches
The synthetic network has only 108 switches (non-spanning tree edges). To increase coverage, we introduce additional switches, aiming to maximize coverage while minimizing the number and length of the added switches. To do so, we use a two-step procedure for each contracted component. We generate a large set R of candidate switches of length less than some . One can solve a redundancy allocation problem to find an optimal set of additional switches S ⊆ R, for instance [41], but for our purposes, a simple greedy algorithm suffices to choose switches that provide good coverage while being inexpensive to construct. Define the exposure of each edge e ∈ T to be x(e) = f (e)p(e), its coefficient in SAIDI. At each step, the algorithm adds the switch s that maximizes the weighted coverage e covered by s 2 −|{t∈S:t covers e}| x(e). For most components, excellent coverage (over 90% of total exposure) can be achieved by setting = 1000m and adding at most 20 switches from S. Figure 4 shows how coverage improves as the number of switches added increases, and how this depends on the choice of . By adding a number of switches equal to an average of 0.18% of the total number of tree edges in each component, we are able to cover 90% of SAIDI exposure.

Approximations for MRT
Having computed switch sets S for each component network using a maximum length of 1000m, we examine reconnection orders for R-Time and SAIDI. To do so, we compare three different approaches for solving MRT: (i) greedy algorithm, (ii) α-point rounding on a linear program solution, and (iii) the integer program. Greedy is extremely computationally inexpensive (hence our use of it in our local search algorithms) and solving the LP takes the majority of the time for α-point rounding. On many components, solving the IP was of comparable speed to α-point rounding, but on some it took much longer. Table 6.5 gives statistics on the 18 distribution networks and their outage metrics when using the IP for MRT to minimize R-Time and SAIDI in turn. For the reconnection orders σ corresponding to each objective, we compute the values of both metrics. The choice of objective matters substantially. The value of SAIDI is on average more than 22% greater when the MRT objective is R-Time than when its objective is SAIDI, and the value of R-Time is on average almost 10% greater when SAIDI is the objective than when R-Time is the objective. Figure 4 compares the performance of the three methods, expressed as a percentage difference relative to the LP objective. For each method, the solid line shows the average performance across the 18 components, and the dotted lines show the best and worst performance over all components. For α-point rounding, 500 sets of samples of rounding points α s were taken for each component and each value of c in K(t, t ) = 2c/(c − 1)(t(t + 1) 2/(c−1) ), and the sample yielding the best objective value was chosen. Note that α-point rounding performs best for small values of c where the kernel decays more aggressively, resulting in a solution that tends to be closer to the LP solution, even when some edges in the tree are covered by many switches and the applicable approximation guarantees do not hold. Overall, both polynomial-time methods are competitive, usually within a few percentage points of the optimum, with the greedy method sometimes obtaining the optimal solution and sometimes being outperformed by α-point rounding.  Table 1: Graphical data and outage metrics for the 18 distribution networks. The gaps are the relative increase in objective (the starred metric) from using the integer programming formulation to optimize for the other metric.

Choice of optimization metric
Of the 145052 buses in the network, 63 run at a medium voltage (MV) with a demand of at least 700 kW, while the rest run at a low voltage (LV) with demand of at most 350 kW. The MV buses correspond to commercial and industrial areas, while most LV buses occur in residential areas. Minimize SAIDI will tend to prioritize outages affecting the higher-demand MV buses, whereas minimizing MRT will prioritize restoring power to the more numerous LV buses. Indeed, optimizing for SAIDI produces an 8% longer expected outage time for LV buses compared to optimizing for R-Time (2.70 units, when optimizing for R-Time and 2.91 units when optimizing for SAIDI), but a 33% reduction in expected outage time for MV buses (3.86 units when optimizing for R-Time and 2.57 units when optimizing for SAIDI).

Local search for multi-objective optimization
In the branch exchange for local search, for any potential exchange of e ∈ T and s ∈ S, the energy cost is easy to compute. To compute the value of SAIDI · R-Time efficiently we use a greedy approach, where for each time step i we choose the switch s which achieves the greatest marginal increase in the objective SAIDI·R-Time. Figure 6 (left) shows the results of 25 different applications of local search to each component of the Greensboro network, each stopping after 100 exchanges or when a local optimum was reached. For each component, we take the local search run achieving the best product and express the value of each objective at each step as a ratio to its initial values on that component. Finally, we plot the average of these ratios over time for all 18 components. Since the possible branch exchanges are sampled randomly, the results of the local search can vary across multiple runs.  losses decreasing by 85%, SAIDI by 43%, R-Time by 17%, and their product by 93%. Similar plots for other components are included in Appendix F, with some variation in the degree of improvement using local search.
Moreover, we find that as an artifact of the local search, reliability across groups of nodes improves, and the gaps in the expected outage time decrease significantly. Recall that the outage time of a vertex v is e:v∈D(e) p(e) min s∈E\T : s covers e σ(s), where D(e) is the set of edges in the unique path in T between e and the vertex r corresponding to the substation, p(e) is the probability of a fault occurring on edge e, and σ is the reconnection order selected by the greedy algorithm to minimize the product of R-Time and SAIDI. Note that our objectives are not defined with respect to any grouping of nodes by demographic or voltage size 6 . However, we find that the difference in expected outage time for medium and low voltage nodes (i.e., industrial and residential nodes, respectively) decreases significantly. For instance, in component 18, which has the most medium voltage nodes (eight) of any component, low voltage nodes had an expected outage time on average 53.3% greater than that of medium voltage nodes, and modifying the base tree using local search reduced this gap to 12.3%. This improvement in service equity is evident from the histogram of expected outage times for all the nodes in the network (see Figure 5).

Conclusion
We analyzed a decentralized self-healing approach for automatically reconfiguring a distribution system into an operational radial network after a fault occurs by creating an ordering in which switches automatically close upon detection of a downstream fault. The choice of the switches' waiting times, which requires small intervals between each switch's assigned times to avoid creating cycles in the network, is equivalent to choosing a reconnection ordering. The choice of this ordering significantly impacts the expected time to reconnect under normal disruptions and thus affects reliability metrics such as SAIDI, which are the basis for regulator-imposed financial incentives for performance. We modeled SAIDI and expected reconnection time R-Time using a new problem called Min Reconnection Time (MRT), which we showed is a special case of the well-known minimum linear ordering problem. We showed that MRT is NP-hard and generalized the kernel-based rounding approaches of Bansal et al. to interpolate approximation guarantees from 9/4 to 4 dependent on the coverage of each tree edge. Finally, using local search, we optimized multiple metrics simultaneously on the NREL SMART-DS Greensboro dataset, thereby giving a proof of concept that branch exchange might be implemented efficiently using proxies for MRT subproblems.
We demonstrated that the choice of outage metric during the optimization process has a large impact on the behavior of the reconnection order. Optimizing for SAIDI resulted in a 33% reduction in reconnection time for the medium voltage buses that occur in commercial and industrial areas, while optimizing for R-Time reduced reconnection time in the more numerous but lower-demand low voltage buses. Depending on the priorities of the network designers, incorporating both metrics into the optimization process, as we do in our branch exchange local search, may be appropriate.
Our work raises interesting theoretical and practical open questions. First, it is open if the greedy algorithm for MRT attains a worst-case ratio better than 4-factor, as our experiments suggest. Second, local search is currently well-understood for maximization of submodular functions under matroid base constraints [7], but our local search minimizes the product of supermodular functions over the matroid base constraint. This seems to be a non-trivial extension, and we leave it as an open question. Lastly, we hope that our work provides a starting point for analyzing multiple simultaneous failures in the network, a situation that might be interesting for major disruptions in practice. cover and generalized min sum set cover. In: Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 998-1005. SIAM (2021)

A Motivation from electrical distribution networks
Our graph-based model is a simplified representation of the distribution network compared to the model used in, for instance, power flow studies that additionally involve information about the line reactances, reactive demands, capacitor susceptances, etc. [23]. While precluding details such as reactive power injections and voltages, our approach enables application of the graph theoretic concepts that are the basis for this paper's methodology. 7 In the network G = (V, E), vertices v ∈ V correspond to buses and edges e ∈ E correspond to lines. The initial configuration of the network is a spanning tree T , with the edges that are initially inactive corresponding to the set of switches S = E \ T . We specify a reconnection order σ : S −→ [|S|] on the switches. Events which cause tree edges to become inactive correspond to electrical faults. Reconnecting the network by activating an edge corresponds to closing a switch on a line not in T , thus energizing it. The constraint of energized lines forming a radial structure is common in distribution networks [30,52,23]. It is particularly crucial to maintain this structure after a fault, as otherwise we risk energizing the fault.
Some edges have breakers which will trip and stop flow in the event of a nearby fault, thus isolating it even after the network is reconnected and power is restored to vertices that had lost it. In general, not every edge will have a breaker, but if necessary we can preprocess the graph by contracting each set of connected edges in T that has only one breaker to a single edge e . We set the probability p(e ) that e experiences a fault in a given time period to be the sum of the fault probabilities p(e) of the contracted edges.
After a fault, every bus receiving flow will have positive voltage, and the others will have zero voltage; the sensors and relays employed on switches s read the voltages of the incident buses to determine whether they are receiving power and thus decide whether to wait σ(s) time before closing if one bus still has zero voltage. Such relays may be expensive, but installing them on a small number of lines is feasible for current distribution systems [5].
Therefore f (t + 1) ≥ f (t) + 1/p, and from Equation 9 we have that which completes the induction.

C Proof of the Integrality Gap in Theorem 4
Proof. For a suitable k = ω(1) and i = 1, . . . , k, let n i = N i −α where α = 2/(c + 1) + ε, with ε approaching 0 and N large enough that n i can be rounded without affecting the solution. Let H be the hypergraph consisting of disjoint copies of the complete c-uniform hypergraphs K i on n i vertices.
We first upper-bound the LP cost of MSSC on H. Setting gives a feasible solution. In this solution, each edge e in K i is completely covered by time (n 1 + · · · + n i )/c, and so the LP objective is at most As we make ε arbitrarily small, Thus, the objective of the LP solution is at most This gives a bound of approximately N c+1 /c!c(c − 1)ε for the LP solution for sufficiently small ε and large k.
Next, we show that the greedy algorithm gives an optimum solution to MSSC on H, and lower-bound the cost of this solution. In any solution σ to MSSC, the jth vertex selected from K i covers n i −j+1 c hyperedges that had not been covered before. Therefore, the order of vertices chosen within each K i does not matter, and permuting the order in which vertices from each K i are chosen relative to each other does not change the number of hyperedges those vertices cover. Thus and tree edges e the tree T − e + s remains connected. During the local search procedure, T and S = E \ T will evolve, requiring connectivity updates at each step. Indeed, updating this information, which is input to the greedy algorithms for MRT, is significantly more computationally expensive than executing those algorithms, computing energy costs, and comparing the objective values to evaluate whether to accept a branch exchange. This information is useful in filtering and efficiently choosing (at random) feasible branch exchange pairs (e, s).
In this section, we give a description of those pairs of tree edges and switches whose connectivity data might change after a branch exchange update. Updating only these pairs improves the computational efficiency of this step significantly: by a factor of Ω(min{|E − T |, |V |/d}), where d is the circumference, or length of a longest cycle in G.
Consider a branch exchange update on T ⊆ E. This update replaces T with T = T − e + s e , where e ∈ T , s e ∈ E − T , and T is connected. That is, it exchanges the tree edge e for the switch s e , yielding the new spanning tree T . To compute a reconnection order on the new set of switches E − T , whether by the greedy algorithm or an integer program, it is necessary to know the covering data of G and T , i.e. for which pairs (f, s) of edges f ∈ T , s ∈ E − T the graph T − f + s is connected. If we have already computed the covering data for G and T , to update this list for T it suffices to consider only those pairs (f, s) excluded by the following lemma.
Lemma 4. Let G = (V, E) be a graph and let T ⊆ E be a spanning tree of G. Let e ∈ T , s e ∈ E − T be an edge and a switch such that T = T − e + s e . Then, all covering data for T also hold for the new spanning tree T , except the following pairs (f, s): (i) f is in the unique cycle C e in T + s e and the unique cycle C s in T + s contains e.
(ii) f is in the unique cycle C e in T + e and the unique cycle C s in T + s contains s e .
In other words, T − f + s is connected if and only if T − f + s is connected, for all other such pairs of edges (f, s).
To prove this result, we show a second lemma: Lemma 5. Let G = (V, E) be a graph and let T ⊆ E be a spanning tree of G. Let s e , s f ∈ S = E − T and let C e , C f be the unique cycles in T + s e , T + s f , respectively. Let e ∈ C e ∩ T and f ∈ C f ∩ T . Then if e ∈ C f or f ∈ C e , T − e − f + s e + s f is connected.
Proof. By symmetry, it suffices to show the result when e ∈ C f . By hypothesis, T − e + s e is a spanning tree on G. Let u and v be the two vertices incident to f . Then T − e − f + s e has two connected components, one containing u and one containing v. Therefore, it suffices to show that there is a path between u and v in T − e − f + s e + s f . Indeed, C f − f is such a path, since e ∈ C f . Thus T − e f + s e + s f is connected.
Proof of Lemma 4 Suppose neither of the conditions holds.
If T − f + s is connected, f ∈ C s . Since condition (i) does not hold, either e ∈ C s or f ∈ C e . Therefore, by Lemma 5, T − e − f + s e + s = T − f + s is connected.
If T − f + s is connected, f ∈ C s . Since condition (ii) does not hold, either f ∈ C e or s e ∈ C s . Therefore, by Lemma 5, T − s e − f + e + s = T − f + s is connected.
Therefore T − f + s is connected if and only if T − f + s is connected.
In general, computing the connectivity of T − f + s for all pairs (f, s) of edges f ∈ T , s ∈ E − T takes O(|V | 2 |E − T |) time, for instance by performing a depth-first search on each of the |V ||E − T | graphs T − f + s. Let d be the circumference (length of longest cycle) of G. Then by updating Algorithm 3 (Tree Contraction) Reducing tree size 1: Input: Spanning tree T over a vertex set V ; probabilities of failure p(e) for each edge e ∈ T ; weights w(v) for each v ∈ V , weight threshold W . 2: Output: A tree T . 3: Initialize: T = T . 4: while a vertex was deleted in the previous loop do 5: for v ∈ V do 6: if deg T (v) = 1 and w(v) < W then 7: Add w(v) to w(u), where u is v's neighbor. 8: Add p(uv) · w(v)/w(u) to p(uw), where w is u's parent. Delete v.

9:
if deg T (v) = 2 then 10: Add w(v)/2 to w(u) and w(v), where u and w are v's neighbors. 11: Add edge uw with failure probability p(uw) = p(uv) + p(vw). Delete v. Therefore, updating only pairs (f, s) as described in Lemma 4, we can save an overall factor of Ω(min{|E − T |, |V |/d}) runtime in each step of the local search procedure.

E Network preprocessing
We employ two reduction steps in our preprocessing, which reduces the size of the components and improves tractability: (i) we contract degree 2 vertices while splitting the demand evenly across its two neighbors, and (ii) we contract degree 1 vertices if their demands are less than a threshold. These steps eliminate bridge vertices, as well as leaves corresponding to buses with low weight. We give precise pseudocode in Algorithm 3. Repeatedly applying these steps significantly reduces the size of the network. Using a threshold of W = 10 kW on the Greensboro network, the resulting contracted trees have an average of 17% of the the number of nodes of the original trees. These simplifications primarily consist of contracting leaves corresponding to low-demand buses in residential areas, and do not significantly change the network topology.

G Integer programming formulations
Let G = (V, E) be a network with no specified initial spanning tree, and let b(e) be our desired edge weights in the MRT objective min σ:S−→[|S|] e∈T b(e) min s covers e σ(s) once a spanning tree T is selected. By solving the following integer program, one can find both an initial spanning tree T and a switch reconnection order σ on S = E \ T that minimizes the MRT objective: minimize e,t t · b(e)x et (10) subject to e⊂C s e ≤ |C| − 1, ∀ cuts C ⊆ V, e s e = n − 1, x c ef t ≤ y f t , ∀e, f, t, c ef t ≤ g across C s g − s e , ∀e, f, t, cuts C crossed by e but not f , all variables binary.
Here constraints (11), (12) enforce that T = {e : s e = 1} is a spanning tree. Constraint (13) enforces that each tree edge e is covered at exactly one time t, for which x et = 1. Constraint (14) enforces that e is covered by a switch f that has waiting time t (constraints (15), (16)), is not a tree edge (constraint (17)), and covers e (constraint (18)). Note that b(e) should contain only p(e) or other edge-specific data, as including f (e) or other data that depends on T will make the objective non-linear. Thus this IP can minimize MRT with R-Time as the objective, but not with SAIDI as the objective.
This exponential-size formulation is intractable for large graphs, so we adapt the O(mn)-size formulation due to [33]. This yields an O(m 3 n)-size formulation. Note that if the graph is planar or otherwise low genus, even smaller formulations for the spanning tree polytope and hence for this IP exist [49].
s e = a k,i,j + a k,j,i , ∀e = {i, j} ∈ E, 1 ≤ k ≤ n, j a k,i,j ≤ 1, ∀1 ≤ i, k ≤ n, a k,k,j = 0, ∀1 ≤ j, k ≤ n (24) Figure 9: R-Time, SAIDI, energy, and product objectives for Greensboro components 13-18 during the branch exchange local search. Objectives are plotted as a ratio of their value after each step to the initial values, and each plot shows the median values and percentiles (first to last deciles) for each objective, taken over 50 applications of the branch exchange local search on the component.


extfieldsofstudy:
Computer Science
Medicine

text:
A review of swarm intelligence algorithms deployment for scheduling and optimization in cloud computing environments

Background This review focuses on reviewing the recent publications of swarm intelligence algorithms (particle swarm optimization (PSO), ant colony optimization (ACO), artificial bee colony (ABC), and the firefly algorithm (FA)) in scheduling and optimization problems. Swarm intelligence (SI) can be described as the intelligent behavior of natural living animals, fishes, and insects. In fact, it is based on agent groups or populations in which they have a reliable connection among them and with their environment. Inside such a group or population, each agent (member) performs according to certain rules that make it capable of maximizing the overall utility of that certain group or population. It can be described as a collective intelligence among self-organized members in certain group or population. In fact, biology inspired many researchers to mimic the behavior of certain natural swarms (birds, animals, or insects) to solve some computational problems effectively. Methodology SI techniques were utilized in cloud computing environment seeking optimum scheduling strategies. Hence, the most recent publications (2015–2021) that belongs to SI algorithms are reviewed and summarized. Results It is clear that the number of algorithms for cloud computing optimization is increasing rapidly. The number of PSO, ACO, ABC, and FA related journal papers has been visibility increased. However, it is noticeably that many recently emerging algorithms were emerged based on the amendment on the original SI algorithms especially the PSO algorithm. Conclusions The major intention of this work is to motivate interested researchers to develop and innovate new SI-based solutions that can handle complex and multi-objective computational problems.

INTRODUCTION
Scheduling and optimization techniques have been applied to cloud environments, leading to a research area called evolutionary scheduling and optimization and represents the integration of artificial intelligence (AI) and operational research. Working with a cloud environment is complex and tedious in that there is a large need for better scheduling and optimization strategies. Since the computational problems are generally multi-objective in nature and complex, the traditional scheduling and optimization techniques are considered inadequate. With the emergence of AI techniques, these AI-based algorithms boosted the performance of scheduling and optimization approaches. Over the years, it has become abundantly manifest that these biodiversity of resources strategies are great enhancer for cloud computing work environments; therefore, they provide a robust, reliable, and enhanced strategies for better task achievement and workload distribution among the available cloud resources.
The evolutionary algorithms mimic species evolution based on Darwin's theory. They form a cluster of algorithms in which the genetic algorithm (GA) was the first proposed one. Recently, several SI algorithms have been applied widely to solve complex multi-objective problems. The ant colony optimization (ACO), for example, has been utilized in weather routing and in the travelling salesman problem (TSP). The particle swarm optimization (PSO) algorithm had a large implementation in constrained and unconstrained functional optimization problems. However, this article aims to review and summarize the most recent publications of SI techniques. In cloud computing, task scheduling is very important (Zuo et al., 2015) due to its direct effect in the performance of systems. As task scheduling problems are considered NP-hard problems, they need to meet user needs and improve the overall performance of the systems. This work would be of interest to the students and readers in this domain since SI algorithms lack enough supporting publications and resources as compared to the well-known methods like neural networks or genetic algorithms. Moreover, the challenge of identifying the changes of parameter settings in the mentioned SI methods in this work, and the hybrid associations between the existing SI approaches, facilitates the way for students and readers in this domain better understand and build on the existing techniques. Figure 1 presents the reviewed SI-based algorithms in this work.
This review contributes to the overall deployment of SI based techniques namely PSO, ABC, ACO, and FA, respectively, in scheduling and optimization problems. As many researchers had emphasized the importance of hybrid swarms in solving multi-objective scheduling and optimization problems, this review provided a reference in which it summarizes the recent hybrid techniques used to solve multi-objective problems. The review also highlighted the importance of parameter settings in scheduling problems. Additionally, it elaborated on the basics of SI methods that focused on the implementation of PSO, ABC, ACO, and FA in cloud environment scenarios. However, this study is structured into different sections starting with a basic introductory background. This is followed by a survey methodology which is then followed by sections separately dealing with SI-based algorithms in details. The algorithms discussed among SI-based are PSO, ACO, ABC, and FA studies. A future directions of action discusses the probability of some algorithms to gain prominence in research. Finally, a conclusions section has been introduced.

SURVEY METHODOLOGY
This review is conducted in several stages. First of all, the particular algorithms to be investigated were identified. Second, the authors paid attention to the hybrid nature between the identified SI-algorithms and the commonly parametric settings for problem solving. The aim of this review was to survey the literature to determine how SI algorithms were modified and hybridized to improve the performance of scheduling in cloud computing environment. However, this review scoped the latest publications for the following algorithms namely (PSO, ACO, ABC, and FA) in scheduling and optimization problems. Therefore, the last 5 years' publications for the mentioned algorithms were almost reviewed with a focus on determining the main parameters that have been changed or modified to optimize the performance of each SI algorithm in cloud computing environment. However, this review highlighted the hybrid approach between the reviewed algorithms. In addition, a summarized and brief applications for the identified algorithms were conducted. Finally, the review is unbiased since it just highlighted the main modified parameters in the above-mentioned SI algorithms and their applications in the last five years. It is noteworthy that other SI methods such as Cuckoo search and Levy flights were excluded from the current study, thereby decreasing the scope in order to have a detailed discussion.

Particle Swarm Optimization (PSO)
The PSO represents a well-known metaheuristic optimization technique due to its ease implementation in unsupervised, and complex problems. It is a reliable technique that has been used for treating several optimization problems. In fact, it is based on a physical model in which its transition rules are constructed by mimicking the social collective behavior observed from flocks of birds and/ or schools of fish (Sengupta, Basak & Peters, 2018). The PSO initializes a swarm of particles in which they traverse the search space looking for an optimal global best. In fact, each particle represents a potential solution. Suppose that X i(t ) be the position of any ith particle at a given time t. Then, its velocity is regulated based on End-While the current position being lower than the global best position (Sengupta, Basak & Peters, 2018). Table 1 illustrates the metaheuristic PSO algorithm.
As the particles search for food sources using original PSO, they may stick in local search. This may lead to less convergence in the search space. Due to some major shortcomings of the original PSO algorithm such as stagnation and local optima convergence, several studies were conducted to overcome such flaws. For these reasons, several researchers proposed a modified PSO or hybrid PSO computational strategies to enhance the performance of the original PSO algorithm. Generally, any given optimization problem concerns the selection of best possible solution that minimizes or maximizes a utility function based on some constraints. Therefore, SI-based approaches could introduce an acceptable and reliable solution to scheduling and optimization problems. SI-based solution for any given optimization problem, can be though as watching a team of players who cooperate together, share information, and update their positions collectively seeking a goal that formulates the rapprochement of victory (global best solution). Hence, seeking an efficient task allocation, a hybrid GA-PSO algorithm was proposed by Manasrah & Ali (2018). The proposed GA-PSO aimed at the reduction of the following parameters: makespan, cost, and load balance of cloud computing dependent tasks. However, another study by Ebadifard & Babamir (2018) presented a static task scheduling approach to improve PSO performance by utilizing a load balancing method. Another study by Alsaidy, Abbood & Sahib (2020) tried to improve PSO's initialization using both ''longest job to fastest processor (LJFP)'' and ''minimum completion time (MCT)'' methods. Additionally, Zhou et al. (2018) proposed a cloud computing model based on energy consumption named M-PSO that is capable of handling the slow convergence issue and local optimum. Tabrizchi  determine the most important QoS considerations in cloud computing environments. The literature claimed that many researchers tried to develop new PSO scheduling strategies to enhance optimal solution convergence by introducing different load balancing methods. However, vectors in PSO can be updated using Eqs. (1), (2) below. Figure 2 illustrates the basic PSO algorithm.

Ant Colony Optimization (ACO)
Ant colony optimization algorithm has a great advantage in addressing the combinatorial optimization problems. Several studies had investigated the scheduling tasks using ant colony algorithm in cloud computing environment. They normally categorized according to their targets focus such as scheduling efficiency, system performance, or cost. ACO represents an intelligent algorithm for path planning (Dai et al., 2019;Jovanovic, Tuba & Voß, 2016;Wang, Lin & Wang, 2016). It has a strong calculative mechanism (Ahmed et al., 2020). Generally, it is used for optimization by updating the pheromone trails and orienting the ants around the search space by which each ant generates a new fitness function to be used for generating an overall global fitness. The next state in ACO strategy is determined by the roulette wheel method in which it will be repeated till the goal point has been achieved. Upon the completion of each iteration, the ants update the pheromone trails along the length of path planning. In the available literature, the ACO has been applied mostly to society detection with single objective (Shahabi Sani, Manthouri & Farivar, 2020), while it has been applied to a multi-objective ACO optimization using decomposition (Mu et al., 2019). In fact, ant colony inspired researchers in how ants find the best route to food source. Updating the pheromone trails is proposed by Ekmekci (2019) using a modified ACO that memorizes solution costs.
To solve the TSP problem, Tamura, Sakiyama & Arizono (2021) introduced a modified ACO algorithm using individual memories (IM) named Ant System Using Individual Memories (ASIM) that aims to optimize ant's diversity in the search space. Seeking an optimal solution for ship-weather routing multi-objective optimization problem, Zhang et al. (2021) introduced an improved ACO algorithm considering several parameters such as fuel consumption, sailing time, and navigation safety. A unified adaptive ACO algorithm was proposed by Yuan, Yuan & Huang (2017) related to SNP epistasis with multi-objective functions detection GWAS datasets. In addition, Senthil Kumar & Venkatesan (2019) proposed a hybrid genetic-PSO (HGPSO) algorithm to solve the problem of task scheduling. Another modified PSO algorithm named IPSO was introduced by Yu (2020) to optimize resource scheduling efficiency. The generated solution around the gbest for each ant can be expressed as in Eq. (3). The ACO algorithm diagram can be seen in Fig. 3.

Artificial Bee Colony Optimization (ABC)
The ABC represents a meta-heuristic approach for investigating the behavior of bees. A typical ABC's applications can be found in several areas such as cloud computing, image processing, big data analysis, and neural networks. The ABC algorithm represents the most successful optimization SI algorithms (Aslan & Karaboga, 2020

Firefly Algorithm (FA)
The firefly algorithm (FA) represents a metaheuristic approach that mimics the flashing behavior of fireflies (Farahlina Johari et al., 2017 (2017) proposed a modified FA algorithm that ranks the fireflies based on a quick sort algorithm instead of bubble sort technique.
To handle the optimal operation of thermal generating unit's problem, an improved FA algorithm named improved firefly algorithm (IFA) was proposed by Nguyen, Quynh & Van Dai (2018) to reduce the cost of electricity generation fuel. Another study by Ma et al. (2019) aimed to overcome the problem of FA being fall into slow convergence and local extremum, by using a reverse learning initialization and Levy perturbation mechanisms based on FA algorithm. A hybrid optimizer based on PSO and FA entitled ''FAPSO'' has been proposed by Xia et al. (2018) to sanction the flies to explore more favorable sub-regions. Another study by Tighzert, Fonlupt & Mendil (2019) tried to reduce the computational cost and memory storage of the traditional FA algorithm by introducing a compact firefly approach that uses a minimum computational cost. Wahid & Ghazali (2019) proposed pattern search (PS) to terminate the FA to handle the drawback of the standard FA in its ending phase as it fails to get the optimal value since there is no observed improvement to the quality of the outcomes. A study by Hussein & Jaber (2020) introduced a modified FA algorithm to handle unit commitment problems. They claimed that the modified FA algorithm is more efficient than the classical FA in the selection of generator and error amid load and generation. To solve several non-linear ''convex'' optimal power flow (OPF), a hybrid algorithm consists of FA and PSO named ''HFPSO'' algorithm was introduced by Khan et al. (2020). Additionally, Dai, Liang & Zhang (2020) proposed a new FA-based algorithm to search for the optimal solution for uplift effect in the high-pressure jet grouting (HPJG) project. Another study (Peng et al., 2018) proposed a hybrid fish swarm algorithm based on the behavior of Lévy flight and firefly named LFFSA to overcome the problem of local optimum convergence. Several components (logistic and Gauss, Lévy flight, and adaptive inertia weight) were utilized by Chou & Ngo (2017) to introduce a modified FA algorithm (MFA) to optimize the multidimensional structural design. To adjust the parameters of the proportional integral-derivative (PID) controller in a buck converter, a hybridized algorithm using FA and PSO named HFPSO was proposed by Ekinci et al. (2019). Figure 4 represents the common modified and hybrid FA algorithms.
V.1 FA Position Update In FA, the distance between any two fireflies i and j at X i and X j can be calculate using Cartesian distance as per Eq. (6).
where k represents spatial coordinate component andd represents the number of dimensions. However, the movement of any firefly i towards an attractive firefly j can be described as per Eq. (7) below.
where α randomization parameter and r and is function generator.

The future research directions of SI algorithms
This review explored the potential applications of PSO, ABC, ACO, and FA algorithms. However, there was a little research on multi-objective scheduling and optimization compared to a single-objective approach. This indeed highlights the importance of utilizing the swarm algorithms in solving complex multi-objective problems. As many scholars developed a modified SI algorithm, Table 2 summarizes the modified SI methods and their applications. It can be utilized to further introduce new modified or hybrid algorithms and to be used for multi-objective complex problems optimization. PSO algorithm, for instance, still has a potential for more optimized modifications in which it can be self-adaptive to handle loss of diversity, and/ or local optima stagnation issues. Moreover, despite the modifications that carried out on ACO algorithm, still it can be improved for applications that are more practical. Expert prior knowledge can also be applied to ACO algorithm in future, which believed to improve efficiency of ACO algorithm. Additionally, ABC can be applied to parallel computation in run-time by tuning its parameters in which this could optimize solutions to the NP-Hard combinatorial problems. Path prioritization represents a promising challenge for ABC algorithm. However, there are several areas in which FA algorithm can be utilized to cope with. Applying FA's variations such as Gaussian, and/ or multi-population in biomedical engineering (BME) and healthcare (HC) areas can be fruitful research opportunities. Table 3 illustrates the most used parameters for modification. However, the main challenges in SI-based in scheduling and optimization problems are multi-objective search, multidimensional numeric problems, fitness function improvement, local optima escaping, global optima finding. Figure 5 shows a count analysis for the reviewed articles in this survey.

CONCLUSIONS
This review focused on the overall deployment of SI-based algorithms (PSO, ABC, ACO, and FA, respectively) in scheduling and optimization problems. As stated in the literature, several scholars tried to introduce new SI-based scheduling strategies to optimize search space exploration and exploitation by proposing a variety of parametric-modification and load balancing schemes. However, many researchers had emphasized the importance of hybrid swarms in solving multi-objective scheduling and optimization problems. As task-scheduling represents a major issue in cloud computing environment, many hybrid techniques were proposed by scholars to improve the performance of traditional SI algorithms and to allocate the suitable cloud resources to user tasks. However, the reviewed algorithms in general lose solution quality when their dimensionality increased. It is noteworthy that parameter settings for one problem do not operate for every problem. However, the basics of SI methods that target the implementation and illustration of PSO, ABC, ACO, and FA in cloud environment scenarios have been elaborated in detail. In addition, some of the most current and noteworthy applications of SI-based techniques for cloud environment scheduling we are surveyed. The future plan for this work aims to develop a hybrid SI strategy utilizing the most dominant parameters such as inertia weight, acceleration coefficients, and Tabu list size.

ADDITIONAL INFORMATION AND DECLARATIONS Funding
The authors received no funding for this work.