1

Strategic Bidding for Producers in Nodal Electricity
Markets: A Convex Relaxation Approach

arXiv:1606.05979v1 [math.OC] 20 Jun 2016

Mahdi Ghamkhari, Student Member, IEEE, Ashkan Sadeghi-Mobarakeh, Student Member, IEEE
and Hamed Mohsenian-Rad, Senior Member, IEEE

Abstract—Strategic bidding problems in electricity markets
are widely studied in power systems, often by formulating
complex bi-level optimization problems that are hard to solve.
The state-of-the-art approach to solve such problems is to
reformulate them as mixed-integer linear programs (MILPs).
However, the computational time of such MILP reformulations
grows dramatically, once the network size increases, scheduling
horizon increases, or randomness is taken into consideration.
In this paper, we take a fundamentally different approach and
propose effective and customized convex programming tools
to solve the strategic bidding problem for producers in nodal
electricity markets. Our approach is inspired by the Schmudgen’s
Positivstellensatz Theorem in semi-algebraic geometry; but then
we go through several steps based upon both convex optimization
and mixed-integer programming that results in obtaining close
to optimal bidding solutions, as evidenced by several numerical
case studies, besides having a huge advantage on reducing
computation time. While the computation time of the state-ofthe-art MILP approach grows exponentially when we increase
the scheduling horizon or the number of random scenarios, the
computation time of our approach increases rather linearly.
Keywords: Nodal electricity market, strategic bidding, equilibrium constraints, convex optimization, computation time.

R, R+
S
N
D
G
S
L
k
[t]
T
K
PG
PD
θ
λ
σ, δ, ζ,
ξ, φ, ψ
A
BG
BD
BS
V

N OMENCLATURE
Set of real and non-negative real numbers
Set of symmetric matrices
Set of nodes in power grid in arbitrary order
Set of demand nodes in ascending order
Set of generation nodes in ascending order
Subset of strategic generation nodes in set G
Set of transmission lines, in arbitrary order
Index for random scenarios
Hourly time slots
Number of hourly time slots
Number of random scenarios
Vector of power generations
Vector of demands
Vector of phase angels of power grid
Vector of locational marginal prices
Vectors of dual variables corresponding
to inequalities in economic dispatch problem
Bus-line incidence matrix
Generator-bus incidence matrix
Demand-bus incidence matrix
Strategic generators to generators incidence matrix
Diagonal matrix of transmission lines reactance

The authors are with the Department of Electrical Engineering, University of California, Riverside, CA, USA, e-mails: {ghamkhari, asade004,
hamed}@ee.ucr.edu. This work was supported by NSF grants 1253516,
1307756, and 1319798. The corresponding author is H. Mohsenian-Rad.

a
b
c
C
PGmin , PGmax
min
max
PD
, PD
Γ
0
x
n
F, Q
f, p, v, q, d
r, O, x̄
∗
Rank(·)
(·)T
tr(·)

i, j
z
m
l
el

Vector of energy price bid of generators
Vector of demand price bid of loads
Vector of cost parameter of strategic generators
Vector of line capacities
Vector of minimum and maximum generation
Vector of minimum and maximum demand
Ramp constraint parameter
A column vector or a matrix with zero entries
Column vector of all variables in (21)
Length of the vector x
Symmetric matrices of parameters in Sn
Vectors of parameters in Rn
Defined in (32)
Point-wise production of two vectors
Rank of a matrix
Transpose of a vector or a matrix
Trace of a matrix
Matrix inequality
Indices for I linear inequalities in (23), i, j ≤ I
Index for Z quadratic equalities in (23), z ≤ Z
Index for M linear equalities in (23), m ≤ M
Index for n elements of a vector in Rn , l ≤ n
lth element of the standard basis for Rn space
I. I NTRODUCTION

Strategic bidding plays a central role in wholesale electricity
markets, where market participants seek to choose their bids
to the day-ahead and/or real-time markets so as to maximize
their profits. Strategic bidding in electricity markets has been
extensively studied previously, e.g., for producers [1]–[4],
consumers [5]–[7], and energy storage units [8]–[10].
The literature on strategic bidding is often categorized based
on whether the market participant is small and price-taker
[6], [8], [11], or large and price-maker [1]–[5], [7], [9], [10].
The focus in this paper is on the latter, where the details on
how the market operates are explicitly considered in formulating the strategic bidding problem. Accordingly, the strategic
bidding problem is formulated as a bi-level program, where
the lower level problem constitutes the economic dispatch
problem that is solved by the independent system operator
(ISO) in order to minimize the cost of electricity dispatch and
to set the market prices. Following the common approach in
the electricity market literature, the strategic bidding problem
is then reformulated as a single mathematical program with
equilibrium constraints (MPEC), see [1], [12]–[14].
A wholesale market offering strategy is proposed in [13] for
a wind power producer with market power, which participates
in the day-ahead market as a price-maker, and in the balancing

2

market as a deviator. Optimal bidding for a large consumer is
formulated in [15] as an MPEC problem. MPEC formulation
is also used in [14] for optimal strategic bidding of a regulation resource in the performance-based regulation market
considering the system dynamics. The preventive maintenance
scheduling of power transmission lines within a yearly time
framework using a bi-level optimization approach was studied
in [16]. In [17], a vulnerability analysis of an electric grid
under disruptive threat is formulated as a bi-level optimization.
Finally, in [12], strategic gaming in electricity markets was
analyzed using an MPEC formulation.
The MPEC problem formulations that appear in power
systems are often difficult to solve. The difficulty arises due
to the necessary use of bilinear terms that create non-convex
objective function and constraints. The common approach to
solve such problems is to transform them into mixed integer
linear programs (MILPs), e.g., see [1]–[3], [7], [9], [10].
While the MILP reformulations of strategic-bidding problems are popular in the power systems community, such
reformulations are prone to major computational challenges.
Specifically, the computational time often increases dramatically, once the network size grows, scheduling horizon increases, or randomness is taken into consideration. For example, for one of our case studies with 10 random scenarios, the
MILP approach in [1] did not converge even after letting it
run for about three days, see Section V-B for details.
To tackle the aformentioned computational challenges, some
attempts with little success have been made recently to solve
the strategic bidding problems in power systems using convex
optimization techniques. In particular, in [18] and [19], the
authors used semidefinite relaxation and lift-and-project linear
relaxation to solve the MPEC problems in electricity markets.
However, in both cases, the performance was often poor
with respect to not only optimality but also computation
time. Moreover, no clear recovery method was proposed to
guarantee obtaining a feasible solution of the original MPEC
problem. Finally, only small MPEC problems were discussed.
Therefore, to the best of our knowledge, it is fair to say that
solving the strategic bidding problems in wholesale electricity
markets using convex programming is still an open problem
and no reliable and scalable solution approach currently exists
to address the relatively large and hence practically relevant
problems. Accordingly, our goal in this paper is to tackle this
open problem. Without loss of generality, we focus on the
case of strategic bidding for producers. The main technical
contributions in this paper can be summarized as follows:
•

•

We take a fundamentally different approach from [1]–
[3] and [18], [19], and propose innovative and effective
convex programming tools to solve the strategic bidding
problem for producers in nodal electricity markets, where
our approach is customized to exploit the main characteristics of such problems. Our proposed solution method
is accurate, reliable, and computationally tractable in
solving the strategic bidding problems in power systems.
Our approach is initially inspired by the Schmudgen’s
Positivstellensatz Theorem [20, Theorem 3.16] [21, Section 4.3] in semi-algebraic geometry; but then we go

through several steps based upon both convex optimization and mixed-integer programming in order to develop
an algorithm, Algorithm 1, that is guaranteed to give a
feasible and very close-to-optimal solution to the original
MPEC problem, besides having a huge advantage on
reducing computation time.
• We compare the optimality and the computation time of
our proposed approach and that of the MILP approach in
[1] for the case of a market over the IEEE 30 bus test system. While the computation time of the MILP approach
in [1] increases exponentially when we increase the
scheduling horizon or the number of random scenarios,
the computation time of our proposed approach increases
rather linearly. Interestingly, the average optimality of the
solution from our proposed approach is 99% or higher.
It is worth pointing out that the state-of-the-art polynomial
optimization problem relaxations that are formulated based
on Schmudgen’s Positivestellensatz [20, Theorem 3.16] and
Lasserre’s sum-of-squares [22], [23] tend to provide tight
upper bounds for the intended non-convex optimization problems only when we significantly increase the order of added
coefficients or polynomials. Accordingly, in both cases, we
often face convex but very large optimization problems for
any descent size problem, which makes the resulting convex
relaxation approach of little interest in practice. In contrast,
in this paper, we use Schmudgen’s Positivestellensatz but not
Lasserre’s sum-of-squares method, because we are able to
build upon it a new methodology, combined with a heuristic
algorithm, which results in obtaining very close to optimal
bidding solutions within a reasonable computational time.
The proposed approach in this paper can be applied to
the other MPEC problems in electricity markets, e.g., to find
optimal bids for large energy storage units [9], or to tackle the
strategic generation investment problem for producers [2].
II. P ROBLEM S TATEMENT
Consider a strategic price-maker generation firm that bids
in a day-ahead nodal electricity market. Once the bids from all
market participants are collected, the ISO solves an economic
dispatch problem, which is presented below in vector-format,
in order to determine the clearing market price and the energy
reward to each producer [24, Appendix C], [25]:
minimize aT PG − bT PD
PG ,PD ,θ

(1)

subject to
BG PG − BD PD − AV −1 AT θ = 0 : λ
PG −
PGmax

PGmin

(2)

≥0:σ

(3)

− PG ≥ 0 : δ

(4)

min
PD

PD −
≥0:ζ
max
PD − PD ≥ 0 : ξ

(5)
(6)

V −1 AT θ + C ≥ 0 : φ

(7)

C − V −1 AT θ ≥ 0 : ψ,

(8)

where the notations are explained in the Nomenclature. The
vector of power flows on all transmission lines is modeled here

3

as V −1 AT θ. The variable after each colon in (2)-(8) shows the
dual variable corresponding to each constraint. Constraint (2)
enforces the power balance and its dual variable is the market
clearing price. Constraints (3)-(6) enforce the generations and
loads to operate within their limits. Furthermore, constraints
(7)-(8) enforce the capacity for transmission lines.
Note that, for the ease of discussions, the problem formulation in (1)-(8) is for economic bidding over a single hour.
The case for multiple hours is discussed later in Section IV.

δ ≥ 0, ξ ≥ 0, ψ ≥ 0

(19)

σ ≥ 0, ζ ≥ 0, φ ≥ 0.

(20)

Once we replace the lower-level problem with its equivalent
KKT conditions, the bi-level strategic bidding problem in (9)
takes the form of a standard MPEC problem as follows:
maximize λT BG BS T BS PG − cT BS PG

BS a,PG ,PD ,φ
θ,λ,σ,δ,ζ,ξ,ψ

(21)

subject to (2) − (8) and (10) − (20).
A. Bi-level Problem Formulation
The bidding problem for the strategic generation firm of
interest can be formulated as a bi-level program [1], [2]:
maximize

λT BG BS T BS PG − cT BS PG

subject to



BS a,PG ,PD ,φ
θ,λ,σ,δ,ζ,ξ,ψ

PG ,PD
φ,θ,λ,σ
δ,ζ,ξ,ψ



= argmin

aT PG − bT PD

(9)

subject to (2) − (8).

The two terms in the objective function in (9) denote the total
generation revenue and the total generation cost for the strategic generation firm of interest, respectively. The upper-level
problem in (9) constitutes the profit maximization problem
that the strategic generation firm seeks to solve. The lowerlevel problem in (9) constitutes the economic dispatch problem
that the ISO must solve, before the profit of the generation
firm can be calculated at the upper-level problem. Note that,
the optimization variables in problem (9) include the vector of
price bids for strategic generators, which is represented here
as BS a, where BS ∈ R|S|×|G| is the incidence matrix for the
vector of strategic generators to the vector of all generators,
and a is the vector of price bids for all generators. The
elements of vector a that belong to the set of non-strategic
generators are taken as parameters in problem (9).
In formulating problem (9), we followed the same assumption as in [26, Section 4] and [27] in the sense that if there
exist multiple solutions for problem (1)-(8), then the solution
that is most profitable to the firm is considered.

The lower-level problem in (9) is a linear program. Therefore, its corresponding Karush-Kuhn-Tucker (KKT) optimality
conditions are both necessary and sufficient [28, Section 5.5.3].
They comprise (2)-(8), and the following constraints:
b − BG λ + ζ − ξ = 0

(10)
(11)

AV −1 (AT λ + ψ − φ) = 0

(12)

σ ∗ (PG − PGmin ) = 0
δ ∗ (PGmax − PG ) = 0

(13)
(14)

min
ζ ∗ (PD − PD
)=0

(15)

ξ∗

max
(PD

− PD ) = 0

φ ∗ (C + V −1 AT θ) = 0
ψ ∗ (C − V

−1

T

A θ) = 0

III. S OLUTION M ETHOD
A. Fundamental Convex Relaxation Approach
The common approach to solve problem (21) is to reformulate it as a mixed integer linear program, e.g., see [1]–[3],
[9]. However, the computation time of solving such MILP
reformulation grows exponentially as the size of problem
(21) increases [1]. Therefore, in this section, we present an
alternative approach to solve problem (21) based on convex
optimization, where computation time grows linearly. We
concatenated all the optimization variables in problem (21)
into a single optimization vector as follows:
T

T

T T T T T T T T T
x , [(BS a) PGT PD
λ σ δ ζ ξ φ ψ θ ] .

(22)

Let n denotes the length of vector x. First, we represent
problem (21) in its vector form as follows [28, Section 4.4]:

B. MPEC Problem Reformulation

a − BG λ − σ + δ = 0

Problem (21) is non-convex and hard to solve. Non-convexity
is due to the bilinear terms, both in the complimentary slackness constraints (13)-(18) and in the first term in the objective
function. For the rest of this paper, we seek to solve problem
(21) in an accurate yet computationally tractable fashion.
We assume that the economic dispatch problem in (1)-(8)
is always feasible [29], [30]. Note that, since this problem
is a linear program, it always satisfies the slater’s constraints
qualifications conditions [28, Section 5.2.3]. Therefore, there
always exists a solution for the KKT conditions of the economic dispatch problem. That is, the set of constraints in (2)(8) and (10)-(20) is always feasible. Therefore, the MPEC
problem in (21) always has a feasible solution.

(16)
(17)
(18)

maximize
x

xT F x + 2f T x

subject to pTi x + pi0 ≥ 0
T
vm
x + vm0 = 0

∀i
∀m

(23)

xT Qz x + 2qzT x = 0 ∀z,
where x ∈ Rn is the column vector of all decision variables in
problem (21). Here, F and f are derived from the objective
function in (9); pi and pi0 , ∀i, are derived from the linear
inequality constraints in (3)-(8), (19), (20); vm and vm0 , ∀m,
are derived from the linear equality constraints in (2), (10)(12); and Qz and qz , ∀z, are derived from the quadratic
equality constraints in (13)-(18). Since all quadratic equality
constraints are due to complimentary slackness, we can write
Qz = dz qzT

∀z,

(24)

4

where dz , ∀z, is derived from (13)-(18). We will use (24) later
in Section III-C. Problem (23) is always feasible, since it is a
reformulation of problem (21), see Section II-B.
Problem (23) is a quadratically-constrained quadratic program (QCQP). Following the analysis in [20, Theorem 3.16],
we propose the following relaxation of problem (23):
minimize
Λ,αi ,̺ij
βz ,hm ,hm0

Λ

tractable problem in its current form. Therefore, next, we
derive a tractable representation for problem (25).
Lemma 1: Building upon the fourth property of problem
(25) mentioned earlier, its constraint can be reformulated as
 T  
1
1
Υ
≥0
∀x ∈ Rn ,
(26)
x
x
where

subject to Λ − xT F x − 2f T x −

I
X

αi (pTi x + pi0 )−


 X 
pi0 pTi /2
−f T
−
αi
−
pi /2
0
−F
i


   T X
Z
I X
I
X
0 qzT
p
pj0
−
−
βz
̺ij i0
qz Qz
pi
pj



Λ
Υ,
−f

i=1

I
I X
X

̺ij (pTi x + pi0 )(pTj x + pj0 )−

i=1 j=1
M
X

T
(hTm x + hm0 )(vm
x + vm0 )−

m=1
Z
X
z=1

βz (xT Qz x + 2qzT x) ≥ 0

∀x ∈ Rn ,

(25)
where Λ ∈ R, αi ∈ R+ and ̺ij ∈ R+ ∀i and ∀j, βz ∈ R
∀z, hm ∈ Rn ∀m, and hm0 ∈ R ∀m. We shall point out four
key properties of problem (25). First, x in problem (25) is
neither an optimization variable nor a parameter. Instead, it is
an index vector. In fact, the single constraint in problem (25)
is a compact presentation for an infinite number of constraints,
where each constraint is indexed by one choice of x ∈ Rn .
Second, if we set the scalars ̺ij and the vectors hm to
zero, then problem (25) reduces to the standard Lagrange
dual problem associated with problem (23), see [28, Section
5.2]. In that sense, problem (25) can be seen as a generalized
dual problem for primal problem (23), where the Lagrange
multipliers corresponding to the linear inequality and linear
equality constraints are affine rather than scalar [20]. Third, the
second line in (25) involves multiplying every linear inequality
constraint by itself and every other linear inequality constraint.
Fourth, the expression on the left hand side in the inequality
constraints in (25) is a quadratic function of index vector x.
Problem (25) is a relaxation of problem (23), because any
Λ that satisfies the constraints in problem (25) gives an upper
bound for the optimal objective value of the maximization in
(23). In that sense, problem (25) seeks to find the lowest, i.e.,
the best, such upper bound [21, Section 4.3]. The difference
between the provided upper bound from (25) and the true
optimal objective value of problem (23) is referred to as the
relaxation gap. In this paper, the relaxation gap is presented in
percentage by dividing it by the true optimal objective value of
problem (23). If the resulting optimal Λ is equal to the optimal
objective value in (23), then the relaxation is exact, and the
relaxation gap is zero. For every x ∈ Rn that is feasible in
strategic bidding problem (23), X = xxT is feasible in the
proposed relaxation problem (25). Thus, the infeasibility of
problem (25) is a certificate of infeasibility for problem (23).
Problem (25) is a convex optimization problem because the
objective function is linear and the feasible set is convex. However, since this problem has an infinite number of constraints,
i.e., one constraint for any x ∈ Rn , it is not a computationally

z=1

i=1 j=1

T
 
 
T
M X
n
X
0 vm0
1 vm0
.
−
hml
hm0
el vm
0 vm
m=1 l=1
m=1
(27)
Here, hml denotes the lth element of hm , ∀m.
From [31, Excercise 3.32], a quadratic polynomial in x
such as the one on the left hand side of (26) in Lemma 1
is always non-negative, if and only if it can be written as
the sum of squares of some other polynomials [31, Definition
3.24]. From this, together with the analysis in [31, Section
3.1.4], the infinite number of constraints in (26) is equivalent
to the following single matrix inequality constraint:
M
X

Υ  0.

(28)

By replacing the constraints in (25) with the one in (28), we
express problem (25) in the following equivalent form:
minimize

Λ,αi ,̺ij ,βz
hml ,hm0

Λ
(29)

subject to Υ  0.
Problem (29) is a semidefinite program (SDP), which can be
solved using convex programming tools such as Mosek [32].
B. Reduced Computation Complexity
In this section, we reformulate problem (23) to significantly
reduce the number of variables in problem (29). This is done
by systematically eliminating all linear equality constraints in
problem (23). First, we note that from [33, pp. 46], set
T
{x | vm
x + vm0 = 0,

∀m},

(30)

is equivalent to set
{Oy + x̄ | y ∈ Rr },

(31)

where
T

r , Rank ([v1 , . . . , vM ]) , O , Null([v1 · · · vM ] )
T

T

x̄ , [v1 · · · vM ] \[v10 · · · vM0 ] ,

(32)

Here, the matrix operator Null(·), which is also a command
in Matlab [34], returns an orthonormal basis for the null
space of its argument matrix, obtained from its singular value
decomposition. Moreover, the operator \ which is also a
command in Matlab [34], returns an arbitrary member of the

5

set (30). From (30) and (31), we replace optimization problem
(23) with the following equivalent optimization problem:

T

maximize Oy + x̄ F Oy + x̄ + 2f T Oy + x̄
y

subject to


pTi Oy + x̄ + pi0 ≥ 0

T

Oy + x̄ Qz Oy + x̄ + 2qzT Oy + x̄ = 0

(33)

∀i
∀z.

Note that, the above problem does not have any linear equality
constraint. While problem (23) has n variables, problem (33)
has r variables, where, in practice, r ≪ n. Once we solve
problem (33) and obtain its optimal solution y ⋆ , the optimal
solution of problem (23) is readily obtained as
x⋆ = Oy ⋆ + x̄.

(34)

Similar to problem (23), problem (33) is also a QCQP; therefore, we can repeat the analysis in Section III-A and introduce
the following convex relaxation associated with problem (33):
Λ

minimize
Λ,αi ,̺ij βz

subject to ΩT Ψ Ω  0,

(35)

where
Ψ,


 X 
pi0 pTi /2
−f T
−
αi
−
pi /2
0
−F
i
 (36)

   T X
Z
I
I X
X
0 qzT
pi0 pj0
,
βz
−
̺ij
qz Qz
pj
pi



Λ
−f

z=1

i=1 j=1

and
Ω,




1 0
.
x̄ O

(37)

Here, matrix Ψ is a reduced version of matrix Υ, where the
optimization variables hml and hm0 are eliminated. Similar
to problem (29), problem (35) is also an SDP. However,
while problem (29) has n(n + 1)/2 variables, problem (35)
has r(r + 1)/2 variables. For example, for the case of the
MPEC problem in Section V-B, the number of variables
corresponding to problems (29) and (35) are 11476 and 2016,
respectively. This means 82% drop in the number of variables.

C. Recovery of Original Optimization Variables
In this section, we explain how we can recover a solution
y for problem (33) by solving its convex relaxation in (35).
A solution x for problem (23) is then obtained from y using
(34). Suppose strong duality holds for the SDP in (35), which
is a convex optimization problem. Accordingly, problem (35)
and its dual problem, which itself is an SDP as shown below,

have equal optimal objective values:




0 fT
ΩY
maximize tr ΩT
f F
Y ∈Sr+1
subject to
Y11 = 1




pi0 pTi /2
T
ΩY ≥ 0
tr Ω
pi /2
0
   T


pj0
T pi0
ΩY ≥ 0
tr Ω
pi
pj




0 qzT
T
ΩY = 0
tr Ω
qz Qz

∀i

(38)

∀i, j
∀z

Y  0.

Therefore, the above dual problem is still a convex relaxation
of problem (33). Next, suppose matrix Y ⋆ denotes the optimal
variable in problem (38). The following theorem explains the
case where the above convex relaxation is exact:
Theorem 1: Suppose we obtain vector y ⋆ ∈ Rr from matrix
Y ⋆ by taking the first column of Y ⋆ as follows:
 
1
= Y ⋆ e1 .
(39)
y⋆

If Rank(Y ⋆ ) = 1, then y ⋆ is the optimal solution of problem
(33), and x⋆ in (34) is the optimal solution of problem (23).
The proof of Theorem 1 is given in the Appendix. While Theorem 1 is promising, in practice, we often have Rank(Y ⋆ ) > 1.
Fortunately, even in that case, the approach in (39) gives a
good approximate solution for problem (33). That being said,
there are still many cases where such approximation is not
feasible. Specially, y ⋆ may not satisfy all the quadratic equality
constraints in (33). Therefore, we need a mechanism to adjust
y ⋆ from (39) to make it feasible. Such mechanisms are often
customized for particular QCQP formulations, see [35, Section
IV-C] for an example in Communications. In our case, we
rather use the fact that the quadratic equality constraints in (33)
are all due to complimentary slackness, and hold the particular
structure in (24). Accordingly, we propose Algorithm 1 to
derive a feasible solution y ⋆ from Y ⋆ . The feasibility aspect
of solution from Algorithm 1 is analytically guaranteed, and
its optimality is shown to often be exact through extensive
numerical Case Studies in Section V.
From the model in (24), the last constraint in (33) can be
rewritten as
(dz T (Oy + x̄) + 2)(qzT (Oy + x̄)) = 0

∀z.

(40)

Therefore, we can express the last constraint in (33) as


dz T Oy + x̄ + 2 = 0 or qzT Oy + x̄ = 0, ∀z. (41)

Now, suppose for one quadratic equality constraint index z,
neither of the two equalities in (41) holds for y = y ⋆ , making
y ⋆ an infeasible solution to problem (33). But suppose there
exists a small ǫ > 0 and another number ∆ ≫ ǫ, for which


|qzT Oy ⋆ + x̄ | ≤ ǫ and |dz T Oy ⋆ + x̄ + 2| ≥ ∆. (42)

In that case, it is likely that at optimality we have

qzT Oy + x̄ = 0.

(43)

6

One can also make the opposite argument. That is, if


|qzT Oy ⋆ + x̄ | ≥ ∆ and |dz T Oy ⋆ + x̄ + 2| ≤ ǫ, (44)
then, it is likely that at optimality we have

dz T Oy + x̄ + 2 = 0.

(45)

Therefore, if it turns out that (42) holds for a specific index
z, then we can replace the corresponding complimentary
slackness constraint in (33) which is non-convex, with its
equivalent-at-optimality linear constraint in (43). Similarly, if
(44) holds for a specific z, the corresponding complimentary
slackness constraint in problem (33) is replaced with (45).
The above argument is the foundation of Algorithm 1. Once
we encounter an infeasible solution y ⋆ in Line 3, we first
initialize the values of parameters ∆ and ǫ in Line 4, and then
we go through iterations of augmenting problem (33) in Lines
5 to 11 until we obtain a feasible solution. In the first iteration,
we deal with a version of problem (33) in which we have
removed several complimentary slackness constraints through
Lines 5 to 9. Therefore, solving the MILP-equivalent of such
augmented problem in Line 10 is a light task. Next, as we keep
iterating through Lines 5 to 11, we decrease ǫ, and we choose
to keep more original complimentary slackness constraints
in problem (33), until the augmented problem (33) becomes
feasible. Accordingly, the computation time in solving the
MILP-equivalent of problem (23) will gradually grow as we
iterate. However, as we will see in Section V-B, in practice, we
often need to iterate very few times; therefore, in general, the
computation time for Algorithm 1 is much lower compared to
the standard MILP approach in [1]–[3].
In summary, Algorithm 1 exploits the solution that comes
from the proposed relaxation problem in (38) in order to
reduce the computation time in solving problem (23). The
solution of Algorithm 1 is guaranteed to be feasible to problem
(23), due to Steps 3 and 12 in Algorithm 1. However, neither
the computation time nor the optimality of Algorithm 1 is
guaranteed. Nevertheless, the numerical examples in Section
V suggest that Algorithm 1 often performs very effectively in
solving problem (23), with high optimality and low computation time. As for the convergence of Algorithm 1, we note that,
it iteratively solves a finite number of MILPs one-after-one
until one does converge. In the worst case scenario, Algorithm
1 would end up solving the original MILP reformulation of
problem (23) based on [1], which is guaranteed to converge
to a feasible solution, but it may take a long time to do so.
This is because problem (23) is a reformulation of problem
(21), and by construction problem (21) is always feasible.
IV. M ULTIPLE T IME S LOTS

AND

R ANDOM S CENARIOS

In practice, problem (21) may need to be solved over T ≥ 1
time slots, e.g., over 24 hourly time slots in a day-ahead
market. Also, one may often need to address uncertainty by
taking into account K ≥ 1 random scenarios. In that case,
the price and energy bid parameters of generators and loads
and also all the variables in MPEC problem are indexed
by t and k. For example, xk [t] means the vector of the
original optimization variables x indexed at time slot t and

Algorithm 1
1: Solve convex relaxation problem (38) and obtain Y ⋆ .
2: Obtain y ⋆ from Y ⋆ using (39).
3: if y ⋆ is feasible to problem (33) then exit.
4: Set ∆ = 1 and ǫ = 0.1.
5: for each complimentary slackness constraint z do
6:
if condition (42) holds for y = y ⋆ then
7:
Replace constraint z in (33) with (43).
8:
if condition (44) holds for y = y ⋆ then
9:
Replace constraint z in (33) with (45).
10: Solve the MILP equivalent of problem (33), see [1].
11: Set ǫ = ǫ − 0.01.
12: if the MILP equivalent is infeasible then Go to Step 5.

random scenario k. Hence, we can extend the MPEC problem
formulation in (21) and present it in vector-format as [1]:
maximize
xk [t]

subject to

K
T X
X

xk [t]T

t=1 k=1

K
T X
T
X
Fk [t]
fk [t]
2
xk [t] +
xk [t]
K
K
t=1
k=1

pi,k [t]T xk [t] + pi0,k [t] ≥ 0

∀t, k, i

T

vm,k [t] xk [t] + vm0,k [t] = 0
T

T

∀t, k, m

xk [t] Qz,k [t]xk [t] + 2qz,k [t] xk [t] = 0

∀t, k, z

eTl xk [t] − eTl xk [t − 1] +
eTl xk [t − 1] − eTl xk [t] +
eTl xk [t] − eTl x1 [t] = 0

Γ≥0

∀t, k, ∃l

Γ≥0

∀t, k, ∃l
∀t, k, ∃l.

(46)
The notation ∀t, k in the constraints of problem (46) indicates
that the corresponding constraints hold for all the time slots
and all the scenarios within their corresponding ranges, i.e.,
t = 1, · · ·, T and k = 1, · · ·, K. Also, the notation ∃l indicates
that the constraint holds only for strategic generators. The
first three constraints in (46) are simply the extensions of
the constraints in problem (23), across time slots and random
scenarios. The fourth and fifth constraints in (46) includes the
ramp constraints for strategic generators, where in each case
the index l and accordingly the basis el are selected such that
eTl xk [t] indicates the generation output of a particular strategic
generator at time slot t and random scenario k. Finally, the
sixth constraint in (46) is used to make sure that the bids of the
strategic generators are the same across all random scenarios,
where in each case the index l and accordingly the basis el are
selected such that eTl xk [t] indicates the price bid of a particular
strategic generator at time slot t and random scenario k.
A. Immediate Solution Approach
Just like problem (23), problem (46) is a QCQP. However,
the size of the optimization vector in (46) is T K times the
size of the optimization vector in problem (23). One approach
to solve problem (46) is to follow exactly the same analysis in
Section III. This is done by expanding the inequality constraint
in (25) to also include the last three constraints in problem
(46). Specifically, since the last three constraints in (46) are
linear, their corresponding Lagrange multipliers in (25) would

7

be affine, just like the case of the linear constraints in problem
(23), please refer to the second and the third properties of
problem (25) that we discussed in Section III-A.
Once problem (25) is updated as we explained above, we
would then follow the rest of the analysis in Section III and
end up with solving an SDP similar to the one in (38). While
in this approach we would achieve a convex relaxation for
problem (46), the matrix domain of the resulting SDP problem
would be ST Kr+1 , which means having T Kr(T Kr + 1)/2
scalar variables. Unfortunately, the number of constraints in
such SDP grows in proportional to T 2 K 2 . In other words,
even though the problem itself remains convex, its size will
grow exponentially as the number of time slots and random
scenarios grows. As a result, such convex relaxation may
impose huge computation burden and may not be practical.
B. Alternative Solution Approach
In this section, we propose an alternative convex relaxation
approach to solve problem (46) to tackle the curse of dimensionality in the number of time slots and random scenarios.
Again, we start by expanding the inequality constraint in (25)
to also include the last three constraints in problem (46).
However, as opposed to the approach in Section III-A, where
we would use affine Lagrange multipliers for these three new
sets of linear constraints, we would use only scalar Lagrange
multipliers, just like in the standard Lagrange dual problem
formulation [28, Section 5.2]. This would, in presence of
large T and K, significantly reduce the number of additional
Lagrange multipliers in the extension of problem (25); and
accordingly the number of variables in problem (47). The rest
of the analysis would be similar to Section III. Here, we only
show the final convex relaxation problem that we must solve:




T
K
T
1 XX
0
fk [t]
Ωk [t]Yk [t]
tr Ωk [t]T
maximize
fk [t] Fk [t]
yk [t],Yk [t] K
t=1 k=1

subject to

Y11,k [t] = 1
"

T pi0,k [t]
tr Ωk [t]
pi,k [t]

∀t, k
pi,k [t]T
2

0

2

#

Ωk [t]Yk [t]



≥0

∀t, k, i


T

pi0,k [t] pj0,k [t]
tr Ωk [t]
Ωk [t]Yk [t] ≥ 0, ∀t, k, i, j
pi,k [t]
pj,k [t]




T
0
qz,k [t]
T
Ωk [t]Yk [t] = 0, ∀t, k, z
tr Ωk [t]
qz,k [t] Qz,k [t]


T



Yk [t]  0,


1
= Yk [t]e1 ,
yk [t]

∀t, k,

eTl Ok [t]T (yk [t] − yk [t − 1]) + Γ ≥ 0,

∀t, k, ∃l

T
eTl Ok [t]
T
eTl Ok [t]

(yk [t − 1] − yk [t]) + Γ ≥ 0,

∀t, k, ∃l

(yk [t] − y1 [t]) = 0,

∀t, k, ∃l,
(47)

where

∀t, k



1
0
Ωk [t] ,
x̄k [t] Ok [t]



∀t, k.

(48)

29
27
26
G

G

G

30

28

25

G

G

24

23
19
18

15

20

G

G

21

17

14
16
G

10

12

13

11

22

9

3
1

8

6

4
G
G

2

5
7

G

G

Fig. 1: The IEEE 30-bus test system that we considered in our case studies.
The generators in the strategic generation firm are highlighted in gray.

Next, we highlight some of the key properties of problem
(47). First, if T = K = 1, then problem (47) reduces to
problem (38), where the last three sets of constraints in (47)
will disappear and the sixth constraint in (47) reduces to (39)
in Theorem 1. Second, the SDP problem in (47) has a mix
of matrix variables Yk [t] and vector variables yk [t]. Third, the
number of variables in problem (47) is only T Kr(r + 1)/2,
which grows only linearly with respect to either the number
of time slots T or the number of random scenarios K. As we
will see in Sections V-C and V-B, this latter property plays a
drastic role in lowering the computation time in our proposed
approach, compared to the standard MILP approach in [1]–
[3]. Fourth, matrices Yk [t] ∀t, k are dense, i.e., not sparse.
Therefore, the matrix completion methods such as the one in
[36], [37] are not applicable to problem (47).
As in Theorem 1, if Rank(Yk⋆ [t]) = 1, ∀t, k, then the convex
relaxation in problem (47) is exact, i.e., the optimal solutions
of the original MPEC problem in (46) are obtained as
x⋆k [t] = Oyk⋆ [t] + x̄k [t],

(49)

where yk⋆ [t], ∀t, k is the optimal solution of problem (47).
Again, in practice, Rank(Yk⋆ [t]) > 1, for several time slot t
and random scenario k instances. In such cases, we can still
use Algorithm 1, where we replace Lines 1 and 2 with “Solve
Problem (47) and obtain Yk⋆ [t] and yk⋆ [t] for all t and k.”
V. C ASE S TUDIES
A. Simulation Setup
In this section, we assess the performance of the proposed
approach based on the extended IEEE 30 bus test system in
[9], see Fig. 1, where the four generators in the strategic
generation firm are highlighted using color gray. Here, the
network includes 30 buses and 41 transmission lines. We have:
S = {4, 16, 24, 30}. The transmission lines data, generation
data, and load energy bids data are the same as those in Tables
I to III in [9]. Specifically, the transmission line between bus
#2 and bus #4 has a limited capacity of 0.2. Each strategic
generation unit has 1 GW capacity and the ramp parameter
is Γ = 0.3. The cost vector for strategic generators is cT =
[45.84 47.84 55.56 63.88] $/MWh. All loads, except for those

8

TABLE I: Load Data
Hourly Price Bids
Bus # 1
2
3
4
5
6
7
8
9
10 11 12
13
14 15 16 17 18 19 20 21 22 23
24
26 43.5 41.6 33.7 36.1 35.5 43.9 48.2 58.0 41.0 46.2 41.9 43.8 43.9 45.0 44.0 42.5 48.4 58.4 63.0 72.4 65.7 59.1 52.7 48.7
29 42.4 38.0 35.8 38.0 38.2 40.5 54.3 60.0 53.1 47.0 44.5 45.8 41.6 41.7 44.9 48.9 48.8 59.2 62.1 68.2 64.0 62.4 53.1 45.0

TABLE II: Scaling Factors for Construction of Random Scenarios
1
2.0

Scenario #
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
1.9 1.8 1.7 1.6 1.5 1.4 1.3 1.2 1.1 1.0 0.9 0.8 0.7 0.6 0.5 0.4 0.3 0.2 0.1

TABLE III: Computation Time for Different Separate Time Intervals (Minutes)
(a) Proposed Approach

K
6
9
8
9
10

1
11
13
14
11
19

2
15
17
19
21
21

Time Interval
3
4
11
12
9
7
18
15
20
11
12
10

(b) MILP Approach in [1]

5
9
13
14
17
12

6
10
7
11
10
16

at buses 26 and 29, submit a price bid of 72 $/MWh for all
24 market operation hours. The hourly price bids of the load
at bus 26 and bus 29 are as in Table I. As in [1], we construct
20 random scenarios by scaling the price bids of loads and
non-strategic generators by using the 20 scaling factors that
are given in Table II. All problems are solved using a single
Intel Xeon E5-2450-v2 CPU.
Problem (47) is solved using Yalmip [38], where Mosek
[32] is the SDP solver. All MILP formulations are solved
using Gurobi [39]. In all case studies, the number of time
slots T and the number of random scenarios K are selected
such that, the MILP approach in [1] can converge in a timely
manner to allow us assess the optimality of our own design.
The optimality of our proposed approach is measured based on
the profit that is gained by the generation firm, after bidding
the solution that comes from our proposed approach. In this
regards, for any solution x⋆ that is feasible to the constraints of
problem (21), the optimality of x⋆ is defined as the numerical
value of the objective function in (21) at x = x⋆ , divided by
the true optimal objective value of problem (21).
B. Impact of Increasing the Number of Random Scenarios
Suppose T = 4. Fig. 2(a) shows the average computation
time versus the number of random scenarios K for our
approach as well as for the MILP approach in [1]. Here, the
average is taken across six MPEC problems for six different
time intervals of length four hours. From Fig. 2(a), we can
see that as K increases, the computation time for MILP
approach in [1] grows exponentially while for our proposed
approach grows rather linearly. The difference between the
two approaches becomes particularly significant where there
are K = 6 or more random scenarios. For this range of random
scenarios, the computation times are shown in Table III. We
can see that, when K = 10, the MILP approach in [1] does

K
6
7
8
9
10

1
236
949
2126
553
2197

2
97
119
537
-

Time Interval
3
4
516
174
287
285
1135 137
329
470
587

5
35
54
23
71
70

6
21
57
40
70
161

not converge for the second and third time intervals, even
after running for three days. In contrast, our approach always
converged in less than 21 minutes. Interestingly, the optimality
of the solution that comes from our proposed approach is
always 96% or better, for all the cases that are studied in this
section. For example, where K = 8, the average computation
time for the approach in [1] and our approach are 667 minutes
versus only about 16 minutes, respectively. This suggests an
improvement factor over 40. Note that, we did not go beyond
K = 10 scenarios, mainly because the MILP approach in [1]
could not converge in a timely manner for the larger number
of scenarios. In particular, the MILP approach in [1] could
not converge even after running the MILP algorithm for three
days. Otherwise, as far as our proposed approach is concerned,
we can handle larger K in this case, if needed.
Next, we take a closer look at how Algorithm 1 behaves.
Out of the 10 × 6 = 60 total case instances that are analyzed
in the case studies in this Section, in 36 cases, the inner loop
of Algorithm 1 was executed only once. In 24 cases, the
inner loop of Algorithm 1 was iteratively executed between
two to nine times. That being said, Algorithm 1 never iterated
more than nine times between Step 5 and Step 12, and never
ended up solving the original problem in (23) using the MILP
approach [1]. Of course, this may change in other test cases.
C. Impact of Increasing the Scheduling Horizon
Next, we examine the impact of changing the scheduling
horizon. To allow the competing MILP approach in [1] to
converge in a timely manner, we assume that K = 2, and we
instead increase the number of time slots T . The results are
shown in Fig. 3. We can see in Fig. 3(a) that, the computation
time of proposed approach grows linearly, as T increases,
while the computation time of the MILP approach in [1] grows
with a significantly higher rate. Specifically, for the case with

9

(a)

700

0

2

4

6

8

600

(a)

2500
MILP Approach in [1]
Proposed Approach

10
16

0

5

10

15

12

500

Computation Time (minutes)

Average Compution Time (minutes)

20
25

2000

8
400
4
300
0
200

20
15

1500

10
5

1000

0

500
100
MILP Approach in [1]
Proposed Approach

0

0
0

1

2

3

4

5

6

7

8

9

10

0

(b)

1

8

12

16

20

24

16

20

24

(b)

1

0.995

0.995

0.99

0.99

0.985

0.985

0.98

0.98

Optimality

Average Optimality

4

0.975

0.975

0.97

0.97

0.965

0.965

0.96

0.96

0.955

0.955
Proposed Approach

Proposed Approach

0.95

0.95
0

1

2

3

4

5

6

7

8

9

10

Number of Scenarios

0

4

8

12

Scheduling Horizon

Fig. 2: The impact of increasing the number of random scenarios on the
performance of the proposed approach and the MILP approach in [1]: (a) the
computation time; (b) the optimality.

Fig. 3: The impact of increasing the optimization scheduling horizon on
the performance of the proposed approach and the approach in [1]: (a) the
computation time; (b) the optimality.

T = 19, the MILP approach in [1] does not converge even
after running the related code for three days. In contrast, the
computation time of our proposed approach is always less than
25 minutes. Also, from Fig. 3(b), our proposed approach is
also always very accurate in terms of achieving the optimal
profit for the strategic producers.

is 0.2 and the ramp parameter Γ varies from 0.1 to 0.5. The
results are shown in Fig. 5. We can see that our proposed
approach significantly outperforms the MILP approach.

D. The Impact of Congested Line Capacity
To show that the performance of our proposed approach
is not sensitive to the choice of system parameters, in this
section, we examine the impact of transmission line capacity,
where we set T = 8 and K = 3. The results are shown in
Fig. 4, where we change the capacity of transmission line 3 [9]
from 0.1 to 1.0. Again, we can see that our proposed approach
is accurate and much more computationally efficient.
E. The impact of Ramp Parameter
In this Section, the impact of the ramp parameter Γ on the
computation time as well as on the optimality of our proposed
approach is assessed for the same simulation setup in Section
V-D, where the capacity of the congested transmission line

F. Comparison with other Convex Relaxation Approaches
In this Section, the performance of our proposed approach is
compared with that of the ones in [19] and the SDP relaxation
approaches in [18] and [40]. The comparison is done based on
the case of the IEEE 30-Bus System in Fig. 1, where K = 1,
and T varies from 1 to 5. First and foremost, we note that
[19], [18] and [40] do not provide any feasible solution to
problem (21). This is a common problem in many standard
SDP relaxation techniques, c.f. [41]. Accordingly, we can
only compare the objective values under relaxation, i.e., the
relaxation gap. With that in mind, we note that the approach
in [19] always results in an unbounded objective value, which
suggests an extremely poor performance. The approach in [40]
results in unbounded objective values for T = 1 and T = 2.
This approach does not converge for T > 2. Therefore, the
performance of the approach in [40] is very poor too. Finally,
the approach in [18] does converge and it is bounded for the
cases of T = 1 and T = 2. This convergence is achieved after

10

(a)

1000
900
0

0.2

0.4

0.6

0.8

160

Computation Time (minutes)

Computation Time (minutes)

1

700
10
600
500

5

400
0

300

120
100
80
60
40

100

20

0.3

0.4

0.5

0.6

0.7

0.8

0.9

0
0.1

1

(b)
1

1

0.995

0.995

0.99

0.99

0.985

0.985

0.98

0.98

Optimality

Optimality

140

200

0.2

MILP Approach in [1]
Proposed Approach

180

15

800

0
0.1

(a)

200
MILP Approach in [1]
Proposed Approach

0.975

0.15

0.2

0.25

0.3

0.35

0.4

0.5

(b)

0.975

0.97

0.97

0.965

0.965

0.96

0.96
0.955

0.955

Proposed Approach

Proposed Approach

0.95
0.1

0.45

0.2

0.3

0.4

0.5

0.6

0.7

0.8

0.9

1

0.95
0.1

0.15

0.2

0.25

Capacity of Congested Line

Fig. 4: The impact of changing the capacity of the congested transmission
line on the performance of the proposed approach and the approach in [1]:
(a) the computation time; (b) the optimality.

0.3

0.35

0.4

0.45

0.5

Ramp Prameter Γ

Fig. 5: The impact of changing the ramp parameter Γ on the performance of
the proposed approach and the approach in [1]: (a) the computation time; (b)
the optimality.
TABLE IV: Constructed Networks

1239 and 63315 seconds, with a relaxation gap of 5534% and
3386%, respectively. In contrast, once our approach is used,
the convergence times are only 22 and 49 seconds, and the
relaxation gaps are only 0.07% and 0.15%, respectively. As for
the cases with T > 2, the approach in [18] does not converge.
From the above results, we can see that our proposed approach
clearly outperforms the approaches in [18], [19] and [40].
G. The Impact of the Number of Buses
In this Section, the impact of the size of the power grid on
the performance of our proposed approach is assessed. For this
purpose, several power networks are constructed by extending
the number of buses, loads and generators in our base test
cases according to Table IV. The energy demands of the added
generators are chosen such that the total added generation is
equal to the total added load. In addition, the price bids for
the added generators and added loads are set to zero and 72
$/MWh, respectively. The line with finite capacity and the
location of strategic generators are as in Section V-B. Fig 6(a)
and Fig. 6(b) show the computation time and the optimality
of our proposed approach, respectively, for the case of T =
10 time slots and K = 3 random scenarios. From Fig. 6(a),

Buses
Generators
Loads

30
12
16

40
15
21

50
17
26

60
19
31

70
21
35

80
23
41

the computation time of our approach is much lower than the
MILP approach in [1]. Note that, for the power networks with
60, 70 and 80 buses, the MILP approach did not converge after
three days running time. Also, from Fig. 6(b) the optimality
of our approach is greater than 99% for power networks with
50 buses or less. As for the cases with more than 50 buses,
we simply do not know the level of optimality because we do
not have a truly optimal reference for comparison. As for the
networks with over 80 buses, the computation time even for
our proposed approach starts growing significantly.
VI. C ONCLUSIONS
A new and innovative method was proposed to solve strategic bidding problems in nodal electricity markets. Without loss
of generality, we focused on the case of strategic bidding for
producers. Unlike the state-of-the-art solution approach, where

11

A PPENDIX : P ROOF

4000

3500

Computation Time (minutes)

3000

2500

2000

1500

1000

500

0
30

40

50

60

70

80

1

0.995

0.99

0.985

0.98

Optimality

OF

T HEOREM 1

From (39), the objective value of (33) at y = y ⋆ becomes:
T


Oy ⋆ + x̄ F Oy ⋆ + x̄ + 2f T Oy ⋆ + x̄ =

 T



  

T
T
1
1
⋆
T 0 f
T 0 f
,
tr
ΩY
Ω
=
tr
Ω
Ω
f F
y⋆
f F
y⋆
(50)
where the last equality is due to the fact that since Rank(Y ⋆ ) =
⋆
1, Y11
= 1, and (39) holds, we have:
   T
1
1
⋆
Y = ⋆
.
(51)
y
y⋆

MILP Approach in [1]
Proposed Approach

By taking the same steps, one can show that y = y ⋆ satisfies
the constraints in problem (33). Therefore, on one hand, y ⋆ in
(39) satisfies all the constraints in problem (33) and produces
an objective value for problem (33) that is equal to the optimal
objective value of problem (38). On the other hand, since
problem (38) is a convex relaxation of problem (33), its
optimal objective value gives an upper bound for the optimal
objective value of problem (33). Hence, y ⋆ is an optimal
solution for problem (33) and the relaxation gap is zero. 

0.975

R EFERENCES

0.97

0.965

0.96

0.955
Proposed Approach

0.95
30

40

50

60

70

80

Number of Nodes

Fig. 6: The impact of increasing the number of buses on the performance of
the proposed approach and the approach in [1]: (a) the computation time; (b)
the optimality.

the strategic bidding problem is reformulated to an MILP,
the approach in this paper is based on convex programming.
Therefore, in addition to its potential in achieving very accurate optimal solutions, the proposed approach is much more
reliable and often computationally more tractable in solving
the strategic bidding problems in power systems. For example,
in a case study based on an IEEE 30-bus network with 10
random scenarios, while the state-of-the-art MILP approach
does not converge even after running for about three days,
our approach achieved the solution in less than twenty one
minutes, running on the same computation platform.
While the proposed approach in this paper takes a major
leap in solving strategic bidding problems in nodal electricity markets compared to the state-of-the-art MILP-based approaches, it still faces some limitations that could be addressed
in future follow up studies. For example, it appears that the
proposed method is well-capable of handling the increases in
the number of time slots and the number of random scenarios.
However, it is still not fully capable of handling the increases
in the number of buses. Another interesting direction for
future work is to obtain analytical performance bounds, i.e., on
optimality and computational time, of the proposed method.

[1] C. Ruiz and A. J. Conejo, “Pool strategy of a producer with endogenous
formation of locational marginal prices,” IEEE Trans. on Power Systems,
vol. 24, no. 4, pp. 1855–1866, Sep. 2009.
[2] S. J. Kazempour, A. J. Conejo, and C. Ruiz, “Strategic generation
investment using a complementarity approach,” IEEE Trans. on Power
Systems, vol. 26, no. 2, pp. 940–948, May 2011.
[3] D. Pozo and J. Contreras, “Finding multiple nash equilibria in poolbased markets: A stochastic EPEC approach,” IEEE Trans. on Power
Systems, vol. 26, no. 3, pp. 1744–1752, Aug. 2011.
[4] C. G. Baslis and A. G. Bakirtzis, “Mid-term stochastic scheduling of
a price-maker hydro producer with pumped storage,” IEEE Trans. on
Power Systems, vol. 26, no. 4, pp. 1856–1865, Nov. 2011.
[5] D. Zhang, Y. Wang, and P. B. Luh, “Optimization based bidding
strategies in the deregulated market,” IEEE Trans. on Power Systems,
vol. 15, no. 3, pp. 981–986, Aug. 2000.
[6] H. Mohsenian-Rad, “Optimal demand bidding for time-shiftable loads,”
IEEE Trans. on Power Systems, vol. 30, no. 2, pp. 939–951, Mar. 2015.
[7] A. Daraeepour, S. J. Kazempour, D. Patino-Echeverri, and A. J. Conejo,
“Strategic demand-side response to wind power integration,” accepted
for publication in IEEE Trans. on Power Systems, Nov. 2015.
[8] H. Mohsenian-Rad, “Optimal bidding, scheduling, and deployment of
battery systems in california day-ahead energy market,” IEEE Trans. on
Power Systems, vol. 31, no. 1, pp. 442–453, Jan. 2016.
[9] ——, “Coordinated price-maker operation of large energy storage systems in nodal energy markets,” IEEE Trans. on Power Systems, vol. 31,
no. 1, pp. 786–797, Jan. 2016.
[10] H. Akhavan-Hejazi and H. Mohsenian-Rad, “Optimal operation of
independent storage systems in energy and reserve markets with high
wind penetration,” IEEE Trans. on Smart Grid, vol. 5, no. 2, pp. 1088–
1097, Mar. 2014.
[11] D. Ladurantaye, M. Gendreau, and J. Y. Potvin, “Strategic bidding for
price-taker hydroelectricity producers,” IEEE Trans. on Power Systems,
vol. 22, no. 4, pp. 2187–2203, Nov. 2007.
[12] B. F. Hobbs, C. B. Metzler, and J. S. Pang, “Strategic gaming analysis
for electric power systems: an mpec approach,” IEEE Transactions on
Power Systems, vol. 15, no. 2, pp. 638–645, May 2000.
[13] L. Baringo and A. J. Conejo, “Strategic offering for a wind power
producer,” IEEE Transactions on Power Systems, vol. 28, no. 4, pp.
4645–4654, November 2013.
[14] A. S. Mobarakeh and H. Mohsenian-Rad, “Strategic selection of capacity
and mileage bids in california iso performance-based regulation market,”
in Proc. of IEEE PES General Meeting, Boston, MA, July 2016.
[15] S. J. Kazempour, A. J. Conejo, and C. Ruiz, “Strategic bidding for a
large consumer,” IEEE Transactions on Power Systems, vol. 30, no. 2,
pp. 848–855, March 2015.

12

[16] H. Pandzic, A. J. Conejo, I. Kuzle, and E. Caro, “Yearly maintenance
scheduling of transmission lines within a market environment,” IEEE
Transactions on Power Systems, vol. 28, no. 1, pp. 407–415, February
2012.
[17] A. L. Motto, J. M. Arroyo, and F. D. Galiana, “A mixed-integer LP
procedure for the analysis of electric grid security under disruptive
threat,” IEEE Transactions on Power Systems, vol. 20, no. 3, pp. 1357–
1365, August 2005.
[18] M. Fampa and W. Pimentel, “SDP relaxation for a strategic pricing
bilevel problem in electricity markets,” in Proc. of Simpsio Brasileiro
de Pesquisa Operacional, Natal, Brazil, Sep. 2013.
[19] H. Haghighat, “Strategic offering under uncertainty in power markets,”
International Journal of Electrical Power & Energy Systems, vol. 63,
pp. 1070–1077, Dec. 2014.
[20] M. Laurent, Sums of squares, moment matrices and optimization over
polynomials, in Emerging Applications of Algebraic Geometry, M. Putinar and S. Sullivant, Eds.
IMA Volumes in Mathematics and its
Applications, vol. 149, New York, NY: Springer, 2009, pp. 157-270.
[21] A. Papachristodoulou, J. Anderson, G. Valmorbida, S. Prajna, P. Seiler,
and P. A. Parrilo, SOSTOOLS user’s guid, October 2013. [Online].
Available: http://www.cds.caltech.edu/sostools/sostools.pdf/
[22] V. Jeyakumar, T. S. Phamb, and G. Li, “Convergence of the lasserre
hierarchy of SDP relaxations for convex polynomial programs without
compactness,” Operations Research Letters, vol. 42, pp. 34–40, 2014.
[23] J. Nie, “Optimality conditions and finite convergence of Lasserre’s
hierarchy,” Submitted to the journal of Optimization and Control, 2012.
[Online]. Available: https://arxiv.org/abs/1206.0319
[24] S. Gabriel, A. Conejo, J. Fuller, B. Hobbs, and C. Ruiz, Complementarity
Modeling in Energy Markets. New York, USA: Springer, 2013.
[25] Y. Fu and Z. Li, “Different models and properties on lmp calculations,”
in Proc. of IEEE PES General Meeting, Montreal, Canada, June 2006.
[26] P. Garcia-Herreros, L. Zhang, P. Misra, E. Arslan, S. Mehta, and I. E.
Grossmann, “Mixed-integer bilevel optimization for capacity planning
with rational markets,” Operations Research Letters, vol. 86, no. 4, pp.
33–47, March 2016.
[27] S. Dempe and A. B. Zemkoho, “The bilevel programming problem:
reformulations, constraint qualifications and optimality conditions,”
Journal of Mathematical Programming, vol. 138, pp. 447–473, 2013.
[28] S. Boyd and L. Vandenberghe, Convex Optimization. New York, NY,
USA: Cambridge University Press, 2004.
[29] C. Zhao, E. Mallada, and F. Dorfler, “Distributed frequency control
for stability and economic dispatch in power networks,” in American
Control Conference, Chicago, IL, July 2015.
[30] N. Li, L. Chen, C. Zhao, and S. H. Low, “Connecting automatic
generation control and economic dispatch from an optimization view,”
in American Control Conference, Portland, OR, July 2014.
[31] G. Blekherman, P. A. Parrilo, and R. R. Thomas, Semidefinite Optimization and Convex Algebraic Geometry. MOS-SIAM Series on
Optimization, Mar. 2013.
[32] MOSEK ApS, The MOSEK optimization toolbox for MATLAB
manual Version 7.0 (Revision 141), 2015. [Online]. Available:
http://docs.mosek.com/7.0/toolbox/
[33] D. C. Lay, Linear Algebra and its Applications. Boston, MA: AddisonWesley, 2000.
[34] Mathworks, “System of linear equations,” 2016. [Online]. Available: http://www.mathworks.com/help/matlab/math/systems-of-linearequations.html?refresh=true
[35] H. Mohsenian-Rad, J. Mietzner, R. Schober, and V. Wong, “Preequalization for pre-rake DS-UWB systems with spectral mask constraints,” IEEE Trans. on Communications, vol. 59, pp. 780–791, 2011.
[36] L. Vandenberghe and M. S. Andersen, “Chordal graphs and semidefinite
optimization,” Journal of Foundations and Trends in Optimization,
vol. 1, no. 4, pp. 241–433, 2015.
[37] A. Jabr, “Exploiting sparsity in SDP relaxations of the OPF problem,”
IEEE Transactions on Power Systems, vol. 27, no. 2, pp. 1138–1139,
May 2012.
[38] J. Lofberg, “Yalmip : A toolbox for modeling and optimization in
matlab,” in proc. of IEEE International Symposium on Computer Aided
Control Systems Design, Taipei, Taiwan, Sep. 2004.
[39] G. O. Inc., “Gurobi optimizer reference manual,” 2015. [Online].
Available: http://www.gurobi.com
[40] B. Xiaowei, N. V. Sahinidis, and M. Tawarmalani, “Semidefinite relaxations for quadratically constrained quadratic programming: A review
and comparisons,” Journal of Mathematical Programming, vol. 129,
no. 1, pp. 129–157, 2011.

[41] S. You and Q. Peng, “A non-convex alternating direction method
of multipliers heuristic for optimal power flow,” in Proc. of IEEE
Conference on Smart Grid Communications, Venice, Italy, Nov. 2014.

