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

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

Coordination of Midterm Outage Scheduling With Short-Term Security-Constrained Unit Commitment

The proposed model solves the coordinated generation and transmission maintenance scheduling with security-constrained unit commitment (SCUC) over the scheduling horizon of weeks to months. The model applies the Lagrangian relaxation technique to decompose the optimization problem into subproblems for generation maintenance scheduling, transmission maintenance scheduling, and short-term SCUC. The decomposition and cooperation strategy is applied to the first two subproblems for the scheduling of generation and transmission maintenance. The SCUC solution is based on the mixed integer programming (MIP) technique. The optimal hourly results for maintenance scheduling, generation unit commitment, and transmission flows are obtained using a chronological load curve. Effective strategies are applied for accelerating the convergence of the hourly solution. The numerical examples demonstrate the effectiveness of the proposed model.     

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     

发电经济调度可行解判据及其求解方法

发电经济调度问题是一个经典混合整数规划问题,然而用拉格朗日松弛法得到的对偶解对原问题通常是不可行的,要获得可行解必须先得到一种可行的机组组合.本文分析了现有可行化条件中存在的问题,提出了一个易于检验的可行化条件,并证明它是充分必要的.随后,介绍了获得可行解的方法.     

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.     

松弛约束发电计划优化模型和算法

安全约束机组组合和安全约束经济调度是发电计划优化的核心,算法鲁棒性是影响其工程应用的关键因素.在对通用安全约束机组组合优化模型分析基础上,提出安全约束发电计划的松弛约束模型.通过松弛机组发电量约束、环保约束、网络约束、机组速率约束和机组调节范围约束等,提高算法收敛性能.文中所提出的模型和算法已成功应用于某省级电网.     

A new method for unit commitment with ramping constraints

Unit commitment with ramping constraints is a very difficult problem with significant economic impact. A new method is developed in this paper for scheduling units with ramping constraints within Lagrangian relaxation framework based on a novel formulation of the discrete states and the integrated applications of standard dynamic programming for determining the optimal discrete states across hours, and constructive dynamic programming for determining optimal generation levels. A section of consecutive running or idle hours is considered as a commitment state. A constructive dynamic programming (CDP) method is modified to determine the optimal generation levels of a commitment state without discretizing generation levels. The cost-to-go functions, required only for a few corner points with a few continuous state transitions at a particular hour, are constructed in the backward sweep. The optimal generation levels can be obtained in the forward sweep. The optimal commitment states across the scheduling horizon can then be obtained by standard dynamic programming. Numerical testing results show that this method is efficient and the optimal commitment and generation levels are obtained in a systematic way without discretizing or relaxing generation levels.     

考虑发电机组输出功率速度限制的最优机组组合

本文对发电机组输出功率速度限制条件下的电优机组组合问题进行了研究，提出了基于拉格朗日松弛原理的协调求解方法，构造在了构弛功率平衡约束的情况下的分离单机子问题的简单的网络模型，从而利用最短路径算法求出可行的组合方案。在此基础，利用动态优化调度的新算法－积留量法进行调整，从而达到机组组合与运行的良好协调，算例的试算，获得了较满意的效果。     

考虑网络安全约束的机组组合新算法

市场机制驱使电网运行于安全极限的边缘,考虑网络安全约束的机组组合问题变得尤为重要,基于对偶原理的拉格朗日松弛法是解决这一问题的有效途径。文章提出了一种解决网络安全约束下的机组组合问题的新算法,在拉格朗日对偶分解的基础上结合变量复制技术,通过引入附加人工约束将网络约束嵌入单机子问题中,实现在机组组合中考虑网络安全约束。该算法摆脱了现有各种处理手段在解决网络安全约束的机组组合问题时将网络安全约束与机组启停相分离的不足,揭示了安全经济调度和安全约束下的机组组合在概念上的区别和联系。     

A combination of the genetic algorithm and lagrangian relaxation decomposition techniques for the generation unit commitment problem

Unit commitment involves the scheduling of generators in a power system in order to meet the requirements of a given load profile. An analysis of the basis for combining the genetic algorithm (GA) and Lagrangian relaxation (LR) methods for the unit commitment problem is presented. It is shown that a robust unit commitment algorithm can be obtained by combining the global search property of the genetic algorithm with the ability of the Lagrangian decomposition technique to handle all kinds of constraints such as pollution, unit ramping and transmission security.     

机组优化组合的人工神经网络拉格朗日混合方法

本文提出了一种求解电力系统组合优化问题的混合神经网络－拉格朗日方法，至今，拉格朗日枪驰法－直被记是机组优化组合近解的实用方法，这样，基于神经网络的监督学习和自适应识别概念，我们用神经网络来推测负荷需求与拉格朗日乘子的非线性关系，并且采用了优化的学习速率和势态项来加速网络的收敛，数值计算的结果表明本文的方法是可行的。     

Cooperative coevolutionary algorithm for unit commitment

This paper presents a new cooperative coevolutionary algorithm (CCA) for power system unit commitment. CCA is an extension of the traditional genetic algorithm (GA) which appears to have considerable potential for formulating and solving more complex problems by explicitly modeling the coevolution of cooperating species. This method combines the basic ideas of Lagrangian relaxation technique (LR) and GA to form a two-level approach. The first level uses a subgradient-based stochastic optimization method to optimize Lagrangian multipliers. The second level uses GA to solve the individual unit commitment sub-problems. CCA can manage more complicated time-dependent constraints than conventional LR. Simulation results show that CCA has a good convergent property and a significant speedup over traditional GAs and can obtain high quality solutions. The "curse of dimensionality" is surmounted, and the computational burden is almost linear with the problem scale     

A solution method using neural networks for the generator commitment problem

This paper studies the feasibility of applying the Hopfield-type neural network to unit commitment problems in a large power system. The unit commitment problem is to determine an optimal schedule of what thermal generation units must be started or shut off to meet the anticipated demand; it can be formulated as a complicated mixed integer programming problem with a number of equality and inequality constraints. In our approach, the neural network gives the on/off states of thermal units at each period and then the output power of each unit is adjusted to meet the total demand. Another feature of our approach is that an ad hoc neural network is installed to satisfy inequality constraints which take into account standby reserve constraints and minimum up/down time constraints. The proposed neural network approach has been applied to solve a generator scheduling problem involving 30 units and 24 time periods; results obtained were close to those obtained using the Lagrange relaxation method.     

Augmented Lagrange Hopfield network based Lagrangian relaxation for unit commitment

This paper proposes an augmented Lagrange Hopfield network based Lagrangian relaxation (ALHN-LR) for solving unit commitment (UC) problem with ramp rate constraints. ALHN-LR is a combination of improved Lagrangian relaxation (ILR) and augmented Lagrange Hopfield network (ALHN) enhanced by heuristic search. The proposed ALHN-LR method solves the UC problem in three stages. In the first stage, ILR is used to solve unit scheduling satisfying load demand and spinning reserve constraints neglecting minimum up and down time constraints. In the second stage, heuristic search is applied to refine the obtained unit schedule including primary unit de-commitment, unit substitution, minimum up and down time repairing, and de-commitment of excessive units. In the last stage, ALHN which is a continuous Hopfield network with its energy function based on augmented Lagrangian relaxation is applied to solve constrained economic dispatch (ED) problem and a repairing strategy for ramp rate constraint violations is used if a feasible solution is not found. The proposed ALHN-LR is tested on various systems ranging from 17 to 110 units and obtained results are compared to those from many other methods. Test results indicate that the total production costs obtained by the ALHN-LR method are much less than those from other methods in the literature with a faster manner. Therefore, the proposed ALHN-LR is favorable for large-scale UC implementation.     

A solution to the unit commitment problem considering LNG fuel constraints

In this paper, an algorithm is proposed for finding a quasi-optimal schedule for the short-term thermal unit commitment problem taking LNG fuel constraints into account. In recent years, LNG fuel has been used increasingly. As a result, LNG fuel constraints should be considered in making a unit commitment schedule. Generally, unit commitment is a nonlinear combinatorial problem including discrete variables. To solve the problem, a two-step algorithm is developed using mathematical programming methods. First a linear programming problem is solved to determine the amount of LNG fuel to be consumed by each LNG unit, then a Lagrangian relaxation approach is used to obtain a unit commitment schedule. This two-step algorithm simplifies the problem and thus has good convergence characteristics. To test the effectiveness of the proposed algorithm, a numerical simulation was carried out on a 46-unit thermal system over a 24-hour period. A result with a dual gap of 0.00546 was obtained. © 1998 Scripta Technica, Electr Eng Jpn, 125(3): 22–30, 1998     

适用于不同电价机制的统一机组组合算法

现有电力市场中存在两种结算电价机制：按机组报价结算(一机一价)和按市场出清价格结算(统一电价)。不同市场之间的结算方式也有所不同,例如,双边交易中采用一机一价结算方式,而实时市场中采用边际电价结算方式。不同结算电价机制下,机组组合的目标函数不同,传统机组组合方法必须根据电价机制的不同进行调整。通过研究发现,两种结算方式下机组组合问题的最优条件具有类似的数学表达形式。基于这一统一的最优条件表达形式,提出了一种新的机组组合算法。与传统拉格朗日松弛法相比,新算法能够有效地求解两种电价机制下的机组组合问题。     

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.     

Optimization-based scheduling of hydrothermal power systems withpumped-storage units

This paper presents an optimization-based method for scheduling hydrothermal systems based on the Lagrangian relaxation technique. After system-wide constraints are relaxed by Lagrange multipliers, the problem is converted into the scheduling of individual units. This paper concentrates on the solution methodology for pumped-storage units. There are, many constraints limiting the operation of a pumped-storage unit, such as pond level dynamics and constraints, and discontinuous generation and pumping regions. The most challenging issue in solving pumped-storage subproblems within the Lagrangian relaxation framework is the integrated consideration of these constraints. The basic idea of the method is to relax the pond level dynamics and constraints by using another set of multipliers. The subproblem is then converted into the optimization of generation or pumping; levels for each operating state at individual hours, and the optimization of operating states across hours. The optimal generation or pumping level for a particular operating state at each hour can be obtained by optimizing a single variable function without discretizing pond levels. Dynamic programming is then used to optimize operating states across hours with only a few number of states and transitions. A subgradient algorithm is used to update the pond level Lagrangian multipliers. This method provides an efficient way to solve a class of subproblems involving continuous dynamics and constraints, discontinuous operating regions, and discrete operating states     

A genetic algorithm solution to the unit commitment problem

This paper presents a genetic algorithm (GA) solution to the unit commitment problem. GAs are general purpose optimization techniques based on principles inspired from the biological evolution using metaphors of mechanisms such as natural selection, genetic recombination and survival of the fittest. A simple GA algorithm implementation using the standard crossover and mutation operators could locate near optimal solutions but in most cases failed to converge to the optimal solution. However, using the varying quality function technique and adding problem specific operators, satisfactory solutions to the unit commitment problem were obtained. Test results for power systems of up to 100 units and comparisons with results obtained using Lagrangian relaxation and dynamic programming are also reported     

Unit commitment using a hybrid model between Lagrangian relaxation and genetic algorithm in competitive electricity markets

This paper presents a hybrid model between Lagrangian relaxation (LR) and genetic algorithm (GA) to solve the unit commitment problem. GA is used to update the Lagrangian multipliers. The optimal bidding curves as a function of generation schedule are also derived. An IEEE 118-bus system is used to demonstrate the effectiveness of the proposed hybrid model. Simulation results are compared with those obtained from traditional unit commitment.