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.     

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.     

An efficient linear model and optimisation algorithm for multi-site combined heat and power production

Combined heat and power (CHP) production is an important energy production technology which can help to improve the efficiency of energy production and to reduce the emission of CO₂. Cost-efficient operation of a CHP system can be planned using an optimisation model based on hourly load forecasts. A long-term planning model decomposes into hourly models, which can be formulated as linear programming (LP) problems. Such problems can be solved efficiently using the specialized Power Simplex algorithm. However, Power Simplex can only manage one heat and one power balance. Since heat cannot be transported over long distances, Power Simplex applies only for local CHP planning.In this paper we formulate the hourly multi-site CHP planning problem with multiple heat balances as an LP model with a special structure. We then develop the Extended Power Simplex (EPS) algorithm for solving such models efficiently. Even though the problem can be quite large as the number of demand sites increases, EPS demonstrates very good efficiency. In test runs with realistic models, EPS is from 29 to 85 times faster than an efficient sparse Simplex code using the product form of inverse (PFI). Furthermore, the relative efficiency of EPS improves as the problem size grows.     

Lagrangian relaxation based algorithm for trigeneration planning with storages

Trigeneration is a booming power production technology where three energy commodities are simultaneously produced in a single integrated process. Electric power, heat (e.g. hot water) and cooling (e.g. chilled water) are three typical energy commodities in the trigeneration system. The production of three energy commodities follows a joint characteristic. This paper presents a Lagrangian relaxation (LR) based algorithm for trigeneration planning with storages based on deflected subgradient optimization method. The trigeneration planning problem is modeled as a linear programming (LP) problem. The linear cost function poses the convergence challenge to the LR algorithm and the joint characteristic of trigeneration plants makes the operating region of trigeneration system more complicated than that of power-only generation system and that of combined heat and power (CHP) system. We develop an effective method for the long-term planning problem based on the proper strategy to form Lagrangian subproblems and solve the Lagrangian dual (LD) problem based on deflected subgradient optimization method. We also develop a heuristic for restoring feasibility from the LD solution. Numerical results based on realistic production models show that the algorithm is efficient and near-optimal solutions are obtained.     

An improved unit decommitment algorithm for combined heat and power systems

This paper addresses the unit commitment in multi-period combined heat and power (CHP) production planning, considering the possibility to trade power on the spot market. In CHP plants (units), generation of heat and power follows joint characteristics, which means that production planning for both heat and power must be done in coordination. We present an improved unit decommitment (IUD) algorithm that starts with an improved initial solution with less heat surplus so that the relative cost-efficiency of the plants can be determined more accurately. Then the subsequent decommitment procedures can decommit (switch off) the least cost-efficient plants properly. The improved initial solution for the committed plants is generated by a heuristic procedure. The heuristic procedure utilizes both the Lagrangian relaxation principle that relaxes the system-wide (heat and power) demand constraints and a linear relaxation of the ON/OFF states of the plants. We compare the IUD algorithm with realistic test data against a generic unit decommitment (UD) algorithm. Numerical results show that IUD is an overall improvement of UD. The solution quality of IUD is better than that of UD for almost all of tested cases. The maximum improvement is 11.3% and the maximum degradation is only 0.04% (only two sub-cases out of 216 sub-cases) with an average improvement of 0.3–0.5% for different planning horizons. Moreover, IUD is more efficient (1.1–3 times faster on average) than UD.     

A variant of the dynamic programming algorithm for unit commitment of combined heat and power systems

The paper addresses the unit commitment in multi-period combined heat and power (CHP) production planning under the deregulated power market. In CHP plants (units), generation of heat and power follows joint characteristics, which means that production planning must be done in coordination. We introduce in this paper the DP-RSC1 algorithm, which is a variant of the dynamic programming (DP) algorithm based on linear relaxation of the ON/OFF states of the units and sequential commitment of units one by one. The time complexity of DP-RSC1 is proportional to the number of generating units in the system, the number of periods over the planning horizon and the time for solving a single-period economic dispatch problem. We have compared the DP-RSC1 algorithm with realistic power plants against the unit decommitment algorithm and the traditional priority listing method. The results show that the DP-RSC1 algorithm gives somewhat more accurate results (0.08–0.5% on average, maximum 10% for the individual sub-case) and executes 3–5 times faster on average than the unit decommitment algorithm. It is not surprising that the solution quality of the DP-RSC1 algorithm is much better than that of the priority listing method.     

Optimal Operations Management and Network Planning of a District Heating System with a Combined Heat and Power Plant

District heating plants are becoming more common in European cities. These systems make it possible to furnish users with warm water while locating the production plants in the outskirts having the double benefit of lowering the impact of pollution on the center of the city and achieving better conversion performances. In order to amortize the costs throughout the year, the system often includes a combined heat and power (CHP) plant, to exploit the energy during the summer as well, when the demand for warm water decreases. A linear programming model for the optimal resource management of such a plant is presented and some results for a real case are reported. A distribution network design problem is also addressed and solved by means of mixed integer linear programming.     

Local and global returns to scale in performance measurement

In data envelopment analysis, the type of local returns to scale (RTS) exhibited by a technically efficient unit indicates whether an increase or reduction of the scale of operations could improve the productivity of the unit. One of the approaches to testing RTS is based on the comparison of the efficiency of the unit in specially constructed reference technologies. It has been suggested that this approach is equally suitable for convex and non-convex, including the free disposal hull, technologies. In this paper, we construct examples that show that this suggestion in the case of non-convex technologies is not correct. We show that the type of RTS obtained by this approach is not a local, but global, characteristic of the technology, as it indicates the direction to the most productive scale size of the unit. In non-convex technologies, the local and global classifications of RTS are generally different.     

Robust duality for generalized convex programming problems under data uncertainty

In this paper we present a robust duality theory for generalized convex programming problems in the face of data uncertainty within the framework of robust optimization. We establish robust strong duality for an uncertain nonlinear programming primal problem and its uncertain Lagrangian dual by showing strong duality between the deterministic counterparts: robust counterpart of the primal model and the optimistic counterpart of its dual problem. A robust strong duality theorem is given whenever the Lagrangian function is convex. We provide classes of uncertain non-convex programming problems for which robust strong duality holds under a constraint qualification. In particular, we show that robust strong duality is guaranteed for non-convex quadratic programming problems with a single quadratic constraint with the spectral norm uncertainty under a generalized Slater condition. Numerical examples are given to illustrate the nature of robust duality for uncertain nonlinear programming problems. We further show that robust duality continues to hold under a weakened convexity condition.     

Estimating non-convex production sets – imposing convex input sets and output sets in data envelopment analysis

In this paper, we present Data Envelopment Analysis models for estimating non-convex production sets. In contrast to the Banker et al. (Banker, R.D., Charnes, A. and Cooper, W.W., 1984. Management Science 30 (9), 1078–1092) model, these models give statistically consistent estimators for production sets that are non-convex, but do have convex input sets and/or convex output sets, as is typically assumed in micro-economic theory. In addition, these models suffer less from a finite sample error than the Free Disposable Hull (Deprins, D., Simar, L., Tulkens, H., 1984. In: Marchand, M., Pestieu, P., Tulkens, H. (Eds.), The Performance of Public Enterprises. North-Holland, Amsterdam, pp. 243–267) model.     

An alternating iterative method and its application in statistical inference

This paper studies non-convex programming problems. It is known that, in statistical inference, many constrained estimation problems may be expressed as convex programming problems. However, in many practical problems, the objective functions are not convex. In this paper, we give a definition of a semi-convex objective function and discuss the corresponding non-convex programming problems. A two-step iterative algorithm called the alternating iterative method is proposed for finding solutions for such problems. The method is illustrated by three examples in constrained estimation problems given in Sasabuchi et al. （Biometrika, 72, 465472 （1983））, Shi N. Z. （J. Multivariate Anal., 50, 282-293 （1994）） and El Barmi H. and Dykstra R. （Ann. Statist., 26, 1878 1893 （1998））.     

Solving continuous min max problem for single period portfolio selection with discrete constraints by DCA

In this article, we consider the application of a continuous min–max model with cardinality constraints to worst-case portfolio selection with multiple scenarios of risk, where the return forecast of each asset belongs to an interval. The problem can be formulated as minimizing a convex function under mixed integer variables with additional complementarity constraints. We first prove that the complementarity constraints can be eliminated and then use Difference of Convex functions (DC) programming and DC Algorithm (DCA), an innovative approach in non-convex programming frameworks, to solve the resulting problem. We reformulate it as a DC program and then show how to apply DCA to solve it. Numerical experiments on several test problems are reported that demonstrate the accuracy of the proposed algorithm.     

CO2 emissions trading planning in combined heat and power production via multi-period stochastic optimization

The EU emissions trading scheme (ETS) taking effect in 2005 covers CO₂ emissions from specific large-scale industrial activities and combustion installations. A large number of existing and potential future combined heat and power (CHP) installations are subject to ETS and targeted for emissions reduction. CHP production is an important technology for efficient and clean provision of energy because of its superior carbon efficiency. The proper planning of emissions trading can help its potential into full play, making it become a true “winning technology” under ETS. Fuel mix or fuel switch will be the reasonable choices for fossil fuel based CHP producers to achieve their emissions targets at the lowest possible cost. In this paper we formulate CO₂ emissions trading planning of a CHP producer as a multi-period stochastic optimization problem and propose a stochastic simulation and coordination approach for considering the risk attitude of the producer, penalty for excessive emissions, and the confidence interval for emission estimates. In test runs with a realistic CHP production model, the proposed solution approach demonstrates good trading efficiency in terms of profit-to-turnover ratio. Considering the confidence interval for emission estimates can help the producer to reduce the transaction costs in emissions trading. Comparisons between fuel switch and fuel mix strategies show that fuel mix can provide good tradeoff between profit-making and emissions reduction.     

Logarithmic SUMT limits in convex programming

The limits of a class of primal and dual solution trajectories associated with the Sequential Unconstrained Minimization Technique (SUMT) are investigated for convex programming problems with non-unique optima. Logarithmic barrier terms are assumed. For linear programming problems, such limits – of both primal and dual trajectories – are strongly optimal, strictly complementary, and can be characterized as analytic centers of, loosely speaking, optimality regions. Examples are given, which show that those results do not hold in general for convex programming problems. If the latter are weakly analytic (Bank et al. [3]), primal trajectory limits can be characterized in analogy to the linear programming case and without assuming differentiability. That class of programming problems contains faithfully convex, linear, and convex quadratic programming problems as strict subsets. In the differential case, dual trajectory limits can be characterized similarly, albeit under different conditions, one of which suffices for strict complementarity. Received: November 13, 1997 / Accepted: February 17, 1999?Published online February 22, 2001     

Relaxations of linear programming problems with first order stochastic dominance constraints

Linear stochastic programming problems with first order stochastic dominance (FSD) constraints are non-convex. For their mixed 0-1 linear programming formulation we present two convex relaxations based on second order stochastic dominance (SSD). We develop necessary and sufficient conditions for FSD, used to obtain a disjunctive programming formulation and to strengthen one of the SSD-based relaxations.     

带阀点效应水火联合调度问题的一种半定凸松弛求解法

水火联合调度问题是电力系统中一类复杂的优化问题。合理安排调度周期内的水火电出力,确定一个最优发电计划,可以带来巨大的经济效益。在实际系统中,汽轮机调汽阀开启时出现的拔丝现象会使机组耗量特性产生阀点效应。忽略阀点效应,在一定程度上降低求解的精度。本文考虑带阀点效应的水火联合调度问题。该问题非凸非光滑,且带有非线性约束,直接使用确定性全局优化方法求解是相当困难的。本文使用高效的半定规划求解此问题。首先用耗量特性函数的初始周期代替其余有限的周期,并对其进行二次拉格朗日插值拟合。再通过引进0-1变量,得到整个耗量特性函数的近似,进而把问题松弛为半定规划模型。最后,采用凸规划应用软件包CVX求解一个仿真算例,得到一个近似全局最优解。     

An Integrated Market for Electricity and Natural Gas Systems with Stochastic Power Producers

In energy systems with high shares of weather-driven renewable power sources, gas-fired power plants can serve as a back-up technology to ensure security of supply and provide short-term flexibility. Therefore, a tighter coordination between electricity and natural gas networks is foreseen. In this work, we examine different levels of coordination in terms of system integration and time coupling of trading floors. We propose an integrated operational model for electricity and natural gas systems under uncertain power supply by applying two-stage stochastic programming. This formulation co-optimizes day-ahead and real-time dispatch of both energy systems and aims at minimizing the total expected cost. Additionally, two deterministic models, one of an integrated energy system and one that treats the two systems independently, are presented. We utilize a formulation that considers the linepack of the natural gas system, while it results in a tractable mixed-integer linear programming (MILP) model. Our analysis demonstrates the effectiveness of the proposed model in accommodating high shares of renewables and the importance of proper natural gas system modeling in short-term operations to reveal valuable flexibility of the natural gas system. Moreover, we identify the coordination parameters between the two markets and show their impact on the system’s operation and dispatch.     

Joint planning of combined heat and power and electric power systems: An efficient model formulation

The growing importance of combined heat and power (CHP) around the world has increased the need to consider its role within electric power systems. In this paper, we show how the problem of joint planning of CHP and electric power systems may be formulated more efficiently than has previously been done, by exploiting the special structure of the optimal solution. Numerical tests indicate that this reformulation typically allows a reduction in the time required for problem solution by a factor of two to five.     

Solving two-stage stochastic programming problems with level decomposition

We propose a new variant of the two-stage recourse model. It can be used e.g., in managing resources in whose supply random interruptions may occur. Oil and natural gas are examples for such resources. Constraints in the resulting stochastic programming problems can be regarded as generalizations of integrated chance constraints. For the solution of such problems, we propose a new decomposition method that integrates a bundle-type convex programming method with the classic distribution approximation schemes. Feasibility and optimality issues are taken into consideration simultaneously, since we use a convex programming method suited for constrained optimization. This approach can also be applied to traditional two-stage problems whose recourse functions can be extended to the whole space in a computationally efficient way. Network recourse problems are an example for such problems. We report encouraging test results with the new method.      

Variational principles with integrands defined through a minimum

We revisit a systematic approach for the computation and analysis of the convex hull of non-convex integrands defined through the minimum of convex densities. It consists in reformulating the non-convex variational problem as a double minimization and exploiting appropriately the nature of optimality of the inner minimization. This requires gradient Young measures in the vector case, even if the initial problem was scalar, as the full problem is recast through the computation of a certain quasiconvexification. We illustrate this strategy by looking at two typical non-convex scalar problems. We hope to address vector problems in the near future.