Portal de Periódicos da CAPES

Fast identifying redundant security constraints in SCUC in the presence of uncertainties

2020; Institution of Engineering and Technology; Volume: 14; Issue: 13 Linguagem: Inglês

10.1049/iet-gtd.2019.1275

1751-8695

Tao Ding, Ming Qu, Jiawen Bai, Wenhao Jia, Jiang Wu, Yuankang He, Tianen Chen,

Power System Reliability and Maintenance

IET Generation, Transmission & DistributionVolume 14, Issue 13 p. 2441-2449 Research ArticleFree Access Fast identifying redundant security constraints in SCUC in the presence of uncertainties Tao Ding, Corresponding Author Tao Ding tding15@mail.xjtu.edu.cn State Key Laboratory of Electrical Insulation and Power Equipment, School of Electrical Engineering, Xi'an Jiaotong University, Xi'an, Shaanxi, 710049 People's Republic of ChinaSearch for more papers by this authorMing Qu, Ming Qu State Key Laboratory of Electrical Insulation and Power Equipment, School of Electrical Engineering, Xi'an Jiaotong University, Xi'an, Shaanxi, 710049 People's Republic of ChinaSearch for more papers by this authorJiawen Bai, Jiawen Bai State Key Laboratory of Electrical Insulation and Power Equipment, School of Electrical Engineering, Xi'an Jiaotong University, Xi'an, Shaanxi, 710049 People's Republic of ChinaSearch for more papers by this authorWenhao Jia, Wenhao Jia State Key Laboratory of Electrical Insulation and Power Equipment, School of Electrical Engineering, Xi'an Jiaotong University, Xi'an, Shaanxi, 710049 People's Republic of ChinaSearch for more papers by this authorJiang Wu, Jiang Wu State Key Laboratory of Electrical Insulation and Power Equipment, School of Electrical Engineering, Xi'an Jiaotong University, Xi'an, Shaanxi, 710049 People's Republic of ChinaSearch for more papers by this authorYuankang He, Yuankang He Northwest Branch of State Grid Corporation of China, Xi'an, Shaanxi, 710048 People's Republic of ChinaSearch for more papers by this authorTianen Chen, Tianen Chen Northwest Branch of State Grid Corporation of China, Xi'an, Shaanxi, 710048 People's Republic of ChinaSearch for more papers by this author Tao Ding, Corresponding Author Tao Ding tding15@mail.xjtu.edu.cn State Key Laboratory of Electrical Insulation and Power Equipment, School of Electrical Engineering, Xi'an Jiaotong University, Xi'an, Shaanxi, 710049 People's Republic of ChinaSearch for more papers by this authorMing Qu, Ming Qu State Key Laboratory of Electrical Insulation and Power Equipment, School of Electrical Engineering, Xi'an Jiaotong University, Xi'an, Shaanxi, 710049 People's Republic of ChinaSearch for more papers by this authorJiawen Bai, Jiawen Bai State Key Laboratory of Electrical Insulation and Power Equipment, School of Electrical Engineering, Xi'an Jiaotong University, Xi'an, Shaanxi, 710049 People's Republic of ChinaSearch for more papers by this authorWenhao Jia, Wenhao Jia State Key Laboratory of Electrical Insulation and Power Equipment, School of Electrical Engineering, Xi'an Jiaotong University, Xi'an, Shaanxi, 710049 People's Republic of ChinaSearch for more papers by this authorJiang Wu, Jiang Wu State Key Laboratory of Electrical Insulation and Power Equipment, School of Electrical Engineering, Xi'an Jiaotong University, Xi'an, Shaanxi, 710049 People's Republic of ChinaSearch for more papers by this authorYuankang He, Yuankang He Northwest Branch of State Grid Corporation of China, Xi'an, Shaanxi, 710048 People's Republic of ChinaSearch for more papers by this authorTianen Chen, Tianen Chen Northwest Branch of State Grid Corporation of China, Xi'an, Shaanxi, 710048 People's Republic of ChinaSearch for more papers by this author First published: 14 May 2020 https://doi.org/10.1049/iet-gtd.2019.1275Citations: 3AboutSectionsPDF ToolsRequest permissionExport citationAdd to favoritesTrack citation ShareShare Give accessShare full text accessShare full-text accessPlease review our Terms and Conditions of Use and check box below to share full-text version of article.I have read and accept the Wiley Online Library Terms and Conditions of UseShareable LinkUse the link below to share a full-text version of this article with your friends and colleagues. Learn more.Copy URL Share a linkShare onFacebookTwitterLinkedInRedditWechat Abstract Security constrained unit commitment (SCUC), with renewable resources integrated into power grid, is one core function in the day-ahead market. However, it confronts with critical challenges as the heavy complicated security constraints are considered. Usually, it is observed that lots of security constraints are redundant, which can be identified and eliminated, so as to reduce the computational complexity. In this study, the authors first lift the uncertain feasible region of SCUC into a high dimensional space. Furthermore, a fast identification method is proposed to relax the original feasible region, which thus can be solved by the classical greedy algorithm. In order to prevent the over-relaxation and find more redundant constraints, an efficient feasible-based bound tightening strategy is utilised to provide a tighter bound. Numerical results on large-scale test systems verify the effectiveness of the proposed method. 1 Introduction Security constrained unit commitment (SCUC) is one of the most important tools for independent system operator (ISO) or regional transmission organisation (RTO) to plan a secure and economic generation schedule in the day-ahead markets [1–4]. Its objective is to explore the optimum allocation of generation among available generating units so that the cost of generation is minimised while considering various equality and inequality constraints such as the power balance and network security constraints [5–7]. It therefore plays an essential role in power system operations [8, 9], power system planning [10], power system maintenance [11] and power system resilience [12]. Nowadays, renewable energy resources such as wind power and solar energy have been well developed to resolve the environment pollution, carbon emission and energy crisis [13–16]. However, the stochastic nature of renewable energy resources brings huge challenges to the accommodation [17]. Therefore, it is urgent to formulate an appropriate unit commitment model for accommodating renewable energy resource while addressing the uncertainties [18]. For example, interval SCUC model was proposed in [19] to find the optimal solution with the uncertainties bounded in an interval. Some researchers focus on the stochastic SCUC. A two-stage stochastic SCUC model was proposed in [20] by adjusting the generation output to cope with the uncertainties. Furthermore, a dynamic multistage stochastic unit commitment model was established in [21], where two additional state variables were introduced to track the minimum up/down time of the generation units. The information gap decision theory was incorporated in the stochastic SCUC model in [9]. To guarantee the feasibility for full scenarios, the robust optimisation was applied to SCUC in [22–24], where the uncertainty set was introduced to describe the uncertainty information. To utilise the superiorities from both stochastic and robust approaches, a novel distributionally robust optimisation framework for solving the SCUC problem was presented in [25], where the probability of contingency and the corresponding expected total costs were considered. From the mathematical view, SCUC model is a large-scale mixed-integer linear programming problem with a large number of continuous and binary decision variables, as well as a series of prevailing equality and inequality constraints [26–28]. To efficiently find the optimal solution, various optimisation methods were proposed, including dynamic programming [29], Lagrange relaxation [30], genetic algorithm [31], evolutionary algorithm [32] and the hybrid method [33] for the SCUC problem. Recently, the branch-and-bound and cutting plane based approaches for solving mixed integer programming (MILP) model became popular and can be regarded as an essential tool to solve the SCUC [34]. With the increasing of size of ISOs/RTOs as well as the proportion of renewable energy in power systems, the aforementioned approaches would probably face critical challenges as more complicated constraints are considered. Sometimes, the MILP method could fail to explore the optimal solution as the number of constraints and decision variables increase [35, 36]. Therefore, SCUC model has extremely high computational burden when a large number of equality and inequality constraints are considered. To accelerate the computational speed of the SCUC model, a clustered unit commitment formulation was proposed in [37] to group similar plants and provide fast approximations. It was reposted in [38, 39] that the security constraints in the SCUC problem were the most challenging but fortunately many security constraints were redundant. If these redundant security constraints could be identified and eliminated before the computation, it is possible to significantly simplify the problems and improve the computational efficiency. Features of redundant constraints were presented in [40], which reported that over 85% of the security constraints were redundant. Moreover, an optimisation method was proposed in [41, 42] to identify the umbrella constraints of the deterministic security-constrained DC optimal power flow model. However, the uncertainties from renewable energy resources will bring challenge for identifying the redundant security constraints. The power flow on the transmission lines will fluctuate within a certain interval and the definition of the redundant constraints under the uncertain boundary condition is not straightforward. Moreover, the method [40] for identifying redundant security constraints under deterministic feasible region may be over-relaxed due to the uncertainties, leading to leave out lots of redundant constraints. To address the uncertainties and prevent the over-relaxation problem, this paper proposes a new fast method for identifying redundant security constraints. The contributions can be briefly summarised as follows: (i) A sufficient and necessary condition is investigated by using a bi-level optimisation model to identify the redundant security constraints with the consideration of uncertainties. (ii) A greedy algorithm is utilised to fast identify the redundant security constraints with uncertainties. (iii) An efficient feasible-based bounds tightening (FBBT) strategy is employed to provide a tighter bound to prevent the over-relaxation for the original feasible region, which can find more redundant constraints. The rest of the paper is organised as follows. Section 2 presents the SCUC model considering the uncertain net load demands and the definition of security constraints. Section 3 employs the greedy algorithm with FBBT strategy for identifying redundant security constraints under uncertain net load demands. Section 4 reports the numerical results on several test systems. Finally, Section 5 draws the conclusions. 2 SCUC model with uncertain net load demands 2.1 SCUC model with uncertainties The SCUC problem aims to find the minimum system costs while meeting several necessary operational constraints for power systems [1], which can be expressed as follows: (1a) (1b) (1c) (1d) (1e) (1f) (1g) (1h) (1i) (1j) (1k)where f (·) is the operating cost function; ui,t, vi,t, yi,t are the status of start-up, shut-down and on/off of the unit i at time period t ; Pi,t is the generation of unit i at time period t ; T is the number of time periods; N is the number of units; M is the number of net load sites; L is the number of transmission lines; Dj,t is the net load demand of bus j at time period t ; SUi/SDi is the start-up/shut-down cost of the unit i ; is the min-up time for the unit i ; is the min-down time for the unit i ; Rui/Rdi is the ramp-up/ramp-down rate for the unit i ; is the startup/shutdown ramp rate for unit i ; is the minimum/maximum capacity of unit i ; is the transmission line limit of line l ; H is the power transfer distribution factor matrix. In this model, the total costs in the objective function include start-up/shut-down costs and operating cost of power systems. As for the constraints, (1b), (1e), (1f) and (1g) represent the constraints of the power balance, minimum up/down time limit and generation limit; constraints (1h) and (1i) describe the ramping rate limits; constraints (1j) are the transmission line limit constraints, called as security constraints; constraints (1c), (1d) and (1k) represent the relationship between the unit status and start-up/shut-down state. It should be noted that the net load demand includes the load demand, the renewable energy generation and so on, which is usually uncertain. To characterise the uncertainties, the interval-based modelling is widely used, such that (2)where is the lower/upper bound of net load demand j at time period t. Furthermore, two-stage robust SCUC models in [17–20] were set up to find the optimal solution under the worst scenario that immunes against any possible realisation within the interval. However, for large-scale power systems, the number of security constraints (i.e. transmission line limit constraints in (1j)) is huge which will significantly affect the computational performance of the robust SCUC model. Note that each security constraint in the SCUC model is double-side. There are 2TL security constraints in total. The L double-side security constraints can be reformulated as 2L single-side security constraints by (3)For brevity, let and be an augmented power transfer distribution factor matrix and an augmented transmission line limit vector. Then, (3) can be expressed as a compact form as (4)Actually, some security constraints can be eliminated without changing the solution of the original model, which are deemed to be redundant. If these constraints can be found before the computation, the complexity of the optimisation problem can be reduced and the computational efficiency can be improved. 2.2 Identifying redundant constraints with uncertainties For the k th security constraint of the SCUC model without uncertainties, if removing this constraint does not affect the original feasible region, this security constraint is in fact redundant. Note that the redundant constraints are not related to the objective function, but only dependent on the feasible region. As shown in Fig. 1, it illustrates that the k th security constraint never intersects with the original feasible region if this security constraint is redundant. When it comes to a non-empty feasible region with the consideration of uncertainty, a security constraint is redundant if it never intersects with the original feasible region for any realisation from the uncertainty set. Here, 'never intersects' can be mathematically expressed as: the maximum (and minimum) power flow on this security constraint is smaller (and greater) than the upper (and lower) bound limit. For that, a sufficient and necessary condition is given to identify a redundant security constraint with uncertainties, such that Fig. 1Open in figure viewerPowerPoint Definition of redundant constraints with/without uncertainties Corollary 1.(Sufficient and necessary condition)If , the k th security constraint is redundant; otherwise, it is not. Where (5a) (5b) (5c) The optimisation (5) indicates that for a given realisation of the net load demand Dj,t, the maximum transferred power flow on the k th security constraint can be computed. Thus, under the uncertain net load demand, the maximum transferred power flow on the k th security constraint will be a function of Dj,t, i.e. . Furthermore, Corollary 1 suggests that if the maximum transferred power flow on the k th security constraint is redundant for all realisations Dj,t, this security constraint will be redundant. Note that Corollary 1 needs to solve one bi-level mixed integer optimisation problem as (6a) (6b) (6c)Moreover, the 'max-max' bi-level model can be equivalent to a single-level 'max' model by combining decision variables and uncertainties together. Thus, (6) is reformulated as (7a) (7b) (7c) (7d)Furthermore, the original Corollary 1 will be rewritten as: Corollary 2.(Sufficient and necessary condition)If , the k th security constraint is redundant; otherwise, it is not. However, identifying one security constraint needs to solve one MILP model, whose computational complexity is similar to the original SCUC model. Moreover, the identification method by Corollary 1 will deal with 2TL MILP models. It is actually not practical, because the number of security constraints is quite huge. To address this problem, Dvorkin et al. [40] pointed that we do not need to identify all the redundant security constraints precisely. Instead, we can identify some security constraints in a fast speed. This idea can be realised by relaxing the feasible region of the original model. In Fig. 2, we can find that if a security constraint is redundant on the relaxed feasible region, it must be redundant on the original feasible region, but if the security constraint is active on the original feasible region, we cannot determine whether it is redundant on the relaxed feasible region. This shows that after the relaxation, we could only find a sufficient but not necessary condition for identifying redundant security constraints. But please keep in mind that there are two points that should be addressed: (i) the feasible region should not be over-relaxed. Fig. 2 depicts that for different relaxed feasible regions, we may find different identification. The security constraint under both the original feasible region and the relaxed feasible region 1 is redundant, while it is active for the relaxed feasible region 2; (ii) the optimisation model over the relaxed feasible region must be easy to solve. Fig. 2Open in figure viewerPowerPoint Security constraint using the tighter and original bounds According to [40], the original MILP model is relaxed into a simple LP, where (i) the feasible region of integer variables is neglected and considered the integer numbers to be continuous, leading to an security-constrained economic dispatch problem; (ii) only power balance constraint and generation output limits are kept; (iii) the generation output limits are relaxed by . By use of this relaxation, Corollary 3 is given to fast identify the security constraint with uncertainties. For the security constraint k at time t, we consider (8a) (8b) (8c) (8d) Corollary 3.(Sufficient but not necessary condition): If , the k th constraint at time t is redundant. 3 Proposed FBBT-based redundant security constraints identification method 3.1 FBBT method for tightening bounds As aforementioned, Corollary 3 is only a sufficient but not necessary condition, since the original precise feasible region has been relaxed. Then, a question is raised whether the original feasible region is over-relaxed that leaves out many redundant constraints? To address this question, this paper presents a new relaxed LP model, where the capacity of each unit (8c) is tightened by the lower and upper bounds Li,t and Ui,t, instead of its original physical limit , leading to a tighter capacity limit, such that [Li,t, Ui,t]⊆[0, ]. It should be noted that Li,t and Ui,t should be dynamically adjusted which is related to the time period t. Thus, the relaxed model with a tighter bound may find more redundant constraints. Recall the relaxed model (8) that indicates if the security constraint intersects with the equality constraint, it is redundant. Fig. 3 gives the comparison of the redundant constraints for the polyhedral with and without tighter bounds. Fig. 3Open in figure viewerPowerPoint Interval Security constraint using the tighter and original bounds Observe that the interval inequality constraint is considered to be redundant using a tighter bound because it does not intersect with truncated equality constraint, whereas it will be termed as an active security constraint using the original bound. Therefore, it is important to find a method for tightening the original bound. The FBBT method is an iterative range-reduction technique that is also known as bounds propagation in the constraint programming community [43]. It involves tightening the variable ranges using all of the constraint restrictions; the procedure is iterated as long as the variable ranges keep changing and stops when the improvement after several iterations is small, say within a given tolerance. Moreover, FBBT is computationally inexpensive for the case of linear constraints and may produce minimal bounds tightening. Variable bounds are tightened by using the constraints of the problem to calculate extremal values attainable by the variables, which is done by isolating a variable on the left-hand side of a constraint and evaluating the right-hand side extremal values by means of interval arithmetic strategy. We denote a real interval by ''. For an interval vector , the i th component of is . It often happens that is not as tight as possible, in sense that the variable of the optimisation model might be constrained in an interval vector that is much smaller than the initial given bound, so the FBBT aims to restrict the initial variable range to a tighter range . Here, we introduce some basic interval arithmetic operations. Given two interval numbers as and , the interval addition, subtraction and intersection are defined as (9a) (9b)For the original feasible region, we only relax the integer constraint while keeping all the other continuous constraints including the ramp rate limit constraints, giving the relaxed convex feasible region as (10a) (10b) (10c) (10d) (10e)It is obvious that this convex region is a polyhedron enclosed by T equalities, NT + L inequalities and NT element-wise constraints with NT variables. Keep in mind that Hl,ref in (10d), the element in the distribution factor with respect to the reference bus ref, is always 0 [44]. Reformulate (10a) by (11)Taking (11) into the inequalities (10b)–(10d) will eliminate the decision variables (Pref,1, Pref,2, …, Pref,T) and the equivalent convex region is only enclosed by the inequalities, yielding For the (10b): (12a) (12b)For the (10c): (12c) (12d)For the (10e): The reference bus can be eliminated, due to Hl,ref = 0 for all l (13)Finally, the feasible region enclosed by the constraints (12) and (13) is equivalent to that in (10), which can be compactly formulated in a matrix form as (14)It should be noted that the model aims to find the maximum possible power output region, which can be equivalent to (15)Let and . The feasible region (16) can be reformulated as (16)Since all the constraints in the above feasible region for P are limited by the lower and upper bounds, this renders to an interval form that can be expressed as (17a)where (17b) (17c)with the initial interval value being (17d)At each iteration, FBBT alternately applies the 'up' and 'down' functions to propagate the effect of inequalities, where the set of all real intervals forms a lattice with interval intersection, giving the 'up' function on the coefficient matrix A as upA : , the 'down' function on the coefficient matrix A as downA : and the FBBT function on the coefficient matrix A as fbbtA : in the following: (18a) (18b) (18c)But it should be noted from (18) that for each variable, the corresponding security constraint with zero component of A can be ignored when doing variable bound reduction. Fortunately, A is generally a sparse matrix with many zero components, so the 'down' operator can be calculated much fast. Of course, the up and down functions are deflationary because each of their interval components is an intersection with the original interval. In order to measure this deflation, it yields γ∞ for any two interval vectors (19)As aforementioned, FBBT cycles through (18), inferring tighter variable values, until either the variable bounds fail to be improved by a preset factor. Last but not the least, FBBT is usually fast in practice, but the worst case might need lots of iterations to reach the given termination tolerance. Therefore, a limit on the number of allowable cycles through the equations is preset to produce a relatively better bound than the initial one, although not the tightest bound. For the given tolerance ɛ, the number of allowable cycles is K and the flowchart of FBBT algorithm for (17) is shown in Fig. 4, where η is a flag. Therein, η = +1 means that the feasible region is non-empty and the bound is tightened but not within the given tolerance; η = 0 means that the feasible region is non-empty and the bound is tightened by [L, U] within the given tolerance; η = −1 means that the feasible region is empty and the bound is not tightened. Fig. 4Open in figure viewerPowerPoint Flowchart of FBBT algorithm 3.2 Greedy algorithm for identifying redundant constraints The obtained L and U from the FBBT method can be used to replace the upper and lower bounds in (8). For the given k th security constraint at the t th time period, we have (20a) (20b) (20c) (20d)Note, the relaxed convex region (16) is only employed to compute a tighter bound but is not used to identify redundant security constraints. This is because the optimisation model on (16) is a large-scale LP model and identifying all the security constraints needs to solve 2TNL large-scale LP models. In contrast, the model (20) has a special structure in which there is only one equality constraint with element-wise inequality constraints. Let and . The M + N dimensional LP model (20) will be reformulated as its increment model by (P i,t, D j,t)→(ΔP i,t, ΔD j,t), yielding (21a) (21b) (21c) (21d)where Q is a constant number that can be calculated by (21e)It is easy to see that the LP model (21) is similar to the classical Knapsack Problem [45] that is described as 'Given a set of items, each with a mass and a value, determine the weight of each item to include in a collection so that the total weight is less than or equal to a given limit and the total value is as large as possible'. For each given k th security constraint at the t th time period, let the total number of items be N + M, value of item per weight be c, weight of item be G with the limit and maximum weight of each item be G max (22) (23) (24)Then, a greedy algorithm, quite powerful and convenient, is proposed to solve the optimisation problem. This attractive algorithmic strategy builds up a solution piece by piece, and always chooses the next piece that offers the most obvious and immediate benefit [46, 47]. In many discrete problems, a greedy strategy does not in general produce an optimal solution, but the global optimal solution must be achieved in a reasonable number of steps for the continuous LP model (21), because LP is convex. Furthermore, the flowchart of greedy algorithm is presented in Fig. 5. Fig. 5Open in figure viewerPowerPoint Flowchart of greedy algorithm Finally, it can be found that for each security constraint at each time period, we can calculate as given in Fig. 5. Then, according to Corollary 3, if , the constraint k at the time period t is redundant. Besides, it is observed that there needs only once permutation and summation for the greedy algorithm, so the time complexity is O ((N + M)log(N + M)). 4 Case study In this section, IEEE9-bus system, IEEE 118-bus system, IEEE 2383-bus system and IEEE 2736-bus system are studied to investigate the effectiveness of the proposed greedy algorithm implemented FBBT strategy ('GA-FBBT'). The total number of time periods is 24. The GA method without FBBT (GA-WO) and the sufficient and necessary condition in Corollary 1 ('Actual') are used for comparison. Besides, the detailed parameters of test systems can be found in MATPOWER [48]. The proposed approach is performed using MATLAB and CPLEX 12.7 on a personal computer with Intel® Core™ i5 Duo Processor T420 (2.50 GHz) and 8 GB RAM. At the beginning, we adopt two typical net load curves over one day presented in Fig. 6 to study the impact of net load profiles on the solution performance, where one case depicts a small valley-to-peak value (denote 'S') and the other shows a large one (denote 'L'). Note, different net load demand uncertainty levels and tie-line constraint limits may also affect the solution performance. Therefore, we will define the net load demand uncertainty level α and constraint limit level β as (25), respectively. In general, the tie-line constraint limit level can be deployed according to the system conditions (25)where Fmax,0 and Fmax denote the maximum transmission capacity given in [48] and actual maximum transmission limits. It can be easily known that α belongs to [0,1] and the uncertainty becomes larger when α tends to 1. Meanwhile, the constraint limit level is tighter with increasing the positive number β. Fig. 6Open in figure viewerPowerPoint Two net load curves with small and large valley-to-peak value 4.1 Test on the 9-bus system In the 9-bus system, there are nine transmission lines, generating 2 × 9 × 24 = 432 security constraints over 24 time periods. Here, we only present the results on the unit 1 due to the limited space. It is observed from Fig. 7 that the FFBT method brings about a tighter upper and lower bounds than the original physical maximum and minimum physical limit. In Fig. 7b, it is interesting to find that the upper bound during 2–9 h and lower bound during 10–23 h will get tighter and tighter by FBBT with the increase of α. Comparing Fig. 7a with Fig. 7b, it can be observed that both the lower and upper bounds tend to be tighter under large peak-to-valley net load profile than that of the small one. Comparing Fig. 7a with Fig. 7c, the up