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)