=Paper=
{{Paper
|id=Vol-1623/paperme3
|storemode=property
|title=An Investigation of a Bilevel Energy Market Model
|pdfUrl=https://ceur-ws.org/Vol-1623/paperme3.pdf
|volume=Vol-1623
|authors=Nadezhda Dresvyanskaya
|dblpUrl=https://dblp.org/rec/conf/door/Dresvyanskaya16
}}
==An Investigation of a Bilevel Energy Market Model==
https://ceur-ws.org/Vol-1623/paperme3.pdf
An Investigation of a Bilevel Energy
Market Model
Nadezhda V. Dresvyanskaya
Melentiev Energy System Institute SB RAS,
Lermontov st., 130, Irkutsk, Russia, 664033
nadyadresvyanskaya@gmail.com
Abstract. The two-level model of interaction between power producers (GC)
and System Operator (SO) is considered. The upper level corresponds to GC
which try to increase their profit by distortion information about the character-
istics operating costs of their power plants. The lower level corresponds to SO
which solves the generation scheduling problem on the basis of technical param-
eters of the power plants provided by the producers. SO is aimed at minimizing
total production costs in Electric Power System (EPS). Two formulations of this
model are considered. In the first case the bounds on generation and capacities
of lines are considered insignificant. For this case we study properties of the
objective function of the upper level and investigate the existence of the Nash
equilibrium. In the second case we will take into account additional bounds on
the power generation and power flows. In this case the standard replacement
of the lower level problem by the Karush-Kuhn-Tucker (KKT) optimality con-
ditions is proposed. In this paper, we present a simple numerical example to
validate the proposed approach and demonstrate its main features.
Keywords: Electricity market, bilevel optimization, Nash equilibrium, nonco-
operative game, mixed-integer quadratic programming.
1 Introduction
A lot of investigations are devoted to research of the electricity market. Today an
actual task is study of interaction between System Operator and power producers [1].
Producers in the electricity market are Generation Companies (GC).
Power producers provide their costs to the System Operator in the market condi-
tions. SO solves a generation scheduling problem, minimizing total costs of electricity
generation and calculating the nodal prices (dual variables) on the basis of technical pa-
rameters of the power plants provided by the producers. To increase their profit power
producers deliberately distort real values of some technical parameters of the power
plants thereby implicitly influencing the prices. This interaction between SO and GC
can be modeled using a two-level mathematical programming problems [2, 3]. Earlier
the bilevel programming technique was used for modeling the heat energy market [4].
Copyright c by the paper’s authors. Copying permitted for private and academic purposes.
In: A. Kononov et al. (eds.): DOOR 2016, Vladivostok, Russia, published at http://ceur-ws.org
564 N.V. Dresvyanskaya
The two-level model of interaction between System Operator and producers is con-
sidered in this paper. The upper level corresponds to the profit maximization of Gener-
ation Companies with true costs functions. The lower level of the problem corresponds
to SO efforts to schedule generation and calculate local marginal prices (LMP) on
the basis of total production costs minimization. On the upper level there are several
GC, each seeks to maximize its own profits, therefore on the upper level there is the
equilibrium search problem.
In the considered model the limits on generation and capacities of lines are consid-
ered insignificant. For this case we research properties of the objective function of the
upper level and prove the existence of the Nash equilibrium.
This paper presents a numerical example demonstrating the applicability of the
proposed approach to the solution of the considered problem.
2 Problem formulation
The Electric Power System (EPS), consisting of n nodes and m lines is considered [1,
5]. We assume that the first k (k < n) nodes are power producers and the others (n−k)
are consumers. Each power producer operates one power plant.
The network topology is given by the incidence n × m matrix A with entries
−1, if line j enters node i,
aij = 0, if line j is not connected to node i,
1, if line j leaves node i.
The power flows must satisfy Kirchhoff’s first law
Ax = b,
where xj is power flow on the line j, bi ≥ 0 is power generation for i = 1, k and power
demand (in this case bi ≤ 0) for i = k + 1, n. Note that matrix A has the following
property: if λT A = 0, then λ1 = λ2 = . . . = λn .
In this paper the demand is inelastic, i.e. bi = const, i = k + 1, n.
Generation of power producers is determined by quadratic costs function
ci (bi ) = αi b2i + βi bi + γi , i = 1, k, (1)
where αi > 0, βi > 0, γi > 0.
System Operator solves the convex quadratic programming problem
k
X k
X
ci (bi ) = αi b2i + βi bi + γi → min , (2)
(x,b1 ,...,bk )
i=1 i=1
Ax = b. (3)
Constraints (3) are always consistent, the objective function in (2) is strictly convex.
This provides unique solution in variables b1 , . . . , bk .
An Investigation of a Bilevel Energy Market Model 565
In (2) the total production costs in the EPS is considered. Solving this problem,
SO determines the Lagrange multipliers associated with the constraints (3), which act
as nodal equilibrium prices, and determines the amounts of generation for each power
producer. Further on the basis of these data power producers define their own profit.
Such pricing system is aimed only to meet the demand with minimum costs and
completely ignores the interests of producers. GC are aimed at maximizing their profits
in market conditions. The minimum total production costs in the EPS is not the
objective for them.
In this situation power producers deliberately distort real values of some technical
parameters of the power plants. This means that parameter values αi , βi , γi in (2),
reported to the SO, can be deliberately changed by power producers and may differ
from the true values α̂i , β̂i , γ̂i for the purpose of maximizing the profit with prices and
amounts of generation, determined after the solution of the problem (2)-(3).
In this paper it is assumed that αi = α̂i , γ = γ̂i , i.e. we study the impact of
parameters βi on GC profit. The problem of existence and finding the Nash equilibrium
between GC is investigated. Therefore variable parameters βi are used in problem
formulation of SO, and for calculating producer’s costs we use true values β̂i .
3 Search for the Nash equilibrium
To solve the problem (2)-(3), in which αi = α̂i , γ = γ̂i and vector β = (β1 , . . . , βk )T is
external parameter, we use the method of Lagrange multipliers. The Lagrange function
has the form
k
X
L(b, x, λ) = α̂i b2i + βi bi + γ̂i + λT (Ax − b).
i=1
Calculate the partial derivatives and equal them to zero:
∂L
= 2α̂i bi + βi − λi = 0, i = 1, k (4)
∂bi
!T
∂L ∂L
Lx = AT λ = 0, Lx = ,..., . (5)
∂x1 ∂xm
Using the property of matrix incidence A, from (5) we obtain, that all prices λi are
equal to the same price, which we denote by p,
λ1 = λ2 = . . . = λn = p. (6)
Thus, from (4) and (6) we have
2α̂i bi + βi = p. (7)
Note that the value of 2α̂i bi + βi is the value of marginal costs of power producer
i, because c0i (bi ) = 2α̂i bi + βi . Therefore in optimal solution all power producers facing
the same level of marginal costs, which is equal to the established price.
566 N.V. Dresvyanskaya
Thus in the model all calculations are performed assuming a uniform price deter-
mined by GC’s current costs.
Now we describe the profit for power producer i as a function of the zero marginal
costs βi = c0i (0). We assume, that in practice the impact of parameter βi on profit is
more significant.
As noted above the main aim of power producer is to maximize profit
p∗ (β)b∗i (β) − α̂i b∗i (β)2 − β̂i b∗i (β) − γ̂i → max,
βi
where p∗ (β) and b∗i (β) are the corresponding to a given parameter vector β optimal
values of the dual and primal variables, obtained after solving the problem (2)-(3).
Profit functions of power producers
πi (β) = p∗ (β)b∗i (β) − α̂i b∗i (β)2 + β̂i b∗i (β) + γ̂i , i = 1, k, (8)
we rewrite in a form suitable for the further analysis.
From (7) we obtain
(2α̂i bi + βi )bi − α̂i b2i − β̂i bi − γ̂i = α̂i b2i + βi bi − β̂i bi − γ̂i ,
where β̂i is real zero costs of power producer i.
Since A is matrix incidence, then, summing all the equations of the system (3), we
obtain the equation
X n
0= bi
i=1
or
b1 + b2 + . . . + bk = |bk+1 | + . . . + |bn | = bT , (9)
where bT is total power demand.
From (7) and (9) we derive
1P k β
i
bT + 2
i=1 α̂i
∗
p (β) = 2 (10)
k 1
P
i=1 α̂i
and
k β −β
P i q
2bT +
i=1 α̂i 1
b∗q (β) = · . (11)
Pk 1 2α̂q
i=1 α̂i
Note that increase parameter βi involves increase p∗ (β).
Analytical expression of profit functions as functions of parameters β turns out
substitution of expressions (10) and (11) in (8) and has the form
πq (β) = Kq βq2 + ξq (β), q = 1, k, (12)
An Investigation of a Bilevel Energy Market Model 567
where ξq (β) = ξq (β1 , . . . , βk ) is affine function relatively to βq , Kq is constant, defined
below. As will be seen from further analysis, there is no need to explicitly write the
view functions ξq (β), moreover, this functions have a bulky appearance.
Let us make some remarks. We obtained analytical problem solution for SO (the
lower level problem) and substituted this solution in objective functions of the upper
level problems thus excluded the lower level problem from further consideration. As a
result, we received non-cooperative k-person game with profit functions (12). It should
be noted that the profit of power producer q depends not only on its own zero marginal
costs, but also zero marginal costs other power producers. Besides, the increase of
its own costs (parameter βq ) will reduce its own production, and thus, will lead to
production increase of other power producers.
It is known that some games allow the reduction to optimization problem [6]. Such
games are called potential and finding Nash equilibrium for them is significantly facil-
itated. The majority of practically interesting games are not potential and this is an
obstacle to develop computational procedures, guaranteed determine the equilibrium
point.
Lemma 1 ([7]). The non-cooperative k-person game with profit functions (12) is not
potential.
Proof. The proof of this lemma can be found in [7].
We prove existence of the Nash equilibrium in this game.
Lemma 2 ([7]). The values Kq < 0 ∀q = 1, k.
Proof. By simple mathematical reformulation we get
!2
k 1
α̂q2
P
−1
1 i=1 α̂i
Kq = − · !2 =
4 Pk 1
α̂q3
i=1 α̂i
!2 !2
k α̂ k α̂
P q P q
− 1 1+ − 1
1 α̂
i=1 i
1 α̂
i6=q i
=− !2 = − !2 < 0.
4 Pk 1 4 Pk 1
α̂q3 α̂q3
i=1 α̂i i=1 α̂i
Therefore each function πq (β) is concave in βq . We can assume that the parameters
βi vary within some reasonable limits: βi ∈ [0, β], β = const > 0. Then the set of strat-
egy in our game is convex and compact. These conditions [8] guarantee the existence
of the Nash equilibrium.
To find equilibrium we find partial derivatives
∂πq ∂p ∂bq ∂bq
= · bq + β q · − β̂q · . (13)
∂βq ∂βq ∂βq ∂βq
568 N.V. Dresvyanskaya
Pk 1
Denote σ = , then
i=1 α̂i
" #
∂p 1 ∂bq 1 1
= , = −1 .
∂βq α̂q σ ∂βq 2α̂q α̂q σ
Substitute the found partial derivatives in (13) and equate the received expression
to zero.
" #
∂πq 1 1 1 1
= · p − βq · − β̂q · − 1 = 0.
∂βq 2α̂q2 σ 2α̂q 2α̂q α̂q σ
After standard reformulation we obtain
k
" #
X βi 2 21
2bT + − βq α̂q σ = β̂q α̂q σ · −1 .
α̂
i=1 i
α̂q σ
As a result, finding the equilibrium is reduced to the solution system of linear
equations of the following form:
k
" #
X βi 2 2 1
− βq α̂q σ = β̂q α̂q σ · − 1 − 2bT . (14)
α̂
i=1 i
α̂q σ
In vector-matrix form equation (14) can be written as follows:
Dβ = r, (15)
where
1 2
1 1
α̂ − α̂ 1 σ · · ·
1 α̂2 α̂k
1 1 2
1 " #
− α̂2 σ · · ·
2 1
D=
α̂1 α̂2 α̂k , r = β̂q α̂q σ ·
− 1 − 2bT .
.. .. . . .. α̂q σ
. . . .
1 1 1 2
··· − α̂k σ
α̂1 α̂2 α̂k
Lemma 3 ([7]). If k > 1 then matrix D−1 exists and all its elements are negative.
Proof. The complete proof can be found in [7].
Lemma 4 ([7]). The elements of the vector r are negative.
Theorem 1. If k > 1 then the solution β ∗ of the system (15) exists and is unique, the
components of the vector β ∗ are positive and
1 1
1
α̂ · · · 0 α̂3 · · · 2 r1
1 1 α̂1 α̂k
1 1 .. r2 .
β ∗ = − 2 ... . . . ... +
.. . .
. . . .
σ ..
k 1
P
1 σ2 − 2
1 1
0 ··· i=1 α̂i ··· rk
α̂k α̂k α̂12 α̂k3
An Investigation of a Bilevel Energy Market Model 569
Proof. The proof follows from the two last lemmas.
The existence of the Nash equilibrium under assumption of bounded parameters βi
variation was proved above. As follows from this theorem, there is no need to set upper
bounds on βi . It is possible even to admit also the negative values of these parameters,
still the equilibrium is achieved at the interior point of non-negative orthant, which
corresponds to the practical interpretation of βi .
4 The two-level problem formulation with constraints on the
power generation and power flows
In this section we will take into account additional bounds on x and b. Consider first the
problem with one power producer. Without loss of generality, assume that the power
producer is in node 1. The problem of the System Operator
α̂1 b21 + β1 b1 + γ̂1 → min,
(x,b)
A1 x = d1 − b1 ,
Ai x = di , i = 2, n,
where A is the incidence matrix, Ai are the rows of matrix A, d is demand. It’s obvious
that
Xn
b∗1 = bT = di . (16)
i=1
Thus the optimization is carried out only in the variable x. From the optimality con-
ditions obtain
λ∗1 = 2α̂1 bT + β1 = λ∗2 = λ∗3 = . . . = λ∗n . (17)
The power producer’s profit subject to (16)-(17)
λ∗1 b∗1 − (α̂1 (b∗1 )2 + β̂1 b∗1 + γ̂1 ) = (2α̂1 bT + β1 )bT − (α̂1 b2T + β̂1 bT + γ̂1 )
is linear, increasing relative to β1 function. Therefore under the constraints
0 6 β1 6 β 1
profit reaches its maximum at the right end of the segment: β1∗ = β 1 .
Let us pass now to the general statement. The problem of the System Operator
n
X
(α̂i b2i + βi bi + γ̂i ) → min, (18)
(x,b)
i=1
Ax = d − b, (19)
x 6 x 6 x, (20)
0 6 b 6 b. (21)
570 N.V. Dresvyanskaya
The Lagrange function
n
X
L(b, x, λ, µ1 , µ2 , η 1 , η 2 ) = (α̂i b2i + βi bi + γ̂i )+
i=1
n
X m
X m
X m
X
+ λi (di − bi − aij xj ) − µ1j (xj − xj ) + µ2j (xj − xj )−
i=1 j=1 j=1 j=1
n
X Xn
− ηi1 bi + ηi2 (bi − bi ).
i=1 i=1
The optimality conditions represent the stationarity conditions, conditions of com-
plementary slackness, constraints on the sign of the dual variables corresponding to
inequality constraints:
∂L
= 2α̂k bk + βk − λk − ηk1 + ηk2 = 0, k = 1, n, (22)
∂bk
n
∂L X
=− λi ais − µ1s + µ2s = 0, s = 1, m, (23)
∂xs i=1
µ1j (xj − xj ) = 0, µ2j (xj − xj ) = 0, j = 1, m, (24)
ηi1 bi = 0, ηi2 (bi − bi ) = 0, i = 1, n, (25)
µ1j > 0, µ2j > 0, j = 1, m, (26)
ηi1 > 0, ηi2 > 0, i = 1, n, (27)
supplemented by the conditions (19)-(21).
If in some nodes there are no power producers then we set αi = βi = 0 and bi = 0
for these nodes.
Now interaction between GC and SO is formulated as the bilevel problem with GC
at the first level and SO at the second. We replace the lower level by the system of
necessary optimality conditions (19)-(27) obtaining the one-level nonconvex problem.
It is known [9, 10] that the nonlinear constraints of the form
wv = 0, w > 0, v > 0
can be rewritten in the form of linear constraints by introducing an additional Boolean
variable ϑ as follows:
w 6 M ϑ, v 6 M (1 − ϑ), w > 0, v > 0.
An Investigation of a Bilevel Energy Market Model 571
Let M be a sufficiently large constant. In the example below M = 106 . Introduce the
following Boolean variables: ζj1 , ζj2 , ζi3 , ζi4 . Then the constraints (24)-(27) are equivalent
µ1j 6 M ζj1 , (xj − xj ) 6 M (1 − ζj1 ),
µ2j 6 M ζj2 , (xj − xj ) 6 M (1 − ζj2 ),
ηi1 6 M ζi3 , bi 6 M (1 − ζi3 ),
ηi2 6 M ζi4 , (bi − bi ) 6 M (1 − ζi4 ),
µ1j > 0, µ2j > 0, ηi1 > 0, ηi2 > 0,
ζj1 ∈ {0, 1}, ζj2 ∈ {0, 1}, ζi3 ∈ {0, 1}, ζi4 ∈ {0, 1}.
After the introduction of additional variables and replace the constraints an equiva-
lent mixed-integer quadratic programming problem is obtained. To solve the problems
of this class the solver CPLEX can be used.
The solution of this problem are variables of upper level and lower level problems.
Optimization in a one-level problem is carried out on all variables: (bi , xj , λi , βi , µ1j ,
µ2j , ηi1 , ηi2 , ζj1 , ζj2 , ζi3 , ζi4 ).
5 Numerical example
Consider the Electric Power System, consisting of two producers and two consumers.
Initial data are given in Table 1.
Table 1. Initial data for the EPS nodes and lines
Node Costs functions Demand Generation Line Flow limits,
limits MW
1 c1 (b1 ) = 0.1b21 + 80b1 85 30-500 1 0-260
2 c2 (b2 ) = 0.09b21 +100b2 - 50-300 2 0-320
3 - 412.4 - 3 -
The results of the calculation with β1 = 80, β2 = 100 are shown in Table 2. Power
producers gain profits π1 = 8 308.35 and π2 = 3 937.23.
Table 2. The results of the calculation with exact characteristics of costs
Node bi Prices Line xj
1 288.24 137.65 1 203.24
2 209.16 137.65 2 -
3 - - 3 412.40
Table 3 shows the solution obtained under the assumption that producers distort
information about the characteristics operating costs of their power plants. Producers
gain profits π1 = 20 147.40 and π2 = 12 306.44.
572 N.V. Dresvyanskaya
Table 3. The results of the calculation with distorted characteristics of costs
Node bi βi Prices Line xj
1 291.40 120.00 178.28 1 206.40
2 206.00 141.20 178.28 2 -
3 - - - 3 412.40
The results of numerical example demonstrate the effect achieved by power pro-
ducers due to distortion information about the characteristics operating costs of their
power plants. Producers increase the level of market prices by changing βi . The prices
increase provide producers the opportunity to obtain additional profit.
6 Conclusion
The electricity market model of interaction between power producers (GC) and System
Operator (SO) was considered. This model is formulated as two-level mathematical
programming problem. Thus on the upper level GC maximizes its own profits due
to the distortion of technical parameters of the power plants, transmitted SO. Two
formulations of this model are considered. In the first one the bounds on generation
and capacities of lines are considered insignificant. For this case we prove the existence
of the Nash equilibrium. The equilibrium is unique and is achieved at the interior point
of non-negative orthant. In the second one the model takes into account additional
bounds on the power generation and power flows. For this case the equivalent one-level
mixed-integer quadratic programming problem is proposed.
References
1. Nechaev, I.A.: Power plant generation scheduling in the wholesale electricity market en-
vironment (in Russian). Izvestiya Akademii Nauk. Energetika. 6, 71–84 (2011)
2. Bard, J.F.: Practical bilevel optimization: Algorithms and applications. Kluwer Academie
Publishers, Dordrecht (1998)
3. Dempe, S.: Foundations of Bilevel Programming. Kluwer Academie Publishers, Dordrecht
(2002)
4. Stennikov, V.A., Khamisov, O.V., Pen’kovskii, A.V.: Optimizing the heat market on the
basis of a two-level approach. Thermal Engineering. 58(12), 1043–1048 (2011)
5. Palamarchuk, S.I.: Bilateral contract scheduling for electricity delivery in the competitive
wholesale market (in Russian). Izvestiya Akademii Nauk. Energetika. 2, 77–91 (2011)
6. Monderer, D., Shapley, L.S.: Potential Games. Games and Economic Behavior. 14, 124–
143 (1996)
7. Dresvyanskaya, N.V.: The Analysis of the Behavior of Generators in the Two-Level Market
Model of Functioning of the EPS (in Russian). Izvestiya Irkutskogo Gosudarstvennogo
Universiteta. Series Mathematics. 16, 43–57 (2016)
8. Nikaido, H., Isoda, K.: Note on Noncooperative Convex Games. Pacific Journal of Math-
ematics. 5(5), 807–815 (1955)
9. Korbut, A.A., Finkelstein, Y.Yu.: Discrete programming (in Russian). Nauka, Moscow
(1969)
An Investigation of a Bilevel Energy Market Model 573
10. Audet, C., Hansen, P., Jaumard, B., Savard, G.: Links between linear bilevel and mixed 0-
1 programming problems. Journal of Optimization Theory and Applications. 93, 273–300
(1997)