Symbolic Reduction Technique for Real Power Flow Tracing

Symbolic Reduction Technique for Real Power Flow Tracing

G. V. Narayana

Department of Electrical Engineering Andhra University

Vishakhapatnam, India

Dr. G.V. Siva Krishna Rao Department of Electrical Engineering Andhra University

Vishakhapatnam, India

Abstract Power flow tracing is used to find the allocation of generators and loads in the line flows and generator contribution in loads and load contribution in generators. Due to multiplicity of solutions, recently optimal power flow tracing methods have been proposed. However, the size of optimization problem increases drastically with size of the system. Therefore, in this paper, we propose a symbolic reduction step wherein variables which will be set to zero at optimal are identified a priori by a graph theoretic analysis. This leads to reduce number of variables in the LP problem. Further, the reduced problem can be solved efficiently by sparse LP method. Results on large

488 node Indian utility system illustrate the necessity of proposed approach.

Keywords Real power flow tracing, Depth first search, Variable reduction, Linear Programming (LP), Transmission system usage cost and loss allocation, Object oriented design

1. INTRODUCTION

   Real power tracing is required to know the following components:

   • How much of a particular load power has been supplied by each of generators in the system (Generation Allocation)?

   • How much power is dispatched by a generator to a load (Load allocation)?

   • What is the contribution of each generator and each load in the power flow of a line (Flow Allocation)?

   All three contributions will be used to find the usage allocation. Usage allocation refers to the power contribution of each generator and/or each load. The advantage of knowing the usage allocation includes loss allocation associated to each path, cost assignment to transmission line pricing, congestion management, ancillary services and decision on scheduling of generators.

   To compute the usage cost of a transmission, following methods have been proposed in literature [1].

   1) Postage stamp method: In the postage-stamp method, transmission users are not differentiated by the extent of use of transmission facilities but charged

   would be confined to flow along an artificially specified path through the involved transmission systems. Once the contract path has been determined the transmission cost related to the specified path are assigned to the transaction. In reality, however, the actual path taken by a transaction may be quite different from the specified contract path thus involving the use of transmission facilities outside the contracted systems.

   1. MW-Mile method: MW-Mile methodology may be regarded as the first pricing strategy proposed for the recovery of fixed transmission costs based on the actual use of transmission network. In this method, charges for each wheeling transaction are based on the measure of transmission capacity utilized in this transaction. However, it is difficult to segregate flow in a line in components of various simultaneous transactions.

   2. Proportionate sharing: This method was proposed by J. Bialek [2]. The procedure assumes that the power reaching a certain node in the electric network is proportionately shared by all the paths going out from that node.

      Fig. 1. Proportional sharing principle.

      The principle of “proportional sharing'' illustrated in Fig. 1 where four lines are connected to node , two with inflows and two with outflows. The total flow through the node is 40 + 60 = 100 units of which 40% is supplied by line , and 60% by line . As electricity is indistinguishable and each of the outflows down the line from node depends only on the voltage gradient and the line impedance, it was assumed that each unit leaving the node contains the same proportion of the inflows as the total nodal flow. Hence the 70 units outflowing in line consists of 40×70 = 28 supplied

      based on an average embedded cost and the magnitude of transacted power.

      by line and

      60×70

      100

      100

      = 42 supplied by line .

      2) Contract path methodology: Contract path method, on the other hand, assumes that the transacted power

      Similarly, the 30 units outflowing in line consists of

      40×30 = 12 supplied by line and 60×30 = 18 supplied by

      100 100

      line . Even though the proportional sharing assumption cannot be proved or disproved, its application leads to simplicity.

   3. Tracing compliant modified postage stamp method: Since, tracing problem is amenable to multiple solutions; we need to define an objective to sample out the appropriate solution. Therefore tracing problem has been framed as an optimization problem in [3]. The objective here is to choose the tracing compliant solution that is nearest to the postage stamp allocation of transmission fixed costs. Thus, advantages of usage based and nearly equitable distribution of transmission fixed cost allocation is achieved simultaneously. Same methodology is used for the loss allocation also.

   4. Min-max fairness method [4], [5]: A Min-max fair power flow tracing has been proposed in [4]. The min-max power flow tracing further improved in [5] for application in large systems. A solution is said to be min-max fair, if any reduction in, say, percentage usage costs (MU/MW) for one entity leads to increase in share of another entity, which has either equal or higher percentage cost. In absence of traceability constraint min-max fairness and

   constraints. In fact, set is both compact and convex. This leads to a linear constrained optimization problem. It models relationship between the flow entities and associated network usage costs. Constraints in OPT problem can be grouped into the following specifications

   • flow specification constraints for series branches, i.e., transmission lines and transformers;

   • source and sink specification constraints pertaining to shunts, e.g., generators and loads;

   • conservation of commodity flow constraints.

   1. Flow Specification Constraints

      Traditionally, two types of tracing problems, viz., generation tracing and load tracing, are discussed in the literature. Generation tracing traces generator flows to loads, while load tracing traces load flows to generators. We first discuss modeling of the flow specification constraints for generation tracing problem.

      1. Generation Tracing: Let (MW) be the flow on a line . Flow is supplied by generators 1, 2,

         with components 1 , 2

         postage stamp method would lead to identical cost

         distribution. An advantage of min-max fairness model

         = 1 + 2 +. . . + (2)

         over modified postage stamp method is that it guarantee`s

         fairness for each individual user, as within traceable constrained space, no other solution exists by which a

         The component of generator on line can be expressed as fraction of the total injection by generator

         higher cost entity (MU/MW) can off load usage costs to a

         lower cost entity. Min-max fairness also meets an important fairness criterion known as `aggregate

         , i.e., . Therefore

         = .

         (3)

         invariance' which implies that artificial splitting of load or generator at a bus will not alter the final solution.

         Whileoptimal tracing is superior to normal tracing as one can rigorously impose a fairness related objective on the

         = .

         =1

         , (4)

         space of traceable solutions, there are certain computational challenges to be overcome. In particular number of variables in optimal tracing problem is increased drastically. Thus, as the system size increases, the optimization solver becomes inefficient.

         In this paper, we proposed a variable reduction technique. The rest of the paper is organized as follows: the optimal tracing methods i.e. Tracing compliant modified postage stamp method and Min-max fairness tracing method are

         Since the branch flows are known and are unknown, flow equations for generation allocation can be written as follow:

         [ ][] = [] (5)

      2. Load Tracing: The power flow on line can also be expressed as a summation of load components, i.e.,

         = 1 + 2 +. . . + (6)

         explained in Section II. Symbolic reduction technique to

         improve computational efficiency of optimal tracing problem is explained in Section-III. Object oriented design in unified

         The component of load ( ) on line is expressed as a fraction of load as follows:

         modelling language (UML) of tracing engine is discussed in

         Section IV. Section V presents the results and Section VI concludes the paper.

         = .

         (7)

2. OPTIMIZATION APPROACH TO REAL POWER TRACING: AN APPLICATIONS TO TRANSMISSION FIXED COST ALLOCATION

   [3]

   The optimal tracing problem can be compactly defined as follows:

   = . , (8)

   =1

   In matrix form, the flow equations for load allocation can be written as follows:

   [][] = [] (9)

   }

   }

   (, ): {, (, )

   (1)

   1. Source and Sink Specification Constraints

      The set represents the set of all possible tracing solutions and a specific set of and vectors represents a solution to generation and load tracing problem. It is shown that set can be characterized by a set of linear equality and inequality

      1. Generation Tracing: In a generation tracing problem, it is necessary to write sink (load) constraints. They express the contribution of generators in loads. For a

         load ( ), the contribution of various generators is

         where is the node at which the load is connected.

         governed by the following constraint:

         [

         ] ] = [

         ] (19)

         = 1 + 2 +. . . + (10)

         [

         D. Lossy Flow network

         = . , = 1, . . . , (11)

         =1

         In the matrix form, the load equations for generation allocation can be written as follows:

         [ ][] = [ ] (12)

         For a lossy flow network, the flow reduces along the arc from the sending end to the receiving end. Under such situations, it is necessary to model two flow equations per line, one for the sending end and one for the receiving end. An alternative approach has been developed to restrict the number of variables and equations in the optimization problem to the corresponding lossless formulation. For taking care of lossy flow network we need to change the and

         . Let is origin and is destination of an arc .

         ( , ) = 1 (20)

      2. Load Tracing: In the load tracing problem, it is necessary to model the share of loads in a generator. Let

      (21)

      = 1 + 2 +. . . + . . , = . (13)

      (, ) = ,

      ( , ) = , (22)

      =1

      In matrix form, the generator equations for load allocation

      ( , ) = 1 (23)

      can be written as follows:

      [ ][] = [ ] (14)

   2. Conservation of Commodity flow constraints

   The conservation of flow constraints can be neatly expressed by using arc or bus incidence matrix of the underlying graph. In the matrix, rows correspond to nodes and columns to arcs. The entry (, ) is set to 1 if arc is

   1. Modeling of Boundary Conditions

      In a megawatt flow network, if the results are consistent, then this difference, i.e., power dispatched by generator to load minus power received from generator by load , should correspond to the loss incurred in the generator- load- interaction. Let us define this loss as , where

      outgoing at node; it is -1 if the arc is incoming at node; else,

      =

      (24)

      it is set to zero. The shunt arcs have one node as ground,

      which is not modeled in . The corresponding entry in is either 1 or -1, depending upon whether the arc represents load or generation.

      1. Generation Tracing: Let represents sub-matrix formed by considering series branches and shunt loads

         = [, ] (15)

         [][] = [ ] = 1. . . (16)

         The above equation should satisfy the following loss properties of a network:

         0, {1,2, , } (25)

         {1,2, , }

         =

         (26)

         Where represents the set of -variables for lines and loads associated with the generator. is the node at which generator is connected, and is the column of identity matrix.

         Instead of partitioning variables by generator numbers, they can be partitioned by series branch flow () and shunt flow variables. The set of the continuity equations can be rearranged and written in block matrix notations with and the variable partition as follows:

         =1 =1

         Equation (25) models the constraint that loss is a non- negative number, while (26) models the requirement that total generator-load interaction losses should be equal to the power loss in the system.

   2. Explicit formulation

      1. Objective Function for Transmission Fixed Cost Allocation Using Modified Postage Stamp Method: The transmission system usage cost per MW paid by a load can be

         [

         ] ] = [

         ] (17)

         worked out as follows:

         [

         =

      2. Load Tracing: The following similar arguments as in generation tracing, the continuity equations for load tracing are given as follows:

         [][] = [] = 1. . . (18)

         = (27)

         The transmission system usage cost per MW paid by a generator can be worked out as follows:

         (1 )

         where is the ratio of total system loss to total system

         =

         load, and

         is the ratio of total system loss to total system

         = (1 ) (28)

         where is the cost of line per MW, is the P. U. share of the load in total transmission cost, 0 1. Further, we assumed without loss of generality that =

         generation.

      3. Optimal Tracing Problem Formulation: Now, OPT problem that was defined in (1) can be explicitly expressed as folows:

   (, ) (35)

   0

   .

   Let the postage stamp rate for the loads be given by

   [ 0

   ] [] = [] (36)

   . Then

   0, {1,2, . . . , }

   =

   =

   =1

   (29)

   {1,2, . . . , }

   (37)

   Let the postage stamp rate for the loads be given by

   [0,0, . . . ,0] [] [1,1, . . . ,1] [] [0,0, . . . ,0] (38)

   where is all the equality constrained matrices

   . Then

   corresponding to generation tracing, and is all the

   = (1 )

   (30)

   equality constrained matrices corresponding to load tracing.

   =1

   By solving above optimization problem we can allocate the generation and load to find the transmission usage cost and loss allocation.

   The aim of tracing compliant postage stamp method

   is to compute the closest traceable solution to the proportionate distribution of transmission system usage costs. Therefore, the objective function {, } in (1) is written as

   {, } = | |

3. SYMBOLIC REDUCTION TECHNIQUE

   The tracing problem discussed in Section-II is modeled by a multi-commodity LP problem, where the number of variables are given by following equation:

   . = × ( + ) + 2 × (

   =1

   × ) + 2(

   + ) (39)

   + | | (31)

   where is number of generators, is number of branches,

   =1

   and is number of loads of the network. The number of variables required for different systems is tabulated in Table

   1. Objective Function for Loss Allocation: Another I.

      S. No Name of the system No. of variables
      1	IEEE 6 bus	70
      2	IEEE 30 bus	1498
      3	IEEE 57 bus	4640
      4	IEEE 118 Bus	15252
      5	NER Grid (India)	4511420

      S. No Name of the system No. of variables
      1	IEEE 6 bus	70
      2	IEEE 30 bus	1498
      3	IEEE 57 bus	4640
      4	IEEE 118 Bus	15252
      5	NER Grid (India)	4511420

      choice of objective function can be developed on similar lines for equitable distribution of losses. The per unit loss for load

      is given as follows:

      Table I No. of variable of different systems

      = ( ) 1 (32)

      =1

      The per unit loss for generator is given as follows:

      = 1 ( )

      =1

      These numbers are quite large in comparison to the size of

      Let us assume that percentage share of loss for generators in total loss of system is ShrLossG and percentage share of loss for loads in total loss of system is ShrLossL.

      Therefore the objective function {, } in (1) for loss allocation is written as:

      {, } = | |

      (33)

      the system. In the final LP solution it is seen that many of the variables are set to zero. By identifying this large subset of zeros before the LP formulation we can reduce the size of the problem.

      This suggests that additional work is required to improve computational efficiency of the method. This can be achieved by:

      1. exploitation of sparsity linear programming and

         =1

      2. improvement in modeling and algorithm.

   The following methodology is proposed for the symbolic

   + | | (34)

   reduction. Symbolic reduction approach is a graph theoretic

   =1

   preprocessing on the output of load flow program to identify the reach of generator and load to transmission lines. It also identifies as to which generator can deliver power to loads and vice versa in the tracing frame work. The basic method can be explained as follows:

   Let be the directed graph of the system and arc be represented as (, ). If load flow or state estimation output power flow is from node to node , then origin is and destination is . On the other hand if power flow is from

   Therefore instead of considering all the generators to decompose the flow of a branch, consider only those generators whose power is flowing through that branch. Then the equation (4) is modified as follows:

   to then origin is and destination is . If it is said that the generator at node can reach the node then the node can be reached by traversing a sequence of connected arcs in the direction of flow. In other words, node is in the reach of

   =

   .

   .

   ,

   node if following sequence of arcs

   (, 1), (1, 2). . . . . (, ) exists. Reach set of generator is the set of all nodes which can be reached by generator. A generator is said to reach an arc (, ) if

   where is the reach set of the generator . Similarly,

   where generator reach set for line i.e., it is the set of

   all generators which reach line .

   Similarly, to decompose the load in terms of generator contributions consider the generators from which that load can be supplied. Then the equation (11) is modified as follows:

   the load reach set can be found out and load is said to

   =

   .

   , = 1, . . . ,

   reach an arc (, ) if .

   (41)

   where generator reach set for load i.e., it is the set of all generators which reach load .

   Fig. 2. Graph of a 6 bus system.

   This method is illustrated using the Figures 2 and 3. Let us take a directed graph as shown in Figure 2 which is a 6-bus system with 2 generators, 4 loads, and 7 branches. If we start from generator 1 and traverse in the direction of flow we can reach the nodes 1, 3, 4, and 5 only. So, the power from generator 1 is flowing through branches II, VI, and VII only and it can supplying to the loads 1, 3, and 4 only. This information is tabulated in Table II.

   Fig. 4. Reach of load L1.

   Table III Reach set of loads

   Load	Branches	Generators
   L1	I,II, and IV	G1 and G2
   L2	IV	G2
   L3	VII	G1
   L4	III, IV, V, VI, and VII	G1 and G2

   From the graph shown in Figure 4, load 1is drawing power from both the generators 1 and 2 through the branches I, II, and IV (for other loads it is listed in Table III). So, instead of decomposing the branch flow to all load cmponents, we restrict decomposition to only those loads which can reach a line and generator. Thus, equations (6) and

   (13) can be modified as follows:

   =

   . ,

   (42)

   Fig. 3. Reach of Generator G1. Table II Reach set of generators

   Generator	Branches	Loads
   G1	II, VI, and VII	L1, L3 and L4
   G2	I, III, IV, and V	L1, L2 and L4

   Generator	Branches	Loads
   G1	II, VI, and VII	L1, L3 and L4
   G2	I, III, IV, and V	L1, L2 and L4

   Where load reach set for line i.e., it is set of all loads which reach line .

   = . , = 1, . . . , (43)

   where load reach set for generator i.e., it is the set of all loads which reach generator .

   In this implementation to traverse the graph and keep the

   track of visited nodes and edges we used the well-known

   depth first search [6].

   For an arc, if a generator or load is not in its reach set, then it implies that the corresponding commodity flow cannot reach the arc. Hence the corresponding generator tracing or load tracing variables can set to zero. This can achieve significant reduction in the number of variables actually modeled by LP. This leads to reduced number of variables in the LP problem. Further, the reduced problem can be solved by sparse LP method.

4. OBJECT ORIENTED DESIGN [7] FOR EFFICIENT TRACING ENGINE

   Implementation of the computationally efficient tracing engine requires sparse linear programs. Any commercial LP package would be sufficed. The tracing engine has mainly two classes one is tracing engine and another one is for core tracing algorithm. The class names are given as follows:

   1. TracingEngine

   2. TracingAlgo

      The class diagram of the above two classes are shown in the Figures 5 and 6.

      Fig. 5. Class diagrams of main classes of Tracing Engine.

      Fig. 6. Class diagram of TracingAlgo.

      1. Tracing Engine

         The tracing engine is mainly meant for the following tasks.

         • build the input

         • pre-process the input data

         • build input network object

         • find the reach set

         • compute the output of the tracing engine

      2. Tracing Algorithm

      1. Attributes of TracingAlgo class: The tracing algorithm class (TracingAlgo) is a design for core computation of the tracing. This class will call dashoptimization tool box for solving linear programming problem.

      2. Methods in TracingAlgo class:

         • InitDashOpt(): Initialize the dash optimization tool.

         • XPRBPrbDef(): used to define a problem for Dash optimization.

         • Run(InputTracingNw:, Reachset:): Run the tracing algo by passing arguments InputTracingNw and ReachSet.

         • RegVar(): Register the common variables for all the methods. It is a private method.

         • RegSpecVar(): Register the specific variables for particular method. It is a protected method.

         • RegConstr(): Register the common constraints for all the methods. It is a private method.

         • RegSpecConstr(): Register the specific constraints for particular method. It is a protected method.

         • Solve(): This method used to call the solve method of dashoptimization

5. RESULTS

   The algorithm has been tested on the standard IEEE test systems [8] and a real life Indian Grid system [9].

   1. IEEE 6 Bus System

   2. IEEE 30 Bus System

   3. IEEE 58 Bus System

   4. IEEE 118 Bus System

   5. NER Grid (India) 488 Bus System [9].

   TABLE IV: COMPARISON OF ALGORITHMS WITH AND WITHOUT SYMBOLIC REDUCTION TECHNIQUE

   S.No	System	No. of Nodes	No. of Variable		No. of constraints		Time required (Secs)
   			Without reduction	With reduction	Without reduction	With reduction	Without reduction	With reduction
   1	IEEE 6 Bus	6	70	41	488	343	0.01	0.007
   2	IEEE 30 Bus	30	1498	542	1065	511	0.05	0.03
   3	IEEE 57 Bus	58	4640	1131	3293	1190	0.18	0.07
   4	IEEE 118 Bus	118	23544	3210	15252	3808	1.4	0.29
   5	NER Grid (India)	488	4511420	45703	3995453	72168	#	21.83
   # – Could not solve optimal tracing problem without symbolic reduction technique

   The number of variables and the computational time of the algorithm with and without symbolic reduction technique is given in the Table IV. The table clearly shows that symbolic reduction technique significantly reduces number of variables and time required to solve optimal tracing problem. The number of variables for solving optimal tracing problem on NER Grid (India) system with symbolic reduction technique is 45703 and it is solved in 21.83 seconds. However, without application of the symbolic reduction technique, the number of variables is 4511420; a commercial optimization software could not solve the problem. The results of different systems is shown in Table IV. The percentage reduction in variables, constraints, and computational time with symbolic reduction technique is given in Table V and Figure 7.

6. CONCLUSION

The number of variables and the time required for solving an optimal tracing problem have been reduced significantly with symbolic reduction technique. A commercial optimization tool box which failed to solve the large system like NER grid (India) system without symbolic reduction. However it is solved the same system in 21.83 seconds with symbolic reduction technique.

The symbolic reduction technique is not an addition to the optimal tracing problem, it is a prerequisite for the optimal tracing problem.

Table V Comparison of existing and proposed methods

NER Grid (India)

Fig. 7. Percentage reduction in variables, constraints and computational time using proposed method.

REFERENCES

1. D. Shirmohammad, X. Filho, B. Gorenstin, and M. V. Pereira, Some fundamental technical concepts about cost based transmission pricing, IEEE Transactions on Power Systems, vol. 11, no. 2, pp. 10021008, May 1996.

2. J. W. Bialek, Tracing the flow of electricity, Proc. Inst. Elect. Eng. Gen., Transm., Distrib., vol. 143, no. 4, pp. 313320, July 1996.

3. A. R. Abhyankar, S. A. Soman, and S. A. Khaparde, Optimization approach to real power tracing: an application to transmission fixed cost allocation, IEEE Transactions on Power Systems, vol. 21, no. 3, pp. 13501361, Aug. 2006.

4. A. R. Abhyankar, S. A. Soman, and S. A. Khaparde, Min-max fairness criteria for transmission fixed cost allocation, IEEE Transactions on Power Systems, vol. 22, no. 4, pp. 20942104, Nov. 2007.

5. M. Rao, S. Soman, P. Chitkara, R. Gajbhiye, N. Hemachandra, and B. Menezes, Min-max fair power flow tracing for transmission system usage cost allocation: A large system perspective, IEEE Transactions on Power Systems, vol. 25, no. 3, pp. 14571468, Oct. 2010.

6. Wikipedia, Depth-first search wikipedia, the free encyclopedia, 2016, [Online; accessed 7-March-2016]. [Online]. Available: https://en.wikipedia.org/w/index.php?title=Depth- first_search&oldid=702377813

7. G. Booch, Object-oriented Analysis and Design with Applications, ser. Object Technology Series. Addison-Wesley, 2007. [Online]. Available: https://books.google.co.in/books?id=3NQgAQAAIAAJ

8. University of Washington Electrical Engineering, Resources: Power systems test case archive, 2016, [Online; accessed 7-March-2016]. [Online]. Available: https://www.ee.washington.edu/research/pstca/

9. Power System Operation Corporation Limited, Truncated network and load flow results, 2016, [Online; accessed 7-March-2016]. [Online]. Available: http://posoco.in/attachments/article/181/Truncated% 20Network%202013-2014 Q1.zip G. Eason, B. Noble, and I.N. Sneddon, On certain integrals of Lipschitz-Hankel type involving products of Bessel functions, Phil. Trans. Roy. Soc. London, vol. A247, pp. 529-551, April 1955.

G. V. Narayana received his B.Tech degree from Acharya Nagarjuna University, India in 1999 and M.Tech JNTU College of Engineering (Autonomous), Hyderabad, India, in 2008. Currently, he is pursuing his Ph.D. Degree in Power Systems at Andhra University College of Engineering (Autonomous), Visakhapatnam, India. His interested research areas are Power Systems operation and control, Network Analysis, Control Systems and Electrical Machines.

Dr. G.V. Siva Krishna Rao is a Professor in the Department of Electrical Engineering, Andhra University, Vishakhapatnam, India. Dr G. V. Siva Krishna Rao has received his Ph.D in Electrical and Electronics Engineering from Andhra University, in 2007. He is having 21 years of teaching and research experience. He has published 23 Papers in Journals and 25 Papers in Conferences. He has served various positions at administrative levels (Principal, Academic Council member, Member of the UGC, AICTE Committees, Academic-Senate)