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.     

三角形分布的双方叫价拍卖模型在电力交易中的应用

在完全开放的双边电力市场下,大用户直接购电问题已成为我国电力改革的重大课题.研究发电公司和大用户如何建立有效的报价策略具有十分重要的理论和实践价值.将发电公司看成卖方,将买电代理看成买方,针对卖方的成本和买方的估计是私有信息,并服从区间(0,1)上的三角形分布,建立了基于三角形分布的双方叫价拍卖的贝叶斯博弈模型,并得到了预期的均衡结果.通过一个数值例子与基于均匀分布的经典双方叫价拍卖模型进行比较.结果表明:建立的双方叫价拍卖模型在电力交易拍卖中的应用,能够提供更为准确的理论预期结果,具有更为现实的指导意义.     

Evaluating the impact of average cost based contracts on the industrial sector in the European emission trading scheme

The inception of the emission trading scheme in Europe has contributed to power price increases. Energy intensive industries have reacted by arguing that this may affect their competitiveness and will induce them to leave Europe. Taking up a proposal of these industrial sectors, we explore the possible application of special contracts, where electricity is sold at average generation cost to mitigate the impact of CO₂ cost on power prices. The model supposes fixed generation capacities. We first consider a reference model representing a perfectly competitive market where all consumers (industries and the rest of the market) are price-takers and buy electricity at short-run marginal cost. We then change the market design by assuming that energy intensive industries pay power either at a regional or at a zonal average cost price. The analysis is conducted with simulation models applied to the Central Western European power market. The models are implemented in GAMS/PATH. This work has been financially supported by the Chair Lhoist Berghmans in Environmental Economics and Management and by the Italian project PRIN 2006, Generalized monotonicity: models and applications, whose national responsible is Prof. Elisabetta Allevi.     

An optimization problem in the electricity market

New types of optimization problems are faced by the generating companies that operate on deregulated electricity markets. The characteristics of these problems depend on the various market structures. In the framework of the recently settled Italian electricity market, one of these new problems is the transition from hourly energy programs, defined by the market, to more detailed power generation dispatches, defined for intervals of 15 min. Such a more detailed plan is needed on the one hand by the national system operator (Terna, Rete Elettrica Nazionale) for the assessment of power system stability and security, and on the other hand by the power plant operators for its implementation. The transition procedure should respect the hourly energy constraints and take the main operating constraints of the generating units into account. The paper presents possible solutions of the problem through linear optimization models and reports computational results on real-world instances.      

Modeling and Solving an Airline Schedule Generation Problem

Since opening a new flight connection or closing an existing flight has a great impact on the revenues of an airline, the generation of the flight schedule is one of the fundamental problems in airline planning processes.In this paper we concentrate on a special case of the problem which arises at charter companies. In contrast to airlines operating on regular schedules, the market for charter airlines is well-known and the schedule is allowed to change completely from period to period. Thus, precise adjustments to the demands of the market have a great potential for minimizing operating costs.We present a capacitated network design model and propose a combined branch-and-cut approach to solve this airline schedule generation problem. To tighten the linear relaxation bound, we add cutting planes which adjust the number of aircraft and the spill of passengers to the demand on each itinerary.For real-world problems from a large European charter airline we obtain solutions within a very few percent of optimality with running times in the order of minutes on a customary personal computer for most of the data sets.     

A specialized primal-dual interior point method for the plastic truss layout optimization

We are concerned with solving linear programming problems arising in the plastic truss layout optimization. We follow the ground structure approach with all possible connections between the nodal points. For very dense ground structures, the solutions of such problems converge to the so-called generalized Michell trusses. Clearly, solving the problems for large nodal densities can be computationally prohibitive due to the resulting huge size of the optimization problems. A technique called member adding that has correspondence to column generation is used to produce a sequence of smaller sub-problems that ultimately approximate the original problem. Although these sub-problems are significantly smaller than the full formulation, they still remain large and require computationally efficient solution techniques. In this article, we present a special purpose primal-dual interior point method tuned to such problems. It exploits the algebraic structure of the problems to reduce the normal equations originating from the algorithm to much smaller linear equation systems. Moreover, these systems are solved using iterative methods. Finally, due to high degree of similarity among the sub-problems after preforming few member adding iterations, the method uses a warm-start strategy and achieves convergence within fewer interior point iterations. The efficiency and robustness of the method are demonstrated with several numerical experiments.     

Electricity price forecasting accounting for renewable energies: optimal combined forecasts

Electricity price forecasting is an interesting problem for all the agents involved in electricity market operation. For instance, every profit maximisation strategy is based on the computation of accurate one-day-ahead forecasts, which is why electricity price forecasting has been a growing field of research in recent years. In addition, the increasing concern about environmental issues has led to a high penetration of renewable energies, particularly wind. In some European countries such as Spain, Germany and Denmark, renewable energy is having a deep impact on the local power markets. In this paper, we propose an optimal model from the perspective of forecasting accuracy, and it consists of a combination of several univariate and multivariate time series methods that account for the amount of energy produced with clean energies, particularly wind and hydro, which are the most relevant renewable energy sources in the Iberian Market. This market is used to illustrate the proposed methodology, as it is one of those markets in which wind power production is more relevant in terms of its percentage of the total demand, but of course our method can be applied to any other liberalised power market. As far as our contribution is concerned, first, the methodology proposed by García-Martos et al (2007 and 2012) is generalised twofold: we allow the incorporation of wind power production and hydro reservoirs, and we do not impose the restriction of using the same model for 24?h. A computational experiment and a Design of Experiments (DOE) are performed for this purpose. Then, for those hours in which there are two or more models without statistically significant differences in terms of their forecasting accuracy, a combination of forecasts is proposed by weighting the best models (according to the DOE) and minimising the Mean Absolute Percentage Error (MAPE). The MAPE is the most popular accuracy metric for comparing electricity price forecasting models. We construct the combination of forecasts by solving several nonlinear optimisation problems that allow computation of the optimal weights for building the combination of forecasts. The results are obtained by a large computational experiment that entails calculating out-of-sample forecasts for every hour in every day in the period from January 2007 to December 2009. In addition, to reinforce the value of our methodology, we compare our results with those that appear in recent published works in the field. This comparison shows the superiority of our methodology in terms of forecasting accuracy.     

Open versus closed loop capacity equilibria in electricity markets under perfect and oligopolistic competition

We consider two game-theoretic models of the generation capacity expansion problem in liberalized electricity markets. The first is an open loop equilibrium model, where generation companies simultaneously choose capacities and quantities to maximize their individual profit. The second is a closed loop model, in which companies first choose capacities maximizing their profit anticipating the market equilibrium outcomes in the second stage. The latter problem is an equilibrium problem with equilibrium constraints. In both models, the intensity of competition among producers in the energy market is frequently represented using conjectural variations. Considering one load period, we show that for any choice of conjectural variations ranging from perfect competition to Cournot, the closed loop equilibrium coincides with the Cournot open loop equilibrium, thereby obtaining a ‘Kreps and Scheinkman’-like result and extending it to arbitrary strategic behavior. When expanding the model framework to multiple load periods, the closed loop equilibria for different conjectural variations can diverge from each other and from open loop equilibria. We also present and analyze alternative conjectured price response models with switching conjectures. Surprisingly, the rank ordering of the closed loop equilibria in terms of consumer surplus and market efficiency (as measured by total social welfare) is ambiguous. Thus, regulatory approaches that force marginal cost-based bidding in spot markets may diminish market efficiency and consumer welfare by dampening incentives for investment. We also show that the closed loop capacity yielded by a conjectured price response second stage competition can be less or equal to the closed loop Cournot capacity, and that the former capacity cannot exceed the latter when there are symmetric agents and two load periods.     

An efficient envelope-based Branch and Bound algorithm for non-convex combined heat and power production planning

Combined heat and power (CHP) production is universally accepted as one of the most energy-efficient technologies to produce energy with lower fuel consumption and fewer emissions. In CHP technology, heat and power generation follow a joint characteristic. Traditional CHP production is usually applied in backpressure plants, where the joint characteristic can often be represented by a convex model. Advanced CHP production technologies such as backpressure plants with condensing and auxiliary cooling options, gas turbines, and combined gas and steam cycles may require non-convex models. Cost-efficient operation of a CHP system can be planned using an optimization model based on forecasts for heat load and power price. A long-term planning model decomposes into thousands of single-period models, which can be formulated in the convex case as linear programming (LP) problems, and in the non-convex case as mixed integer programming (MIP) problems.     

Developing concurrent investment plans for power generation and transmission

Decisions on electric power generation and transmission investments may have crucial effects on the development of industrial and residential areas. Decisions made on the infrastructure should have economically beneficial consequences for producers and consumers. The aim of this paper is to propose a model that considers transmission and generation investments simultaneously. The proposed model fills in the gap between models for developing long-term power generation policies and instantaneous power flow models. Unlike other investment models, it explicitly takes the high voltage transmission network into account and the selection of new generation plants located on the interconnected network is made in a more realistic manner considering transmission bottlenecks.The problem subsumes the capacitated network location problem and the network design problem, the former being related to decisions on generation expansion and the latter to decisions on transmission network expansion. The integrated model becomes NP in both feasibility and optimality, because of the sub-problems it contains. Here, a practical procedure is proposed to achieve overall feasibility and also to improve investment decisions when the solution is feasible. The model is tested on the dense interconnected network of an industrialized region in Turkey. The implementation shows how future infeasibilities in the transmission network are highlighted by the model and how generation investment decisions are affected by network expansion alternatives.     

Incremental-like bundle methods with application to energy planning

An important field of application of non-smooth optimization refers to decomposition of large-scale or complex problems by Lagrangian duality. In this setting, the dual problem consists in maximizing a concave non-smooth function that is defined as the sum of sub-functions. The evaluation of each sub-function requires solving a specific optimization sub-problem, with specific computational complexity. Typically, some sub-functions are hard to evaluate, while others are practically straightforward. When applying a bundle method to maximize this type of dual functions, the computational burden of solving sub-problems is preponderant in the whole iterative process. We propose to take full advantage of such separable structure by making a dual bundle iteration after having evaluated only a subset of the dual sub-functions, instead of all of them. This type of incremental approach has already been applied for subgradient algorithms. In this work we use instead a specialized variant of bundle methods and show that such an approach is related to bundle methods with inexact linearizations. We analyze the convergence properties of two incremental-like bundle methods. We apply the incremental approach to a generation planning problem over an horizon of one to three years. This is a large scale stochastic program, unsolvable by a direct frontal approach. For a real-life application on the French power mix, we obtain encouraging numerical results, achieving a significant improvement in speed without losing accuracy.     

Nodal aggregation of resource constraints in a shortest path problem

The shortest path problem with resource constraints consists of finding the minimum cost path between two specified points while respecting constraints on resource consumption. Its solving by a dynamic programming algorithm requires a computation time increasing with the number of resources. With the aim of producing rapidly a good heuristic solution we propose to reduce the state space by aggregating resources. Our approach consists of projecting the resources on a vector of smaller dimension and then to dynamically adjust the projection matrix to get a better approximation of the optimal solution. We propose an adjustment based on Lagrangian and surrogate relaxations in a column generation framework, in which the sub-problems are shortest path problems with resource constraints. We adjust the multipliers only one time at each column generation iteration. This permit to obtain good solutions of the scheduling problem in few time.     

Capacity expansion and forward contracting in a duopolistic power sector

The surge in demand for electricity in recent years requires that power companies expand generation capacity sufficiently. Yet, at the same time, energy demand is subject to seasonal variations and peak-hour factors that cause it to be extremely volatile and unpredictable, thereby complicating the decision-making process. We investigate how power companies can optimise their capacity-expansion decisions while facing uncertainty and examine how expansion and forward contracts can be used as suitable tools for hedging against risk under market power. The problem is solved through a mixed-complementarity approach. Scenario-specific numerical results are analysed, and conclusions are drawn on how risk aversion, competition, and uncertainty interact in hedging, generation, and expansion decisions of a power company. We find that forward markets not only provide an effective means of risk hedging but also improve market efficiency with higher power output and lower prices. Power producers with higher levels of risk aversion tend to engage less in capacity expansion with the result that together with the option to sell in forward markets, very risk-averse producers generate at a level that hardly varies with scenarios.     

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.     

“新常态”下的中国天然气消费分析及预测

作为一种优质、高效的绿色能源,天然气在中国能源结构中所占比重逐渐增加。但可再生能源的崛起使得天然气成为过渡能源的选择,天然气消费量的增长趋势不明晰,因此相关企业及部门需要合理、准确的天然气需求预测模型为未来的工作提供指导性信息。基于此,本文首先从经济水平、产业结构、能源结构、天然气价格等方面选取影响天然气消费的12个因素。其次,运用贝叶斯模型平均(BMA)法构建了一个包含相关文献中常用的6个影响因素的基准模型,针对该模型,围绕影响天然气消费量的各种因素,以逐个添加的方式建立对比模型,从备选模型中选出预测精度最高的对未来天然气消费量进行预测。最后,将BMA模型与ARIMA模型、ETS模型、BVAR模型、逐步回归模型以及等权重加权平均模型的预测精度进行对比。结果表明,最优的BMA模型包含了涉及经济水平、产业结构、能源结构、人口因素、天然气价格、天然气供给六个方面9个影响因素,其预测精度优于对比预测模型,且该模型预测 2022年天然气消费量将达到3254.153亿立方米,年均增长率为8%。     

A Lagrangean based branch-and-cut algorithm for global optimization of nonconvex mixed-integer nonlinear programs with decomposable structures

In this work we present a global optimization algorithm for solving a class of large-scale nonconvex optimization models that have a decomposable structure. Such models, which are very expensive to solve to global optimality, are frequently encountered in two-stage stochastic programming problems, engineering design, and also in planning and scheduling. A generic formulation and reformulation of the decomposable models is given. We propose a specialized deterministic branch-and-cut algorithm to solve these models to global optimality, wherein bounds on the global optimum are obtained by solving convex relaxations of these models with certain cuts added to them in order to tighten the relaxations. These cuts are based on the solutions of the sub-problems obtained by applying Lagrangean decomposition to the original nonconvex model. Numerical examples are presented to illustrate the effectiveness of the proposed method compared to available commercial global optimization solvers that are based on branch and bound methods.     

Sparsity-promoting distributed charging control for plug-in electric vehicles over distribution networks

Uncoordinated charging of plug-in electric vehicles brings a new challenge on the operation of a power system as it causes power flow fluctuations and even unacceptable load peaks. To ensure the stability of power network, plug-in charging needs to be scheduled against the base load properly. In this paper, we propose a sparsity-promoting charging control model to address this issue. In the model, the satisfaction of customers is improved through sparsity-promoting charging where the numbers of charging time slots are optimized. Dynamic feeder overload constraints are imposed in the model to avoid any unacceptable load peaks, and thus ensure the network stability. Then, a distributed solution strategy is developed to solve the problem based on the alternating direction method of multipliers (ADMM) since most of power networks are managed typically in a distributed manner. During solving process, Lagrangian duality is used to transform the original problem into an equivalent dual problem, which can be decomposed into a set of homogeneous small-scaled sub-problems. Particularly, each sub-problem either has a closed-form solution or can be solved locally by an accelerated dual gradient method. The global convergence of the proposed algorithm is also established. Finally, numerical simulations are presented to illustrate our proposed method. In contrast to traditional charging models, our sparsity-promoting charging model not only ensures the stability of power network, but also improves the satisfaction of customers.     

Joint Modelling of Gas and Electricity Spot Prices

Abstract

The recent liberalization of electricity and gas markets has resulted in the growth of energy exchanges and modelling problems. In this article, we jointly model gas and electricity spot prices using a mean-reverting model that fits the correlation structures for the two commodities. The dynamics are based on Ornstein processes with parameterized diffusion coefficients. Moreover, using the empirical distributions of the spot prices, we derive a class of such parameterized diffusions that captures the most salient statistical properties: stationarity, spikes and heavy-tailed distributions. The associated calibration procedure is based on standard and efficient statistical tools. We calibrate the model on French market for electricity and on UK market for gas, and then we simulate some trajectories that reproduce well the observed prices behaviour. Finally, we illustrate the importance of the correlation structure and of the presence of spikes by measuring the risk on a power plant portfolio.     

Hybrid pricing in a coupled European power market with more wind power

In the European electricity market, the promotion of wind power leads to more network congestion. Zonal pricing (market coupling), which does not take the physical characteristics of transmission into account, is the most commonly used method to relieve network congestion in Europe. However, zonal pricing fails to provide adequate locational price signals regarding scarcity of energy and thus creates a large amount of unscheduled cross-border flows originating from wind-generated power. In this paper, we investigate the effects of applying a hybrid congestion management model, i.e., a nodal pricing model for one country embedded in a zonal pricing system for the rest of the market. We find that, compared to full nodal pricing, hybrid pricing fails to fully utilize all the resources in the network and some wrong price signals might be given. However, hybrid pricing still outperforms zonal pricing. The results from the study cases show that, within the area applying nodal pricing, better price signals are given; the need for re-dispatching is reduced; more congestion rent is collected domestically and the unit cost of power is reduced.     

A hierarchical decomposition approach to retail shelf space management and assortment decisions

Shelf management is a crucial task in retailing. Because of the large number of products found in most retail stores (sometimes more than 60?000), current shelf space management models can only solve sub-problems of the overall store optimization problem, since the size of the complete optimization problem would be prohibitively large. Consequently, an optimal allocation of store shelf space to products has not yet been achieved. We show that a hierarchical decomposition technique, consisting of two interwoven models, is suitable to overcome this limitation and, thus, is capable of finding accurate solutions to very large and complex shelf space management problems. We further conclude that other important variables (such as product-price) can be included into the methodology and their optimal values can be determined using the same solution technique. Our methodology is illustrated on a real-life application where we predict a 22.33% increase in store profits if our model's solution is implemented.