Introduction
Over the years the world population has grown fast which has resulted in increased industrialization, ultimately demanding more energy. There are two kinds of energy resources: conventional and non-conventional. Conventional energy resources are limited and also cause pollution while non-conventional renewable energy resources are environmentally friendly and abundant. Among all resources, water is efficient, clean and utilized by hydropower plants for electricity generation. The yearly power generation of a hydropower reservoir depends on annual discharge management of reservoir scheduling. The planning of hydro power systems is complex because it requires assuring the peak demand throughout the working process of the electric power system efficiently. As human tasks follow regular, seasonal and yearly periods and due to changes in peak demands, this becomes a difficult task. More energy is produced by good planning with the same quantity of water, making considerable savings for the producer even with a slight computational improvement [1,2]. The planning of electric power system is divided according to time horizon i.e., for a day, week or year. The weekly planning is known as short-term scheduling; sometimes weekly schedules are also named as medium term. For yearly planning it is considered long-term scheduling. The long-term optimization approach usually follows a few years of planning horizon [3,4]. On a weekly basis, medium term optimization is used to plan the reservoir volumes [5]. The short-term optimization approach follows the hours–ahead to day-ahead time horizon. In power system operations, unit commitment is one of the central approaches [6–11]. For achieving accuracy in testing, all daily operations and market clearing is done in advance. Independent system operators are responsible to deal with hydropower systems operations and unit commitment schedules [12]. The unit commitment problem deals with mixed integer and several stages decisions. The goal of unit commitment is to find the optimal schedule on an hourly basis of ON-OFF units and it also determines the level of generation for each generating unit of electric power system in a given time horizon. The hourly schedule is determined for 24 h in short-term scheduling while it helps in minimizing the start-up/shut-down cost, fuel cost, satisfying the multi-vibrational zones, up time/down time constraints, load balance equations ramp rate constraints and spinning reserve constraints [13]. Moreover, spinning reserve makes hydro scheduling a complex, nonlinear, high dimensional problem. In power system, spinning reserves are estimated [14,15].
The considerable amount of money is saved during hydro scheduling, when the most appropriate and profitable schedules are found. It also focuses on starting and stopping times for all units in a system satisfying itemized loading schedules by turning units off when they are not in use. This problem is very complex as it involves a large number of variables because the size of the system is large as the decisions of starting and stopping the units consist of many constraints having integer values. The decision making for optimal unit commitment is very complex because scheduling is done on an hourly basis for multiple units to fulfill the predicted demand and all the constraints are involved in this problem. As unit commitment is a wide-ranging, combinational and mixed integer nonlinear programming problem [16–19]. Several optimization methods have been used to solve this type of problem including priority listing [20,21], mixed integer programming [22–25], dynamic programming [26–33], hierarchical optimization [34–39], lagrange relaxation method [40–45], tabu search [46–48], non-linear programming problem [49,50] and branch and bound method [51].There are two families of unit commitment, one is deterministic unit commitment problem and the other is stochastic unit commitment problem. A lot of research focuses on deterministic unit commitment but there are several studies which discuss the methodology and formulation of stochastic unit commitment problem. Stochastic unit commitment problem deals with the uncertainty. In the literature, several studies discuss the scenario based stochastic programming for solving unit commitment with different methods like progressive hedging [52–56], dual decomposition [57–59], benders decomposition [60–64], spatial decomposition [57], directly solved method [65–70], cutting plane [71], dynamic formulation [72] and heuristic methods [73–75].
Hydro generation scheduling is one of the main aspects of producing energy by lowering the total cost. There are many optimization techniques used to solve this problem but still researchers are working on the methods for achieving the best optimal solution. This review paper helps to present the different modeling and solution techniques which are supportive for current practical applications and will also be helpful in proposing new methods. It will be beneficial for the researchers working on hydro generation scheduling for unit commitment problem in terms of advantages and disadvantages of different techniques. Solving the hydro scheduling problem is complex due to net head effect on production of power and non-linearities in unit performance curves. Therefore, in order to deal with these problems different modeling and solution techniques are reviewed in this paper. This review paper focuses on the past studies carried out to solve the unit commitment problem for different time horizon. It also discusses the hydro unit commitment-based constraints. Several studies present different optimization techniques based on time horizon like short-term, long-term and medium term, on constraints like security network constraints and price-based constraints; and stochastic environment based constraints, time based constraints. The main purpose of this paper is to summarize the various techniques which are the most suitable for solving hydro generation scheduling with a special focus on different constraints for future implementation.
Hydro Constraints
In hydro-based system, each unit is treated as a separate unit in plant. Some additional constraints like startup/shutdown, minimum up/minimum down constraints are added in hydro unit commitment [22]
These are constraints which fulfill the generation companies (GENCO’s) special criteria.
(1) |
hydro power system consists of a set of generating units (GN) and a set of pumping units (PL). The sum of these sets of units must satisfy system load demand.
(2) |
Where is the high operating limits of generating unit, S is the system minimum spinning reserve requirement in time t.
(3) |
(4) |
Constraints of maximum and minimum number of online units in time t.
(5) |
The jth unit startup constraint for plant k is the function of startup and shutdown of units.
(6) |
Minimum up/down constraints for unit j of plant k.
(7) |
|
(8) |
shows minimum up and down time of jth unit.
Rate of change of turbine flow between two successive limits
(9) |
Several modelling and solution methods have been introduced in the past for the optimal solution of different time horizon for hydro unit commitment as shown in Table 1. These methods are divided into groups and classified as heuristic (or stochastic) methods which depend on different parameters. In order to obtain the optimum global solution, it needs proper tuning. The second group is of mathematical approaches—it gives good results but it is also computationally extensive. The third group contains hybrid techniques which are good at minimizing the time of execution. Hydropower generation scheduling can be solved by different optimization techniques. In the literature, the same methods were used by researchers for different problem formulations. In Sections 3.1 and 3.2, dissuasion is based on results obtained from previous studies for different considered parameters used for the unit commitment problem. Modelling techniques are used for simplification of real-world problems. The first step of designing a solution technique is modelling, i.e., to propose a model for solution of a problem. Several modelling techniques discussed in Section 3.1 are solved by various solution techniques discussed in Section 3.2. This review paper is helpful in describing the most feasible modelling and solution techniques for hydro scheduling.
Table 1. Different techniques for solving the unit commitment problem.
Groups |
Techniques |
Heuristic |
Genetic algorithm, differential evolution, bacterial foraging algorithm, simulated annealing, artificial bee colony algorithm, harmony search algorithm, particle swarm optimization and imperialistic competition algorithm. |
Mathematical programming |
Mixed integer linear programming, priority list approach, branch and bound approach, lagrange relaxation, linear programming, successive quadratic linear programming, nonlinear approach, bender decomposition, dynamic programming, stochastic programming, model predictive control, value function approximation, generation method, column-constraint, nested CG, state-space approximation and stabilized LR. |
Hybrid techniques |
Artificial neural network, genetic algorithm, tabu search and dynamic programming. |
Modelling Techniques
Mixed Integer Programming
Norouzi et al. [76] solved the short-term unit commitment problem while taking into account the security constraints by using mixed integer programming modelling technique. The goal of their work was to lower the overall cost and emissions. The ε-constraint and lexicographic optimization solution approach was used as a solution technique. This strategy was implemented by introducing the valve loading effect along with linear formulation and replacing the fixed ramp rate for thermal units with the dynamic one. Before using the analytical technique, first mixed integer nonlinear problem was linearized to mixed integer linear problem. To select the most desirable solution, fuzzy based solution technique was implemented to select the appropriate solution. The result obtained from these methods was efficient but the speed of these methods is slow. The future research will focus on other security indices to the proposed problem. Ahmadi et al. [77] reported a new problem named as self–scheduling of hydrothermal plant which was solved by the mixed integer programming model while considering cost of valve loading, outages of generator, prohibited operating zones, services of operating. The proposed method was solved by the same solution technique which Norouzi, Ahmadi, Nezhad and Ghaedi [76] used. Ahmadi, Aghaei, Shayanfar and Rabiee [77] used arbitrary trade instead of using fuzzy method because it was more economical and realistic. It gave more profit rather than emission generation. Research work will rely depend on using the approximate stochastic dynamic programming method for this problem by considering financial risks. Esmaeily et al. [78] implemented mixed integer linear programming on the stochastic self-scheduling issue. The main function was to increase the profit rate. For ramping constraints, the scenario tree for characterizing the uncertainties of price was implemented, and flexible technique by taking into consideration multi-performance curves and prohibited operating zones. The practical constraints were considered beside the conventional ones and the result showed that it takes more time to converge. Borghetti et al. [79] studied short-term operation depending on head of the reservoir by using mixed integer linear programming approach. This approach represented the electric power system application efficiently and was also efficient in computations. The model was divided into a set of two constraints: linear and non-linear. After this the linearization was enhanced through two dimensional considerations. This approach was highly efficient because it gave accurate solution and time of computation was better. The main drawback was its size which adversely affected its performance criteria. Future research involves the extension of the model. Chang, Aganagic, Waight, Medina, Burton, Reeves and Christoforidis [22] described the experiences to find optimal schedules with mixed-integer linear programming. The model was used for both conventional and pumped storage. The system-based relational database management was developed for mixed integer linear programming and short-term hydro scheduling function. AMPL is named as Algebraic mathematical programming language or CPLEX, which is an optimizer and is named for the simplex method based on C programming language, was used for modeling/optimization. Combined modelling language formulated the problem easily and updated it with less programming efforts. In the future this will also be checked on security constraints. Li et al. [80] implemented the mixed integer programming model on Three Gorges project, China for optimizing the hydro unit commitment problem. The main goal was to lower the objective cost by using iterative method to obtain the water level of tail-race and then use interpolation technique. The net head and unit performance curve were considered on a unit. This model was efficient for solving complex multi-unit hydropower system and with constant penstock, the computational burden was lower. Penstock head loss factors are difficult to model, so in the future researchers must focus on this factor. Carrión and Arroyo [17] presented another mixed-integer linear approach for solving the unit commitment problem of hydrothermal power plant. The objective was to present another way to reduce the time of computation with the help of binary constraints and variables. This approach solved realistic application. Minimization of overall cost was the main aim of solving unit commitment. The cost of production in this method for the power output was presented as a function of quadratic and startup cost was expressed as nonlinear. This method was tested on a realistic case study. This method was computationally efficient but for large systems it is difficult to find the accurate solution by this method. This approach should be applied to the new scheduling problems.
Teegavarapu and Simonovic [81] developed a model for optimal operation of cascaded hydropower plants. The optimization tool adopted for this hydro-scheduling was mixed integer nonlinear programming model. The curves of tail water elevation were used. The objective function was to minimize the cost. The EMMA model was applied to a series of four reservoirs on the Winnipeg River in Manitoba, Canada. This model provided the daily scheduling rules. The fixed flow transport delay times were introduced in the formulation. The issue of unit commitment was also solved because this approach also handles the integer variables. The global optimal solution from MINLP was not guaranteed. The computational burden increases due to increase in binary variables. For real-time operation a detail optimization problem is necessary to work together with this model.
Dynamic Programming
Dynamic programming follows a recursive relationship which is called Bellman’s Principle. It is used to find the optimal policy which find the optimal policy for each state. By using backward procedure, the feasible solution is found. This is done stage to stage until it reaches to starting stage. Lowery [82] engendered the unit commitment problem solved by dynamic programming. The objective was to find the feasibility of the method. The cost curve for a unit from minimum output to maximum capacity was constructed. The cost curve showed input function in dollars per hour and output function in megawatts. The big advantage of this method was finding the feasible way of working k + 1 unit instead of k units. The computational time was longer. The feasibility of this method needs to be checked in the future by using more constraints.
Nonlinear Approach
Catalão et al. [83] reported on the deregulation environment of electric power system and proposed an approach called nonlinear for solving this issue. The objective was to maximize the revenue and water storage level. This problem was normalized with linear and nonlinear constraints and it was named the quadratic programming issue, having quadratic function. The head sensitive cascaded reservoir was considered. This approach was applied on Portuguese cascaded hydro systems. The main asset of this technique was to examine the change in head as a single function of water storage and discharge. Moreover, as this approach was differentiated with a linear one. Future recommendation is to handle the problem with more constraints while considering the computational time.
Stochastic Modelling
Takriti et al. [84] solved a unit commitment problem by introducing a stochastic model. The scenario analysis was used for modeling the uncertainty about future demand. The different starting penalties and different updating strategies to get good policies were considered. The model was solved using progressive hedging solution technique. The model was implemented in parallel to reduce the computation time. This model was implemented on pump storage hydropower plant. It should be tested for conventional one for further work. Wu et al. [85] presented the stochastic model for random parameters like faults in calculating the loads, random generator outages and random flow lines. Time of a generator and frequency was enhanced by assigning weight to each scenario and this whole process was done with monte carlo simulation in this model. The advantage of this model was reliability in decisions in terms of long-term application of units which were generated, consumption of fuel and allocation of energy. Computational time was greater, therefore, to improve the calculation time, further work will be required.
Successive Linear Programming
Fosso and Belsnes [86] addressed the demanding behavior of liberalized electric power system and introduced successive linear programming for short time horizon operation. The goal of this paper was to maximize the profit and minimize the cost. The successive linear programming was used to obtain the solution which consists of iterations. Two modeling modes were used for dealing with plant losses. Normally the method was to find the short-term boundary conditions and long-term policy for scheduling. Later, these bids are calculated. Future research requires focusing on strategic bidding.
Solution Techniques
Lagrange Relaxation
This method focuses on finding the commitment schedules which satisfy all reserve and capacity constraints. For this purpose, it is required to determine the lagrange multipliers set which helps in searching for the most feasible solution. In order to satisfy the demand condition, this method used economic dispatch measurements which consider the single unit having reserve constraints.
Wang et al. [87] studied a solution technique, lagrange relaxation, which further modified and was named augmented lagrange relaxation for scheduling a generation in short-term horizon by considering environmental, transmission conditions and to avoid oscillations related to piece-wise linear cost functions while satisfying system constraints. To improve algorithm, unification quadratic penalty terms are added to modify the objective function. These additional quadratic penalty terms are also connected with power demand for improving the algorithm. Initial values were assigned to lagrangian multipliers for different constraints of the system such as, for capacity of transmission line, for emission purpose, for power balance and spinning reserve in order to solve a unit commitment. After this environmental conditions are satisfied by using decomposition approach. The conclusion was a new algorithm called augmented lagrangian relaxation method. This algorithm was efficient, applicable, speedy and booming. It gives probable results in real time. The hourly generation cost was higher than the proposed approach. If this method will apply to more practical systems, it will be more accurate in terms of cost savings. Frangioni et al. [88] solved short-term unit commitment problem by sequentially applying solution and modeling techniques: lagrangian and mixed integer linear programing (MILP). This sequential process was used for improving the efficiency. The lower bound of lagrangian was computed for developing feasible solution without any heuristic approach. After this MILP approach was started. This approach allowed accurate adjustment between the outcome and the running time as compared to the original lagrange technique. The positive side of this sequential approach was that it worked very well in giving accurate results in spite of the fact that it was a difficult thing to do. One disadvantage of using the lagrangian bound was that increase in running time made it less efficient. In the future, much work is needed to improve the lagrangian lower bound accuracy.
Orero and Irving [89] combined two solution techniques: genetic algorithm and lagrangian relaxation decomposition technique, and made a new algorithm for solving short-term unit commitment. The transmission line, ramping rate and pollution were considered as a constraint. This combined method was used in alternative ways, while solving the UC problem this algorithm handles continuous and discrete framework and benefits overall characteristics of genetic algorithm and it also gave output to each separate unit sub-issues by using lagrange relaxation. The disadvantage of using LR was that it did not guarantee an optimal solution. As there was no standard LR algorithm, presently heuristics and other algorithms are used to for calculating the value of lagrange multipliers. Further research is needed to find a standard LR algorithm. Beltran and Heredia [90] used a solution technique called augmented lagrange relaxation and tested by block coordinated descent and auxiliary problem principle method for short-term operation. This method was used to overcome the drawback of non-separable behavior of the pure lagrangian. To minimize effect of non-separable augmented lagrangian, the problem was divided into smaller sub problems. Auxiliary problem principle method used approximation to augmented lagrangian while block coordinated descent method directly minimized augmented lagrangian. In the first test the n-dimensional version of UC problem is taken and it compared the auxiliary problem principle with block coordinated decent method (BCD). After this, a second test was performed practically. It was concluded that the BCD method was faster theoretically and practically as compared to auxiliary lagrangian method. The major drawback of this is quality and much research is needed in improvement and quality of the solution. Virmani et al. [91] implemented lagrange relaxation method on the unit commitment problem to explain the critical aspects related to the practical and theoretical application of this method. This solution method found the optimal solution by determining lagrangian multipliers set which was used to find the commitment. Initial estimate for lagrange multiplier was obtained by ignoring the time dependent constraints. Feasible solution was obtained by using step sub gradient method. After feasible solution, new economic dispatch calculation was performed. Lagrangian multipliers were updated until the termination of solution by following specific rules. The viability of this technique is improved when it is applied practically. The main advantage of this technique is the linear behavior of execution time for units. The LR method was more suitable for large systems operation. Research is needed for small systems. Gröwe-Kuska et al. [92] developed a solution technique called lagrange relaxation which deals with uncertainties of inflows and of fuel. The stochastic lagrangian relaxation method was used as a solution technique. The stochastic problems of power management depend on lagrange relaxation schemes. Two types of lagrange had been introduced which found nearly optimal solution for first stage. The deterministic lagrangian heuristic named as lagrange heuristic 1 (LH1) gave nearly optimal decision only at nodes and it computed the mean values of scenario based stochastic process. The stochastic lagrangian heuristic named as lagrange heuristic 2 (LH2) was based on binary decisions and it gave nearly optimal solution at every stage while the deterministic heuristic required short computing time as compared to the stochastic one. The stochastic solution developed a guaranteed accuracy bounds while for the deterministic one the case was different. The improvement of existing stochastic lagrange solution approach requires further study still and finding a way of computing solution in a minimum time. Baldick [93] proposed lagrangian decomposition for solving unit commitment in a generalized way. The objective is to lower the overall cost by considering generator minimum on/off time, ramping rate, voltage reserve, transmission line, energy limit and fuel constraints. This problem was formulated as mixed integer non-linear problem. To obtain the primal feasible solution, the lagrange multiplier was initialized appropriately. The sub-problems which were solved at every redundancy were quadratic and separable. Sparse matrix and interior point approaches were implemented for the solution of sub problems. The central processing unit time increased quadratically because of non-sparse and non-separable implementation. This approach was unique in the sense that it could solve generalized problems directly but it did not give the quality of solution for special solutions. The future research should focus on the quality while considering price-based constraints.
Bender Decomposition Approach
Zheng et al. [94] solved a stochastic unit commitment problem by using bender decomposition. The benders decomposition approach was applied. The first stage consists of start-up/shut-down cost while in the second stage electric power dispatches were decided. To ease the burden of too many scenarios, the decision variables of the first stage were fixed and the next stage was divided into separate sub-problems. The information based on the solution was in the feedback cuts. This algorithm was efficient but it does not converge fast. Further work is required to consider faster convergence while focusing on implementation of advanced and stronger benders cuts.
Linear Quadratic Penalty Approach
Franco et al. [95] presented a solution technique known as linear quadratic penalty which coupled the electrical and hydro variables. The objective is to minimize the three terms load, cost, transmission losses and reservoir targets. The non-linear constraints of hydraulic and electric sub-problems were indirectly considered through a linear quadratic penalty technique. It had the advantage of augmented lagrange and exact-penalty procedures. Electric sub-problem was solved with side constraints algorithm via non-linear network flow. Hydro sub-problem was solved via dedicated algorithm. The advantage of this method was that it handles multi-objectives in a flexible way. However, it takes time to solve the problem—parallel processing can be used to improve the time.
Genetic Algorithm
The basic procedure of genetic algorithm is given below [96].
Kazarlis et al. [97] presented a heuristic technique called genetic algorithm in a different way. The operators were added which were specific for each problem and a varying technique related to quality function. To form the initial population, genotypes were produced at random. The operating schedule was for nth-unit and after random production of genotype, it was then decoded. After this fitness, value was assigned to genotype and cost of fuel was calculated. In genetic algorithm, the UC problem was not divided by time or by unit. GAs can be easily transformed to computation at the same time. The drawback in this method is optimality of the solution which is not certain and it had high execution time. Future research needs to focus on progress in the hardware of parallel computing. Ahmed and Sarma [98] introduced a genetic algorithm for multipurpose reservoir operation. The objective was to determine optimal operating policy. This method used piece-wise linear function for connecting all the end points of coordinates. For handling constraints, strings were randomly generated. To fix the best parameter, sensitivity analysis was taken. Genetic algorithm was efficient but was more specific because of piece-wise linear function. Leite et al. [96] used genetic algorithms aiming to find more efficient solution of the operation planning. The main goal was to minimize the generating cost. Nonlinear network flow algorithm (NNFA) algorithm for defining the volume for each set of plants was used. These volumes were used as initial population by genetic algorithm. The implementation of technique did not become more complex but it was argued that it cannot reach to efficient solution in a shorter computation.
Enhanced Simulated Annealing
Wong [99] solved the unit commitment problem by using enhanced simulated annealing solution method as shown in Figure 1 because this technique was easy to implement and did not need large memory. In this method, iteration number was equal to temperature level. For every trial of iteration number, a candidate solution was generated then a probabilistic test helped the solution to jump out of the local optimal. In this way all the accepted solutions were used to generate another candidate new solution. The solution process continued until the desired cost was found. However, the computational speed was improved by adopting parallel version but still it needs more improvement.
Figure 1. Flow chart of the enhanced simulated annealing for Unit Commitment [99].
3.2.6. Genetic Algorithm, Tabu Search and Simulated Annealing
Mantawy et al. [100] solved power system operation by combining three techniques integrating tabu search (TS), simulated annealing (SA) and genetic algorithms (GA) as shown in Figure 2. Basically, this method consisted of genetic algorithm but for the generation of new offspring’s tabu search technique was helpful. For accelerating the convergence of GA, SA was used. They solved three examples and compared with other methods. The result obtained was better than Integer programming, lagrange relaxation and separately used SA, TS, and GA. This algorithm gave high speed of convergence but did not give high quality of solution. For reducing computation time and finding wider solution space, further work is required.
Figure 2. Flow chart of the Genetic algorithm, Tabu search and Simulated Annealing [100].
Heuristic Algorithms
Kjeldsen and Chiarandini [101] solved the yearly power system operation with combined heat and power plants by using heuristic solutions. The objective was to reduce the cost of electricity while taking constraints on electricity, heating and biomass consumption. The four heuristic orithms relax-and-fix, LP-fix heuristic, lagrangian relaxation and heuristic dispatching were contrived heuristic for making the solution at initial stage of the program. For reducing the size of the problem, they used relax-and fix by restricting time horizon while using time as subsets. Dispatching heuristic sorted the units and satisfied the heating and electricity demands for all regions. The LP-fix approach solved the overall LP-relaxation by considering all the constraints. Lagrangian relaxation technique was good in solving the constraints which were good in binding the units together for the main purpose. The solution was improved by two local search methods, i.e., stochastic and mixed integer programming Solver as sub-procedure and economic dispatcher was also used as improvement method. The good quality solution results and better computational times were obtained but this method did not consider security and head-dependent constraints. This method will implement for short term while considering strategic decisions and new investments.
Combination of Modeling and Solution Techniques
Combined Method
Johannesen et al. [102] combined heuristic techniques and the iterative network linear programming model to find optimal short-term hydro scheduling. The demand and water level were considered as constraints and their major goal was to lower the cost at the end of the planning cycle. This problem was divided into a two-stage process. In the first stage, optimal production schedule was established and the problem was decomposed in sub problems and solved iteratively by using network flow algorithm. The hydro and electrical sub-problems were solved for initial solution stage without including security constraints. By using this optimization method, 0.3–0.4% increased utilization of available volume was obtained but this method takes a lot of time. Further work is needed to improve the quality of solution in terms of time.
Dynamic Programming with Heuristic Techniques
Patra et al. [13] combined the dynamic programming with fuzzy and simulated annealing. The objective was to solve the major drawback of dynamic programming called obscenity of dimensions. To predict the startup/shutdown cost, fuzzy approach was used and dynamic programming approach needs a lower number of policies to be kept at every step of multistage decision. The computation time of this method was fast and quality of solution was better. This method did not consider the load forecast uncertainty. The recommended algorithm will be suitable in the future for finding the solution of UC problem while taking security constraints and head-sensitive constraint into consideration. Su and Hsu [103] introduced a mixed technique which was a combinatorial of dynamic programming and fuzzy approach for power system operation. This method considered the faults in the calculation of load on an hourly basis and expressed it in fuzzy set notations. The objective function was to minimize the cost. In this approach, constraints were divided into two groups. This model includes crisp constraints and crisp state variables. The aim was to reach the optimal decision by using a membership function. Sensitivity analysis was taken to examine the effect of different membership functions. The major drawback of this approach was it took more time in contrast to conventional dynamic programming. Future research is needed to make it easy computationally.
Advantages and Disadvantages
Lagrange relaxation approaches are still the applicable method of working in the operational state, when a very extensive situation and very speedy running times are demanded [104,105]. The lagrange relaxation uses sub-gradient method to solve the dual problem [106]. In practice, to make the commitment decision effective, it is mandatory to implement more and more precise models of the actual operating ways of generating units. The deep-rooted rigor of lagrange relaxation rationalizes the interest towards the methods that are more buoyant to changes of the mathematical model of the generating units [7,23,107–109]. It makes it additionally multiplex which results in more difficulty to solve the optimization problem. However, this method usually engenders solution to be moderately infeasible since the linking constraints are scarcely satisfied with the first solutions [1]. The Lagrange decomposition algorithm is also suitable for dealing with the hydrothermal scheduling problem with uncertainty in load [110].
The mixed-integer linear programming (MILP) has tempted more heed [22,25,111–115]. This is owning to the fact that MILP deals with the non-linearities using piecewise linear approximation, adding constraints and the introduction of discrete nature of the problem via including integer variables or constraints. In power system, limits of power output depend on the net head and similarly in unit performance curves. The power output non-linearly depends on the unit total head and turbine jet. It is still very challenging to model non-linear characteristics through MILP techniques. In real time MILP mechanism, immense mathematical measures are involved. The MILP technique is limited in its implementation and applied on some turbine units. To combine two relatable problems, one economic dispatch and other unit commitment, research was conducted in the 1960s. Garver [116] proposed optimization model of mixed integer for scheduling of system while considering thermal units only. Despite the fact that this approach was uncomplicated to a certain extent, this method established intuition to the implementation of branch-and-bound algorithm which is used as application of mixed integer programming method for scheduling of electricity generation. Mixed integer programming method combined with other algorithms later and were presented more appropriate models [117]. The optimal unit commitment problem with probabilistic reserve determination preferred a mixed integer programming technique. The scheduling of hydropower plants was not only discussed in the past but also emphasized on scheduling of hydrothermal systems [118–130]. The addition and restriction in branch and bound algorithm is considered as the central key in the development of integer programming approach [131]. The problem of mixed integer programming was discussed; it was reported that mixed integer programming algorithm is worse in this case as it did not take the edge of special structure problems which results in a larger size of the system; and it also rapidly wore out computer measures. The mixed integer programming uses the reduction of the solution space by dismissing the infeasible subsets and by doing this it can solve the unit commitment problem [117]. Based on benders method, unit commitment is further divided into two different sub problems: one is an integer non-linear and the second is a non-linear economic dispatch sub problem.
The primary approach which is used to solve a unit commitment is dynamic programming (DP) [132]. Although DP performed good for small scale systems and is very effective, this technique gives the problem for large scale systems as it experiences the curse of dimensionality. The curse of dimensionality limits its direct implementation for cascaded reservoirs of hydro systems. However, DP is good at handling non-linear and non-convex features of the hydro and hydrothermal model. The short-term unit commitment experiences more difficulty in using DP as compared to long term optimization problem. The curse of dimensionality has restricted its application to large scale systems, otherwise it is an effective technique. The DP was used to solve unit commitment in a way that it represents the decision stages and is treated as a sequentially static optimization with generation units [133]. The unit commitment problem is also solved by many heuristic techniques. Kothari and Ahmad [35] proposed a method which combines dynamic programming with expert system and a rule-based system for solving the unit commitment problem and named this method as hybrid approach.
The artificial neural network (ANN) is a favorable method for solving the short-term unit commitment problem. However, one problem arises while using artificial neural networks (ANNs) in practical application for reinforcement of ANN, i.e., the computer takes more time for execution [134]. A very famous heuristic method is genetic algorithm (GA) which is introduced by [37,97,135]. It is a robust technique and is better for non-convex problems. However, one disadvantage of using this method is its surety related to attainment of optimal solutions while solving the unit commitment problem. The GA can also be used for multi-reservoir system operation and can be helpful for finite horizon deterministic related problems. This technique is simply suitable for complex systems and non-linear problems [38]. In spite of the advantages of GA, there are the flaws of genetic algorithm technique [136]. The GA method take a lot of time while solving the real-world problems and also creates some hurdles in the implementation of other heuristic programming approaches. Benders decomposition algorithm is efficient but does not converge fast. The advantage of this linear quadratic penalty approach is that it handles multi-objectives in a flexible way. However, it takes time to solve the problem. The main asset of the nonlinear technique is to examine the change in head as a single function of water storage and discharge. The advantage of stochastic programming is reliability in decisions in terms of long-term application of units, consumption of fuel and allocation of energy. The disadvantage is that it has more computational time.
Discussion
There has been rich literature on solving hydro unit commitment problem while considering different constraints. The algorithms and models are different even if they lie within the same category. Wang, Shahidehpour, Kirschen, Mokhtari and Irisarri [87], Frangioni, Gentile and Lacalandra [88], Orero and Irving [89], Beltran and Heredia [90], Virmani, Adrian, Imhof and Mukherjee [91] and Gröwe-Kuska, Kiwiel, Nowak, Römisch and Wegner [92] used augmented lagrange relaxation, sequential lagrange and MILP, lagrange relaxation decomposition and genetic algorithm, augmented lagrange relaxation, decomposition techniques (block coordinate descent and auxiliary problem principle), lagrange relaxation, stochastic lagrange relaxation methods, respectively. The different modelling and solution techniques are summarized in Table 2 and Table 3, respectively.
Summary of Modelling Techniques
Non-linear method takes the change of head as an individual function. Catalão et al. [83] used the nonlinear modelling approach for solving hydrogenation scheduling and results obtained show that it gives feasible and good computationally solution. Patra et al. [13] implement dynamic programming with heuristic techniques and results show that it is very efficient during imprecise hourly loads. The mixed integer linear programming (MILP) method gives efficient results and it is more capable in precision and execution time for large scale systems. The MILP model gives more profit rather than emission generation but less programming efforts are required because of the use of combined programming language. The MILP model is effective for solving large scale complex multi-unit commitment. Esmaeily, Ahmadi, Raeisi, Ahmadi, Nezhad and Janghorbani [78] implemented MILP for solving unit commitment problem, results obtained show that the computational time was rationale.
4.2. Summary of Solution Techniques
Augmented Lagrange Relaxation is fast, efficient and robust in practical size systems. The augmented lagrange relaxation, decomposition techniques (auxiliary problem principle and block coordinate descent) reported a global optimizer, Beltran and Heredia [90] used this solution technique for solving unit commitment problem and found that results obtained were not clear. The sequential lagrange and MILP is also efficient and lagrange relaxation decomposition handles both discrete and continuous parameters. The execution time and number of time stages varies linearly in lagrange relaxation. Frangioni, Gentile and Lacalandra [88] implemented this sequential approach and found that it was more effective as compared to standard mixed integer linear programming. The enhanced simulated annealing improved the speed by using parallel version, Wong [99] used this technique and results obtained were satisfactory. Zheng et al. [94] used benders decomposition and found that results obtained were efficient but the convergence was not faster.
Table 2. Summary of different modeling techniques by researchers.
Modelling Techniques |
Authors |
Remarks |
Mixed Integer programming-constraint method |
Ahmadi, Aghaei, Shayanfar and Rabiee [77] |
This method gives more profit rather than emission generation |
Mixed integer linear programming |
Borghetti, D’Ambrosio, Lodi and Martello [79] |
This method is effective for solving large scale complex multi-unit commitment. |
MILP |
Li, Li, Wei, Wang and Yeh [80] |
By adopting parallel version speed is improved |
Stochastic programming |
Gröwe-Kuska, Kiwiel, Nowak, Römisch and Wegner [92] |
It gives guaranteed accuracy bounds |
Nonlinear Approach |
Catalão, Mariano, Mendes and Ferreira [50] |
As the Binary variables are large, Computational burden increases. |
Mixed integer nonlinear programming |
Teegavarapu and Simonovic [81] |
This method is computationally efficient. |
Stochastic dynamic programming |
Archibald et al. [137], Borges and Pinto [138], Stedinger et al. [139] |
It focused on energy availability and reliability with random inflow and availability of generating the units. It is also good in solving the problem easily as it divides the original problem into independent, low dimensional sub-problems. Stochastic dynamic programming models, either stationary or non-stationary, are good in finding the policies which are helpful in operating the reservoirs. |
Mixed integer programming |
Aghaei et al. [140], Norouzi, Ahmadi, Nezhad and Ghaedi [76] and Ahmadi, Aghaei, Shayanfar and Rabiee [77] |
It controls the emissions of Hydrothermal plants. It also helps in computational requirement. This method deals with security constraints effectively. It also studies the effect of prohibited operating zones and valve loading effect |
Nonlinear programming |
Barros et al. [141] |
For better operation of real time nonlinear programming, this is the better choice. |
Stochastic programming |
Soares and Carneiro [142] |
This method deals with both cascaded and single reservoirs with high head for optimal operation. |
Linear programming |
Shawwash et al. [143], Yoo [144] |
It finds the generation on hourly basis. It is computationally fast. |
Simulation model |
Le Ngo et al. [145] |
For increasing the production of hydropower plant, it maintains the level of reservoir high. |
Stochastic dual dynamic programming |
Mo et al. [146] |
It focused on price as well operation of plant. |
Sensitivity analysis, Dynamic programming SIMULINK |
Aslan et al. [147] Mahmoud et al. [148] |
It finds the ideal configuration by using the flow rates when they are higher and also finds the key element of plant efficiency is head loss. |
Differential dynamic programming |
Chang et al. [149] |
It works better for small tail and high head reservoir plants. |
Mixed integer linear programming |
Carrión and Arroyo [17] |
It minimizes the curse of dimensionality |
Dynamic programming |
Lowery [82], Mariño and Mohammadi [150], [151,152] |
It is good in determining the optimum way of k + 1 units instead of k unit. It is also worthy in giving maximum power, when head and discharge changes. Multi-reservoirs have no impact on DP. It works in investigating the optimization models analytically. |
Table 3. Summary of different Solution Techniques by researchers.
Solution Techniques |
Authors |
Remarks |
Augmented Lagrange Relaxation |
Wang, Shahidehpour, Kirschen, Mokhtari and Irisarri [87] |
New algorithm was developed which is fast, efficient and robust in practical size systems. |
Sequential Lagrange-mixed integer linear programming |
Frangioni, Gentile and Lacalandra [88] |
Efficiency is improved by the sequential process of these two techniques. Here, mixed integer programming is a modelling technique and sequential lagrange is a solution technique. |
Lagrange Relaxation decomposition, Genetic Algorithm |
Orero and Irving [89] |
This combined method handles both discrete and continuous parameters. |
Augmented Lagrange relaxation ALR, Decomposition techniques (Auxiliary problem principle APP and Block coordinate descent BCD) |
Beltran and Heredia [90] |
Augmented Lagrange Relaxation method becomes a local and global optimizer by using Auxiliary problem principle (APP) and Block coordinated descent (BCD). The comparison of APP and BCD shows that BCD is faster as compared to APP. |
Lagrange relaxation |
Virmani, Adrian, Imhof and Mukherjee [91], Norouzi, Ahmadi, Nezhad and Ghaedi [76] and Finardi and Scuzziato [153] |
The linear variability is involved between the time of execution and time stages. This method gives efficient results and it is more capable in precision and execution time for large level systems. It also considers the turbine losses. |
Combined LP and heuristic technique |
Johannesen et al. [102] |
It handles multi-objectives more easily. |
Linear-quadratic penalty approach |
Franco et al. [150] |
It solves general problems directly, but it does not give good quality results. |
Lagrangian decomposition |
Baldick [95] |
It considers the effect of head change in single function. |
Fuzzy and simulated annealing with dynamic programming |
Patra, Goswami and Goswami [93] |
The computation time is good. |
Artificial Neural network |
Naresh and Sharma [134] |
This approach deals with the optimization of hydropower system which is interconnected |
Multi objective optimization |
Duckstein and Opricovic [154], Kuby et al. [155] |
This helps in decision making process and also evaluates the trade-offs based on economics and ecology. |
Regression method |
Singal et al. [156] |
The correlations are developed for finding the project cost and compare it with current project cost |
Genetic Algorithm |
Sharif and Wardlaw [157] Oliveira and Loucks [36] |
This is used for any reservoir and it also considers the real vectors. |
Ant-colony, multi-colony Ant algorithm |
Jalali et al. [158,159] |
The work of ant colony method is to provide good results while multi colony deals with probability of reducing the domain of global optimality. |
Different optimization techniques |
Iqbal et al. [160] |
Suggested different optimization techniques for different users. |
5.1. Conclusion
The current review has been initialized to study the prior research work for hydro scheduling by considering various constraints and different solutions and modelling techniques. It has been found that the hydro generating units deal with different constraints like head dependent, demand, discharge, security constraints, cascaded reservoirs, etc. The preceding studies emphasized the different time horizon unit commitment operation of hydropower plants by using various optimization methods. The centralized analysis of different mathematical models which are refined for different time horizon unit commitment of hydropower plants have been discussed in this paper. The most commonly used modelling and solution techniques for hydro scheduling are dynamic programming, lagrange relaxation and mixed integer linear programming (MILP). The dynamic programming is adapted easily; lagrange relaxation gives good results. However, for large scale complex problems, mixed integer linear programming model is effective because it handles the non-linearity and accurate solution. Moreover, MILP is computationally efficient and minimizes the curse of dimensionality; it also supports bidding strategies in market. Scheduling generation by optimizing the use of water resource helps in lowering the cost of electricity but due to scarcity of water, energy produced from hydropower plants becomes a critical issue. There is a need to implement these methods which save water and give more profit in terms of power generation. The methods discussed in this paper are helpful in meeting the energy goals while considering challenges of power generation from water. These modelling and solution techniques are helpful in consuming less water with high generation efficiency.
5.2. Prospective Outlook
In the future, lagrange relaxation needs to be modified to improve the quality of small-scale systems and to upgrade the lower bound accuracy of lagrange. The mixed integer linear programming needs to be considered for further improvement in terms of model extension and also attention should be given to penstock head loss function. The feasibility of dynamic programming is necessary to be examined in the future while considering more constraints such as security constraints and head sensitive cascaded reservoirs. To get good results while solving unit commitment problem, the center of interest for non-linear approach is computational time. Future work is required in stochastic programming for better quality of solution in terms of time. It is recommended for linear quadratic penalty approach to use the parallel processing to achieve better time. The bender decomposition requires faster convergence while focusing on implementation of advanced, and strong bender cuts is still a research gap. For genetic algorithm, it is necessary to handle the parallel computing, as genetic algorithm is more specific with piece-linear function. Therefore, it is necessary to check the policy by doing further tests.
References