Automatic reconfiguration of power systems has been well studied and published in the literature. Fault Location, Isolation, and Service Restoration (FLISR) is an existing group of technologies that seek to: 1) locate faults on the grid; 2) isolate those faults through various means; and 3) reconfigure the system in such a way that can restore power to the healthy portions of the grid while leaving the damaged portions de-energized. In fact, many utilities currently have FLISR programs integrated into their Distribution Management Systems (DMS) that are used as a reference for system operators. In some cases, utilities have implemented true DA schemes where the FLISR logic is trusted to perform switching operations without a human-in-the-loop  . These cases are still relatively rare despite consistent evidence that DA can have a significant impact on reducing customer outage frequency and duration  . In addition, islanding from the grid and forming a DG-powered micro-grid is still a very new idea and the potential benefits of doing so are often not considered by existing FLISR methods.
According to  , approaches for finding the optimal configuration of a distribution system fall into the following four categories: heuristic methods   , rule-based approaches   , genetic algorithms  , and mathematical programming. After finding the optimal configuration, power flow considerations should be made to ensure that the new state of the system does not overload any of the circuit elements, cause misoperations of protection equipment, or violate any voltage constraints.
 formulates a Linear Program (LP) to solve the reconfiguration problem for distribution systems considering the locations of DG as potential service points. A linearized, single-phase formulation for power flow and voltage drop calculations is presented. This formulation is used within an LP to constrain the voltage at each vertex and the current flowing through each edge. However, it can only accommodate radial systems as each edge is directed with a strictly defined parent node. In some configurations, it may be true that power reverses direction causing the opposite node to become the parent node. This is not to say that closed looped configurations should be considered as feasible solutions, but that some optimal configurations may shift the open point of a loop to a new location. Conversely,  uses an approach that treats the network as an undirected graph, thus considering the looped nature of a power system and making all configurations feasible. However, the author seeks to partition transmission systems which operate very differently from distribution systems. Namely, any configuration considered as a solution in a distribution system needs to be radial which is not the case with transmission systems.  uses a searching algorithm where an unbalanced three-phase power flow is calculated at each iteration of the search. In  , a bi-objective optimization model based on fuzzy membership function and the memetic algorithm are employed to solve the islanding problem. Voltage variance is added to the cost function as objective to represent the power quality. In  , an islanding method based on improved dynamic programming is applied with the target of restoring load power based on priority. The structure of the distribution system is converted to an undirected graph with weights and island region is calculated. A two-stage method based on branch and bound algorithm is designed in  where the first stage consists of an island isolating process composed of a serial of tree knapsack problems (TKPs) and island combination process. In the second stage, the feasibility of formed islands is checked by running power flow and adjustments are made to mitigate the constraint violations. Branch and bound algorithm is used to solve each TKP.  also suggests a two-stage algorithmic solution. ACSP based method creates a collection of network partitioning results in respect to individual DGs meeting the imposed constraints assuming the fault occurrence at certain points. The heuristic simulated anneal arithmetic (SAA) algorithmic design was employed to identify the optimal partitioning solution. However, the approach needs to be further validated through a simulation of large-scale power distribution networks through a range of network operational scenarios. Also, it did not investigate/evaluate the potential adverse impact of islanding operation. But the method proposed in this paper is validated by simulating a 4700-node substation model.
In all these papers, most of them find optimal partitions based on the priority of the loads and impose voltage and power balance constraints. They consider DGs as potential sources for forming micro-grids but did not consider forming a single micro grid connecting multiple sources if the capacity is needed to supply the load. Also, the method developed in this paper can reconfigure systems containing any number of loops and sources and result in a radial configuration. This paper enforces topological constraints using graph theory inside an LP  . A two-step approach similar to  is employed as it can provide a better estimate of the power flow profile in the reconfigured state. An iterative, closed-loop method will be used to validate the constraints placed on power flow. It is shown to fix the back feeding condition of voltage regulators resulting in low voltage conditions and undesirable conditions in the distribution system.
2. Relevant Background
2.1. Graph Theory Review
Partitioning a graph is the method of finding a set of subgraphs such that the union equals the original graph G and the intersection is the empty set . This paper uses two different partitions to separate out the different elements of G and find the optimal configuration. The first partition, , separates the de-energized and energized portions of the grid, denoted and respectively.
The second partition, , is over the active subgraph and separates the connected components of , subgraphs in which any two vertices are connected, but no vertices are connected to other vertices in the super graph. The subgraphs in this partition represent the micro-grids that are formed as a result of reconfiguration.
The fundamental idea from graph theory that will be exploited in this paper is shown below in Equation (1). This equation describes the relationship between the numbers of vertices, edges, cycles in cycle basis, and connected components in a graph.
Here, if the condition is forced, the connectivity of the subgraphs of the active elements of G can be ensured given that the number of subgraphs is known.
2.2. Distribution Switching Criteria
Typically for switching to occur on a distribution system, a request will be made to a distribution dispatch center. The switching operations will then be simulated using some type of power flow analysis software. The two most crucial constraints that are checked before any switching is approved are over current conditions and under voltage conditions. Stability and transient issues should also be considered when partitioning power networks, especially when operating micro-grids islanded from the bulk power grid, however, these issues are not often studied with respect to distribution switching and are beyond the scope of this paper.
Over current conditions occur when the thermal limit of a conductor is violated. This condition causes heat to build up which eventually will cause the conductor material to fail. For this paper, the Long-Term Emergency (LTE) ampacity, the maximum current that a conductor can carry for emergencies lasting less than 3 hours, is used to prevent failure of conductors during reconfiguration.
Additionally, coordination of protection devices cannot be relied upon when the circuit is not in normal configuration. For this reason, the protection settings of the devices are also considered to prevent misoperations. The minimum value on the Time-Current Characteristic (TCC) curve is used as a limit for the current passing through a protective device.
Using the ampacity ratings of conductors and operating characteristics of protection devices, the current through each edge of G is constrained to prevent overloading or misoperations. Equation (2) shows the general form of this constraint.
Voltage constraints on a distribution system stem from the American National Standards Institute (ANSI) Standard C84.1  . For residential utility services greater than 100 V, the voltage supplied to the customer’s meter should be within ±5% of the nominal service voltage. This tolerance can be separated out to the voltage drop over primary conductors and that over secondary conductors. It is recommended that less than 3% voltage drop be allowed on either so that the combined voltage drop meets the standard. Inequality (3) shows the constraint for voltage throughout the system.
3. Problem Formulation
3.1. Sets and Parameters
Any given vertex can have a load, a source, both or neither, so the sets L and D are not necessarily disjoint and the union does not necessarily contain all of V.
Additionally, let the set C contain all the simple cycles in G.
Note that, then . The set C is not necessarily a partition of G since it may be true that certain vertices or edges belong to multiple cycles while others may not belong to any cycle.
Each distribution system has a configuration that it takes during normal operation when the entire system is healthy. In this state, the inactive subgraph, , contains the normally open edges for each loop as well as any edges that connect sources which are not normally connected to the circuit. All other edges belong to the active subgraph . , are used to ensure that the sources connected to a micro-grid can supply all of the connected loads plus reactive power and losses.
The goal of the problem is to find an optimal partition of the graph G. Therefore, the variables are defined so that their values depict the partitions and . This is accomplished through binary variables that decide whether each vertex or edge belongs to a given subgraph or not, thus the problem is a Binary Integer Linear Program (BILP). Note that the maximum number of subgraphs formed by and is equal to the number of sources in G plus one for the inactive subgraph. Each vertex and edge then has binary variables associated with it defined in the following way
It may be possible for and for some k indicating that subgraph does not contain any elements. In this situation, the number of connected subgraphs formed by is strictly less than the number of sources ( ). Since the number of connected subgraphs is required for the topological constraints discussed previously, a variable is needed to indicate whether each of the subgraphs is empty.
In addition, it may be true that a vertex is active, but the load or source located at that node is not. Therefore, a separate variable A is defined for loads and sources.
Note that the loads and sources located at the same node are not assumed to be linked so that both can be connected or disconnected individually.
Finally, a variable is needed to track whether an edge has changed states or not.
The variable B is critical for obtaining the solution to the problem since the switching operations that need to occur to reach the optimal configuration are stored in this variable.
For the distribution system to be well defined, certain assumptions are made for each of the elements. First, all sources considered in the set D must be able to be dispatched. This can include gas powered generators, energy storage, potential tie points with adjacent circuits, etc. Sources that cannot be dispatched, such as photovoltaic (PV) and wind turbine generation (WTG), are not considered because islanding in this manner would cause instability and potentially damage equipment. Instead, these sources are modeled as a load with a “negative demand” so that their effect on the capacity of a micro-grid remains.
Additionally, each edge should be able to toggle between active and inactive, symbolic of a switch opening or closing. This is an accurate representation of underground circuits as distribution switchgear and pad mounted transformers typically have switches for each of the cable feeds entering or leaving the cabinet, however, overhead systems do not normally have switches located between every pole. To account for this, a reduced model is generated by collapsing the sections located in between switches to a single vertex.
Similarly, all edges in the graph must be able to carry three phase power so that a solution where a single or double phase line is reconfigured to carry three-phase load does not occur. The model reduction can also be used to prevent this situation by removing all the single and double phase elements. All the load associated with these elements should be added to the most downstream three-phase vertex in the path between the load and the substation.
The optimal partition is the one that maximizes the total weighted re-energized load while executing the minimum number of switching operations. The weights should be defined in such a way that high priority loads with a small amount of demand will take precedence over low priority loads with a large demand. Thus, the problem is bi-objective. The summation quantifies the first objective, the total weighted load belonging to an active subgraph. Here is only counted if for some k. The second objective, minimizing the number of switching operations required to reach the reconfigured state, is used to prevent any unnecessary switching from occurring (i.e. moving an open point to another location on a healthy loop). The number of switching operations are counted using . Maximizing the first objective is equivalent to minimize the additive inverse, thus the two objectives are summed into a single minimization state shown in (4). A regularization parameter λ is used to adjust the relative weights of each objective.
It is important to note that the switching objective criteria are secondary to the weighted load criteria, and thus the regularization parameter should be tuned in such a way that de-energizing a load is costlier than preventing a switch from toggling.
3.5.1. Distribution System Condition Constraints (DSCS)
The DSCS ensure that the unhealthy portions of the feeder are de-energized. Equation (5) and Equation (6) will force these elements of unhealthy sections to be in the inactive subgraph .
3.5.2. Switching Variable Constraints (SVC)
The SVC constrain the relationships between the variables a, b, A, and B due to switching. The variable A is related to the variable a by the condition that a load cannot be connected to a subgraph unless the vertex that it is located at also belongs to that subgraph. Inequality (7) ensures that A is less than or equal to a satisfying this condition.
Similarly, B is the variable that tracks whether an edge has changed states. Equation (8) uses an absolute value to describe this relationship where
indicates if edge
belongs to an active subgraph and
Equivalently, this statement is expressed using the following linear inequality constraints:
3.5.3. Subgraph Connectivity and Radiality Constraints (SCRC)
The SCRC require all active subgraphs formed by partition to be connected and radial. For a subgraph to be active, it must contain a source. Furthermore, the capacity of the sources contained by a subgraph must be sufficient to supply all the loads contained in the same subgraph. Inequalities (13) and (14) forces to track whether contains a source or not and Inequality (15) ensures the capacity constraint is satisfied.
Equation (16) and Equation (17) ensure that and meet the two requirements of being a partition: 1) all subgraphs are disjoint; and 2) the union of all subgraphs is the original graph. This is accomplished by setting the sum of the binary variables a and b over all subgraphs equal to one for every vertex and edge respectively
Furthermore, for an edge to belong to , each of the vertices adjacent to that edge must also belong to unless the edge is inactive. Inequality (18) restricts to be zero unless both and are both one. Note that an edge can remain inactive even if both adjacent vertices belong to the same subgraph as is the case with open points in a loop.
Likewise, if a vertex belongs to a subgraph, there must exist an edge connected to that vertex also in the subgraph. Inequality (19) restricts so that this condition is met.
Finally, to ensure that the solution of the BILP is radial, the set of active vertices and edges must form a forest. Inequality (20) will break each cycle by ensuring at least one edge is inactive and Equation (21) invokes Equation (1) by counting the number of vertices, edges, and non-empty subgraphs of using variables a, b, and d respectively.
3.5.4. Power Flow Constraints (PFC)
The PFC described in inequalities (2) and (3) are enforced externally to the BILP. Once a partition is found, an unbalanced power flow is calculated using the new configuration and the current in each line and voltage at each bus is checked. If a violation is found, the formulation is repeated and a new solution to the BILP is calculated. A flowchart of this two-step iterative method is pictured in Figure 1. For the method to work, a constraint must be formulated and added to the BILP that will prevent the solver from obtaining a previous solution after a violation has been detected. Since the switching operations to adjust the configuration of the circuit are the true outputs to the problem, changing the switching results will yield a different solution. Thus, the variable B, which indicates if a switch has operated or not, is constrained using Inequality (22) to require at least one to change from the previous solution .
This constraint prevents the solver from returning the same partition as the previous iteration while still allowing any other combination of switching operations.
4. Results and Discussion
The two test systems pictured in Figure 2 were used to test the proposed partitioning method. Test System 1 is a modified version of the IEEE-69 bus Test Distribution System found in  . Test System 2 is an entire substation model received from a local utility.
Figure 1. Two-step method for power flow constraint validation.
Figure 2. Test distribution systems.
The source locations for both test systems are marked by the blue stars in Figure 2. Test System 2 was modified from the original model to contain sources where potential circuit tie locations were identified. The 10 sources in Test System 2 include 3 known PV farms (assumed to have energy storage present), 6 circuit ties, and a substation bus. Table 1 shows specifications for both test systems.
For Test System 1 all sections are assumed to be switchable. However, of the 4735 edges in Test System 2, only 840 are switchable. For each Test System, random fault locations are selected to form several different scenarios. The BILP is then formulated and solved for the optimal partition using IBM’s CPLEX called from the MATLAB interface via the OPTI Toolbox.
OpenDSS, an open source simulation tool developed by the Electric Power Research Institute (EPRI) is used for power flow calculations via the COMM interface again from MATLAB. It is designed specifically for the modernizing distribution grid. All simulations were completed on a PC with an Intel Core i5-4590 3.3 GHz processor and 8 GB of RAM.
4.1. Test System 1
Test System 1 is unique for its looped nature. The 5 cycles in the basis of the graph combine to form a total of 26 unique simple cycles. For this test system,
Table 1. Test distribution system specification.
the BILP is formulated and solved for four different scenarios. Case (a) is the trivial, normal operation case where the BILP is solved with no faults on the system. Case (b) places a single main-line fault on the feeder. Case (c) is the case with multiple main-line faults which could occur during a High Impact Low-Frequency event (HILF) such as extreme weather events or coordinated attacks on the system. Case (d) is a fault scenario designed so that multiple sources are connected to a single micro-grid. Here, the capacities of the sources were decreased so that no one source could supply the entire isolated section alone. The results from each case, pictured in Figure 3 on the following page, show the optimal partitions found represented by the different color lines.
Note that for each case, most normally open sections remain open. This shows the effectiveness of enforcing the switching criteria in the objective function and verifies that excessive switching is not occurring. Also, notice the ability of the method to add multiple sources to a single micro grid in scenario (d). For this scenario, most of the system was isolated from the normal feed and the capacities of the three distributed sources were adjusted so that each would need to be active to supply the isolated loads. As expected, each source is energized and all the system load is restored.
4.2. Test System 2
Test System 2 is much larger than Test System 1 and not all edges are switchable, thus model reduction is required. To reduce the model, the loads from all laterals are collapsed down to the main-line node which they are associated with and removed. In addition, sections that cannot switch independently are grouped together. The results of this model reduction process on Test System 2 are shown in Figure 4. The reduced system contains 48 nodes, 53 sections, and 6 loops in the cycle basis forming 20 unique cycles. The 10 sources from the original graph are retained.
Using this model, the partitioning method is solved for normal operation and faulted operation. This solution is projected back to the original graph and a power flow is solved using the full model. In the faulted operation case, eight random fault locations were chosen and the partitioning method was solved until a scenario resulted in multiple iterations of the PFC validation process. Several scenarios were tested where the first partition found did not violate either of the PFC. However, the scenarios shown in Figure 5 and Figure 6 were found to require three iterations to find a feasible solution.
Low voltages in the bottom part of the feeder were noticed in the first iterations as pictured in Figure 5(b). This is due to the back-feeding condition that
Figure 3. Partitioning results for test system 1.
Figure 4. Test system 2 model reduction.
Figure 5. Test system 2 faulted operation―iteration #1.
Figure 6. Test system 2 faulted operation―iteration #3.
the regulator, not marked in the figure but indicated by the sharp change from light blue to dark blue 1/3rd of the way down the feeder.
Once the violation was detected, Inequality (22) was added and the BILP was resolved. The second iteration changed with the bottom micro-grids witched-in but did not fix the back feeding condition on the regulator, thus the violation remained. Finally, in the third iteration as shown in Figure 6(b), the source upstream of the regulator was connected and the device began to function properly bringing the voltage in the entire circuit above the 3% threshold.
Back-feeding of a voltage regulator is a very dangerous system condition and can have undesirable effects on the distribution system. In fact, utilities will typically not connect any DG downstream of a voltage regulator to prevent this condition. The BILP optimization problem is blind to the fact that voltage regulation exists on this circuit. Thus it is imperative that the power flow is calculated and checks for such violations before switching can occur.
4.3. Convergence Results
Convergence results of the partitioning method are shown in Table 2. Most of the tested scenarios required only a single solve of the BILP with the exception of
Table 2. Test distribution system specifications.
the case described for Test System 2. Additional faults are shown to not have a large impact on the time needed for the BILP to converge. However, the solution requiring multiple sources for a single micro-grid on Test System 1 had a noticeable increase in both the BILP and power flow computation times.
It should be noted that for Test System 2, the power flow calculation time includes the time required to map the solution of the BILP to the original graph. The decrease in the time required for the BILP to converge resulting from the model reduction, however, is much greater than the time added from this mapping procedure.
In this paper, linear programming and graph theory were used to create a partitioning method for distribution systems during outage events. The problem was formulated as a BILP and applied to two different test systems of varying size and for several different faulted scenarios. The BILP was shown to be able to consider DG throughout a distribution system as potential sources for forming micro-grids islanded from the bulk electric grid, reconfigure systems containing any number of loops resulting in a radial configuration. It has the ability to connect multiple sources to a single micro-grid if the capacity is needed to supply the microgrid’s load. An iterative method was used, which calculates a power flow externally to the LP and uses a feedback loop to recalculate the solution if a violation is found. It was shown to fix the back feeding condition of voltage regulators resulting in low voltage conditions. A feasible solution was found where a source is connected upstream the regulator in the partitioned microgrid. In each case, the method performed favorably and the optimal system configuration was found. With the use of model reduction for larger test systems, all solution times were reasonable for use in a real-time FLISR scheme.
The authors would like to thank all the members of the Center for Advanced Power Engineering Research (CAPER) and Clemson University Electric Power Research Association (CUEPRA) for their financial support, data, and guidance for this research.
: A binary variable for each load/source at a vertex in V, indicating if it is active or disconnected.
: A binary variable for each edge tracking the change in its state from active to inactive or vice-versa.
: A cycle basis of G-set of linearly independent cycles from which all of the cycles in G can be generated.
: Length of the cycle basis .
: Subset of V containing vertices with sources.
: Set of all edges in a graph G.
: Number of edges in a graph G.
: Set of all edges that are inoperable due to faulty conditions.
: Graph describing a distribution system.
: Maximum allowable current that can pass through the edge .
: Current passing through the edge .
: Number of connected components in the graph. Connected components are subgraphs where each element is connected with the other elements of the subgraph, but not connected to any other element in the original graph.
: Subset of V containing vertices with loads.
: Total number of cycles in G.
: Power rating for each source .
: Set of all vertices in a graph G.
: Number of vertices in a graph G.
: Set of all vertices that are inoperable due to faulty conditions.
: Nominal voltage.
: A binary variable for each vertex in V, indicating its presence in graph .
: A binary variable for each edge in E, indicating its presence in graph .
: A subgraph of G and belongs to C.
d: Vertex in the set D at which source is connected.
#Math_119# :A binary variable indicating whether each of the subgraphs are empty.
: An edge in E representing the conductor between two vertices i and j.
: Vertex in the set L at which load is connected.
: Normal state for edge , it is 1 if the edge belongs to active subgraph during normal operation. Otherwise, it is 0.
: Real power demand for load .
: “Worst case” power factor for loads.
: Vertex in V corresponding to a power distribution pole or pad mount location.
: Weight for load .
: Tolerance for voltage, equal to 3% for this paper.
: Multiplier to estimate power loss.
: A regularization parameter used to adjust the relative weights of each objective in the objective function.
 Gomes, D., Colunga, R., Gupta, P. and Balasubramanian, A. (2015) Distribution Automation Case Study: Rapid Fault Detection, Isolation, and Power Restoration for a Reliable Underground Distribution System. 68th Annual Conference for Protective Relay Engineers, College Station, 30 March-2 April 2015, 325-334.
 Zhu, J. (2015) Optimal Reconfiguration of Electrical Distribution Network. In: Optimization of Power System Operation, 2nd Edition, Wiley-IEEE Press, Piscataway, NJ.
 Hernandez, M. and Ramos, G. (2016) Meta-Heuristic Reconfiguration for Future Distribution Networks Operation. 2016 IEEE/PES Transmission and Distribution Conference and Exposition (T&D), Dallas, 3-5 May 2016, 1-5.
 Yang, H.T., Liao, J.T. and Su, X.H. (2011) A Fuzzy-Rule Based Power Restoration Approach for a Distribution System with Renewable Energies. 2011 IEEE International Conference on Fuzzy Systems (FUZZ), Taipei, 27-30 June 2011, 2448-2453.
 Sun, K., Shao, W., Xu, Z. and Xu, W. (2014) Islanding Partition of the Distribution System with Distributed Generations Based on Memetic Algorithm. 2014 2nd International Conference on Systems and Informatics, Shanghai, 15-17 November 2014, 197-201.
 Pal, S., Sen, S. and Sengupta, S. (2015) Power Network Reconfiguration for Congestion Management and Loss Minimization Using Genetic Algorithm. 2015 Michael Faraday IET International Summit, Kolkata, 12-13 September 2015, 291-296.
 Chen, C., Wang, J., Qiu, F. and Zhao, D. (2016) Resilient Distribution System by Microgrids Formation after Natural Disasters. IEEE Transactions on Smart Grid, 7, 958-966.
 Li, J., Ma, X.Y., Liu, C.C. and Schneider, K.P. (2014) Distribution System Restoration with Microgrids Using Spanning Tree Search. IEEE Transactions on Power Systems, 29, 3021-3029.
 Zhang, C.L., Yang, Z., Ge, L. and Yuan, X.D. (2014) Island Partition of the Distribution System with Distributed Generation Based on Improved Dynamic Programming. China International Conference on Electricity Distribution, 1734-1738.
 Jikeng, L., et al. (2010) Two-Stage Method for Optimal Island Partition of Distribution System with Distributed Generations. IET Generation, Transmission & Distribution, 6, 218-225.
 Dong, R., Yang, Q. and Yan, W. (2014) A Two-Stage Approach on Island Partitioning of Power Distribution Networks with Distributed Generation. The 26th Chinese Control and Decision Conference, 2773-2777.
 Savier, J.S. and Das, D. (2007) Impact of Network Reconfiguration on Loss Allocation of Radial Distribution Systems. IEEE Transactions on Power Delivery, 22, 2473-2480.