Bilevel optimization applied to strategic pricing in competitive electricity markets

In this paper, we present a bilevel programming formulation for the problem of strategic bidding under uncertainty in a wholesale energy market (WEM), where the economic remuneration of each generator depends on the ability of its own management to submit price and quantity bids. The leader of the bilevel problem consists of one among a group of competing generators and the follower is the electric system operator. The capability of the agent represented by the leader to affect the market price is considered by the model. We propose two solution approaches for this non-convex problem. The first one is a heuristic procedure whose efficiency is confirmed through comparisons with the optimal solutions for some instances of the problem. These optimal solutions are obtained by the second approach proposed, which consists of a mixed integer reformulation of the bilevel model. The heuristic proposed is also compared to standard solvers for nonlinearly constrained optimization problems. The application of the procedures is illustrated in case studies with configurations derived from the Brazilian power system.     

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.     

Constrained auction clearing in the Italian electricity market

Most of the liberalized electricity systems use the auction as a market model. The complexity of the underlying optimization formulation depends on the technical and regulatory constraints that must be considered. In Italy, the auction clearing should include not only congestion management limitations, but also a challenging regulatory constraint imposing that, while the zonal prices are allowed on the selling side, a uniform purchasing price has to be applied for all the zones of the Italian system. Such constraint introduces several complexities such as non-linearity and integrality. In this paper we discuss the modeling issues arising in the Italian context and we propose, in addition, a mechanism for the priority management of the offers/bids acceptance. We test the behavior of the models developed on a set of problems that represent all the possible scenarios that can be met in practice. The numerical results demonstrate the validity and the effectiveness of the proposed models.Received: May 2003 , Revised : November 2003, AMS classification: 90-20, 90C90     

Strategic bidding in continuous electricity auctions: an application to the Spanish electricity market

In this paper we introduce an asymmetric model of continuous electricity auctions with limited production capacity and bounded supply functions. The strategic bidding is studied with this model by means of an electricity market game. We prove that for every electricity market game with continuous cost functions a mixed-strategy Nash equilibrium always exists. In particular, we focus on the behavior of producers in the Spanish electricity market. We consider a very simple form for the Spanish electricity market: an oligopoly consisting just of independent hydro-electric power production units in a single wet period. We show that a pure-strategy Nash equilibrium for the Spanish electricity market game always exists.     

Global optimization of multilevel electricity market models including network design and graph partitioning

We consider the combination of a network design and graph partitioning model in a multilevel framework for determining the optimal network expansion and the optimal zonal configuration of zonal pricing electricity markets, which is an extension of the model discussed in Grimm et al. (2019) that does not include a network design problem. The two classical discrete optimization problems of network design and graph partitioning together with nonlinearities due to economic modeling yield extremely challenging mixed-integer nonlinear multilevel models for which we develop two problem-tailored solution techniques. The first approach relies on an equivalent bilevel formulation and a standard KKT transformation thereof including novel primal-dual bound tightening techniques, whereas the second is a tailored generalized Benders decomposition. For the latter, we strengthen the Benders cuts of Grimm et al. (2019) by using the structure of the newly introduced network design subproblem. We prove for both methods that they yield global optimal solutions. Afterward, we compare the approaches in a numerical study and show that the tailored Benders approach clearly outperforms the standard KKT transformation. Finally, we present a case study that illustrates the economic effects that are captured in our model.     

A new pricing scheme for a multi-period pool-based electricity auction

A new pricing scheme is proposed for determining the social welfare distribution in a centralized pool-based auction in the context of solving the unit commitment problems under competition. A significant contribution of this paper over previous publications on this subject is the inclusion of the price-responsive demand side for the multi-period auctions with dynamic commitment characteristics. The model allows every thermal unit and every consumer to obtain individual maximum profits, and at the same time it gives the market coordinator an adequate tool for solving the ensuing technologically constrained unit commitment problem with fair market clearing. The pricing model is in the form of a mixed linear programming model that minimizes the sum of the compensation costs. The accompanying case study illustrates the approach proposed.     

Electricity market clearing with improved scheduling of stochastic production

In this paper, we consider an electricity market that consists of a day-ahead and a balancing settlement, and includes a number of stochastic producers. We first introduce two reference procedures for scheduling and pricing energy in the day-ahead market: on the one hand, a conventional network-constrained auction purely based on the least-cost merit order, where stochastic generation enters with its expected production and a low marginal cost; on the other, a counterfactual auction that also accounts for the projected balancing costs using stochastic programming. Although the stochastic clearing procedure attains higher market efficiency in expectation than the conventional day-ahead auction, it suffers from fundamental drawbacks with a view to its practical implementation. In particular, it requires flexible producers (those that make up for the lack or surplus of stochastic generation) to accept losses in some scenarios. Using a bilevel programming framework, we then show that the conventional auction, if combined with a suitable day-ahead dispatch of stochastic producers (generally different from their expected production), can substantially increase market efficiency and emulate the advantageous features of the stochastic optimization ideal, while avoiding its major pitfalls.     

Modelling start-up costs of multiple technologies in electricity markets

This paper deals with the dispatch problem in providing electric power with minimal costs using different technologies. Initially, we describe this problem in terms of a linear program. This enables us to take generally neglected start-up costs into account. The main result is the explicit solution of a simplified linear program which provides us with a better understanding of the ‘start-up cost’ effects. Furthermore, we show that dominated technologies should be used in the case of limited availability of efficient technologies.      

Nash equilibrium in a pay-as-bid electricity market Part 2 - best response of a producer

We consider a multi-leader-common-follower model of a pay-as-bid electricity market in which the producers provide the regulator with either linear or quadratic bids. We prove that for a given producer only linear bids can maximize his profit. Such linear bids are referred as the ‘best response’ of the given producer. They are obtained assuming the demand is known and some estimate of the bids of the other producers is available. Nevertheless we also show that whenever no best response exists, the optimal profit can be asymptotically attained by a sequence of quadratic bids converging to the so-called ‘limiting best response’. An explicit formula for such a sequence is provided.     

Weekly self-scheduling,forward contracting,and pool involvement for an electricity producer. An adaptive robust optimization approach

This paper addresses the optimization under uncertainty of the self-scheduling, forward contracting, and pool involvement of an electricity producer operating a mixed power generation station, which combines thermal, hydro and wind sources, and uses a two stage adaptive robust optimization approach. In this problem the wind power production and the electricity pool price are considered to be uncertain, and are described by uncertainty convex sets. To solve this problem, two variants of a constraint generation algorithm are proposed, and their application and characteristics discussed. Both algorithms are used to solve two case studies based on two producers, each operating equivalent generation units, differing only in the thermal units’ characteristics. Their market strategies are investigated for three different scenarios, corresponding to as many instances of electricity price forecasts. The effect of the producers’ approach, whether conservative or more risk prone, is also investigated by solving each instance for multiple values of the so-called budget parameter. It was possible to conclude that this parameter influences markedly the producers’ strategy, in terms of scheduling, profit, forward contracting, and pool involvement. These findings are presented and analyzed in detail, and an attempted rationale is proposed to explain the less intuitive outcomes. Regarding the computational results, these show that for some instances, the two variants of the algorithms have a similar performance, while for a particular subset of them one variant has a clear superiority.     

A heuristic for the long-term electricity generation planning problem using the Bloom and Gallant formulation

Long-term power planning is a stochastic problem often confronted by electrical utilities in liberalized markets. One can model it for profit maximization—using market-price estimation functions for each interval—by posing it as a quadratic programming problem with some linear equalities and an exponential number of load-matching linear inequality constraints.     

A linear programming reformulation of the standard quadratic optimization problem

The problem of minimizing a quadratic form over the standard simplex is known as the standard quadratic optimization problem (SQO). It is NP-hard, and contains the maximum stable set problem in graphs as a special case. In this note, we show that the SQO problem may be reformulated as an (exponentially sized) linear program (LP). This reformulation also suggests a hierarchy of polynomial-time solvable LP’s whose optimal values converge finitely to the optimal value of the SQO problem. The hierarchies of LP relaxations from the literature do not share this finite convergence property for SQO, and we review the relevant counterexamples.     

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.     

Multistage stochastic portfolio optimisation in deregulated electricity markets using linear decision rules

The deregulation of electricity markets increases the financial risk faced by retailers who procure electric energy on the spot market to meet their customers’ electricity demand. To hedge against this exposure, retailers often hold a portfolio of electricity derivative contracts. In this paper, we propose a multistage stochastic mean-variance optimisation model for the management of such a portfolio. To reduce computational complexity, we apply two approximations: we aggregate the decision stages and solve the resulting problem in linear decision rules (LDR). The LDR approach consists of restricting the set of recourse decisions to those affine in the history of the random parameters. When applied to mean-variance optimisation models, it leads to convex quadratic programs. Since their size grows typically only polynomially with the number of periods, they can be efficiently solved. Our numerical experiments illustrate the value of adaptivity inherent in the LDR method and its potential for enabling scalability to problems with many periods.     

Dynamic pricing of electricity in retail markets

This paper aims at defining a dynamic and flexible tariff structure for a distribution company that protects the retail consumers against the excessive fluctuations of the wholesales market prices. We propose a two-stage pricing scheme that sets in a first-stage a time-of-use tariff that is corrected later by a dynamic component once the real-time demand has been observed. A personalized tariff scheme may be offered by a distribution company to each dynamic customer by allowing him to choose the appropriate robustness level expressed in terms of variability between the first and the second-stage decisions. The arising limited recourse model has been tested on realistic test problems, by using a slight modification of a recently proposed interior point solution framework.      

Implicit collusion and individual market power in electricity markets

Wholesale electricity markets may not produce competitive outcomes, either as a result of the exercise of market power, or through problems of implicit collusion. In comparison with the great amount of attention paid to issues of market power, the problems of implicit collusion have not been extensively studied. In this paper, we use a coevolutionary approach to explore the effect of the price elasticity of demand, capacity and forward contracts on implicit collusion in a duopoly. We will demonstrate that implicit collusion has the most importance in market conditions under which there is an intermediate amount of market power. Thus markets which are either highly competitive or in which one or both of the two generators can exercise considerable market power, are also markets in which implicitly collusive outcomes are less likely to arise.     

Inverse optimization for linearly constrained convex separable programming problems

In this paper, we study inverse optimization for linearly constrained convex separable programming problems that have wide applications in industrial and managerial areas. For a given feasible point of a convex separable program, the inverse optimization is to determine whether the feasible point can be made optimal by adjusting the parameter values in the problem, and when the answer is positive, find the parameter values that have the smallest adjustments. A sufficient and necessary condition is given for a feasible point to be able to become optimal by adjusting parameter values. Inverse optimization formulations are presented with ℓ₁ and ℓ₂ norms. These inverse optimization problems are either linear programming when ℓ₁ norm is used in the formulation, or convex quadratic separable programming when ℓ₂ norm is used.     

Connectivity-and-hop-constrained design of electricity distribution networks

This paper addresses the problem of designing the configuration of an interconnected electricity distribution network, so as to maximize the minimum power margin over the feeders. In addition to the limitation of feeder power capacity, the distance (as hop count) between any customer and its allocated feeder is also limited for preventing power losses and voltage drops. Feasibility conditions are studied and a complexity analysis is performed before introducing a heuristic algorithm and two integer linear programming formulations for addressing the problem. A cutting-plane algorithm relying on the generation of two classes of cuts for enforcing connectivity and distance requirements respectively is proposed for solving the second integer linear programming formulation. All the approaches are then compared on a set of 190 instances before discussing their performances.     

An optimization heuristic for the berth scheduling problem

Berths are among the most important resources in a port. In this research we present an optimization-based approach for the berth scheduling problem, which is to determine the berthing time and space for each incoming ship. The neighborhood-search based heuristic treats the quay as a continuous space. In additional to basic physical requirements, this model takes several factors important in practice into consideration, including the first-come-first-served rule, clearance distance between ships, and possibility of ship shifting. Computational experience is provided.     

The optimization problem over a distributive lattice

In this paper we give a necessary and sufficient condition for existence of minimal solution(s) of the linear system A * X ≥ b where A, b are fixed matrices and X is an unknown matrix over a lattice. Next, an algorithm which finds these minimal solutions over a distributive lattice is given. Finally, we find an optimal solution for the optimization problem min {Z = C * X | A * X ≥ b} where C is the given matrix of coefficients of objective function Z. This research was completed while the author was a visitor of the Center for Informatics and Applied Optimization, University of Ballarat, Ballarat, Australia.