Transcript Stochastic Optimisation in Electricity Pool Markets

Stochastic Optimization in
Electricity Systems
Andy Philpott
The University of Auckland
www.esc.auckland.ac.nz/epoc
SPXI Tutorial, August 26, 2007
Electricity optimization
Optimal power flow [Wood and Wollenberg, 1984,1996, Bonnans, 1997,1998]
Economic dispatch [Wood and Wollenberg, 1984,1996]
Unit commitment
Lagrangian relaxation [Muckstadt & Koenig, 1977, Sheble & Fahd, 1994]
Multi-stage SIP [Carpentier et al 1996, Takriti et al 1996, Caroe et al 1999, Romisch et al 1996-]
Market models [Hobbs et al, 2001, Philpott & Schultz, 2006]
Hydro-thermal scheduling
Dynamic programming [Massé*, 1944, Turgeon, 1980, Read,1981]
Multi-stage SP [Jacobs et al, 1995]
SDDP [ Pereira & Pinto, 1991]
Market models [Scott & Read, 1996, Bushnell, 2000]
Capacity expansion of generation and transmission
LP [Massé & Gibrat, 1957]
SLP [Murphy et al, 1982]
Multi-stage SP [Dantzig & Infanger,1993]
Multi-stage SIP [Ahmed et al, 2006, Singh et al, 2006]
Market models [Murphy & Smeers, 2005]
* P. Massé, Applications des probabilités en chaîne à l’hydrologie statistique et au jeu des réservoirs
Journal de la Société de Statistique de Paris, 1944
SPXI Tutorial, August 26, 2007
Uncertainty in electricity systems
System uncertainties
• Long-term electricity demand (years)
• Inflows to hydro-electric reservoirs (weeks/months)
• Short-term electricity demand (days)
• Intermittent (e.g. wind) supply (minutes/hours)
• Plant and line outages (seconds/minutes)
User uncertainties (various time scales)
• Electricity prices
• Behaviour of market participants
• Government regulation
SPXI Tutorial, August 26, 2007
What to expect in this talk…
• I will try to address three questions:
– What stochastic programming models are being used by
modellers in electricity companies?
– How are they being used?
– What will be the features of the next generation of models?
• I will not talk about financial models in perfectly competitive markets
(see previous tutorial speakers).
• I will (probably) not talk about capacity expansion models.
• Warning: this is not a “how-to-solve-it” tutorial.
SPXI Tutorial, August 26, 2007
Economic dispatch model
SPXI Tutorial, August 26, 2007
Uncertainty in economic dispatch
• Plant and line outages (seconds/minutes)
– Spinning reserve (N-1 security standard)
• Uncertain demand/supply(e.g. wind)
– Frequency keeping stations (small variations)
– Re-dispatch (large variations)
– Opportunity for stochastic programming (see Pritchard et al
WIND model)
SPXI Tutorial, August 26, 2007
Unit commitment formulation
SPXI Tutorial, August 26, 2007
Stochastic unit commitment model
SPXI Tutorial, August 26, 2007
Lagrangian relaxation decouples by unit
See sequence of papers by Romisch, Growe-Kuska, and others (1996 -)
SPXI Tutorial, August 26, 2007
Hydro-thermal scheduling
SPXI Tutorial, August 26, 2007
Hydro-thermal scheduling literature
• Dynamic programming
Massé (1944)*
Turgeon (1980)
Read (1981)
• Multi-stage SP
Jacobs et al (1995)
• SDDP
Pereira & Pinto (1991)
• Market models
Scott & Read (1996)
Bushnell (2000)
* P. Massé, Applications des probabilités en chaîne à l’hydrologie statistique et au jeu des réservoirs
Journal de la Société de Statistique de Paris, 1944
SPXI Tutorial, August 26, 2007
(Over-?) simplifying assumptions
•
•
•
•
•
Small number of reservoirs (<20)
System is centrally dispatched.
Relatively complete recourse.
Stage-wise independence of inflow process.
A convex dispatch problem in each stage.
SPXI Tutorial, August 26, 2007
p21
w1(2)
w2(2)
w1(1)
p11
p12
w3(2)
p21
w2(1)
p13
p21
w1(2)
w2(2)
w3(1)
w3(2)
SPXI Tutorial, August 26, 2007
Outer approximation
SPXI Tutorial, August 26, 2007
Outer approximation of Ct+1(y)
Θ(t+1)
θt+1 ≥ αt+1(k) + βt+1(k)Ty, k
Reservoir storage, x(t+1)
SPXI Tutorial, August 26, 2007
Cut calculation
SPXI Tutorial, August 26, 2007
Sampling algorithm
SPXI Tutorial, August 26, 2007
w2(1)
w2(2)
w3(3)
w1(2)
w1(1)
w2(2)
w3(2)
p11
p12
w2(1)
p13
w3(1)
SPXI Tutorial, August 26, 2007
w1(1)
p11
p12
w2(1)
p13
w3(1)
SPXI Tutorial, August 26, 2007
w2(1)
p21
w1(3)
w1(2)
w2(2)
w1(1)
p11
w2(2)
w3(2)
p21
w2(1)
p13
p21
w1(2)
w2(2)
w3(1)
w3(2)
SPXI Tutorial, August 26, 2007
w2(1)
p21
w3(3)
w1(2)
w2(2)
w1(1)
p11
w2(2)
w3(2)
p21
w2(1)
p13
p21
w1(2)
w2(2)
w3(1)
w3(2)
SPXI Tutorial, August 26, 2007
SPXI Tutorial, August 26, 2007
Case study: New Zealand system
TPO
HVDC line
MAN
HAW
SPXI Tutorial, August 26, 2007
A simplified network model
demand
TPO
N
MAN
S
HAW
demand
SPXI Tutorial, August 26, 2007
2005-2006 policy simulated with historical inflow sequences
4500
4000
3500
1995
1996
1997
1998
1999
3000
2500
2000
2001
2002
2003
2004
2000
1500
1000
500
00
0
0
10
20
30
40
SPXI Tutorial, August 26, 2007
50
Computational results: NZ model
•
•
•
•
10 reservoirs
52 weekly stages
30 inflow outcomes per stage
Model written in AMPL/CPLEX
• Takes 100 iterations and 2 hours on a standard Windows PC to
converge
• Larger models have slow convergence
SPXI Tutorial, August 26, 2007
Computational results: Brazilian system
• 283 hydro plants
• AR-6 streamflow model
– about two thousand state variables
• 271 thermal plants
• 219 stages
• 80 sequences in the forward simulation
• 30 scenarios (“openings”) for each state in the backward
recursion
• 7 iterations
• 11 hours CPU (Pentium IV-HT 2.8 GHz 1 Gbyte RAM )
Source: Reproduced with permission of Luiz Barossa, PSR
SPXI Tutorial, August 26, 2007
Electricity pool markets
•
•
•
•
•
•
•
•
•
•
•
Chile (1970s)
England and Wales (1990) (NETA 2001)
Nordpool (1996)
New Zealand (1996)
Australia (1997)
Colombia, Brazil, …
Pennsylvania-New Jersey-Maryland (PJM)
New York (1999)
New England (1999)
Ontario (May 1, 2002)
Texas (ERCOT, full LMP by 2009)
SPXI Tutorial, August 26, 2007
Uniform price auction (single node)
price
T1(q)
price
T2(q)
p
quantity
quantity
price
combined offer stack
p
demand
quantity
SPXI Tutorial, August 26, 2007
Nodal dispatch-pricing formulation
p
Tm(q)
q
[pi]
SPXI Tutorial, August 26, 2007
Residual demand curve for a generator
S(p) = total supply curve from other generators
D(p) = demand function
p
c(q) = cost of generating q
R(q,p) = profit = qp – c(q)
Residual demand curve = D(p) – S(p)
Optimal dispatch point to maximize profit
q
SPXI Tutorial, August 26, 2007
A distribution of residual demand curves
p
e
D(p) – S(p) + e
(Residual demand shifted by random demand shock e )
Optimal dispatch point to maximize profit
q
SPXI Tutorial, August 26, 2007
One supply curve optimizes for all demand realizations
p
The offer curve is a “wait-and-see”
solution. It is independent of the
probability distribution of e
q
SPXI Tutorial, August 26, 2007
This doesn’t always work
p
There is no nondecreasing offer
curve passing through both points.
Optimization in this case requires a
risk measure. We will use the
expectation of profit with respect to
the probability distribution of e.
q
SPXI Tutorial, August 26, 2007
Monotonicity Theorem
[Anderson & P, 2002]
If (S-D)-1 is a log concave function of q
and c(q) is convex then a single monotonic
supply curve exists that maximizes profit
for all realizations of e.
p
q
SPXI Tutorial, August 26, 2007
The market distribution function
[Anderson & P, 2002]
Define: y(q,p) = Pr [D(p) + e – S(p) < q]
= F(q + S(p) – D(p))
= Pr [an offer of (q,p) is not fully dispatched]
= Pr [residual demand curve passes below (q,p)]
price
p
( q, p )
q
S(p) = supply curve from
other generators
D(p) = demand function
e
= random demand
shock
F
= cdf of random shock
quantity
SPXI Tutorial, August 26, 2007
Expected profit from curve (q(t),p(t))
t 1
price
E[Profit]   ( q( t )p( t )  c( q( t )))
t 0
dψ( q( t ), p( t ))
dt
dt
Profit  q( t )p( t )  c( q( t ))
p(t)
Prob 
q(t)
dψ( q( t ), p( t ))
dt
dt
quantity
SPXI Tutorial, August 26, 2007
Finding empirical y
• Use small dispatch model
• Aggregated demand
• DC-load flow dispatch
• Piecewise linear losses
• Solved in ampl/cplex
• Draw a sample from demand
• Draw a sample from other
generators offers
• Solve dispatch model with
different offers q
• Increment the locations
where dispatch occur by 1
SPXI Tutorial, August 26, 2007
Estimation of y using simulation
Dispatch count on segment increases by 1
Sampled residual demand curve
SPXI Tutorial, August 26, 2007
The real world
• Transmission congestion gives different prices at
different nodes.
• Generators own plant at different nodes.
• Generators in New Zealand are vertically integrated with
electricity retailers, with demand at a different node.
• Generators have contracts with purchasers at different
nodes.
• Maintenance and outages affect generation and
transmission capacity.
SPXI Tutorial, August 26, 2007
Contracts
A contract for differences (or hedge contract) for
a quantity Q at an agreed strike price f is an
agreement for one party (the contract holder) to
pay the other (the contract writer) the amount
Q(f-p) where p is the electricity price at an
agreed node.
A generator having written a contract for Q
seeks to maximize
E[R(q,p)] = E[qp - c(q) + Q(f-p)]
SPXI Tutorial, August 26, 2007
Generator’s real objective
Owner of HLY station might want to
maximize
gross revenue at HLY + TOK
–$35/MWh fuel cost at HLY
–cost of purchases to cover retail base of
• 25% at OTA
• 5% at ISL
• 5% at HWB
accounting for hedge contracts
at $50/MWh of
• 250MW at OTA
• 150MW at HAY
• 50 MW at HWB
(Numbers are illustrative only!)
SPXI Tutorial, August 26, 2007
Implementation in the real world
•
•
•
•
BOOMER code [Pritchard, 2006]
Single period/single station simulation/optimization model.
Construct discrete y on a rectangular grid.
For every grid segment record all the relevant dispatch
information (e.g. nodal prices at contract nodes)
• Use dynamic programming to construct a step function
maximizing expected profit.
• A longest path problem through acyclic directed graph,
where increment on each edge is the overall profit function
times the probability of being dispatched on this segment
SPXI Tutorial, August 26, 2007
Longest path gives maximum expected profit
SPXI Tutorial, August 26, 2007
without retail and contracts
with retail and 450MW of contracts
SPXI Tutorial, August 26, 2007
with retail customers
moved to be more
remote
SPXI Tutorial, August 26, 2007
What is wrong with this model?
• Single period
• Competitors response not modelled
• Extreme solutions: no “comfort
factor”
• Can be used as a benchmark for
traders
SPXI Tutorial, August 26, 2007
Challenges for SP
• Electricity systems have been a happy hunting ground for
stochastic optimization.
• What are the SP success stories in electricity?
• Tractability is only part of the story – model veracity is
more important.
• In markets the dual problem is as important as the primal
(e.g. WIND model).
• Are the assumptions of the models valid e.g. perfect
competition?
• Are the answers simple enough to verify (e.g. by out-ofsample simulation)?
• Models are used differently from their intended
application.
SPXI Tutorial, August 26, 2007
The End
SPXI Tutorial, August 26, 2007