 Open Access
 Total Downloads : 126
 Authors : G. V. Narayana, Dr. G. V. Siva Krishna Rao
 Paper ID : IJERTV5IS031141
 Volume & Issue : Volume 05, Issue 03 (March 2016)
 DOI : http://dx.doi.org/10.17577/IJERTV5IS031141
 Published (First Online): 28032016
 ISSN (Online) : 22780181
 Publisher Name : IJERT
 License: This work is licensed under a Creative Commons Attribution 4.0 International License
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

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 postagestamp 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.

MWMile method: MWMile 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.

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.

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.

Minmax fairness method [4], [5]: A Minmax fair power flow tracing has been proposed in [4]. The minmax power flow tracing further improved in [5] for application in large systems. A solution is said to be minmax 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 minmax 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.

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.

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 minmax 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. Minmax 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 Minmax fairness tracing method are
Since the branch flows are known and are unknown, flow equations for generation allocation can be written as follow:
[ ][] = [] (5) 
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 SectionIII. 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)



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)

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

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)

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) 

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

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.

Generation Tracing: Let represents submatrix 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 generatorload interaction losses should be equal to the power loss in the system.


Explicit formulation

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:
[=

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.

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
{, } =  


SYMBOLIC REDUCTION TECHNIQUE
The tracing problem discussed in SectionII is modeled by a multicommodity 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

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:

exploitation of sparsity linear programming and
=1

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 6bus 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 wellknown
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.


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:

TracingEngine

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.

Tracing Engine
The tracing engine is mainly meant for the following tasks.

build the input

preprocess the input data

build input network object

find the reach set

compute the output of the tracing engine


Tracing Algorithm

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.

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




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

IEEE 6 Bus System

IEEE 30 Bus System

IEEE 58 Bus System

IEEE 118 Bus System

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.


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)
S.No 
System Name 
No. of Buses 
% Reduction 

Variables 
Constraints 
Time 

1 
6 Bus 
6 
41.43 
29.71 
30 
2 
30 Bus 
30 
63.82 
52.02 
40 
3 
57 Bus 
58 
75.63 
63.86 
61.11 
4 
118 Bus 
118 
86.37 
75.03 
79.29 
5 
488 
98.99 
98.19 
# 

#Could not solve optimal tracing problem without symbolic reduction technique 
Fig. 7. Percentage reduction in variables, constraints and computational time using proposed method.
REFERENCES

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.

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

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.

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

M. Rao, S. Soman, P. Chitkara, R. Gajbhiye, N. Hemachandra, and B. Menezes, Minmax 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.

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

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

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

Power System Operation Corporation Limited, Truncated network and load flow results, 2016, [Online; accessed 7March2016]. [Online]. Available: http://posoco.in/attachments/article/181/Truncated% 20Network%2020132014 Q1.zip G. Eason, B. Noble, and I.N. Sneddon, On certain integrals of LipschitzHankel type involving products of Bessel functions, Phil. Trans. Roy. Soc. London, vol. A247, pp. 529551, 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, AcademicSenate)