Title: Enhanced Lagrange relaxation for the optimal unit commitment of identical generating units
Abstract: IET Generation, Transmission & DistributionVolume 14, Issue 18 p. 3920-3928 Research ArticleFree Access Enhanced Lagrange relaxation for the optimal unit commitment of identical generating units Pavlos Nikolaidis, Pavlos Nikolaidis Department of Electrical Engineering, Cyprus University of Technology, P.O. Box 50329, 3603 Limassol, CyprusSearch for more papers by this authorAndreas Poullikkas, Corresponding Author Andreas Poullikkas [email protected] orcid.org/0000-0003-3703-4901 Cyprus Energy Regulatory Authority, P.O. Box 24936, 1305 Nicosia, CyprusSearch for more papers by this author Pavlos Nikolaidis, Pavlos Nikolaidis Department of Electrical Engineering, Cyprus University of Technology, P.O. Box 50329, 3603 Limassol, CyprusSearch for more papers by this authorAndreas Poullikkas, Corresponding Author Andreas Poullikkas [email protected] orcid.org/0000-0003-3703-4901 Cyprus Energy Regulatory Authority, P.O. Box 24936, 1305 Nicosia, CyprusSearch for more papers by this author First published: 09 July 2020 https://doi.org/10.1049/iet-gtd.2020.0410Citations: 5AboutSectionsPDF 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 Intelligent generation scheduling for seamless integration of uncertain and volatile renewable sources constitutes a crucial solution in delivering future low carbon energy. System operators need to devise effective flexibility adequacy plans for their power systems so as to guarantee power balance and ensure feasible and economical operation over different time horizons and under different generational, environmental and technical constraints. In this work, the authors propose a novel approach for addressing the unit commitment problem of identical generating units, based on Lagrange relaxation framework. The proposed method is characterised by a double decomposition formulation to determine the optimal path for the commitment of identical heat-rate units. This approach is tested and compared to conventional Lagrange relaxation on systems with a number of generating units in the range of 20–100. The proposed approach completely outperforms the conventional alternative in terms of total fuel cost savings, as well as the number of required iterations. In addition, the required iterations are found to increase linearly with system size, which is favourable for large-scale implementations. 1 Introduction Global efforts aiming to shift towards de-carbonisation give rise to remarkable challenges for power systems and their operators. Modern power systems need to deal with the uncertain and volatile behaviour of their components (especially, renewable energy generation); this necessitates the use of increased operating reserves. To ameliorate this expensive requirement, intelligent systems for determining appropriate unit commitment (UC) schedules have risen as a promising solution. This is especially the case for weak power systems with low dispatching flexibility and high dependency on imported fossil fuels. In recent years, extensive research is made around the concept of optimal UC exploring the efficacy of deterministic and stochastic programming. Besides achieving minimum total production cost, the generation schedule must satisfy a large number of different technical, operational and environmental constraints. As a result, global explorations for the optimal solution involve dynamic programming and complete enumeration approaches in the expense of high dimensionality. The mathematical methods include priority list schemes, mixed-integer programming and decomposition techniques. Although priority list constitutes the simplest and fastest method to UC, it possesses a weakness in concluding to a final solution which in many cases may stand out from the optimal [1]. Classified as linear [2], quadratic [3] or non-linear [4] programming, mixed-integer approaches are able to enhance the generation modelling accuracy though they require increased computational efforts to converge to the desired solution. The proposed decomposition alternatives refer to Benders decomposition [5], branch-and-bound [6] and Lagrange relaxation (LR) [7]. Considerable efforts devoted to solving the security-constrained UC task have demonstrated Benders decomposition as the state-of-the-art method, due to its ability to decompose the problem into the UC master problem and two subproblems for taking into account the network constraint in the base and contingencies cases [8]. Together with the branch-and-bound, they provide optimal solutions for limited-size power systems increasing the execution time exponentially. In addition, each solution violation requires new interventions in the master problem to avoid infeasibility. These procedures can be extremely time consuming and even inconclusive in some cases [9]. On the other hand, LR technique can be employed to further decompose the subproblems and deal with dynamical constraints by just relaxing them. It substitutes a lower bound to branch-and-bound method and succeeds in eliminating the duality gap by utilising the product of penalty terms [7]. In this work, we propose an enhanced LR approach for solving the optimal UC problem of identical generating units. Our proposed approach is enhanced through a global exploration procedure retaining the principles of LR framework. Based on a novel formulation, we provide strong experimental evidence regarding the performance and efficacy of our innovative approach by considering an isolated power system comprised by multiple identical generators and a 336-half-hourly power demand in the presence of variable renewable energy sources (VRES). The remaining of the paper is organised as follows. In the following section, the contribution and motivation of this work is presented. We define the UC problem along with the main unit-specific and system-wide constraints that must be always satisfied in Section 3. Section 4 describes the LR framework and introduces the proposed novel methodology for oscillation-free, optimal UC. In Section 5, we present the numerical results stemmed from an extensive experimental evaluation considering optimal UC in a real-world power system. Finally, the conclusions are drawn in Section 6. 2 Contribution and motivation The number and complexity of the constraints presented in today's modern power systems increase, deteriorating the UC optimisation task. These include but are not limited to generation constraints in the presence of renewable generation (RG), network constraints affected by the distributed energy resources (DERs), bilateral contracts enclosing electricity storage provision, corrective security actions in sudden load variation or outage circumstances and so on [10]. Consequently, the level of system security can be set based on either deterministic, probabilistic or hybrid viewpoints and their corresponding criteria [11]. This way, the computation time of exact methods becomes impractical calling for some heuristic approaches for which optimality is not given such a high priority, but the emphasis is on producing near optimal solutions in a lower computational burden [12]. The dominant methods extensively presented in the literature are genetic algorithms [13], simulated annealing [14], particle swarm optimisation [15], fuzzy LOGIC [16], expert systems [17], ant colony [18], Tabu search [17], evolutionary programming [19] and artificial neural networks [17]. Owing to their main disadvantages of local optimum trapping, untraceable transition rules and unreliable findings, hybrid meta-heuristic approaches have been proposed in order to employ more rigorous mechanisms. Both categories require great experience relating to the whole power system's behaviour for their confident design and implementation. In pursuit of the depletion of the energy dependency on third countries and the reduction of transmission costs, the centralised electric sector is gradually being transformed into a distributed scheme. Microgrid is a concept pervasively used in the literature as a possible tool to support the coordination of numerous DERs for power generation [20]. However, at the interconnected mode, such mechanisms constitute crucial and challenging optimisation problems for the day-ahead scheduling. Apart from the variability and uncertainty in net load caused by increasing penetration of RG, system operators are required to address the combined problem of UC and economic dispatch (ED) of identical generating units. Although LR methods have proven to be the most dominant in dealing with systems that consist of hundreds of generating units, their numerical convergence as well as the solution quality are degraded in the presence of identical heat rate units [21]. These generating units are committed as a group on a pro-rata basis, leading to over-scheduled solutions and consequent increased production costs [7]. Based on the extensive literature, only a few research works have identified this sensitivity problem, while the conducted suggestions to address such irregularity are too limited or totally absent. The proposed approaches make use of excessive spinning reserve lists which are updated for each time interval t [22, 23]. Specifically, once the LR optimisation task is carried out, a second-level procedure takes place to form a descending-ordered list according to the average fuel cost of each generator being committed. Based on this ranking, the generating units are sequentially de-committed if the constraints are not violated. The proposed de-commitment depends solely on the average fuel cost and is realised within each time interval without taking into consideration the global time-horizon. Hence, it can recommend only sub-optimal solutions to UC. Farid Benhamida and Bendaoud Abdelbar [12] proposed an initialisation procedure which intends to create a high-quality feasible schedule. Basically, they classified both the generating units and time intervals into distinguished types aiming at global exploration of the solution space. In this regard, the generating units were classified into base, intermediate and peak load units, according to their specific characteristics including operation cost, start-up cost and minimum up/down times. The time intervals were grouped in a similar manner enabling the near-optimal de-commitment of identical units. However, the proposed approach would be inappropriate for power systems characterised by increased RG contribution. The variability of RG systems would cause net-load variations which could fluctuate even more unevenly. This deteriorates the time-interval classification and diverges further apart from optimal. In addition, the overall proposed approach was tested in a modelled system consisted of similar generators rather than identical generating units. As a result, the authors could exploit the initial feasible solution to appropriately de-commit the generating units and eliminate the excessive spinning reserve. In real-case isolated power systems, the generators may possess identical heat-rate coefficients leading the optimisation task into oscillations. This is caused by unnecessary commitments and de-commitments which results in power-balance violations. For example, if a group of generating units is committed, the aggregated minimum power capacity may be greater than the net-load demand. Similarly, when the same group is de-committed to correct the violation, the summed maximum power capacity may occur inadequate to supply the demand and so on. It is therefore apparent that the identical generating units' treatment requires both dual and auxiliary variables to effectively decompose the UC problem into further sub-problems, in order to take into account both the grouped and un-grouped generators, respectively. Our contribution towards the optimal and accurate UC of the identical generating units presented in modern, islanded power grids and isolated networks is two-fold. First, we advocate the optimal treatment of identical cost coefficients to avoid the imposed oscillations which lead into infeasible solutions. Towards this goal, we first make use of composite cost functions to effectively group the units as per their cost coefficient and start-up costs. Subsequently, we utilise dual and auxiliary variables to further decompose the problem into subproblems optimising the active number of generators that take place at each time interval. Moreover, we provide a solution capable of enhancing the total production cost improvement and system's convergence performance, something highly important for large-scale, real-world power systems with variable length of input parameters (such as renewable energy contribution and multiple generators). 3 UC problem formulation Aiming at minimising the total fuel cost (TFC) of thermal generating units, our methodology is based on a formulation that takes into account their technical characteristics along with the system, coupling constraints of power balance and spinning reserve. Generally, the objective function and associated constraints can be formulated as follows. 3.1 Objective function The TFC of a power system consisting of traditional thermal units is mainly composed by the cost of fuel and start-up cost . Denoting the number of generating units with N and the number of periods with T, we can represent the UC problem as follows: (1)The discrete, decision variable , expresses the status (on/off) of generating units, taking the value '1' if the i th unit is on-line at the particular time t or '0' if the unit is off-line according to the following equation: (2)The thermal fuel cost depends on the production level and can be defined by a second-order (quadratic) function such that (3)where, ai, bi and ci are positive fuel cost coefficients derived from the processing of the specific fuel cost and heat rate curve of each generating unit, measured in €/h, €/MWh and €/MW2 h, respectively. For convergence-performance comparison purposes, in our optimisation task start-up cost is considered as warmth-independent corresponding to a constant value for each unit. For those generators which possess identical fuel cost coefficients and start-up cost, a composite cost function in its nominal form can be utilised to represent their contribution. 3.2 Constraints The short-term generation scheduling is subjected to the following system-wide and unit-specific constraints which must be satisfied throughout the optimisation process. 3.2.1 Power balance RG is normally treated as negative load and its contribution is given a priority. Therefore, the sum of the power produced from all committed units must meet the net load demand (given by (5)) along with the transmission losses at each time interval (4) (5)The contribution of identical units expressed via is the aggregated power output for each specific group or single unit. 3.2.2 Spinning reserve Based on the maximum ramping capacity of each unit, the power margins must be guaranteed throughout the short-term period to ensure system stability and reliability (6) takes into account unexpected generation outages, errors in RG forecast and load deviations during each time interval t. 3.2.3 Output capacity limits The maximum and minimum rated MW output confine the generating units to operate within their boundaries (7)The consolidation of identical generating units into groups implies the extension of capacity limits according to their number η, e.g. and . In this case, i can represent the i th group of generators. 3.2.4 Minimum up and down times The minimum waiting time in hours required by a generator before it can change its status is expressed via the predefined values of and . Thus, each unit can change its status satisfying the conditions given by (8) (9)where tu and td represent the time a unit has started-up or shut-down, respectively. Thus, they are individually checked for each generating unit, independently the latter is included in or excluded from a group. 3.2.5 Ramp up and down rates For each generating unit, the rate of change of its power output between consecutive time intervals is restricted by the ramp-up and ramp-down rates according to the following equations: (10) (11)Similar to MU/MD constraints, the rate restrictions need to be qualified for each unit independently. 3.2.6 Unit status restrictions In this category, one can encounter three possible states, known as the must-run, run at fixed-MW output and must-out units. Must-run units remain committed during the whole period or certain intervals to ensure reliability and/or economic operation. Some other units may be requested to operate at a specified, fixed output due to technical or environmental constraints. These limitations can be caused by limited fuels in reserve, increased emissions or during testing and commissioning procedures. Must-out characterises the units which are unavailable for commitment, subjected to forced outages, maintenance or other unforeseen problems [24] (12)The generating units that fall in these restricting categories cannot be included to form a group. Instead, they constitute individual groups which consisted of either single units or identical generators with exactly the same restrictions. 3.2.7 Initial conditions At the beginning of the scheduling period, the initial unit conditions must be properly considered. These may include the on–off status of each generator unit, the real-valued power output, the time duration from the last up or down and so on. Otherwise, the optimisation procedure may lead to wrong decisions regarding the on–off status of the generating units. This constitutes a usual phenomenon especially observed at the beginning of a forward-programming approach which typically forces the units with the lowest start-up cost to get on-line. Once the load demand during the first time-slot is quite low (e.g. at 00:00), the power output of each proposed to be committed unit is proportionally low enough such that its start-up cost to be comparable with its operating cost . In some cases, the parameters of and are set to negative integer values to prevent such units from getting online or offline, respectively. It is simply noted that, according to their value, the formulated composite cost function may vary between intervals in order to satisfy the constraints of (8) and (9). 3.2.8 Plant crew constraints Typically, crew constraints pertain the number of units that can simultaneously start-up or shut down. Apart from the required and , crew size (number of available operators) is another feature restricting the actions that can be performed in a specific thermal plant. A further constraint pertaining the simultaneous start-up of multiple generators is the maximum steam generation which is strictly dependent on the maximum ratings of water feed-pumps supplying the boilers. This type of constraint directly restricts the overall status change of a group. Commonly, identical heat-rate units exist within the same power plant. As a result, the crew size may determine the feasible number η of identical units that can be grouped together to form a common, composite cost function. 4 LR framework In contrast to ED which assumes that all generators are already connected to the system, UC considers that the units are available and seeks for appropriate on–off combinations to provide the minimum fuel cost. The existence of integer variables makes UC more complicated and difficult to mathematically solve, whilst requiring ED to be treated as a subproblem to the solution. Since in real-world power systems the size of such problems can be too large, a mechanism is needed to divide the problem into smaller subproblems which possess lower computational burden [25]. This section provides a comprehensive overview relating to the principles of LR, a mathematical framework that dynamically deals with coupled constraints. Introducing the key concepts of constraints relaxation and decomposition into subproblems, it introduces the enhanced version of an innovative approach able to deal with identical cost-coefficient generating units. Many combinatorial optimisation tasks are composed of an easy, in the NP-complete sense, problem complicated by added constraints. Based on dual optimisation, the constraints linking the different subproblems can be included through a mathematical and implicit manner to solve the master problem. Dual decomposition constitutes a technique that capitalises on the problem by splitting it to subproblems which can be handled independently [26]. The main idea is to relax the problem by removing the complicating constraints. This way, we are allowed to include the constraints into the objective function by assigning them with weights to represent their satisfaction by a penalty. Dualising the coupling constraints produces a Lagrangian problem, whose optimal value is a lower bound on the optimal value of the original minimisation problem. Hence, the Lagrangian function can be defined as follows: (13)where λ and μ are the Lagrange multiplier vectors for and which represent the complicating equality and complicating inequality constraints, respectively [27]. Consequently, a subproblem k can be written as (14)subject to (15) (16)non-complicating equality of (15) and inequality of (16) constraints. Since 1974, when this approach had coined the name of 'Lagrangian Relaxation', it led to drastically improved algorithms for several infamous problems in the areas of routing, location, scheduling, assignment and set covering [28]. In UC, LR attempts to reach the constrained optimum by minimising the Lagrangian (see (17)) with respect to non-negative and . Considering (1), we can rewrite (17) as (17) (18) (19)We observe that the term can be minimised separately for each generating unit according to the following equation: (20)subject to the non-complicating constraints (7)–(12). While the solution is given for each generating unit independently, the remaining constraints can easily be integrated. The dimensionality problems affecting dynamic programming have been avoided and a way remains to be found adjusting Lagrange multipliers' values for the coupling constraints of load balance and spinning reserve [29]. The two general techniques for choosing values refer to multiplier adjustment and sub-gradient methods. Where the Lagrangian function is differentiable we can directly work with the gradients. An example of a systematic way for lower-bound improvement is provided by (21)Considering (17), the partial derivative with respect to results in (22)To avoid oscillations, the values of α must be distinguished according to derivative's sign so that (23)A measure of the closeness to the solution is referred to as relative duality gap (RDG) and is given by the following equation: (24) J * represents the total cost (for the N generating units during the T time periods) estimated by the relaxed λ while q * is the total cost given by the corrected λ values used in ED [30]. RDG is utilised to measure the quality of the solution and the iterative process terminates when either RDG becomes less than a prespecified tolerance, , or the iterations exceed the maximum allowable number. Where possesses multiple optimal solutions, we cannot directly work with the gradients but instead make use of the sub-gradients [31]. Denoting the mismatches of coupling constraints at iteration k with , a simple to implement method for multiplier updating is presented by (25)where (26)Unlike linear programming, integer linear programming does not possess strong duality theory. This implies that the minimum value of Lagrangian dual J* does not have to be absolutely equal to q* of the primal problem, instead holds. Lemma.(Lagrangian bounding principle): For any λ, the value is a lower bound on the optimal objective function value q* of the original problem. Property.(Week duality): The optimal solution J* of the Lagrangian dual is a lower bound on the value q* of an optimal solution (i.e. ) such that (27) The only way to prove optimality is to obtain a for which equals the cost of a known feasible solution, whilst the following sufficient conditions hold [31]: (28)This could be achieved only for and, therefore, the method is terminated after an arbitrary iteration limit. The oscillating behaviour due to identical heat-rate coefficients makes it even more difficult to devise an appropriate stopping criterion, requiring additional methods such as auxiliary problem principle to deal with [25]. In the presence of identical generating units, the process oscillates in consecutive overload and underload conditions violating the power balance constraint. Specifically, the generating units that possesses identical or even similar cost coefficients (a, b and c) and start-up costs (SU) are selected to get online according to mathematical statement of (20). As a result, the generation is over-scheduled leading to increased start-up and production costs. When more constraints are taken into account, the committed units force the optimisation into oscillations providing consecutive infeasible solutions. To deal with such a sensitivity problem, we have to eliminate the unnecessary commitments and de-commitments. We propose a radically novel mechanism through which the identical units j can be grouped to form a composite cost function and an alternative process to optimally define the active unit number () of each group i based on the following mathematical statements [32]: (29) (30)As we observe, the solution of the above problem comprises the computation of three-dimensional matrices. In contrast to conventional LR formulations where each variable could be represented by processing (2-dimensional) matrices, the composition of groups to accommodate identical units requires a further dimension. This is needed, for example, to define a variable's value for a generating unit i classified in group j for the interval t. As this procedure is computationally cumbersome, this work will examine an innovative method that performs the commitment of identical units in two further stages regarding the dual and primal problem for grouped (i) and individually included (j) generating units. This way, the contribution of each generating group is reformulated, by making use of dual variable constraints. To overcome oscillations and achieve the convergence, we propose that such variables are needed to detect which group was last-up, to set the time duration that each distinguished (un-grouped) unit has been on-line or off-line at the end of interval t, and to identify if the unit was started-up at the beginning of this interval. The dual and relaxed problems will be alternatively resolved until the optimal Lagrange multiplier vector is found iteratively. Fig. 1 illustrates the proposed double-decomposition approach capable of accounting for the identical units and treating them as individual composite groups. Fig. 1Open in figure viewerPowerPoint Flowchart of enhanced LR considering identical generating units The concept relating to the optimisation task can be explained through the main steps of the procedure given below: (i) Initialisation: All unit parameters and load demand are imported. (ii) Grouping: Identify the identical generating units (with identical cost coefficients and start-up cost) and group them together to form a composite cost function. (iii) Generate the on–off combinations for each time interval subject to composite, group specific constraints. (iv) ED: For each time interval during which the coupling constraints of power balance and spinning reserve are satisfied, calculate the total generation using the proposed commitment schedule. (v) Un-grouping: For each time interval during which the equalities (or inequalities) are over-constrained, un-group and evaluate the generation of the last-up (most expensive) group, updating the dual variables of active unit number of the particular group as well as the last-up, off-line duration and start-up time of each individual unit included in the corresponding group. (vi) Calculate the total production cost for each time interval and, based on the fitness function (25), update λ and μ values. (vii) Algorithm update: Regroup the units based on the new parameters constraining their contribution and go back to step 3 until the maximum iteration number is achieved. Utilising dual variable constraints, we reformulated the contribution of each generating group based on mathematical statements (29) and (30). The quadratic, pricewise cost function is processed in its nominal form for both stages of either grouped or individually included units. Once the appropriate groups are decided to change their status, two possible conditions may occur alternately, namely overload or underload and hence, three extra variables are required to overcome oscillations and achieve the convergence. These include integer variables to detect which group was last-up and to set the ti