A Modified Linear Programming Method For Distribution System Reconfiguration

ELSEVIER

Electrical Power & Energy Systems, Vol. 18, No. 7, pp. 469-474, 1996 Copyright © 1996 Elsevier Science Ltd Printed in Great Britain. All rights reserved P I I : S0142-0615(96)00005-1 0142-0615/96/$15.00 + 0.00

A modified linear programming method for distribution system

reconfiguration Ali A b u r Department of Electrical Engineering, Texas A&M University, College Station, TX 77843, USA

large number of permissable ones among which one needs to pick the optimal configuration that results in minimum loss. Efficiency of this search is the key to the success of any proposed technique. The reconfiguration problem has been proposed to be formulated and solved in various different ways in the past. One approach is to start from a meshed configuration where all switches are closed, and to find the optimal radial configuration by opening one switch at a time 1. An approximate formula for estimating the change in losses each time a switching takes place, is developed in Reference 2. Operational constraints are taken into account while balancing the feeder loads by using different search techniques in References 3 and 4. Reference 5 studies the optimality conditions for minimum loss reconfiguration problem when using distributed and lumped load models. An efficient power flow algorithm for distribution systems is developed and incorporated into the reconfiguration problem solution in Reference 6. Heuristic search techniques are employed in Reference 7. Loss reduction and load balancing problems are formulated as a multi-objective, constrained and non-differentiable optimization problem and solved using a modified simulated annealing algorithm in References 8 and 9. Reference 10 formulated the problem as a trans-shipment problem with quadratic costs. An efficient heuristic method for loss reduction is described in Reference 11. Reference 12 applies a genetic algorithm to solve the minimum loss reconfiguration problem. In this paper, the reconfiguration problem is formulated as a minimum cost network flow problem. Such problems can be solved using linear programming as long as the line capacity limits are ignored. In order to enforce these limits, the revised Simplex algorithm is modified and the details of its implementation are presented along with examples. The resulting algorithm yields a radial configuration which does not violate any line capacity limits, while minimizing the losses.

This paper presents a reconfiguration method for radial distribution systems. The reconfiguration problem is formulated and solved using a modified linear programming approach. The modifications are introduced mainly to maintain a radial network configuration while enforcing the lineflow capacity limits. The implementation details are explained using a smrrll tutorial example. Simulation results for sample distribution systems are also given. Copyright © 1996 Elsevier Science Ltd Keywords: distribution systems, mathematical programming, utility application

I. I n t r o d u c t i o n Efficient operation of power distribution systems can be achieved by reconfiguring the system to minimize the losses as the operating conditions change. Reconfiguration has to be carried out by taking into account various operational constraint,; such as line and transformer ampacity limits, voltage limits, radiality of the resulting system configuration, etc. Reconfiguration is done by opening and closing switches in order to modify the amount of power flow through the feeder sections. Given a network containing n switches, there will be 2n possible configurations corresponding to the open and closed positions of all the switches. Some ef these configurations are not permissable because tl~ey yield either a disconnected system with several islands, or a non-radial configuration. Distribution systems are configured radially in order to comply with the protective relaying requirements. Certain other configurations may not be feasible due to the violation of operational constraints. Despite all these non-permissable configurations, there still remains a Received11 May 1995; revised13 August 1995; accepted4 January 1996

469

470

Modified linear programming method. A, Abur

II. P r o b l e m f o r m u l a t i o n

GENERATION

[A][Pf]=[P]

L

Minimize J = ~

0dilef(i)[

(2)

i=1

Subject to [A] [Pf] = [P]

(3)

[E] [[Pfl] ~<[pu]

(4)

were ~M i is the cost of transmitting per unit power along branch i. This cost is set equal to the resistance of the corresponding branch, thus penalizing high flows through branches with higher resistance, pu is the vector of branch power capacity limits, and E is a binary matrix relating the branch flows and their limits. Let Pf(i) = X i - Yi, such that both Xi and Yi are non-negative variables which cannot both be non-zero simultaneously. The above optimization problem can then be written as an equivalent linear programming (LP) problem as below: L

Minimize

~ 6

(1)

where [A] = node-to-branch reduced incidence matrix, [Pf] = vector of all branch flows, and [P] = vector of nodal injections, excluding the reference node. If the system is fully connected and has N nodes, then the column rank of the coefficient matrix A in equation (1) will be N - 1. Hence, for a system with L branches, only N - 1 branches will carry non-zero flows, the rest of them will represent open circuits. Depending on the choice of these N - 1 closed branches, the solution of equation (1) will change, yielding a different operating condition. The radial configuration of the system will be maintained as long as each time an open branch is closed, an already closed branch is opened. A new objective function J(Pf) will be considered where, J(Pf) is a weighted sum of the absolute power flows through all the network branches. The weights represent the penalties (or cost) of transporting a unit of power over the respective branches. While other choices are also possible, in this study this cost is set as equal to the resistances of the associated branches. In order to determine the optimal radial configuration while enforcing the line capacity limits, the following optimization problem will have to be solved:

Z ~oi(Xi+ Yi)

(5)

LOAD

Xl

Consider the power balance equations where the system is assumed to be lossless:

x2

Figure 1. Two bus example system x2 i.~"-~

CAPACITY LIMIT

[

6 5.

' • • . ~ . . . - - - - I OPTIMALSOLUTION "'•••

[

J* = 11.0

4_ ••

3_

POWER BALANCE EQUATION

2. 1. I

I

f

I

2

3

4

5

J=

•'t

I

6

v

x1

Xl+2X 2

Figure 2. Graphical illustration of LP solution

I1.1 Example 1 Consider the two node, two branch system shown in Figure 1. Denoting the branch flows by xl and x2, and assuming that the resistances of the branches are 1 and 2 per unit, respectively, and the flow through branch 1 is limited to 1.0 per unit, the corresponding LP problem can be written as below: Minimize J = Xl + 2x2 (8) Subject to Xl + x2 = 6

(9)

x I ~<1

(10)

(11) The optimal solution is shown graphically in Figure 2. The objective function has a value of 11.0 at the optimum and both branch flows are non-zero, xl = 1.0, x2 = 5.0, i.e. the system configuration is not radial. The non-radial solution is obtained due to the fact that one of the branch flows has to be constrained at its capacity limit. X1,X2 >~0.

i=1

III. Proposed m e t h o d Subjectto [ ;

-A][;I

[x],[v]

~ [:u ]

(6)

0.

(7)

The main difficulty in this formulation is how to maintain the radiality of the system while enforcing the line capacity limits. Attempting to solve the above LP problem using the well-known Simplex method will not yield a radial system if at least one of the line flows hits its capacity limit. In this case, the regular LP solution will correspond to a system containing loops. The following simple example will be used to illustrate this point.

A new problem formulation and its solution method will now be described. The formulation will incorporate the line capacity limits and the proposed solution method will ensure a radial system configuration within these limits if one exists. Let us rewrite the LP problem given by equations (5)(7) by introducing slack variables: Minimize WzT x Z (12) Subjectto [ H ; ] [ Z ]

= [:u]

Z,s ~>0

(13) (14)

471

Modified linear programming method: A. Abur where U = the identity matrix, W f = [wl ... WLWl ... w/,], Z T = [xTyT], S = vector of slack variables, and

In order to ensure that the corresponding system remains radially configured, only (N - 1) columns of It in equation (13) must remain in the basis. This will be the case if and only if all columns of U (corresponding to the slack variables s) are forced to remain in the basis as well. Hence, if the LP problem of equations (12)-(14) can be initialized by choosing a basis which contains all the columns of the slack wtriables s, and during the subsequent Simplex iterations if these slack variables are not allowed to leave the basis, then the converged solution will yield the best possible radial configuration. Therefore, the overal.1 algorithm will be composed of two phases: (1) Phase I: Initialization; (2) Phase II: Optimization. The two phases of the proposed algorithm will be described in detail below. Ilia Phase I: Initialization and feasibility check The LP problem of equations (12)-(14) can be initialized by introducing artificial[ variables Xa. The reason behind the introduction of these artificial variables x a, is to create an artificial starting basis which contains all the slack variables s. The columns corresponding to the artificial variables will be driven out of the starting basis one by one and will be replaced by a subset of the columns of H during Phase I. In order to accomplish this, the following LP problem will be set up and then solved: N-I

Minimize ~

(15)

MXa(i)

i=l

I

=['] ° li

Subject to t t O a 1U

pu

Z, Xa, s 3 0

(16)

(17)

where M is a large, positive weight given to the artificial variables, while all the other variables Z, s are assigned zero weights. The starting basis will be chosen as:

[':a 0][':] [;. 1 where Da is a diagonal matrix whose entries are given by: Da(i, i)---

1.0 if P(i)>~0 ] . -1.0 otherwiseft=l'""N-l" k

The LP problem of equations (15)-07) is solved using a modified Simplex method. The modification of the Simplex logic is rather simple and involves a restriction on the selection of the columns to leave the basis at each Simplex iteration. The columns that correspond to the slack variables will not be allowed to leave the basis. A detailed account of how this can be implemented in the form of an algorithm is given in Section III.3 below.

After solving the LP problem given by equations (15)(17) using the modified Simplex method: • If the objective function equation (15) is still non-zero, this will imply that a radial system configuration cannot be found within the line capacity constraints. Hence, the problem will be declared to be infeasible. • If the problem is feasible, then the optimal solution will yield a zero objective function and the initial basis for the subsequent Phase II solution. This initial basis will contain the columns of all the slack variables and will look like:

,:[.l 1 Here, the columns [Da/0 ] of the starting basis are all replaced by a subset of the columns of It, denoted here by the submatrix a 1. 111.2 Phase I1: optimization Let us assume that an initial basis that includes the columns of all the slack variables, has already been obtained in Phase I, as described in the above subsection. In Phase II, the LP problem of equations (12)-(14) will then be solved, again using the modified Simplex method. The objective function is the only change needed to switch from Phase I to Phase II. The objective function of Phase I given by equation (15) will be replaced by equation (12). The solution will be found when the modified Simplex method converges. 111.3 Modified Simplex algorithm The modified Simplex method will be described for the Phase II problem, with the understanding that by a simple change of objective function and initial basis, it can be directly applied to Phase I as well. Assuming that Phase I initialization is successful, the constraint equations can be written in terms of the basic x a and non-basic x o variables as shown below:

[. 0] iz, B

xB

,18, b

Here, Zl and Z 2 represent the basic and non-basic branch flow variables, respectively. Note that as long as all the slack variables remain in the basis during the Simplex iterations, i.e. the columns leaving B are always picked from those corresponding to Z1 variables, then the resulting system configuration will remain always radial. In order to ensure this, the well-known Simplex algorithm for solving linear programming problems 13, will have to be slightly modified. The proposed modifications in the Simplex iterations will be described using the notation of equation (18). The steps of the algorithm are given below: (1) Compute the basic solution xB = B-lb. (2) Set the counter k = 1. (3) Calculate the relative costs of non-basic variables, rD: r T = cT _ c~B-1a Sort the entries of r D in ascending order as: rD(il) ~rD(i2) ~ ' ' " ~rD(iL)

472

Modified linear programming method." A. Abur

(4) IfrD(ik)/>0, stop, XB is the final solution• Else, go to the next step. (5) Solve By = Dik, where Di~ is the ikth column of D. (6) If y(j)~<0 for all j, then the solution is unbounded• Else, find • xB(j) mln--

J y(j)'

x2

.~.~ i

CAPACITYLIMIT [

I OPTIMALRADIALSOLUTION J*

=

12.0

fory(j) > 0.

(7) I f j t h variable of the basis is a slack variable, then increment the counter k = k + 1 and go to step (4). Otherwise, go to the next step. (8) Update the basis B, by replacing thejth column of B by Dik. Go to step (1).

POWERBALANCE EQUATION

3.4 Example 2 Let us apply the above described algorithm to the solution of Example 1, presented earlier. Introducing the slack variable, s, the problem can be rewritten as:

I

I

I

I

2

3

4

5

[J=Xl+2X2

•I x!

6

[

Minimize Xl + 2x2 Subject to Xl + x2 -- 6

XI+S=I Xl~X2~S >jO Assume that Phase I is executed and the initial basic feasible solution is obtained as Xl = 0,x 2 = 6,s-- 1 i.e. the basis columns are chosen as the ones corresponding to variables x2 and s. Then the steps of the algorithm for the Phase II solution will be executed as follows: ek=l. • There is only one non-basic variable Xl and its relative cost i S r o ( 1 ) = l - - 2 = - - l . • Relative cost is negative, so continue. • Solving for y = [1 1]r. • min(XB(l) \ y, ' xB(2)" y2 )I = ( T6' T 1 )=I's°j=2"

• But the second variable Xa (2) is a slack variable, so k is incremented by 1, k = 2 . Go to step (4) of the algorithm. Since D has only one column, the kth (second) column does not exist. Thus, the algorithm terminates at the fourth step with the desired radial solution: x;=0.0,

Figure 3 Graphical illustration of the radial solution If the objective function is not zero, then declare the problem infeasible and stop. There is no radial configuration possible that will satisfy all the line capacity constraints• (2) Starting with the initial basic feasible solution obtained at the end of Phase I, solve the LP problem given by equations (12)-(14) again using the modified Simplex algorithm described in Section 111.3. The branches whose corresponding flow variables are basic at the solution will be the closed branches• The non-basic branch flow variables will indicate the open branches with zero flows through them. V. Test

results

A computer program which executes the proposed algorithm is developed. A 16 bus test system, whose one-line diagram is shown in Figure 4, is used for the simulations. The branch data and bus loads for this system are given in the Appendix. The developed program only uses the real power injections and the branch resistances in the optimization procedure. Once the optimal configuration is determined by the program, a power flow for the corresponding configuration is executed to determine the actual losses for that

x~=6.0

A graphical illustration of this is given in Figure 3. In this case, the modified algorithm settles at a solution which not only satisfies the line capacity constraint but also the radiality of the network. Note that the optimal objective function value is 12.0 which is higher than the one corresponding to the non-radial solution.

IV. Summary of the proposed method

,j

The proposed two phase solution method can now be summarized as below: (1) Solve the LP problem given by equations (15)-(17) using the modified Simplex method described in Section Ill.3. If the objective function is zero at the solution, then continue to step (2).

14

Figure 4. 1 6 Bus Test System

Modified linear programming method."A. Abut

473

Table 1. Unconstrained ease results

Configuration

Base case

Optimal configuration

Open branches Losses Minimum bus voltage

3-8, 5-12, 6-13, 9-15, 10-16, 10-12 14.2 MW 0.918

2-3, 8-9, 9-10, 11-12, 12-13, 10-12 10.0 M W 0.952

Configuration

Case 1

Case 2

Open branches

2-3, 9-10, 9-15, 11-12, 12-13, 10-12

7-8, 8-9, 9-10, 11-12, 12-13, 10-12

Constraints

P1,2 ~<2.0 P8,9 ~<1.0 P14,15 ~ 1.0 Pll,12 ~<3.0 P10,12 ~<1.0

Pl,7 ~ 2.0 P2,3 ~<3.0 P3,11 ~<3.0 P7,8 ~<1.0 Pl0,16 ~ 1.0 P10,12 ~ 1.0 PlI,12 ~<3.0

Losses

10.1 MW

19.3 MW

Table 2. Constrained ease results

Minimum bus voltage

0.951

configuration. Voltage constraints are not taken into account in this work. The base configuration is given in Table 1. Only the open branches are indicated in the table in order to describe the system configuration. Initially, no capacity constraints are introduced and the program is executed to find the optimal reconfiguration. This unconstrained case resulted in the configuration and losses given in Table 1. Note that even though voltage constraints are not used, minimum loss reconfiguration improved the bus voltage profile as can be observed from the minimum bus voltage given for the two cases. Two constrained ca:ses are presented in Table 2. The constraints are satisfied in both cases, while losses are attempted to be miniraized. In the first case, the losses remained almost at their optimal value as in the unconstrained case. The second case which contains more stringent limits resulted in a configuration yielding a much higher loss. The voltage profile is accordingly deteriorated as can be seen from Table 2. In order to test the program's ability to detect infeasible cases, the capacity limit on branches 1-7 is reduced down to 0.5 p.u. in the second case. The program was unable to initialize the LP problem returning an infeasibility flag instead. The program is altso tested using a realistic size distribution system having 474 buses and 496 branches. The tests are executed using a Sun Spare 1000 using the Solaris 2 . 3 0 / S and the recorded cpu time was 49.6 s for this test system. VI. C o n c l u s i o n s

A linear programming based algorithm is presented for distribution system reconfiguration with minimum loss. The proposed method does not take into account the voltage constraints, but accounts for the line capacity limits while maintaining a radial system configuration. It can also determine the infeasibility of a given problem during the initialization of the linear programming solution. The suggested modifications can be implemented in an existing LP program easily, as described in this paper. The natural extension of the presented method to the case

0.913 where voltage constraints are also accounted for in the optimization process, is currently under study.

VII. A c k n o w l e d g e m e n t s The author would like to thank Drs Dariush Shirmohammadi, Carol Cheng, Qin Zhou and Edwin Liu of the Pacific Gas and Electric Company for the valuable discussions during this study.

VIII. References 1 Merlin, A and Back, H 'Search for minimum loss operating spanning tree configuration in urban power distribution systems' Proceedings of 5th Power Systems Computations Conference, UK (1975) 2 Civanlar, S, Grainger, J J, Yin, H and Lee, S S H 'Distribution feeder reconfiguration for loss reduction' IEEE Trans. Power Delivery Vol 3 No 3 (1988) 1217-1223 3 Aoki, K, Kuwabara, H, Satoh, T and Kanezashi, M 'Outage state optimal load allocation by automatic sectionalizing switches operation in distribution systems' IEEE Trans. Power Delivery Vol 2 No 4 (1987) 1177-1185 4 Aoki, K, Kuwabara, H, Satoh, T and Kanezashi, M 'An efficient algorithm for load balancing of transformers and feeders by switch operation in large scale distribution systems' IEEE Trans. on Power Delivery Vol 3 No 4 (1988) 1865-1872 5 Liu, C C, Lee, S J and Vu, K 'Loss minimization of distribution feeders: optimality and algorithms' IEEE Trans. Power Delivery Vol 4 No 2 (1989) 1281-1289 6 Baran, M E and Wu, F F 'Network reconfiguration in distribution systems for loss reduction and load balancing' IEEE Trans. Power Defivery Vol 4 No 2 (1989) 1401-1407 7 Morelato, A L and Monticelli, A 'Heuristic search approach to distribution system restoration' IEEE Trans. Power Delivery Vol 4 No 4 (1989) 2235-2241 8 Chiang, H D and Jumean, R J 'Optimal network reconfigurations in distribution systems: Part 1: A New Formulation and a solution methodology' IEEE Trans. Power Delivery Vol 5 No 4 (1990) 1902-1909

Modified linear programming method." A. Abur

474

9 Chiang, H D and Jumeau, R J 'Optimal network reconfigurations in distribution systems: Part 2: Solution algorithms and numerical results' IEEE Trans. Power Delivery Vol 5 No 3 (1990) 1568 1574

Load data

D0 Glamocanin, V 'Optimal loss reduction of distribution networks' IEEE Trans. Power Syst. Vol 5 No 3 (1990) 774-782 11 Shirmohammadi, D 'Service restoration in Distribution networks via network reconfiguration' IEEE Trans. Power Defivery Vol 7 No 2 (1992) 952-958

12 Nara, K, Shiose, A, Kitagawa, M and Ishihara, T 'Implementation of genetic algorithm for distribution systems loss minimum reconfiguration' IEEE Trans. Power Syst. Vol 7 No 3 (1992) 1044-1051 13 Luenberger, D G 'Linear and nonlinear programming' Addison-Wesley (1984)

Appendix Branch data

From

To

R (p.u.)

X (p.u.)

B (p.u.)*

1 2 3 4 5 1 7 8 9 9 7 14 15 3 11 12 5 6 10 10 3

2 3 4 5 6 7 8 9 10 15 14 15 16 11 12 13 12 13 16 12 8

0.0083 0.0098 0.0012 0.0025 0.0030 0.0020 0.0039 0.0099 0.0069 0.0058 0.0048 0.008l 0.0032 0.0069 0.0078 0.0054 0.0038 0.0062 0.0002 0.007l 0.0024

0.0080 0.0150 0.0066 0.0040 0.0080 0.0040 0.0050 0.0175 0.0099 0.0098 0.0080 0.0180 0.0074 0.0169 0.0110 0.0160 0.0080 0.0130 0.0041 0.0147 0.0051

0.0645 0.0409 0.0190 0.0129 0.0174 0.0138 0.0235 0.0274 0.0220 0.0109 0.0386 0.0203 0.0055 0.0115 0.0494 0.0273 0.0143 0.0272 0.0062 0.0074 0.0134

*½line charging susceptance.

Load (pu) Bus number

P

O

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

0.000 0.330 0.410 0.200 0.130 O.05O 0.400 0.500 0.210 0.050 0.250 0.770 0.180 0.105 0.220 0.430

0.000 0.180 0.210 0.100 0.040 0.020 0.200 0.220 0.160 0.020 0.150 0.240 0.023 0.053 0.050 0.030