A Fast Solution Method to Economic Dispatch Type Problem

Chenjia Feng; Chengcheng Shao; Xifan Wang; Life

网刊加载中。。。

使用Chrome浏览器效果最佳，继续浏览，你可能不会看到最佳的展示效果，

确定继续浏览么?

复制成功，请在其他浏览器进行阅读

A Fast Solution Method to Economic Dispatch Type Problem PDF

- ORCID：
Chenjia Feng (Student Member, IEEE)
✉
- ORCID：
Chengcheng Shao (Member, IEEE)
✉
- ORCID：
Xifan Wang
✉
- ORCID：
Life (Fellow, IEEE)

School of Electrical Engineering, Xi’an Jiaotong University, Xi’an 710049, China

Updated：2021-09-27

DOI：10.35833/MPCE.2019.000212

Abstract

Economic dispatch (ED) aims to minimize the generation cost subject to power balance constraints. It is extensively used in power system operation and planning. ED problem as well as other problems with the same formulation are named as ED-type problems in this letter and a fast solution method is provided. The proposed method is achieved by solving a series of relaxed problems. With a closed-form solution for the relaxed ED-type problems, it is demonstrated that the proposed method consumes far less computing time and memory space than the off-the-shelf solvers and other quadratic programming (QP) methods. Finally, the effectiveness and computational efficiency of the proposed method are verified by the case studies, which shows the great potential in power system planning and operation.

Keywords

Fast solution; economic dispatch; closed-form solution; quadratic programming

I. Introduction

ECONOMIC dispatch (ED) aims at the optimal allocation of power generation for minimizing the cost of supplying loads [

1], [2]. It lays the basis for the power system economics both in theory and practice. The ED problem works as a key component in many optimal operation tools such as unit commitment (UC). It is also deployed in power system planning as the modelling tool of production costs.

With quadratic generation cost functions, the basic ED problem is often formulated as a quadratic programming (QP) problem which only features box constraints for continuous variables and global equations. Meanwhile, many other problems such as hydro scheduling [

3], electric vehicle (EV) charging scheduling [4], and shiftable load scheduling for demand response applications are also formulated as QP problems. Along with ED problem, they are named as ED-type problems in this paper.

The ED-type problems are extensively used in smart grids. On the one hand, the single-period ED is directly adopted in the real-time dispatch for power output allocation which usually requires very fast solution. On the other hand, for the problems with more complex operation constraints such as the multi-period ED (dynamic ED) and security constrained ED (SCED), they can be transformed as a set of ED-type problems in iterations and other related parts via the decomposition methods [

5]. For the demand side, besides being able to be directly applied to the scheduling of single shiftable loads, the ED-type problems also play an important role in the decomposition method for the multi-period microgrid operation.

Many methods such as the active set method, interior point method, and Lamda iteration method [

1], [6] have been proposed to solve ED-type problems. However, the performance of them either depends highly on the initial value of the iteration or is restricted by the problem complexity. Nowadays, the ED-type problems are mainly solved by the off-the-shelf solvers, namely Cplex and Gurobi. Considering the ED-type problem is conducted with a high frequency and numerous iterations to solve other complex problems, it is still of vital necessity to provide fast solutions. For example, ED is executed every 5 min in the operation of power grid in China. In annual planning exercises, chronological ED solutions are often repeated 8760 times to obtain the long-term investment and operation costs of planning schemes in individual scenarios. With the development of smart grids, it is important to develop the methods which are affordable, occupy small memory space and support on-chip applications for numerous smart homes and appliances with shiftable loads.

The closed-form solution is a general idea to accelerate the solution and save the memory, on which some efforts have been made. The closed-form solution for the QPs with a single equality constraint is deduced in [

6], but the box constraints are not included. With the minimum/maximum output constraints taken into consideration, a series of units (variables) are aggregated into the equivalent one and then solved in [7]. However, it needs to calculate the intersections of inverse functions of the unit incremental cost involving large amounts of computational efforts.

In this letter, a fast solution method for ED-type problems is proposed via solving a series of the relaxed problems iteratively. The novelty of this letter lies in the follows.

1) A strict and precise algorithm is proposed to fix the close-form solution of relaxed problems into the allowed ranges. The corresponding proof is also provided.

2) The problem sparsity is fully exploited for solution efficiency improvement.

3) The case studies prove that the proposed method outperforms the off-the-shelf solvers and other QP methods with far less execution time and memory.

Although the formulation of ED-type problems appears simple, it has a great potential in practice as a basic component for the complex problems such as UC, SCED, and dynamic ED which can be decomposed into a series of ED-type problems. Therefore, the proposed method can also provide a pathway for the solution efficiency improvement of practical problems.

II. Proposed Fast Solution Method

A. ED Formulation

The conventional ED-type problem is formulated as:

m i n F = \sum_{g} (a_{g} p_{g}^{2} + b_{g} p_{g} + c_{g})

(1)

s.t.

p_{g, m i n} \leq p_{g}

(2)

p_{g} \leq p_{g, m a x}

(3)

\sum_{g} p_{g} = L

(4)

where p_g is the generation output of unit g; p_g_,min and p_g_,max are the minimum and maximum generation outputs, respectively; a_g, b_g, and c_g are the generation cost coefficients; and L is the system load. In (1), the emission cost can also be included by adjusting the cost function coefficients. The above formulae can be rewritten in a compact form as:

m i n F = \frac{1}{2} x^{T} Q x + b^{T} x + 1^{T} c

(5)

s.t.

x_{m i n} \leq x \leq x_{m a x}

(6)

1^{T} x = d

(7)

where x is the vector of generation output; $x_{m i n}$ and $x_{m a x}$ are the minimum and maximum values of x, respectively; d is the load; b and c are the vectors of generation cost coefficients; and Q is a positive definite symmetric and diagonal matrix.

The QP in (5)-(7) features box constraints which represent the ranges of variables, and an equality constraint for the bus power balance. For example, the scheduling of shiftable loads can be derived through (5)-(7), where (6) defines the load power limits and (7) defines the total energy consumption by the loads.

B. Relaxed Problem and Its Closed-form Solution

To solve the QP in (5)-(7), a relaxed problem is considered first where the generation output limits in (6) are not included. The Lagrangian function of the relaxed problem is defined as:

L (x) = \frac{1}{2} x^{T} Q x + b^{T} x + 1^{T} c - λ (1^{T} x - d)

(8)

where $λ$ is the dual multiplier to the balance constraint.

Then, for calculating the optimal solution x^r, we can obtain

{\frac{\partial L}{\partial x}|}_{x = x^{r}} = Q x^{r} + b - λ 1 = 0

(9)

x^{r} = Q^{- 1} (1 λ - b)

(10)

According to the equality constraint, $λ$ can be solved as:

1^{T} Q^{- 1} (1 λ - b) = d

(11)

λ = (1^{T} Q^{- 1} {1)}^{- 1} (d + 1^{T} Q^{- 1} b)

(12)

Substitute (12) into (10), and we can obtain

x^{r} = Q^{- 1} 1 (1^{T} Q^{- 1} {1)}^{- 1} (d + 1^{T} Q^{- 1} b) - Q^{- 1} b

(13)

Considering the formulae in (14), we can get the relaxed solution for the vector of generation output p^r with its element expressed by (15).

\{\begin{array}{l} Q = 2 d i a g (a_{1}, a_{2}, \dots, a_{M}) \\ b = {[\begin{matrix} b_{1} & b_{2} & \dots & b_{M} \end{matrix}]}^{T} \\ d = L \end{array}

(14)

p_{g}^{r} = \frac{2 L + \sum_{g} a_{g}^{- 1} b_{g}}{2 \sum_{g} a_{g}^{- 1}} a_{g}^{- 1} - \frac{a_{g}^{- 1} b_{g}}{2}

(15)

where M is the number of generators.

The complexity of the numerical calculation to solve the QP model is greatly reduced by the closed-form solution in (13). Furthermore, the computation burden of (15) is smaller than that of (13), which will definitely bring the improvement of solving speed since the direct matrix inverse and multiplication can be avoided. Generally, for the relaxed problem, the computation complexity is O(N), where N is the number of variables, and so is the required memory.

C. Accommodation of Generation Unit Constraints in Relaxed Solution

The solving speed of the relaxed problem is very fast, but the power results may violate the generation output limits (6). Thus, a revised solution is proposed in order to accommodate these limits. We divide the elements of the relaxed solution p^r into three groups according to the following principle.

\{\begin{array}{l} G_{1} = {g | p_{g}^{r} < p_{g, m i n}} \\ G_{2} = {g | p_{g, m i n} \leq p_{g}^{r} \leq p_{g, m a x}} \\ G_{3} = {g | p_{g}^{r} > p_{g, m a x}} \end{array}

(16)

For the generation units in G₁ and G₃, we define the terms (17) and (18), respectively, which describe the extent to which the relaxed solution violates the generation output limits. Herein, if $v i o_{1} = 0$ and $v i o_{3} = 0$ , the relaxed solution will be optimal for (1)-(4). For $v i o_{1} > 0$ or $v i o_{3} > 0$ , the following propositions hold.

v i o_{1} = \sum_{g \in G_{1}} (p_{g, m i n} - p_{g}^{r})

(17)

v i o_{3} = \sum_{g \in G_{3}} (p_{g}^{r} - p_{g, m a x})

(18)

Proposition 1: $p_{}^{*} = (p_{g}^{*})$ is the optimal solution of (1)-(4) while p^ris the relaxed solution. Accordingly, we can obtain

p_{g}^{*} = p_{g, m i n} \forall g \in G_{1}, v i o_{1} \geq v i o_{3}

(19)

p_{g}^{*} = p_{g, m a x} \forall g \in G_{3}, v i o_{3} \geq v i o_{1}

(20)

Proof: for the relaxed problem without considering generation output limits, according to (8)-(10), there exists

λ = 2 a_{g} p_{g}^{r} + b_{g} \forall g

(21)

For the problem stated in (1)-(4), let t_g, m_g, and p denote the dual multipliers of (2)-(4), respectively. According to the Karush-Kuhn-Tucker (KKT) conditions, for each g there exist

π + τ_{g} - μ_{g} = 2 a_{g} p_{g}^{*} + b_{g}

(22)

τ_{g} (p_{g}^{*} - p_{g, m i n}) = 0

(23)

μ_{g} (p_{g, m a x} - p_{g}^{*}) = 0

(24)

\{\begin{array}{l} τ_{g} \geq 0 \\ μ_{g} \geq 0 \end{array}

(25)

Consider (19) first. For a generation unit m in G₁, assume that

p_{m}^{*} > p_{m, m i n}

(26)

It implies $t_{m} = 0$ , and

\begin{array}{l} p_{m}^{*} > p_{m, m i n} \Rightarrow 2 a_{m} p_{m}^{*} + b_{m} > 2 a_{m} p_{m, m i n} + b_{m} \Rightarrow 2 a_{m} p_{m}^{*} + \\ b_{m} > λ = 2 a_{m} p_{m}^{r} + b_{m} \Rightarrow π = 2 a_{m} p_{m}^{*} + b_{m} + μ_{m} - τ_{m} > λ \end{array}

(27)

For generation unit n in G₂, if $m_{n} > 0$ , there exists (28); otherwise, if $m_{n} = 0$ , there exists (29).

p_{n}^{*} = p_{n, m a x} \geq p_{n}^{r}

(28)

\begin{array}{l} 2 a_{n} p_{n}^{*} + b_{n} = π + τ_{n} - μ_{n} \geq π \Rightarrow 2 a_{n} p_{n}^{*} + b_{n} > λ \Rightarrow \\ 2 a_{n} p_{n}^{*} + b_{n} > 2 a_{n} p_{n}^{r} + b_{n} \Rightarrow p_{n}^{*} > p_{n}^{r} \end{array}

(29)

Similarly, we can deduce that for unit k in G₃, there exists $p_{k}^{*} = p_{k, m a x} .$

Both p^* and p^r satisfy the equality constraint, so

\sum_{g \in G_{1}} (p_{g}^{r} - p_{g}^{*}) + \sum_{g \in G_{2}} (p_{g}^{r} - p_{g}^{*}) + \sum_{g \in G_{3}} (p_{g}^{r} - p_{g}^{*}) = 0

(30)

Accordingly, we can obtain

\begin{array}{l} v i o_{3} = \sum_{g \in G_{3}} (p_{g}^{r} - p_{g}^{*}) = \sum_{g \in G_{1}} (p_{g}^{*} - p_{g}^{r}) + \sum_{g \in G_{2}} (p_{g}^{*} - p_{g}^{r}) \Rightarrow \\ v i o_{3} \geq \sum_{g \in G_{1}} (p_{g}^{*} - p_{g}^{r}) > \sum_{g \in G_{1}} (p_{g, m i n} - p_{g}^{r}) \Rightarrow v i o_{3} > v i o_{1} \end{array}

(31)

The result contradicts the premise in (19), which proves the validity of (19). Also, (20) can be proven similarly.

Proposition 2: if $v i o_{1} = v i o_{3}$ , the optimal p^* satisfies

p_{g}^{*} = \{\begin{array}{l} p_{g, m i n} g \in G_{1} \\ p_{g}^{r} g \in G_{2} \\ p_{g, m a x} g \in G_{3} \end{array}

(32)

This can be proven easily in terms of Proposition 1. Using Propositions 1 and 2, we can determine the optimal values of the variables which violate the output limits in the relaxed solution. In this way, the size of the original constrained ED model is reduced. The process would be iterated until the optimal solutions are calculated for all variables as the relaxed solution is within the stated generation output limits. The solution procedure is summarized as below.

Algorithm 1

Preprocessing: check the generation output limits and the load. If $\sum_{g} p_{g, m i n} \leq L \leq \sum_{g} p_{g, m a x}$ , the constrained ED-type problem is feasible; otherwise, exit.

Initialization: solve the relaxed problem to get an initial solution p^r^,0 and set the iteration index k as 1.

while there is any violation of the generation output limits, do

1. Classify the generation units into three groups according to (16).

2. Calculate violations according to (17) and (18),

if vio₁>vio₃, $p_{g}^{*} = p_{g, m i n}, g \in G_{1}$ ;

else if vio₁<vio₃, $p_{g}^{*} = p_{g, m a x}, g \in G_{3}$ ;

else vio₁=vio₃, get p^*according to (32) and return.

3. Update a and b by removing the elements representing the coefficients of the determined variable $p_{g}^{*}$ . Update L by subtracting the calculated power values as expressed below.

$L^{k} = \{\begin{array}{l} L^{k - 1} - \sum_{g \in G_{1}} p_{g}^{*} v i o_{1} > v i o_{3} \\ L^{k - 1} - \sum_{g \in G_{3}} p_{g}^{*} v i o_{1} < v i o_{3} \end{array}$

Update $k \leftarrow k + 1$ .

4. Calculate p^r^,^k by solving the relaxed problem with the remaining unsolved variables.

end do

For the remaining variables $p_{g}^{*} = p_{g}^{r}$ , return p^*.

According to Algorithm 1, the iteration number needed is related to the load level and depends on the box constraint violations of the reduced solution. In each iteration, the output of the generation units which violate the generation output limits can be determined. That is, the more the generation units violate the limits, the more generation outputs can be determined. However, if there is no violation, the feasible optimal solution could be obtained at once. Since at least one variable can be determined in each iteration, the total computation complexity of the proposed method is O(N²) in the worst case and O( $N l g N$ ) on average, which features a high solution efficiency.

III. Case Study

The proposed method is first tested on the modified IEEE RTS-79 system [

8] (denoted as Case A). The base system consists of 26 thermal units with a peak load of 2850 MW. The simulation is carried out in MATLAB on an i7-6700 CPU, 3.40 GHz desktop computer. The proposed method is compared with the widely-used solvers CPLEX and Gurobi and the QP methods such as the active set and interior point methods. To examine the solution performance thoroughly, the load level is changed according to the original load value in the base system and the results are demonstrated in Fig. 1.

Fig. 1 Solving time and iterations for various load levels.

The generation costs and schedules obtained by the proposed method and the other solvers and methods are the same. For different load levels, only 3-4 iterations are needed for the proposed method, which consumes a much less computing time.

Moreover, the system size is changed to test the performance of the proposed method. The results are shown in Table I and Fig. 2. Case A1 denotes the base IEEE RTS-79 system (26 thermal units), while Cases A2 and A3 are twice and triple as the size of the base system, respectively.

Table I ED Results For IEEE RTS-79 System with Different Sizes

Solution	Case A1				Case A2				Case A3
Solution	Time (s)	Iteration	Memory (KB)	Cost ($)	Time (s)	Iteration	Memory (KB)	Cost ($)	Time (s)	Iteration	Memory (KB)	Cost ($)
Proposed method	0.017	3	2.42	43434	0.018	3	4.71	86868	0.018	3	7.00	130300
Cplex	0.580		302.69	43434	0.583		315.69	86868	0.592		328.69	130300
Gurobi	0.628		302.70	43434	0.639		315.70	86868	0.643		328.70	130300
Active set	0.350		29.17	43434	0.397		64.11	86868	0.445		120.17	130300
Interior point	0.400		29.17	43434	0.384		64.11	86868	0.401		120.17	130300

Fig. 2 Generation output results of one hour in Case A1.

It can be seen from Fig. 2 that for systems with different sizes, the proposed method provides strictly the same optimal solution both in generation cost and power output. As shown in Table I, the proposed method always outperforms the Cplex, Gurobi, and QP methods in calculation efficiency. In addition, it occupies much less system memory for computation, which proves to be a desirable characteristic.

To further verify the performance of the proposed method, it is also compared with the open-source tool Matpower. The ED results are shown in Table II. It can be observed that the proposed method outperforms the Matpower for the ED-type problems as well. Furthermore, a one-year simulation is conducted on the modified IEEE RTS-79 system to capture the influence of load variations on ED solved for each hour. The comparison of solving time and generation costs are given in Table III. The solving time of the proposed method is reduced by 2-3 orders of magnitude. According to Fig. 3, the proposed method requires 6 iterations at most and 3 iterations in most cases to determine the optimal power dispatching values.

TABLE II Comparison of ED Results of Proposed Method and Matpower

Solution	Case A1				Case A2				Case A3
Solution	Time (s)	Iteration	Memory (KB)	Cost ($)	Time (s)	Iteration	Memory (KB)	Cost ($)	Time (s)	Iteration	Memory (KB)	Cost ($)
Proposed method	0.017	3	2.420	43434	0.018	3	4.710	86868	0.018	3	7.000	130300
Matpower with Cplex	0.440		25.906	43434	0.450		25.906	86868	0.500		25.906	130300
Matpower with Gurobi	0.270		25.908	43434	0.300		25.908	86868	0.320		25.908	130300
Matpower with interior point	0.320		25.904	43434	0.330		25.904	86868	0.370		25.904	130300

TABLE III Result Comparisons for One-year ED Simulation on IEEE RTS-79 System

Solution	Case A1		Case A2		Case A3
Solution	Time (s)	Cost ($)	Time (s)	Cost ($)	Time (s)	Cost ($)
Proposed method	1.959	217640000	1.964	435270000	2.064	652910000
Cplex	871.660	217640000	1375.900	435270000	1859.500	652910000
Gurobi	1872.800	217640000	2143.400	435270000	2546.300	652910000
Active set	145.640	217640000	316.680	435270000	682.783	652910000
Interior point	59.435	217640000	61.858	435270000	78.910	652910000

Fig. 3 Distribution of iterations in one-year simulation.

To test the performance of the proposed method, the studies are also carried out on the IEEE 118-bus and IEEE 300-bus systems, and the results are provided in Tables IV and V. Case B1 denotes the base IEEE 118-bus system (54 units) while Cases B2 and B3 are twice and triple as the size of the base IEEE 118-bus system, respectively. Case C1 denotes the base IEEE 300-bus system (69 units) while Cases C2 and C3 are twice and triple as the size of the base IEEE 300-bus system, respectively. It can be observed that the proposed method also has outstanding performance in obtaining the exact solution with high efficiency and small memory occupied.

TABLE IV ED Results For IEEE 118-bus System with Different Sizes

Solution	Case B1				Case B2				Case B3
Solution	Time (s)	Iteration	Memory (KB)	Cost ($)	Time (s)	Iteration	Memory (KB)	Cost ($)	Time (s)	Iteration	Memory (KB)	Cost ($)
Proposed method	0.026	1	6.04	184670	0.025	1	12.63	369340	0.025	1	17.85	554010
Cplex	0.579		314.17	184670	0.588		337.69	369340	0.611		362.16	554010
Gurobi	0.621		314.18	184670	0.649		337.69	369340	0.685		363.12	554010
Active set	0.369		67.67	184670	0.420		211.11	369340	0.583		444.42	554010
Interior point	0.394		67.26	184670	0.391		210.28	369340	0.434		444.42	554010

TABLE V ED Results For IEEE 300-bus System with Different Sizes

Solution	Case C1				Case C2				Case C3
Solution	Time (s)	Iteration	Memory (KB)	Cost ($)	Time (s)	Iteration	Memory (KB)	Cost ($)	Time (s)	Iteration	Memory (KB)	Cost ($)
Proposed method	0.031	3	8.40	925450	0.029	3	16.66	1850900	0.030	3	24.93	2776300
Cplex	0.572		320.02	925450	0.625		351.29	1850900	0.658		382.55	2776300
Gurobi	0.644		320.02	925450	0.697		351.29	1850900	0.739		382.54	2776300
Active set	0.410		97.84	925450	0.625		329.10	1850900	0.849		709.14	2776300
Interior point	0.413		97.85	925450	0.409		329.10	1850900	0.421		709.14	2776300

IV. Conclusion

This paper proposes a fast solution method for the ED-type problems. The relaxed problems are solved iteratively, whose closed-form solution is derived so that the proposed method enjoys a very fast solution speed and rather small memory space occupied. The case studies have verified that the proposed method outperforms the off-the-shelf solvers CPLEX and Gurobi and QP methods to obtain the same results which uses far less computing time for various systems with different load levels and sizes. For the applications such as planning in which ED is repeated or iterated for many times, the reduced computing time is significant. Due to the similar model structure which utilizes sparsity, the proposed method also shows significant potentials for the on-chip applications of smart home load management.

The proposed method also throws some light on the acceleration of the decomposition methods for UC/SCED problems, although it cannot be directly applied, which will be studied in the future.

References

A. J. Wood and B. F. Wollenberg, Power Generation, Operation and Control. Hoboken: John Wiley & Sons Inc., 2013. [Baidu Scholar]

M. Mahmoodi, P. Shamsi, and B. Fahimi, “Economic dispatch of a hybrid microgrid with distributed energy storage,” IEEE Transactions on Smart Grid, vol. 6, no. 6, pp. 2607-2614, Nov. 2015. [Baidu Scholar]

G. W. Chang, M. Aganagic, J. G. Waight et al., “Experiences with mixed integer linear programming based approaches on short-term hydro scheduling,” IEEE Transactions on Power Systems, vol. 16, no. 4, pp. 743-749, Nov. 2001. [Baidu Scholar]

L. Gan, U. Topcu, and S. Low, “Optimal decentralized protocol for electric vehicle charging,” IEEE Transactions on Power Systems, vol. 28, pp. 940-951, May 2013. [Baidu Scholar]

A. Rabiee, B. Mohammadi-Ivatloo, and M. Moradi-Dalvand, “Fast dynamic economic power dispatch problems solution via optimality condition decomposition,” IEEE Transactions on Power Systems, vol. 29, no. 2, pp. 982-983, Mar. 2014. [Baidu Scholar]

B. Stephen and V. Lieven, Convex Optimization. Cambridge: Cambridge University Press, 2016. [Baidu Scholar]

L. Bayón, J. M. Grau, M. M. Ruiz et al., “An analytic solution for some separable convex quadratic programming problems with equality and inequality constraints,” Journal of Mathematical Inequalities, vol. 4, no. 3, pp. 453-465, Jan. 2010. [Baidu Scholar]

P. M. Subcommittee, “IEEE reliability test system,” IEEE Transactions on Power Apparatus and Systems, vol. PAS-98, pp. 2047-2054, Dec. 1979. [Baidu Scholar]

Address:No.19 Chengxin Avenue, Jiangning District, Nanjing 211106, China

E-mail: mpce@alljournals.cn

Tel:86-25-81093060

Fax:86-25-81093040

Home

Introduction

Editorial Board

For Author

Call For Papers

APC

Sponsor & Publisher