Solving unit commitment problems with general ramp constraints

Lagrangian relaxation (LR) algorithms are among the most successful approaches for solving large-scale hydro-thermal unit commitment (UC) problems; this is largely due to the fact that the single-unit commitment (1UC) problems resulting from the decomposition, incorporating many kinds of technical constraints such as minimum up- and down-time requirements and time-dependent startup costs, can be efficiently solved by dynamic programming (DP) techniques. Ramp constraints have historically eluded efficient exact DP approaches; however, this has recently changed [Frangioni A, Gentile C. Solving nonlinear single-unit commitment problems with ramping constraints. Oper Res 2006;54(4):767–75]. We show that the newly proposed DP algorithm for ramp-constrained (1UC) problems allows to extend existing LR approaches to ramp-constrained (UC); this is not obvious since the heuristic procedures typically used to recover a primal feasible solution are not easily extended to take ramp limits into account. However, dealing with ramp constraints in the subproblems turns out to be sufficient to provide the LR heuristic enough guidance to produce good feasible solutions even with no other modification of the approach; this is due to the fact that (sophisticated) LR algorithms to (UC) duly exploit the primal information computed by the Lagrangian Dual, which in the proposed approach is ramp feasible. We also show by computational experiments that the LR [approach] is competitive with those based on general-purpose mixed-integer program (MIP) solvers for large-scale instances, especially hydro-thermal ones.     

具有爬升约束机组组合的充分必要条件

在Lagrangian松弛框架下，很难确定机组组合问题的一个可行解是否可通过调整对偶机组组合而获得。对于具有爬升约束的机组组合调度问题来说，由于机组出力在连续的2个开机区间的耦合性，求解可行解就更困难。在Lagrangian松弛框架下，开发1个机组组合新方法的核心是如何获得1个可行的机组组合。文中采用Benders分解可行性条件严格证明了在给定时段，机组组合可行的充分必要条件：即在该时段一个相应于系统负载平衡约束和旋转各用约束的不等式组成立。该条件不需要求解经济分配问题，就可以判定机组组合的可行性。有了此条件，可在发电功率经济分配前知道机组组合是否可行，若不可行，则可通过调整机组组合状态而获得可行的组合。该条件对于构造一个求解机组组合问题的系统方法是重要且有效的。数值测试表明该条件是判定机组组合可行性的有效方法。     

Projected mixed integer programming formulations for unit commitment problem

The thermal unit commitment (UC) problem is a large-scale mixed integer quadratic programming (MIQP), which is difficult to solve efficiently, especially for large-scale instances. This paper presents a projected reformulation for UC problem. After projecting the power output of unit onto [0,1], a novel MIQP reformulation, denoted as P-MIQP, can be formed. The obtained P-MIQP is tighter than traditional MIQP formulation of UC problem. And the reduced problem of P-MIQP, which is eventually solved by solvers such as CPLEX, is compacter than that of traditional MIQP. In addition, two mixed integer linear programming (MILP) formulations can be obtained from traditional MIQP and our P-MIQP of UC by replacing the quadratic terms in the objective functions with a sequence of piece-wise perspective-cuts. Projected MILP is also tighter and compacter than the traditional MILP due to the same reason of MIQP. The simulation results for realistic instances that range in size from 10 to 200 units over a scheduling period of 24 h show that the projected reformulation yields tight and compact mixed integer programming UC formulations, which are competitive with currently traditional ones.     

定制化求解机组组合混合整数线性规划模型的固定—推断法

为了突破机组组合算法的自主可控问题,基于开源混合整数线性规划求解器CBC,提出一种快速获取机组组合问题可行解的固定—推断法。首先将机组组合模型转换为推断标准模型,然后按重要性对所有整数变量进行排序。并利用约束违反函数依次确定整数变量的值,实现整数变量的固定,利用约束关系推断出与其相关的整数变量值。最后经过多轮的固定—推断可以实现所有整数变量的取值,从而求解一个线性规划问题即可得到各机组的出力。仿真结果表明,所述算法能有效求解大规模机组组合问题,可在更短时间内获取质量较好的可行解。与CBC求解器结合,能显著提升CBC求解器对于机组组合问题的求解效率。此外,所述算法还具备在其他求解器上进行定制的潜力。     

Unit commitment by an enhanced simulated annealing algorithm

A new simulated annealing (SA) algorithm combined with a dynamic economic dispatch method has been developed for solving the short-term unit commitment (UC) problem. SA is used for the scheduling of the generating units, while a dynamic economic dispatch method is applied incorporating the ramp rate constraints in the solution of the UC problem. New rules concerning the tuning of the control parameters of the SA algorithm are proposed. Three alternative mechanisms for generating feasible trial solutions in the neighborhood of the current one, contributing to the reduction of the required CPU time, are also presented. The ramp rates are taken into account by performing either a backward or a forward sequence of conventional economic dispatches with modified limits on the generating units. The proposed algorithm is considerably fast and provides feasible near-optimal solutions. Numerical simulations have proved the effectiveness of the proposed algorithm in solving large UC problems within a reasonable execution time.     

Unit commitment using Lagrangian relaxation and particle swarm optimization

Unit commitment (UC) is a NP-hard nonlinear mixed-integer optimization problem. This paper proposes ELRPSO, an algorithm to solve the UC problem using Lagrangian relaxation (LR) and particle swarm optimization (PSO). ELRPSO employs a state-of-the-art powerful PSO variant called comprehensive learning PSO to find a feasible near-optimal UC schedule. Each particle represents Lagrangian multipliers. The PSO uses a low level LR procedure, a reserve repairing heuristic, a unit decommitment heuristic, and an economic dispatch heuristic to obtain a feasible UC schedule for each particle. The reserve repairing heuristic addresses the spinning reserve and minimum up/down time constraints simultaneously. Moreover, the reserve repairing and unit decommitment heuristics consider committing/decommitting a unit for a consecutive period of hours at a time in order to reduce the total startup cost. Each particle is initialized using the Lagrangian multipliers obtained from a LR that iteratively updates the multipliers through an adaptive subgradient heuristic, because the multipliers obtained from the LR tend to be close to the optimal multipliers and have a high potential to lead to a feasible near-optimal UC schedule. Numerical results on test thermal power systems of 10, 20, 40, 60, 80, and 100 units demonstrate that ELRPSO is able to find a low-cost UC schedule in a short time and is robust in performance.     

Resolution of the unit commitment problems by using the hybrid Taguchi-ant colony system algorithm

This work presents a hybrid Taguchi-ant colony system (HTACS) algorithm to solve the unit commitment (UC) problem. The proposed algorithm integrates the Taguchi method and the conventional ant colony system (ACS) algorithm, providing a powerful global exploration capability. The Taguchi method is incorporated into the ACS process before its global pheromone update mechanism. Based on the systematic reasoning ability of the Taguchi method, improved UC solutions are selected quickly to represent potential UC schedules, subsequently, enhancing the ACS algorithm. Therefore, the proposed HTACS algorithm can be highly robust, statistically sound and quickly convergent. Additionally, feasibility of the proposed algorithm is demonstrated on a 10-unit system. Analysis results demonstrate that the proposed algorithm is feasible, robust, and more effective in solving the UC problem than conventional ACS methods.     

Daily generation scheduling optimization with transmissionconstraints: a new class of algorithms

The authors describe a novel class of algorithm dealing with the daily generation scheduling (DGS) problem. These algorithms have been designed by adding artificial constraints to the original optimization problem; handling these artificial constraints by using a dual approach; using an augmented Lagrangian technique rather than a standard Lagrangian relaxation technique; and applying the auxiliary problem principle which can cope with the nonseparable terms introduced by the augmented Lagrangian. To deal with the DGS optimization problem these algorithms are shown to be more effective than classical ones. They are well suited to solve this DGS problem taking into account transmission constraints     

Short-term thermal generation scheduling using improved immune algorithm

This paper proposes a new immune algorithm (NIA), which merges the fuzzy system (FS), the annealing immune (AI) method and the immune algorithm (IA) together, to resolve short-term thermal generation unit commitment (UC) problems. This proposed method differs from its counterparts in three main aspects, namely: (1) changing the crossover and mutation ratios from a fixed value to a variable value determined by the fuzzy system method, (2) using the memory cell and (3) adding the annealing immune operator. With these modifications, we can attain three major advantages with the NIA, i.e. (1) the NIA will not fall into a local optimal solution trap; (2) the NIA can quickly and correctly find a full set of global optimal solutions and (3) the NIA can achieve the most economic solution for unit commitment with ease. The UC determines the start-up and shut-down schedules for related generation units to meet the forecasted demand at a minimum cost while satisfying other constraints, such as each unit's generating limit. The NIA is applied to six cases with various numbers of thermal generation units over a 24-h period. The schedule generated by the NIA is compared with that by several other methods, including the dynamic programming (DP), the Lagrangian relaxation (LR), the standard genetic algorithm (GA), the traditional simulated annealing (SA) and the traditional Tabu search (TS). The comparisons verify the validity and superiority in accuracy for the proposed method.     

Fast unit commitment based on optimal linear approximation to nonlinear fuel cost: Error analysis and applications

Mixed-integer linear programming (MILP) based techniques are among the most widely applied methods for unit commitment (UC) problems. The fuel cost functions are often replaced by their piecewise linear approximations whereas it is more or less disturbing to use piecewise linear approximations without knowing the exact effect on solution deviation from the optima. Therefore, error analysis is important since the optimal solutions are different when different objective functions are adopted. Another important problem is balancing between solution quality and computation efficiency since better solution quality relies on finer discretization with exponentially increased computational efforts. A detailed error analysis is presented in this paper. It is found that the approximation error is inverse proportional to the square of the number of piecewise segments. Lower bounds on the minimum necessary number of discretization segments are also derived. A 2-Stage Procedure is then established to achieve a better balance between solution quality and computation efficiency. Numerical testing to 2 groups of UC problems is exciting. It is found that the operating cost increases no more than 0.6% in all cases while the CPU time is greatly reduced regarding other MILP approaches. The results are still valid in electric power market clearing computation.     

Optimal Scheduling of Spinning Reserve with Transmission Constraints

An effective method is proposed to schedule spinning reserve optimally. The method considers the transmission constraint in the whole scheduling process. To get the feasible solution faster, transmission line limits are first relaxed using the Lagrangian Relaxation technique. In the economic dispatch, after unit generation and spinning reserve are allocated among the committed units to satisfy the system andunit constraints, the schedule is then modified by a linear programming algorithm to avoid line overloads. The schedule is then updated by a probabilistic reserve assessment to meet a given risk index. The optimal value of the risk index is selected via a cost/benefit analysis based on the tradeoff between the total Unit Commitment (UC) schedule cost and the expected cost of energy not served. Finally, a unit decommitment technique is incorporated to solve the problem of reserve over-commitment in the Lagrangian Relaxation–based UC. The results of reserve scheduling with the transmission constraint are shown by the simulation runs performed on the IEEE reliability test system.     

基于外逼近方法的中期机组组合问题

利用外逼近方法（OAM）提出一种求解机组组合（UC）问题新的确定性方法。OAM是一种分解方法,它把UC问题分解为一系列的混合整数线性规划（MILP）主问题和非线性规划（NLP）子问题。应用分支割平面方法求解MILP,应用新的零空间内点法求解NLP。54机组168时段等多个系统的数值仿真表明,OAM具有快速的收敛速度,能有效处理爬坡约束,为大规模安全约束机组组合问题的有效求解提供了一条新途径。     

Short-term resource scheduling with ramp constraints [powergeneration scheduling]

This paper describes a Lagrangian relaxation-based method to solve the short-term resource scheduling (STRS) problem with ramp constraints. Instead of discretizing the generation levels, the ramp rate constraints are relaxed with the system demand constraints using Lagrange multipliers. Three kinds of ramp constraints, startup, operating and shutdown ramp constraints are considered. The proposed method has been applied to solve the hydro-thermal generation scheduling problem at PG&E. An example alone with numerical results is also presented     

Experiences with mixed integer linear programming based approacheson short-term hydro scheduling

This paper describes experiences with mixed integer linear programming (MILP) based approaches on the short-term hydro scheduling (STHS) function. The STHS is used to determine the optimal or near-optimal schedules for the dispatchable hydro units in a hydro-dominant system for a user-definable study period at each time step while respecting all system and hydraulic constraints. The problem can be modeled in detail for a hydro system that contains both conventional and pumped-storage units. Discrete and dynamic constraints such as unit startup/shutdown and minimum-up/minimum-down time limits are also included in the model for hydro unit commitment (HUC). The STHS problem is solved with a state-of-the-art package which includes an algebraic modeling language and a MILP solver. The usefulness of the proposed solution algorithm is illustrated by testing the problem with actual hydraulic system data. Numerical experiences show that the solution technique is computationally efficient, simple, and suitable for decision support of short-term hydro operations planning. In addition, the proposed approaches can be easily extended for scheduling applications in a deregulated environment     

A dynamic model for coordination of generation and transmission expansion planning in power systems

This paper presents a new dynamic approach on the expansion planning problem in power systems. First, the coordination between generation system expansion and transmission system expansion has been formulated as a mixed integer nonlinear programming (MINLP) problem. Then, it has been shown that this MINLP model cannot be efficiently solved by the traditional MINLP solvers. Since the nonlinear term comes from the multiplication of a binary variable by a continuous one, a Benders decomposition approach has been employed to convert the MINLP formulation into a mixed integer linear programming (MILP) master problem, and a linear programming (LP) sub-problem. Besides, different times of construction have been considered for different transmission and generation facilities. In addition, a clustering based algorithm has been proposed to evaluate the reliability of the system at hierarchical level II (HLII). Since this dynamic planning method is an upgraded version of a recent developed static model, the result from both methods have been also compared. A simple 6-bus test system and IEEE 30-bus system have been selected to confirm the effectiveness of the introduced method.     

Machine learning approaches to the unit commitment problem: Current trends,emerging challenges,and new strategies

Traditional power system operation and control decision-making processes, such as the unit commitment (UC) problem, primarily rely on the physical models and numerical calculations. With the growing scale and complexity of modern power grids, it becomes more complicated to accurately formulate the physical power system and more difficult to efficiently solve the corresponding UC problems. As a matter of fact, plenty of historical power system operation records as well as real-time data could provide useful information and insights of the underlying power grid. To this end, machine learning methods could be valuable to help understand the relationship of UC performance to power system parameters, reveal the rationality behind such relationship, and finally address UC problems in a more efficient and accurate way. This article discusses the current practices of using machine learning approaches to solve the mixed-integer linear programming based UC problems. The associated challenges are analyzed, and several promising strategies for adopting machine learning approaches to effectively solve UC problems are discussed in this article. In addition, we will also explore machine learning approaches to promptly solve steady-state nonlinear AC power flow and dynamics differential equations, so that they can be integrated into the UC problems to guarantee AC power flow security and dynamic stability of system operations, as compared to the current DC power flow constrained UC practice. Our studies show that machine learning, as model-free methods, is a valuable alternative or addition to the existing model-based methods. As a result, the effective combination of machine learning based approaches and physical model based methods are expected to derive more efficient UC solutions that can improve the secure and economic operation of power systems.     

The conditions for obtaining feasible solutions to security-constrained unit commitment problems

The core of solving security-constrained unit commitment (SCUC) problems within the Lagrangian relaxation framework is how to obtain feasible solutions. However, due to the existence of the transmission constraints, it is very difficult to determine if feasible solutions to SCUC problems can be obtained by adjusting generation levels with the commitment states obtained in the dual solution of Lagrangian relaxation. The analytical and computational necessary and sufficient conditions are presented in this paper to determine the feasible unit commitment states with grid security constraints. The analytical conditions are proved rigorously based on the feasibility theorem of the Benders decomposition. These conditions are very crucial for developing an efficient method for obtaining feasible solutions to SCUC problems. Numerical testing results show that these conditions are effective.     

Implementation of a Lagrangian relaxation based unit commitmentproblem

An effort is made to provide an understanding of the practical aspects of the Lagrangian relaxation methodology for solving the thermal unit commitment problem. Unit commitment is a complex, mixed integer, nonlinear programming problem complicated by a small set of side constraints. Until recently, unit commitment for realistic size system has been solved using heuristic approaches. The Lagrangian relaxation offers a new approach for solving such problems. Essentially, the method involves decomposition of the problem into a sequence of master problems and easy subproblems, whose solutions converge to an ϵ-optimal solution to the original problem. The authors concentrate on the implementation aspects of the Lagrangian relaxation method applied to realistic and practical unit commitment problems     

Reserve constrained economic dispatch with prohibited operatingzones

A method is described for solving the reserve constrained economic dispatch problem when some of the online generating units have prohibited operating zone(s). For a unit with prohibited zone(s), the zone(s) divide the operating region between the minimum generation limit (Pmin) and the maximum generation limit (Pmax) into disjoint convex subregions. These disjoint subregions form a nonconvex decisions space and the associated economic dispatch problem is thus a nonconvex optimization problem. As a result, the conventional Lagrangian relaxation (LR) approach (e.g. the λ-δ iterative approach) cannot be applied directly. The method proposed decomposes the nonconvex decision space into a small number of subsets such that each of the associated dispatch problems is either infeasible or one that can be directly solved via the conventional LR approach. Based on the decomposition, the optimal solution is the least costly one among all the feasible solutions of the associated dispatch problems. Examples are also given to illustrate the proposed method     

Optimal energy exchange of an industrial cogeneration in a day-ahead electricity market

This paper addresses an optimal strategy for the daily energy exchange of a 22-MW combined-cycle cogeneration plant of an industrial factory operating in a liberalized electricity market. The optimization problem is formulated as a Mixed-Integer Linear Programming Problem (MILP) that maximizes the profit from energy exchange of the cogeneration, and is subject to the technical constraints and the industrial demand profile. The integer variables are associated with export or import of electricity whereas the real variables relate to the power output of gas and steam turbines, and to the electricity purchased from or sold to the market. The proposal is applied to a real cogeneration plant in Spain where the detailed cost function of the process is obtained. The problem is solved using a large-scale commercial package and the results are discussed and compared with different predefined scheduling strategies.