Optimization techniques for Available Transfer Capability (ATC) and market calculations

The recent movement towards an open, competitive market environmentintroduced new optimization problems such as market clearingmechanism, bidding decision and Available Transfer Capability(ATC) calculation. These optimization problems are characterizedby the complexity of power systems and the uncertainties inthe electricity market. Accurate evaluation of the transfercapability of a transmission system is required to maximizethe utilization of the existing transmission systems in a competitivemarket environment. The transfer capability of the transmissionnetworks can be limited by various system constraints such asthermal, voltage and stability limits. The ability to incorporatesuch limits into the optimization problem is a challenge inthe ATC calculation from an engineering point of view. In thecompetitive market environment, a power supplier needs to findan optimal strategy that maximizes its own profits under variousuncertainties such as electricity prices and load. On the otherhand, an efficient market clearing mechanism is needed to increasethe social welfare, i.e. the sum of the consumers’ andproducers’ surplus. The need to maximize the social welfaresubject to system operational constraints is also a major challengefrom a societal point of view. This paper presents new optimizationtechniques motivated by the competitive electricity market environment.Numerical simulation results are presented to demonstrate theperformance of the proposed optimization techniques.     

Divide to conquer: decomposition methods for energy optimization

Modern electricity systems provide a plethora of challenging issues in optimization. The increasing penetration of low carbon renewable sources of energy introduces uncertainty in problems traditionally modeled in a deterministic setting. The liberalization of the electricity sector brought the need of designing sound markets, ensuring capacity investments while properly reflecting strategic interactions. In all these problems, hedging risk, possibly in a dynamic manner, is also a concern. The fact of representing uncertainty and/or competition of different companies in a multi-settlement power market considerably increases the number of variables and constraints. For this reason, usually a trade-off needs to be found between modeling and numerical tractability: the more details are brought into the model, the harder becomes the optimization problem. For structured optimization and generalized equilibrium problems, we explore some variants of solution methods based on Lagrangian relaxation and on Benders decomposition. Throughout we keep as a leading thread the actual practical value of such techniques in terms of their efficiency to solve energy related problems.     

Risk-averse profit-based optimal scheduling of a hydro-chain in the day-ahead electricity market

This paper presents a profit-based model for short-term hydro scheduling adapted to pool-based electricity markets. The objective is to determine a feasible and realistic operation of a set of coupled hydro units belonging to a small or medium-size hydroelectric company in order to build the generation bids for the next 24 hourly periods. The company is assumed to be price-taker, and therefore, market prices are considered exogenous variables and modeled via scenarios generated by an Input/Output Hidden Markov Model (IOHMM). In order to be protected against low prices scenarios, two different risk-aversion criteria are introduced in the model: a minimum profit constraint and a minimum conditional Value-at-Risk (CVaR) requirement, which can be formulated linearly in the context of the optimization problem. In order to ensure a feasible operation, the model takes into account a very detailed representation of the generating units, which includes forbidden discharge intervals, spatial–temporal constraints among cascaded reservoirs, etc. The non-linear relationship among the electrical power, the net-head and the turbine water discharge is treated by means of an under-relaxed iterative procedure where net-heads are successively update until convergence is reached. During each algorithm stage, previous iterations’ information is used to build the input–output curves. This way, the hydro scheduling problem can be formulated as a MILP optimization problem, where unit-commitment decisions are modeled by means of binary variables. The model has been successfully applied to a real-size example case, which is also presented in this paper.     

基于标杆管理优化算法的供电商购电组合策略

针对开放式电力市场环境下,供电商的购电风险管理问题,结合金融输电权拍卖市场和电能交易市场,构造了一个考虑阻塞风险的供电商最优购电组合模型.由于此模型的非可微性和非凸性,使用了一种新型的智能计算方法——标杆管理优化算法对该模型进行了求解计算.仿真实例表明,提出求解计算方法是切实可行的,具有一定的实用性和灵活性.     

Semidefinite relaxations for partitioning, assignment and ordering problems

Semidefinite optimization is a strong tool in the study of NP-hard combinatorial optimization problems. On the one hand, semidefinite optimization problems are in principle solvable in polynomial time (with fixed precision), on the other hand, their modeling power allows to naturally handle quadratic constraints. Contrary to linear optimization with the efficiency of the Simplex method, the algorithmic treatment of semidefinite problems is much more subtle and also practically quite expensive. This survey-type article is meant as an introduction for a non-expert to this exciting area. The basic concepts are explained on a mostly intuitive level, and pointers to advanced topics are given. We provide a variety of semidefinite optimization models on a selection of graph optimization problems and give a flavour of their practical impact.     

电网安全调度中输电阻塞管理的演化策略

输电阻塞是电力系统运行中的常见问题 .本文建立了用于电网安全调度中输电阻塞管理的数学模型——带线性约束的多目标模糊优化问题模型 ,给出了求解该模型的演化策略 .实际的计算结果表明 ,演化策略解决输电阻塞问题是有效的 .     

Non-convex power plant modelling in energy optimisation

The European electricity market has been deregulated recently. This means that energy companies must optimise power generation considering the rapidly fluctuating price on the spot market. Optimisation has also become more difficult. New production technologies, such as gas turbines (GT), combined heat and power generation (CHP), and combined steam and gas cycles (CSG) require non-convex models. Risk analysis through stochastic simulation requires solving a large number of models rapidly. These factors have created a need for more versatile and efficient decision-support tools for energy companies.We formulate the decision-problem of a power company as a large mixed integer programming (MIP) model. To make the model manageable we compose the model hierarchically from modular components. To speed up the optimisation procedure, we decompose the problem into hourly sub-problems, and develop a customised Branch-and-Bound algorithm for solving the sub-problems efficiently. We demonstrate the use of the model with a real-life application.     

Unit commitment in electricity pool markets

We consider an electricity generator making offers of energy into an electricity pool market over a horizon of several trading periods (typically a single trading day). The generator runs a set of generating units with given start-up costs, shut-down costs and operating ranges. At the start of each trading period the generator must submit to the pool system operator a new supply curve defining quantities of offered energy and the prices at which it wants these dispatched. The amount of dispatch depends on the supply curve offered along with the offers of the other generators and market demand, both of which are random, but do not change in response to the actions of the generator we consider. After dispatch the generator determines which units to run in the current trading period to meet the dispatch. The generator seeks a supply function that maximizes its expected profit. We describe an optimization procedure based on dynamic programming that can be used to construct optimal offers in successive time periods over a fixed planning horizon.     

基于双曲型谱风险度量的大用户购电策略

直购电模式正在推行,大用户与电网公司的风险偏好却各不相同。本文将风险偏好纳入结算策略,建立了基于双曲型谱风险的购电优化模型,并用PJM日前市场的数据进行了实证分析。探讨了风险厌恶因子的敏感范围,将大用户划分为积极、稳健和保守三种类型,分别讨论了其购电策略。结果表明:无论风险偏好如何,大用户总愿意为获得高收益而承担更高的风险;风险偏好是购电策略的重要影响因素;当风险偏好既定时,大用户在远期合同市场和日前市场的购电比例可由谱风险值确定。随着谱风险值的增加,大用户会减少远期合同市场的购电量,更倾向于在日前市场购电。     

Mean‐risk optimization of electricity portfolios

We present a mathematical model with stochastic input data for mean‐risk optimization of electricity portfolios containing several physical components and energy derivative products. The model is designed for the optimization horizon of one year in hourly discretization. The aim consists in maximizing the mean book value of the portfolio at the end of the optimization horizon and, at the same time, in minimizing the risk of the portfolio decisions. The risk is measured by the conditional value‐at‐risk and by some multiperiod extension of CVaR, respectively.We present numerical results for a large‐scale realistic problem adapted to a municipal power utility and study the effects of varying weighting of risk. (© 2004 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Tacit collusion games in pool-based electricity markets under transmission constraints

Harrington et al. (Math Program Ser B 104:407–435, 2005) introduced a general framework for modeling tacit collusion in which producing firms collectively maximize the Nash bargaining objective function, subject to incentive compatibility constraints. This work extends that collusion model to the setting of a competitive pool-based electricity market operated by an independent system operator. The extension has two features. First, the locationally distinct markets in which firms compete are connected by transmission lines. Capacity limits of the transmission lines, together with the laws of physics that guide the flow of electricity, may alter firms’ strategic behavior. Second, in addition to electricity power producers, other market participants, including system operators and power marketers, play important roles in a competitive electricity market. The new players are included in the model in order to better represent real-world markets, and this inclusion will impact power producers’ strategic behavior as well. The resulting model is a mathematical program with equilibrium constraints (MPEC). Properties of the specific MPEC are discussed and numerical examples illustrating the impacts of transmission congestion in a collusive game are presented.     

安全约束条件下的经济调度优化模型研究

发电侧放开竞争的电力系统需要更加有效、准确的决策工具对有限的资源进行调度规划。短期经济调度优化问题是一个混合整数非线性规划问题,很难得到有效最优解,尤其是对于大规模电力系统。为了提高求解效率,本文提出了一个考虑安全约束的经济调度优化模型(Security-Constrained Economics Dispatch,SCED),主要采用线性化思想处理经济调度优化问题的模型以及各种约束,采用基于校正的交替求解方法,使得调度优化结果在运行成本最小化的前提下满足系统的安全稳定约束。同时,将本文方法运用到IEEE 30节点系统进行测试,从而验证本文方法有效性。     

Complexity and algorithms for convex network optimization and other nonlinear problems

Nonlinear optimization algorithms are rarely discussed from a complexity point of view. Even the concept of solving nonlinear problems on digital computers is not well defined. The focus here is on a complexity approach for designing and analyzing algorithms for nonlinear optimization problems providing optimal solutions with prespecified accuracy in the solution space. We delineate the complexity status of convex problems over network constraints, dual of flow constraints, dual of multi-commodity, constraints defined by a submodular rank function (a generalized allocation problem), tree networks, diagonal dominant matrices, and nonlinear Knapsack problem's constraint. All these problems, except for the latter in integers, have polynomial time algorithms which may be viewed within a unifying framework of a proximity-scaling technique or a threshold technique. The complexity of many of these algorithms is furthermore best possible in that it matches lower bounds on the complexity of the respective problems. In general nonseparable optimization problems are shown to be considerably more difficult than separable problems. We compare the complexity of continuous versus discrete nonlinear problems and list some major open problems in the area of nonlinear optimization. MSC classification: 90C30, 68Q25     

Two-settlement electricity markets with price caps and Cournot generation firms

We compare two alternative mechanisms for capping prices in two-settlement electricity markets. With sufficient lead time, forward market prices are implicitly capped by competitive pressure of potential entry that will occur when forward prices rise above some backstop price. Another more direct approach is to cap spot prices through a regulatory intervention. In this paper we explore the implications of these two alternative mechanisms in a two-settlement Cournot equilibrium framework. We formulate the market equilibrium as a stochastic equilibrium problem with equilibrium constraints (EPEC) capturing congestion effects, probabilistic contingencies and horizontal market power. As an illustrative test case, we use the 53-bus Belgian electricity network with representative generator costs but hypothetical demand and ownership structure. Compared to a price-uncapped two-settlement system, a forward cap increases firms’ incentives for forward contracting, whereas a spot cap reduces such incentives. Moreover, in both cases, more forward contracts are committed as the generation resource ownership structure becomes more diversified.     

Study on economic withholding in electricity market of Zhejiang Province,China

Power suppliers with market power intend to bid high-price to obtain excessive profit when intensions in the balance of electricity supply and demand emerge. New index is thus necessary to be defined to assess the economic withholding behavior associated with both bidding prices and corresponding bidding capacity. Stages of low price section, economic withholding section and reasonable adventure section were classified in this paper. Based on bidding prices and capacity, absolute index and relative index were proposed to measure the economic withholding degree, with the former used for estimation of the total power system while the latter for comparisons amongst different units. A case study on Zhejiang electricity market indicated that these two proposed indices can accurately assess the economic withholding behavior in the electricity market. Finally, upper limit was suggested to be set for the relative index to suppress the behavior of excessive bidding prices in short of capacity.     

The graph coloring problem: A neuronal network approach

Solution of an optimization problem with linear constraints through the continuous Hopfield network (CHN) is based on an energy or Lyapunov function that decreases as the system evolves until a local minimum value is attained. This approach is extended in to optimization problems with quadratic constraints. As a particular case, the graph coloring problem (GCP) is analyzed. The mapping procedure and an appropriate parameter-setting procedure are detailed. To test the theoretical results, some computational experiments solving the GCP are shown.     

Optimization of transmission network for homogeneous good market

We examine a model of a perfect competitive homogeneous good market with a network structure. Such a structure is typically important for energy resources: natural gas, oil and electricity. Local markets are connected by transmission lines with limited capacities and given cost functions for capacity increments. We consider the total welfare optimization problem and provide a method that determines optimal investments in the transmission system expansion for some types of the networks. In particular, we study the case where the market is divided into two submarkets with binding transmission line flow constraints between the submarkets. We obtain efficient algorithms for determination of the transmission systems optimal expansion. We conclude with the impact of the results and the outlook to future studies.     

Efficient algorithms for combined heat and power production planning under the deregulated electricity market

Combined heat and power (CHP) production is an important energy production technology that can yield much higher total energy efficiency than separate heat and power generation. In CHP production, the heat and power production follows a joint characteristic, which means that the production planning must be done in coordination. Cost-efficient operation of a CHP system can be planned by using an optimization model. A long-term planning model decomposes into thousands of hourly models. Earlier, in the regulated electric power market, the planning problem was symmetrically driven by heat and power demand. The liberalization of the power market has created an asymmetrical planning problem, where heat production responds to the demand and power production to the volatile market price. In this paper, we utilize this asymmetry to develop novel envelope-based dual algorithms for solving the hourly CHP models efficiently. The basic idea is to transform the three-dimensional characteristic operating region for heat and power production of each CHP plant into a two-dimensional envelope by taking the power price as a parameter. Then the envelopes of each plant are used for looking up the optimal solution rapidly. We propose two versions of the algorithm: the on-line envelope construction algorithm (ECON) where the envelopes are constructed for each hour based on the power price and the off-line envelope construction algorithm (ECOFF) where envelopes are pre-computed for all different power price ranges. We derive the theoretical time complexity of the two algorithms and compare their performance empirically with realistic test models against the ILOG CPLEX solver and the Power Simplex (PS) algorithm. PS is an extremely efficient specialized primal algorithm developed for the symmetrical CHP planning problem under the regulated market. On average, when reusing previous basic solutions, ECON is 603 times faster than CPLEX and 1.3 times faster than PS. ECOFF is 1860 times faster than CPLEX and four times faster than PS.     

Bilevel problems over polyhedra with extreme point optimal solutions

Bilevel programming involves two optimization problems where the constraint region of the upper level problem is implicitly determined by another optimization problem. In this paper we focus on bilevel problems over polyhedra with upper level constraints involving lower level variables. On the one hand, under the uniqueness of the optimal solution of the lower level problem, we prove that the fact that the objective functions of both levels are quasiconcave characterizes the property of the existence of an extreme point of the polyhedron defined by the whole set of constraints which is an optimal solution of the bilevel problem. An example is used to show that this property is in general violated if the optimal solution of the lower level problem is not unique. On the other hand, if the lower level objective function is not quasiconcave but convex quadratic, assuming the optimistic approach we prove that the optimal solution is attained at an extreme point of an ??enlarged?? polyhedron.     

Spatial dependencies of wind power and interrelations with spot price dynamics

Wind power has seen strong growth over the last decade and increasingly affects electricity spot prices. In particular, prices are more volatile due to the stochastic nature of wind, such that more generation of wind energy yields lower prices. Therefore, it is important to assess the value of wind power at different locations not only for an investor but for the electricity system as a whole. In this paper, we develop a stochastic simulation model that captures the full spatial dependence structure of wind power by using copulas, incorporated into a supply and demand based model for the electricity spot price. This model is calibrated with German data. We find that the specific location of a turbine – i.e., its spatial dependence with respect to the aggregated wind power in the system – is of high relevance for its value. Many of the locations analyzed show an upper tail dependence that adversely impacts the market value. Therefore, a model that assumes a linear dependence structure would systematically overestimate the market value of wind power in many cases. This effect becomes more important for increasing levels of wind power penetration and may render the large-scale integration into markets more difficult.