1
Download Simulator 13 User Guide
Transcript
Edit Mode Tools and Options Augmenting Path Max Flow Min Cut Algorithm The augmenting path max flow – min cut algorithm is used to identify the minimum number of branches that need to be opened or removed from the system in order to isolate the Facility (power system device) from an External region. The algorithm is an application of the Max Flow - Min Cut theorem, which states that the maximum flow that can be transferred from a set of source nodes to a set of sink nodes across a graph equals the capacity of the minimum cut. The facility analysis in Simulator finds a min cut, although this cut may not be unique. The application consists of three stages: 1. Convert the electric network to a graph structure In this stage, each branch of the system is converted to an undirected arc with graph flow capacity equal to one. Thus, only one unit of graph flow can be sent through a branch. The Facility buses and the External buses are converted to Facility and External supernodes, respectively. This effectively reduces the problem to finding the min cut between these two supernodes. The number of nodes and capacities of the Facility and the External region are also computed during this stage. 2. Find the Max Flow using the Augmenting Path Algorithm This is an iterative process. At each step, the algorithm finds a new augmenting path from the Facility to the External region and augments the graph flow along this path in one unit. Consequently, the branches in the path won’t be available for flow augmentation in the next step. Each new path is determined using a shortest path routine. The algorithm stops when no augmenting path from the Facility to the External region can be found. The number of units transferred from the Facility to the External region (path augmentations) reaches the number of branches in a certain cut. Note that the number of branches in the min cut can not exceed the capacity of either the Facility or the External region. 3. Determine the branches in the min cut The identification of the branches that constitute the min cut consists in tracking down labels in the buses and branches used during each path augmentation. 293 PowerWorld Simulator Version 13 User’s Guide - September 26, 2007
