当前位置：搜档网 › Large-scale Unit Commitment under uncertainty-未发表

Large-scale Unit Commitment under uncertainty-未发表

4OR manuscript No.

(will be inserted by the editor)

Large-scale Unit Commitment under uncertainty

M.Tahanan·W.van Ackooij· A.Frangioni·

https://www.sodocs.net/doc/1214984295.html,calandra

the date of receipt and acceptance should be inserted later

Abstract The Unit Commitment problem in energy management aims at?nding the optimal pro-ductions schedule of a set of generation units while meeting various system-wide constraints.It has always been a large-scale,non-convex di?cult problem,especially in view of the fact that operational requirements imply that it has to be solved in an unreasonably small time for its size.Recently,the ever increasing capacity for renewable generation has strongly increased the level of uncertainty in the system,making the(ideal)Unit Commitment model a large-scale,non-convex,uncertain(stochastic, robust,chance-constrained)program.We provide a survey of the literature on methods for the Uncer-tain Unit Commitment problem,in all its variants.We start with a review of the main contributions on solution methods for the deterministic versions of the problem,focusing on those based on mathemati-cal programming techniques that are more relevant for the uncertain versions of the problem.We then present and categorize the approaches to the latter,also providing entry points to the relevant literature on optimization under uncertainty.

Keywords Unit Commitment·Uncertainty·Large-Scale Optimization·Survey

Contents

1Introduction (2)

2Ingredients of the Unit Commitment problem (4)

2.1A global view of UC (5)

2.2The objective function (6)

2.3Thermal units (8)

2.4Hydro units (9)

2.5Renewable generation units (10)

2.6System-wide constraints (11)

2.7Optimal Transmission Switching (12)

3Methods for the deterministic Unit Commitment (12)

3.1Dynamic Programming (13)

3.2Integer and Mixed Integer Linear Programming (14)

3.2.1Early use:exhaustive enumeration (14)

3.2.2Modern use of MILP techniques (14)

Milad Tahanan

Ecole Centrale Paris,Grande Voie des Vignes,Chatenay-Malabry,France,E-mail:miladtahanan@https://www.sodocs.net/doc/1214984295.html,

Wim van Ackooij

EDF R&D.OSIRIS,Avenue du G′e n′e ral de Gaulle1,F-92141Clamart Cedex,France,E-mail:wim.van-ackooij@edf.fr Antonio Frangioni

Dipartimento di Informatica,Universit`a di Pisa,Largo B.Pontecorvo3,56127Pisa,Italia,E-mail:frangio@di.unipi.it Fabrizio Lacalandra

QuanTek S.r.L,Via G.Marconi,3,40122Bologna,Italia,E-mail:https://www.sodocs.net/doc/1214984295.html,calandra@quantek.it

3.2.3Recent trends in MILP techniques (15)

3.3Lagrangian and Benders Decomposition (16)

3.4Augmented Lagrangian Relaxation (19)

3.5(Meta-)Heuristics (19)

3.5.1Operator rule based:Priority Listing (19)

3.5.2Guided Random Exploration (20)

4Methods for the Uncertain Unit Commitment (21)

4.1Dealing with Uncertainty in UC (21)

4.1.1Dealing with uncertainty in the model (21)

4.1.1.1Stochastic optimization (21)

4.1.1.2Robust optimization (22)

4.1.1.3Chance-Constrained Optimization (22)

4.1.1.4The link between RO and CCO (22)

4.1.2Modelling and solution choices (22)

4.1.2.1The choice of recourse decisions (22)

4.1.2.2Direct approaches vs.decomposition (23)

4.2Stochastic Optimization(Scenario-Tree)approaches (23)

4.2.1Mixed Integer Linear Programming (24)

4.2.2Scenario Decomposition (24)

4.2.3Unit(Stochastic)Decomposition (25)

4.2.4Benders(-Like)Decomposition (26)

4.3Robust Optimization approaches (26)

4.4Chance-Constrained Optimization approaches (28)

5Concluding Remarks (29)

List of acronyms (29)

1Introduction

In electrical energy production and distribution systems,an important problem deals with computing 42

the production schedule of the available generating units in order to meet their technical and opera-43

tional constraints and to satisfy some system-wide constraints,e.g.,global equilibrium between energy 44

production and energy demand.The constraints of the units are very complex;for instance,some units 45

may require up to24hours to start.Therefore,such a schedule must be computed(well)in advance of 46

real time.The resulting family of models is usually referred to as the Unit Commitment problem(UC), 47

and its practical importance is clearly proven by the enormous amount of scienti?c literature devoted 48

to its solution in the last four decades and more.Besides the very substantial practical and economical 49

impact of UC,this proliferation of research is motivated by at least two independent factors:

1.on the one hand,progress in optimization methods,which provides novel methodological approaches 51

and improves the performances of existing ones,thereby allowing to tackle previously unsolvable 52

problems;

2.on the other hand,the large variety of di?erent versions of UC corresponding to the disparate 54

characteristics of electrical systems worldwide(free market vs.centralized,vast range of production 55

units due to hydro/thermal/nuclear sources,...).

Despite all of this research,UC still cannot be considered a“well-solved”problem.This is partly due to 57

the need of continuously adapting to the ever-changing demands of practical operational environments, 58

in turn caused by technological and regulatory changes which signi?cantly alter the characteristics of 59

the problem to be solved.Furthermore,UC is a large-scale,non-convex optimization problem that, 60

due to the operational requirements,has to be solved in an“unreasonably”small time.Finally,as 61

methodological and technological advances make previous versions of UC more accessible,practitioners 62

have a chance to challenge the(very signi?cant)simpli?cations that have traditionally been made, 63

for purely computational reasons,about the actual behavior of generating units.This leads to the 64

development of models incorporating considerable more detail than in the past,which can signi?cantly 65

stretch the capabilities of current solution methods.

A particularly relevant recent trend in electrical systems is the ever increasing use of intermittent(renew-67

able)production sources such as wind and solar power.This has signi?cantly increased the underlying 68

uncertainty in the system,previously almost completely due to variation of users’demand(which could 69

however be forecast quite e?ectively)and occurrence of faults(which was traditionally taken into account 70

by requiring some amount of spinning reserve).Ignoring such a substantial increase in uncertainty levels 71

w.r.t.the common existing models incurs an unacceptable risk that the computed production schedules 72

be signi?cantly more costly than anticipated,or even infeasible(e.g.,[205]).However,incorporating the 73

uncertainty in the models is very challenging,in particular in view of the di?culty of the deterministic 74

versions of UC.

Fortunately,optimization methods capable of dealing with uncertainty have been a very active area of 76

research in the last decade,and several of these developments can be applied,and have been applied,to 77

the UC problem.This paper aims at providing a survey of approaches for the Uncertain UC problem 78

(UUC).To the best of our knowledge no such survey exists,while the literature is rapidly growing.This 79

is easily explained,besides by the practical signi?cance of UUC,by the combination of two factors:on 80

one hand the diversity of operational environments that need to be considered,and on the other hand 81

by the fact that the multitude of applicable solution techniques already available to the UC(here and 82

in the following we mean the deterministic version when UUC is not explicitly mentioned)is further 83

compounded by the need of deciding how uncertainty is modeled.Indeed,the literature o?ers at least 84

three approaches that have substantially di?erent practical and computational requirements:Stochastic 85

Optimization(SO),Robust Optimization(RO),and Chance-Constrained Optimization(CCO).This 86

modeling choice has vast implications on the actual form of UUC,its potential robustness in the face 87

of uncertainty,the(expected)cost of the computed production schedules and the computational cost 88

of determining them.Hence,UUC is even less“well-solved”than UC,and a thriving area of research. 89

Therefore,a survey about it is both timely and appropriate.

We start with a review of the main recent contributions on solution methods for UC that have an impact 91

on those for the uncertain version.This is necessary,as the last broad UC survey[290]dates back some 92

10years,and is essentially an update of[349];neither of these consider UUC in a separate way as we 93

do.The more recent survey[127]provides some complements to[290]but it does not comprehensively 94

cover methods based on mathematical programming techniques,besides not considering the uncertain 95

variants.The very recent survey[337]focuses mainly on nature-inspired or evolutionary computing 96

approaches,most often applied to simple10-units systems which can nowadays be solved optimally 97

in split seconds with general-purpose techniques;furthermore these methods do not provide quali?ed 98

bounds(e.g.,optimality gap)that are most often required when applying SO,RO or CCO techniques to 99

the solution of UUC.This,together with the signi?cant improvement of solving capabilities of methods 100

based on mathematical programming techniques(e.g.,Lagrangian or Benders’decomposition methods, 101

Mixed Integer Linear Programming approaches,...),justi?es why in the UC-part of our survey we 102

mostly focus on the latter rather than on heuristic approaches.

103

Because the paper surveys such a large variety of material,we provide two di?erent reading maps to the 104

readers:

105

1.The?rst is the standard reading order of the paper,synthesized in the Table of Contents above. 106

In Section2we describe the varied technical and operational constraints in(U)UC models which 107

give rise to many di?erent variants of UC problems.In Section3we provide an overview of methods 108

that deal with the deterministic UC,focusing in particular onto methods dealing with large-scale 109

systems and/or that can be naturally extended to UUC,at least as subproblems.In particular,in 110

§3.1we discuss Dynamic Programming approaches,in§3.2we discuss Integer and Mixed Integer Lin-111

ear Programming(MILP)approaches,while in§3.3and§3.4we discuss decomposition approaches 112

(Lagrangian,Benders’and Augmented Lagrangian),and?nally in§3.5we(quickly)discuss(Meta-113

)Heuristics.UUC is then the subject of Section4:in particular,§4.2presents Stochastic Optimiza-114

tion(Scenario-Tree)approaches,§4.3presents Robust Optimization approaches,and§4.4presents 115

Chance-Constrained Optimization approaches.We end the paper with some concluding remarks in 116

§5,and with a list of the most used acronyms.

117

2.The second map is centered on the di?erent algorithmic approaches that have been used to solve 118

(U)UC.The main ones considered in this review are:

119

–

Dynamic Programming approaches,which can be found in §3.1,§3.2.2,§3.3,§3.5.2,§4.1.1.1,120§4.2.1,§4.2.3,§4.2.4,and §4.4;

121–Mixed-Integer Programming approaches,which can be found in §3.2,§3.3,§4.1.2.2,§4.2,§4.2.1,122§4.2.3,§4.2.4,§4.3,and §4.4;

123–Lagrangian Relaxation (decomposition)approaches,which can be found in §3.2.2,§3.3,§3.5.2,124§4.2.1,§4.2.2,§4.2.3,§4.2.4,and §4.4;

125–Benders’decomposition approaches,which can be found in §3.2.2,§3.3,§4.2,§4.2.1,§4.2.2,§4.2.3,126§4.2.4,and §4.3;

127–Augmented Lagrangian approaches,which can be found in §3.3,§3.4,and §4.4;

128–other forms of heuristic approaches,which can be found in §3.1,§3.2.2,§3.3,§3.5,§4.1.2.1,§4.2.2,129and §4.2.3.

130

2Ingredients of the Unit Commitment problem

131

We start our presentation with a very short description of the general structure of electrical systems,132presenting the di?erent decision-makers who may ?nd themselves in the need of solving (U)UC problems 133and their interactions.This discussion will clarify which of the several possible views and needs we will 134cover;the reader with previous experience in this area can skip to §2.1for a more detailed presentation of 135the various ingredients of the (U)UC model,or even to §3for the start of the discussion about algorithmic 136approaches.

137

Fig.1Simpli?ed electricity market structure

When the ?rst UC models were formulated,the usual setting was that of a Monopolistic Producer (MP).138The MP was in charge of the electrical production,transmission and distribution in one given area,often 139corresponding to a national state,comprised the regulation of exchanges with neighbouring regions.In 140the liberalized markets that are nowadays prevalent,the decision chain is instead decentralized and 141signi?cantly more complex,as shown in the (still somewhat simpli?ed)scheme of Figure 1.In a typical 142setting,companies owning generation assets (GENCOs)have to bid their generation capacity over one (or 143more)Market Operator(s)(MO).Alternatively,or in addition,they can stipulate bilateral contracts (or 144contracts for di?erences,CfD)with ?nal users or with wholesales/traders.Once received the bids/o?ers,145the MO clears the (hourly)energy market and de?nes (equilibrium)clearing prices.A Transmission 146System Operator (TSO),in possession of the transmission infrastructure,then has the duty—acting 147in concert with the Power Exchange Manager (PEM)—to ensure safe delivery of the energy,which in 148turns means di?erent duties such as real time frequency-power balancing,spinning reserve satisfaction,149voltage pro?le stability,and enforcing real-time network capacity constraints.The TSO typically operates

150

in a di?erent way programmable and non programmable units,since for instance only the former can 151

participate to balancing markets.

152

This basic setting,which can be considered su?cient for our discussion,is only a simpli?cation of the 153

actual systems,which also vary depending on their geographical position.For instance,transmission(and 154

distribution)assets may actually be in possession of di?erent companies that have to o?er them under 155

highly regulated fair and non-discriminative conditions,leaving the TSO only a coordination role.Also, 156

the TSO and the MO may or may not be the same entity,and so on.We leave aside these other factors, 157

like how many and MOs there are and how exactly these are structured;we refer to[94,173,281,346][91, 158

Chapter1]for a more detailed description.Because of this complexity,standard optimization models 159

may not be entirely appropriate to deal with all the aspects of the problem,since the behavior of 160

di?erent/competing decision makers need be taken into account.This may require the use of other 161

methodologies,such as the computation of equilibria or agent-based simulation.We will not deal with 162

any of these aspects,the interested reader being referred to[149,173,224,281,346,386]for further 163

discussion.

164

2.1A global view of UC

165

In broad terms,the(deterministic or uncertain)Unit Commitment problem(both UC in this section 166

unless explicitly stated)requires to minimize the cost,or maximize the bene?t,obtained by the pro-167

duction schedule for the available generating units over a given time horizon.As such,the fundamental 168

ingredients of UC are its objective function and its constraints.Of course,another fundamental ingredi-169

ent is the time horizon itself;UC being a short-term model this is most often a day or two of operations, 170

and up to a week.In the following we will denote it by T,which is typically considered to be a discrete 171

set corresponding to a?nite number of time instants t∈T,usually hours or half-hours(down to15or 172

5minutes).Thus,the typical size of T varies from24to a few hundred.

173

In mathematical terms,UC has the general structure

174

min

f(x):x∈X1∩X2,

(1)

where x∈R n is the decision making https://www.sodocs.net/doc/1214984295.html,ually(most)elements of x are indexed according to both 175

the generating unit i=1,...,m and the time instant t∈T they refer to.Thus,one often speaks of the 176

subvectors x t of all decisions pertaining to time t and/or x i of all decisions pertaining to unit i.Also, 177

entries of x are typically split among:

178

https://www.sodocs.net/doc/1214984295.html,mitment decision,discrete variables that determine if a particular unit is on or o?at any given 179

time(often denoted by u t i);

180

2.production decision,continuous variables that provide the amount of generated power by a speci?c 181

unit at a given time(often denoted by p t i);

182

https://www.sodocs.net/doc/1214984295.html,work decision,such as these representing phase angle or voltage magnitudes,describing the state 183

of the transmission or distribution network.

184

A UC problem not having commitment decisions is often called Economic Dispatch(ED)(e.g.[426]) 185

or Optimal Power Flow(OPF)when the network is considered,(e.g.[193]).It could be argued that 186

commitment decisions can be easily derived from production decisions(each time a non-zero production 187

output is present the unit has to be on),but for modeling purposed it is useful to deal with the two 188

di?erent concepts separately,cf.§3.2.Besides,the point is that in ED or OPF the commitment of units 189

has already been?xed and cannot be changed.We remark that network decisions may also include binary 190

variables that provide the open or close state of a particular line,as entirely closing a line is one of the 191

few options that the physic of electrical networks allows for“routing”the electrical current(cf.§2.7). 192

While ED can be expected to be simpler than UC,and in many cases it is a simple convex program 193

that can nowadays be solved with o?-the-shelf techniques,this is not always the case.ED was not only 194

challenging in the past(e.g.,[109]and the references therein),but can still be do so today.Indeed,even 195

when commitment decisions are ?xed,the electrical system is highly nonlinear and nonconvex,e.g.,due 196to hydro units e?ciency curves (cf.§2.4)or the transmission network characteristics (cf.§2.6),so that ED 197can still be a nontrivial problem that may require ad-hoc approaches (e.g.[185,192,193,213,254,279]).198In equation (1),X 1is the set modeling all technical/operational constraints of the individual units and 199X 2are the system-wide constraints .The ?rst set is by de?nition structured as a Cartesian product of

200smaller sets,i.e.,X 1= m i =1X 1

i ,with X 1i ?R n i and m i =1n i =n .Moreover,the objective function 201f typically also allows for a decomposition along the sets X 1

i ,i.e.,f (x )= m i =1f i (x i )and x i ∈X 1i

.202Each of the sets X 1

i roughly contains the feasible production schedules for one unit,that can di?er 203very signi?cantly between di?erent units due to the speci?c aspects related to their technological and 204operational characteristics.In most models,X 1is non-convex.However,units sharing the same funda-205mental operational principles often share a large part of their constraints as well.Because of this,these 206constraints are best described according to the type of the generating unit,i.e.,207

1.thermal units (cf.§

2.3);208 2.hydro units (cf.§2.4);

209 3.renewable generation units (cf.§2.3–2.5).

210

While hydro units are arguably a part of renewable generation,in the context of UC it is fundamental 211to distinguish between those units that are programmable and those that are not.That is,hydroelectric 212generation systems relying on a ?ow that can not be programmed are to be counted among renewable 213generation ones together with solar and wind-powered ones.This is unless these so-called run-of-river 214(ROR)units are part of a hydro valley ,preceded by a programmable hydro one (cf.§2.4).

215The set X 2,which usually models at least the o?er-demand equilibrium constraints,is most often,but not 216always,convex and even polyhedral.This set may also incorporate other system-wide constraints,such 217as emission constraints,network transmission constraints (cf.§2.6)or optimal transmission switching 218constraints (cf.§2.7).

219Solving (1)is di?cult when n is large (which usually means that m is large)or X 1is a complex set;the 220latter occurs e.g.when substantial modeling detail on the operations of units is integrated in the model.221Finally,(1)contains no reference to uncertainty,but several sources of uncertainty are present in actual 222operational environments,as summarized in the following table:

223

Data

Uncertain for Severity customer load GENCOs,TSO low/medium reservoirs in?ows GENCOs,TSO medium renewable generation GENCOs,TSO

high

prices/quantities GENCOs,traders,customers medium/high units/network failure

GENCOs,TSO

medium

224

Various ways to incorporate uncertainty in (1)are discussed in §4.1.Obviously,solving (1)becomes 225more di?cult when uncertainty is present,even when n is small and X 1relatively simple.Thus,properly 226exploiting the structure of the problem (the function f and the sets X 1and X 2)is crucial to obtain 227e?cient schemes for UC,and even more so for UUC.This is why we now provide some detail on di?erent 228modeling features for each of these components.

229

2.2The objective function

230

The objective function of UC is one of the main factors re?ecting the di?erent types of decision-makers 231described in the previous section.In fact,when the production needs to be satis?ed (as in the case of 232the MP,or of a GENCO having had a certain set of bids accepted)the objective function fundamentally 233aims at minimizing energy production costs ;this is not necessarily obvious (cf.the case of hydro units 234below),but the principle is clear.However,in the free-market regime the aim is typically rather to

235

maximize energy production pro?ts.This again requires estimating the costs,so the same objective as in 236

the MP case largely carries over,but it also requires estimating the revenues from energy selling,as it is 237

the di?erence between the two that has to be maximized.In particular,if the GENCO is a price maker 238

it may theoretically indulge in strategic bidding[103],whereby the GENCO withdraws power from the 239

market(by bidding it at high cost)in order to push up market prices,resulting in an overall diminished 240

production from its units but higher pro?t due to the combined e?ect of decreased production cost and 241

increased unitary revenue for the produced energy.Of course,the success of such a strategy depends on 242

the(unknown)behavior of the other participants to the market,which thereby introduces signi?cant 243

uncertainty in the problem.The electrical market is also highly regulated to rule out such behavior of the 244

market participants;in particular,larger GENCOs,being more easily price makers,are strictly observed 245

by the regulator and bid all their available capacity on the market.Yet,the solution of strategic bidding 246

problems is of interest at least to the regulators themselves,who need to identify the GENCOs who may 247

in principle exercise market power and identify possible patterns of abuse.Even in the price taker case, 248

i.e.,a GENCO with limited assets and little or no capacity to in?uence market prices,uncertainty is 249

added by the need of accurately predicting the selling price of energy for each unit and each t∈T[156]. 250

This uncertainty must then be managed,e.g.with techniques such as those of Robust Optimization[30]. 251

Energy production costs for fuel-burning units are typically modeled(in increasing order of complexity) 252

as linear,piecewise-linear convex,quadratic convex,or nonconvex functions separable for each t∈T. 253

In fact,while the fuel-consumption-to-generated-power curve can usually be reasonably well approxi-254

mated with a piecewise linear function or a low-order polynomial one,other technical characteristics of 255

generating systems introduce nonconvex elements.The simplest form is that of a?xed cost to be paid 256

whenever the unit is producing at some t∈T,irrespective of the actual amount of generated power. 257

In alternative,or in addition,start-up costs(and,less frequently,shut-down ones)are incurred when a 258

unit is brought online after a period of inactivity.In their simplest form start-up costs can be considered 259

?xed,but most often they signi?cantly depend on the time the unit has been o?before having been 260

restarted,and therefore are not separable for each time instant.The dependency of the start-up cost 261

on time can be rather complex,as it actually depends on the choice between the unit being entirely 262

de-powered(cooling)or being kept at an appropriate temperature,at the cost of burning some amount 263

of fuel during the inactivity period,to make the start-up cheaper(banking).Technically speaking,in the 264

latter case one incurs in a higher boiler cost to o?set part of the turbine cost.The choice between these 265

two alternatives can often be optimally made by simple formul?once the amount of idle time is known, 266

but this is typically not true beforehand in UC since the schedule of the unit is precisely the output of the 267

optimization problem.Fortunately,some of the solution methods allow inclusion of the start-up cost at 268

a relatively minor increase of the computational complexity;this is the case e.g.of MILP formulations, 269

cf.§3.2,exploiting the fact that the optimal start-up cost is nondecreasing as the length of the idle period 270

increases[75,277]).In other cases start-up cost have basically no additional computational cost,such as 271

in DP approaches,cf.§3.1.Other relevant sources of nonconvexity in the objective function are valve 272

points[406],corresponding to small regions of the feasible production levels where the actual working of 273

the unit is unstable,e.g.due to transitioning between two di?erent con?gurations in a combined-cycle 274

unit or other technical reasons,and that therefore should be avoided.

275

Nuclear units are generally considered thermal plants,although they signi?cantly di?er in particular 276

for the objective function.Indeed,fuel cost has a di?erent structure and depends on many factors,not 277

only technical but also political(e.g.,[112]).For convenience,formul?similar to that of conventional 278

thermal plants are often used.However,these units incur additional signi?cant modulation costs whenever 279

variations of power output are required;this cost is therefore again not separable per time instant.

280

Hydro units are generally assumed to have zero energy production cost,although they may in principle 281

have crew and manning costs.In the self-scheduling case,where pro?t has to be maximized,this would 282

lead to units systematically depleting all the available water due to the fact that a short-term model 283

such as UC has no“visibility”on what happens after the end of its time horizon T(the so-called“border 284

e?ect”).Because of this,often a value of water coe?cient is added to the objective function to represent 285

the expected value of reserves left in the reservoirs at the end of T.These values,as well as the required 286

reservoir levels(cf.2.4),are usually computed by means of speci?c mid-term optimization models.A very 287

standard approach is to value the di?erential between the initial and end volume of a reservoir against 288

a volume-dependent water value;we refer to[80,381]for details on various other modeling choices.A 289

particular di?culty appears when we wish to integrate the water head e?ect on turbining e?ciency 290

(e.g.,[132,316]),since this is typically a nonlinear and nonconvex relationship.

291

In general,the case of pro?t maximization requires knowledge of the selling and buying price of energy at 292

each t∈T.Because UC is solved ahead of actual operations,possibly precisely with the aim of computing 293

the bids that will contribute to the setting of these prices(cf.e.g.[60,65,210,320]),this requires nontrivial 294

forecast models in order to obtain reasonable estimates of the prices(e.g.[226,286,419]).Depending on 295

the time horizon and speci?c application,di?erent price models can be considered.These can be obtained 296

from time series modeling(e.g.[117,264,300]),mathematical?nance(e.g.[45,186,271,286,302])or can be 297

based on electricity fundamentals(e.g.[122,384]).For the case where the producer is a price taker,that 298

is,small enough so that its production can be deemed to have little or no e?ect on the realized prices,UC 299

can typically be independently solved for each individual unit(thus being styled as the self-scheduling 300

problem),and it is therefore much easier[16],although uncertainty in prices then becomes a critical 301

factor[30,93,275].Things are signi?cantly di?erent in case the producer can exercise market power,that 302

is,in?uence(increase)the prices by changing(withdrawing)the power it o?ers to the market;modeling 303

this e?ect“ties”all the units back again into an unique UUC[65,92,105,303].Uncertainty in this case is 304

also very relevant,with the behavior of competitors being one obvious primary source[7,307,389,396,401]. 305

The matter is further complicated by the fact that the structure of the PE is usually complex,with more 306

than one auction solved in cascade to account for di?erent kinds of generation(energy,reserve,ancillary 307

services,...)[23,370,395]and by the fact that tight transmission constraints may create zonal or even 308

nodal prices,thereby allowing producers who may not have market power in the global context to be 309

able to exercise it in a limited region[227,301,303].

310

2.3Thermal units

311

A thermal power station is a power plant in which the prime mover is steam driven.Technical/operational 312

constraints can be classi?ed as either static or dynamic:the former hold on each time step,whereas the 313

latter link di?erent(most often adjacent)time steps.Most typical static constraints are:

314

1.O?ine:when the unit is o?ine,the power output is less than or equal to zero(negative power output 315

refers to the power used by auxiliary installations,e.g.,for nuclear plants).

316

2.Online:when the unit is online,the power output must be between Minimal Stable Generation(MSG) 317

and maximal power output.

318

3.Starting:the unit is ramping up to MSG.The ramping pro?le depends on the number of hours a 319

unit has been o?ine(e.g.[214]);see also in starting curve below.A unit in this state can in principle 320

still be disconnected for a later start,but at a cost.

321

4.Stopping:the unit ramps down from MSG to the o?ine power output.As for starting,the ramping 322

pro?le depends on the number of hours a unit has been online;see below in stopping curve.

323

5.Generation capacity:the production capacity of each unit.For some units the production output has 324

to be selected among a discrete set of values.

325

6.Spinning reserve:the extra generating capacity that is available by increasing the power output of 326

generators that are already connected to the power system.For most generators,this increase in 327

power output is achieved by increasing the torque applied to the turbine’s rotor.Spinning reserves 328

can be valued separately from actively generated power as they represent the main mechanism that 329

electrical systems have to cope with real-time variations in demand levels.

330

7.Crew constraint:number of operators available to perform the actions in a power plant.

331

Typical dynamic constraints instead are:

332

1.Minimum Up/Down Time:a unit has to remain online/o?ine for at least a speci?c amount of time. 333

2.Operating Ramp Rate(also known as ramp-down and ramp-up rate):the increment and decrement 334

of the generation of a unit from a time step to another,excluding start-up and shut-down periods, 335

must be bounded by a constant(possibly di?erent for ramp-up and ramp-down).

336

3.Minimum Stable State Duration:a unit that has attained a speci?c generation level has to produce 337

at that level for a minimum duration of time.

338

4.Maximum Numbers of Starts:the number of starts can be limited over a speci?c time horizon(such 339

a constraint is also implicitly imposed by Minimum Up/Down Time ones,and in fact the two are 340

often alternatives).

341

5.Modulation and Stability:these constraints are mainly applied to an online nuclear unit.A unit is 342

in modulation if the output level changes in a time interval,whereas it is stable if the power level 343

remains identical to that of the previous time step.The constraints ensure that the unit is“most 344

often stable”,requiring that the number of modulations does not exceed a prede?ned limit over a 345

given time span(say,24hours).

346

6.Starting(Stopping)Curve(also referred to in literature as start-up/shut-down ramp rate):in order to 347

start(stop)a unit and move it from the o?ine(online)state to the online(o?ine)state,the unit has 348

to follow a speci?c starting(stopping)curve,which links o?ine power output(zero,or negative for 349

nuclear plants)to MSG(or vice-versa)over the course of several time steps.Each starting(stopping) 350

curve implies a speci?c cost,and the chosen curve depends on the number of hours the plant has 351

been o?ine(online).Starting(stopping)may take anything from several minutes(and therefore be 352

typically irrelevant)up to24hours(and therefore be pivotal for the schedule).

353

2.4Hydro units

354

Hydro units are in fact entire hydro valleys,i.e.,a set of connected reservoirs,turbines and pumps that 355

in?uence each other through?ow constraints.Turbines release water from uphill reservoirs to downhill 356

ones generating energy,pumps do the opposite.Note that the power output of ROR units downstream to 357

a reservoir(and up to the following reservoir,if any)must be counted together with that of the turbines 358

at the same reservoir;usually it is possible to do this by manipulating the power-to-discharged-water 359

curve of the unit at the reservoir,and thus ROR units in a hydro valley need not be explicitly modeled. 360

We remark in passing that whether or not a unit is considered ROR depends on the time horizon of the 361

problem:units with small reservoirs can be explicitly modeled in UC because they do have a degree of 362

modulation over the short term,but they may be considered ROR in longer-term problems since the 363

modulation is irrelevant over long periods of time.

364

As for thermal units,we distinguish constraints as being either static or dynamic.The typical ones of 365

the?rst kind are:

366

1.Reservoir Level:the level of water in each reservoir has to remain between a lower and upper bound. 367

Frequently these bounds are used to re?ect strategic decisions corresponding to optimal long-term 368

use of water(cf.§2.2),and not necessarily re?ect physical bounds.An alternative is to use a nonlinear 369

cost of water that re?ects the higher risk incurred in substantially depleting the reservoir level,as 370

water in hydro reservoirs represents basically the only known way of e?ciently storing energy on a 371

large scale and therefore provides a crucial source of?exibility in the system.Yet,bounds on the 372

level would ultimately be imposed anyway by physical constraints.

373

2.Bounds:turbines and pumps can operate only within certain bounds on the?owing water.In par-374

ticular,some turbines might have a minimal production level akin to the MSG of thermal units.

375

The most common dynamic constraints are:

376

1.Flow Equations:these equations involve the physical balance of the water level in each reservoir and 377

connect the various reservoirs together.The reservoir levels get updated according to natural in?ows, 378

what is turbined downhill,what is spilled downhill(i.e.,let go from the reservoir to the next without 379

activating the turbines),and what is pumped from downhill to uphill.Spilling might not be allowed 380

for all reservoirs,nor all have pumping equipment.

381

2.Flow delay:the water?owing(uphill or downhill)from each unit to the next reservoir will reach it 382

after a given delay,that can possibly be of several hours(and occasionally even more[34]).

383

3.Ramp Rate:adjacent turbining levels have to remain su?ciently close to each other.

384

4.Smooth Turbining:over a a given time span(e.g.,one hour),turbining output should not be in 385

a V-shape,i.e.,?rst increase and immediately afterwards decrease(or vice-versa).This constraint 386

is typically imposed to avoid excessive strain on the components,similarly to several constraints 387

on thermal units such as Minimum up/down Time,Maximum Numbers of Starts,Modulation and 388

Stability.

389

5.Turbining/Pumping Incompatibility:some turbines are reversible and therefore pumping and turbin-390

ing cannot be done simultaneously.Moreover,switching from turbining to pumping requires a certain 391

delay(e.g.,30minutes).Some of these constraints actually only refer to a single time instant and 392

therefore they can be considered as static.

393

6.Forbidden Zones:in complex hydro units,e?ects like mechanical vibrations and cavitation strongly 394

discourage using certain intervals of turbined water,as these would result in low e?ciency and/or 395

high output variation(similarly to valve points in thermal units,cf.§2.2).Therefore,constraints that 396

impose that the turbined water lies outside of these forbidden zones might have to be imposed[130]. 397

2.5Renewable generation units

398

Renewable generation in UC mostly refers to wind farms,solar generation,stand alone ROR hydro 399

units,and geothermal production.The fundamental characteristic of all these sources,as far as UC is 400

concerned,is the fact that they cannot be easily modulated:the produced energy,and even if energy is 401

produced at all(in some wind farms energy is actually consumed to keep the blades in security when wind 402

blows too strongly),is decided by external factors.Some of these sources,most notably solar and wind, 403

are also characterized by their intermittency;that is,it is very di?cult to provide accurate forecasts for 404

renewable generation,even for short time horizons(say,day-ahead forecasts).Furthermore,in several 405

cases renewable generation operates in a special regulatory regime implying that they cannot even be 406

modulated by disconnecting them from the grid.This has(not frequently,but increasingly often)led to 407

paradoxical situations where the spot price of energy is actually negative,i.e.,one is paid to consume 408

the energy that renewable sources have the right to produce(and sell at?xed prices)no matter what 409

the demand actually is.All this has lead to signi?cant changes in the operational landscape of energy 410

production systems,that can be summarized by the following factors:

411

1.The total renewable production cannot be predicted accurately in advance.

412

2.Renewable generation has high variance.

413

3.The correlation between renewable generation and the load can be negative,which is particularly 414

troublesome when load is already globally low,since signi?cant strain is added to conventional gen-415

eration assets which may have to quickly ramp down production levels,only to ramp them up(again 416

rapidly)not much later.This goes squarely against most of the standard operational constraints in 417

classical UC(cf.§2.3and§2.4).

418

In other words,in UC terms renewable generation signi?cantly complicates the problem;not so much 419

because it makes its size or structure more di?cult,but because it dramatically increases the level of 420

uncertainty of net load(the load after the contribution of renewables is subtracted),forcing existing 421

generation units to serve primarily(or at least much more often than they were designed to)as backup 422

production in case of?uctuations,rather than as primary production systems.This increases the need 423

of?exible(hydro-)thermal units ready to guarantee load satisfaction at a short notice,which however 424

typically have a larger operational cost.We refer to[67,252,261,341,355]for further discussion of the 425

integration of renewable generation in UC.

426

2.6System-wide constraints

427

The most common form of system-wide constraints are the load constraints guaranteeing that global en-428

ergy demand is exactly satis?ed for each t∈T.This kind of constraint is not present in the self-scheduling 429

version of UC where each unit reacts independently to price signals,but global load satisfaction has to 430

be taken into account,sooner or later,even in liberalized market regimes.For instance,in several coun-431

tries,after the main energy market is cleared,GENCOs can swap demand between di?erent units in 432

order to better adjust the production schedules corresponding to the accepted bids to the operational 433

constraints of their committed units,that are not completely represented in the auctions[318].Alter-434

natively,or in addition,an adjustment market is ran where energy can be bought/sold to attain the 435

same result[291,340].In both these cases the production schedules of all concerned units need be taken 436

into account,basically leading back to global demand constraints.Also,in UC-based bidding systems 437

the global impact of all the generation capacity of a GENCO on the energy prices need to be explicitly 438

modeled,and this again leads to constraints linking the production levels of all units(at least,these 439

of the given GENCO)that are very similar to standard demand constraints.Conversely,even demand 440

constraints do not necessarily require the demand to be fully satis?ed;often,slacks are added so that 441

small amounts of deviation can be tolerated,albeit at a large cost(e.g.,[119,418]).

442

Another important issue to be mentioned is that the demand constraints need in general to take into 443

account the shape and characteristics of the transmission network.These are typically modeled at three 444

di?erent levels of approximation:

445

–The single bus model:basically the network aspects are entirely disregarded and the demand is 446

considered satis?ed as soon as the total production is(approximately)equal to the total consumption, 447

for each time instant,irrespectively of where these happen on the network.This corresponds to simple 448

linear constraints and it is the most common choice in UC formulations.

449

–The DC model where the network structure is taken into account,including the capacity of the trans-450

mission links,but a simpli?ed version of Kirchho?laws is used so that the corresponding constraints 451

are still linear,albeit more complex than in the bus model[137,194,218].In[15]the concept of 452

umbrella constraints is introduced to de?ne a subset of the network DC constraints that are active 453

in order to signi?cantly reduce the size of these constraints.

454

–The AC model where the full version of Kirchho?laws is used,leading to highly nonlinear and 455

nonconvex constraints,so that even the corresponding ED becomes di?cult[255,256,265,356,357]. 456

A recent interesting avenue of research concerns the fact that the non-convex AC constraints can 457

be written as quadratic relations[192,193,213],which paves the way for convex relaxations using 458

semide?nite programming approaches[254].In particular,in the recent[187]a quadratic relaxation 459

approach is proposed which builds upon the narrow bounds observed on decision variables(e.g.phase 460

angle di?erences,voltage magnitudes)involved in power systems providing a formulation of the AC 461

power?ows equations that can be better incorporated into UC models with discrete variables,notably 462

the ones of cf.§2.7.A recount of these recent developments can be found in[55].

463

Although market-based electrical systems have in some sense made network constraints less apparent to 464

energy producers,they are nonetheless still very relevant nowadays;not only in the remaining vertically 465

integrated electrical systems,but also for the TSO that handles network security and e?ciency.This 466

requires taking into account a fully detailed network model,even considering security issues such as N?1 467

fault resilience,together with a reasonably detailed model of GENCOs’units(comprising e.g.infra-hour 468

power ramps,start-up costs,and start-up/shut-down ramp rate),when solving the Market Balancing 469

problem.The latter is basically a residual demand,bidding-based UC.From a di?erent perspective, 470

network constraints might also be important for GENCOs that are able exercise market power in case 471

zonal or nodal pricing is induced by the network structure[312].

472

Finally,both for vertically integrated system and in the TSO perspective,other relevant system-wide 473

constraints are spinning reserve ones:the committed units must be able to provide some fraction(at 474

least3%according to[367])of the total load in order to cope with unexpected surge of demand or 475

failures of generating units and/or transmission equipment.Other global constraints linking all units, 476

or some subsets of them,exist:for instance,all(or speci?c subsets of)fossil-fuel burning units may 477

have a maximum cap on the generation of pollutants(CO2,SO x,NO x,particles,...)within the time 478

horizon[148,158,190,209,399].Alternatively,a cluster of geographically near units(a plant)burning 479

the same fuel(typically gas)may be served by a unique reservoir,and can therefore share a constraint 480

regarding the maximum amount of fuel that can be withdrawn from the reservoir within the time horizon 481

[11,12,87,148,369].Finally,there may be constraints on the minimum time between two consecutive 482

start-ups in the same plant[119],e.g.,due to crew constraints.If a plant comprises a small enough 483

number of units it could alternatively be considered as a single“large”unit,so that these constraints 484

become technical ones of this aggregated generator.The downside is that the problem corresponding to 485

such a meta-unit then becomes considerably more di?cult to solve.

486

2.7Optimal Transmission Switching

487

Traditionally,in UC models the transmission network has been regarded as a“passive”element,whose 488

role was just to allow energy to?ow from generating units to demand points.This is also justi?ed by 489

the fact that electrical networks,unlike most other networks(logistic,telecommunications,gas,water, 490

...)are“not routable”:the current can only be in?uenced by changing nodal power injection,which 491

is however partly?xed(at least as demand is concerned).Indeed,in traditional UC models there were 492

no“network variables”,and the behavior of the transmission system was only modeled by constraints. 493

However,as the previous paragraph has recalled,the transmission network is by far not a trivial element 494

in the system,and separate network variables are required.Recently,the concept has been further 495

extended to the case where the system behavior can be optimized by dynamically changing the topology 496

of the network.This is a somewhat counterintuitive consequence of Kirchho?laws:opening(interrupting) 497

a line,maybe even a congested one,causes a global re-routing of electrical energy and may reduce the 498

overall cost,e.g.by allowing to increase the power output of some cheaper(say,renewable)units[134]. 499

This e?ect can be especially relevant in those parts of the network with a high fraction of renewables 500

whose production is sometimes cut o?because of network constraints.

501

Thus,a new class of problems,called Optimal Transmission Switching(OTS)or System Topology 502

Optimization(STO),has been de?ned whereby each line of the network has an associated binary decision 503

(for each t∈T)corresponding to the possibility of opening it.This makes the problem di?cult to solve 504

even with a very simple model of nodal injections and a simple network model such as the DC one 505

(cf.§2.6);even more so with the AC model and a complete description of the generating units.The 506

so-called UCOTS models[56,134,174–177,207,232,233,243,280,284,285,298,327,388,420]extend UC: 507

almost everything that can be said about UC is a fortiori valid for UCOTS,and therefore in the following 508

we will not distinguish between the two unless strictly necessary.

509

3Methods for the deterministic Unit Commitment

510

We now proceed with a survey of solution methods for(the deterministic)UC.Our choice to?rst focus 511

on the case where the several forms of uncertainty arising in UC(cf.§2.1)are neglected is justi?ed by 512

the following facts:

513

–UC already being a rather di?cult problem in practice,most work has been carried out in the 514

deterministic setting;

515

–uncertainty can be taken into account through various“engineering rules”:for instance,spinning 516

reserves allow to account for uncertainty on load,tweaking reservoir volumes might allow to account 517

for uncertainty on in?ows,and so on;

518

–methods for solving the deterministic UC are bound to provide essential knowledge when dealing 519

with UUC.

520

As discussed in Section2,UC is not one speci?c problem but rather a large family of problems exhibiting 521

common features.Since the set of constraints dealt with in the UC literature varies from one source to 522

another,we de?ne what we will call a basic Unit Commitment problem(bUC)which roughly covers the 523

most common problem type;through the use of tables we will then highlight which sources consider 524

additional constraints.A bUC is a model containing the following constraints:

525

1.o?er-demand equilibrium;

526

2.minimum up or down time;

527

3.spinning reserve;

528

4.generation capacities.

529

The UC literature review[349],of which[290]is essentially an update adding heuristic approaches, 530

generally classify UC methodology in roughly eight classes.We will essentially keep this distinction,but 531

regroup all heuristic approaches in“Meta-Heuristics”,thus leading us to a classi?cation in:

532

1.Dynamic Programming;

533

https://www.sodocs.net/doc/1214984295.html,P approaches;

534

3.Decomposition approaches;

535

4.(Meta-)Heuristics approaches.

536

We will also add some of the early UC approaches in the Heuristic class such as priority listing.However, 537

we will not delve much on that class of approaches,since the recent surveys[127,337]mainly focus 538

on these,while providing little(or no)details on approaches based on mathematical programming 539

techniques,that are instead crucial for us in view of the extension to the UUC case.

540

3.1Dynamic Programming

541

Dynamic Programming(DP,see e.g.[33,49,50])is one of the classical approaches for UC.As discussed 542

below,it is nowadays mostly used for solving subproblems of UC,often in relation with Lagrangian-543

based decomposition methods(cf.§3.3);however,attempts have been made to solve the problem as a 544

whole.There have been several suggestions to overcome the curse of dimensionality that DP is known 545

to su?er from;we can name combinations of DP and Priority Listing(DP-PL)[189,361],Sequential 546

Combination(DP-SC)[293],Truncated Combination(DP-TC)[292],Sequential/Truncated Combination 547

(DP-STC)(the integration of the two aforesaid methods)[293],variable window truncated DP[287], 548

approximated DP[104]or even some heuristics such as the use of neural network[287]or arti?cial 549

intelligence techniques[392].The multi-pass DP approach[124,416]consists of applying DP iteratively, 550

wherein in each iteration the discretization of the state space,time space and controls are re?ned around 551

the previously obtained coarse solution;usually,this is applied to ED,i.e.,once commitment decisions 552

have been?xed.In[293]three of the aforesaid methods,DP-PL,DP-SC,and DP-STC are compared 553

against a priority list method on a system with96thermal units,showing that the DP-related approaches 554

are preferable to the latter in terms of time and performance.The recent[359]performs a similar study 555

on a bUC with10thermal units,but only DP approaches are investigated.

556

Despite its limited success as a technique for solving UC,DP is important because of its role in deal-557

ing with sub-problems in decomposition schemes like Lagrangian relaxation.These typically relax the 558

constraints linking di?erent unit together,so that one is left with single-Unit Commitment(1UC) 559

problems,i.e.,self-scheduling ones where the unit only reacts to price signals.In the“basic”case of 560

time-independent startup costs1UC can be solved in linear time on the size of T.When dealing with 561

time-dependent startup costs instead,this cost becomes quadratic[29,427].However,this requires that 562

the optimal production decisions p i t can be independently set for each time instant if the corresponding 563

commitment decision u i t is?xed,which is true in bUC but not if ramp rate constraints are present.It is 564

possible to discretize power variables and keep using DP[32],but the approach is far less e?cient and the 565

determined solution is not guaranteed to be feasible.An e?cient DP approach for the case of ramp rate 566

constraints and time-dependent startup costs has been developed in[126]under the assumption that the 567

power production cost is piecewise linear.This has been later extended in[142]for general convex cost 568

functions;under mild conditions(satis?ed e.g.,in the standard quadratic case),this procedure has cubic 569

cost in the size of T.DP has also been used to address hydro valley subproblems in[360]where a three 570

stage procedure is used:?rst an expert system is used to select desirable solutions,then a DP approach 571

is used on a plant by plant basis,and a?nal network optimization step resolves the links between the 572

reservoirs.In[334]expert systems and DP are also coupled in order to solve UC.We also mention the 573

uses of expert systems in[253].

574

Most often DP approaches are applied to bUC,but other constraints have been considered such as 575

multi-area,fuel constraint,ramp rates,emission constraints,and hydro-thermal systems.We refer to 576

Table1for a complete list.

577

Table1Sources using Dynamic Programming

Basic UC Additional UC constraints

Must Fixed Crew Ramp Operating Maint-Hydro Fuel Emission

Run/O?Generation Constr.Rate Reserve nance-Thermal Const.

[292][293][287][292][288][292][292][142][143][360][253][143][360][4][190]

[288][142][143][126][253]

[126][360][334][392]

[253][359][32]

3.2Integer and Mixed Integer Linear Programming

578

3.2.1Early use:exhaustive enumeration

579

As its name implies,this approach focuses on a complete enumeration of the solution space in order to 580

select the solution with the least cost.bUC is addressed in[172,204],while in[172]the cost function 581

considers penalties for loss of load and over production.In[204]a set of12thermal units on a two hour 582

basis is scheduled.In[172]a problem with two groups,each of which has5thermal units is analyzed. 583

This traditional approach obviously lacks scalability to large-scale systems.However,some enumeration 584

may?nd its way into hybrid approaches such as decomposition methods under speci?c circumstances, 585

like in[132]where enumeration is used in some of the subproblems in a decomposed hydro valley system. 586

3.2.2Modern use of MILP techniques

587

With the rise of very e?cient MILP solvers,MILP formulations of UC have become common.In general, 588

their e?ciency heavily depends on the amount of modeling detail that is integrated in the problem. 589

Early applications of MILP can be found in[88,151,263],and in[88]it is stated that the model could be 590

extended to allow for probabilistic reserve constraints.Hydro-thermal UC is considered in[114,304,348] 591

where constraints regarding hydro units such as?ow equations,storage level of reservoirs,pump storage 592

and min and max of out?ow of each reservoir are incorporated in the model.

593

Some speci?c constraints such as the number of starts in a day or particular cost functions with integrated 594

banking costs can be found in[212,376].In[212]the authors combine Lagrangian relaxation(e.g.,[262]) 595

with a B&B procedure in order to derive valid bounds to improve the branching procedure.The upper 596

bound is derived by setting up a dynamic priority list in order to derive feasible solutions of the UC and 597

hence provide upper bounds.It is reported that a250unit UC was solved up to1%of optimality in less 598

than half an hour,a signi?cant feat for the time.A similar approach is investigated in[299],where a 599

heuristic approach using,among things,temporal aggregation is used to produce a good quality integer 600

feasible solution to warm-start a B&B procedure.

601

While MILP is a powerful modeling tool,its main drawback is that it may scale poorly when the 602

number of units increases or when additional modeling detail is integrated.To overcome this problem it 603

has been combined with methods such as DP[61],logic programming[191]and Quadratic Programming 604

(QP)[345].In[345]a hydro-thermal UC with various constraints is solved;a customized B&B procedure 605

is developed wherein binary variables are branched upon according to their di?erence from bounds. 606

The approach does not require any decomposition method,and it is reported to reduce solution time 607

signi?cantly in comparison to other methods.The paper builds upon[147],where a six-step solution is 608

proposed to solve large-scale UC;the algorithm is reported to be capable of solving security-constrained 609

problems with169,676and2709thermal units in27s,82s and8minutes,respectively.This so-called 610

Fast-Security Constraint Unit Commitment problem(F-SCUC)method is based on an ad-hoc way of 611

?xing binary variables and gradually unlock them if needed,using Benders-type cuts to this e?ect. 612

However,in[143]it is reported that MILP models where the objective function is piecewise-linearly 613

approximated are much more e?ective than the direct use of MIQP models,at least for one speci?c 614

choice and version of the general-purpose MIQP solver.In[145]MILP and Lagrangian methods are 615

combined,solving problems with up to200thermal units and100hydro units in a few minutes if the 616

desired accuracy is set appropriately.

617

Systems with a signi?cant fraction of hydro generation require a speci?c mention due to a notable char-618

acteristic:the relationship between the power that can be generated and the level of the downstream 619

reservoir(head-to-generated-power function),that can be highly nonlinear[76],and in particular noncon-620

vex.This can be tackled by either trying to?nd convex formulations for signi?cant special cases[417], 621

developing ad-hoc approximations that make the problem easier to solve[77],or using the modeling 622

features of MILP to represent this(and other nonconvex)feature(s)of the generating units[83,306]. 623

However,developing a good approximation of the true behavior of the function is rather complex be-624

cause it depends on both the head value of the reservoir and the water?https://www.sodocs.net/doc/1214984295.html,P models for accurately 625

representing this dependency have been presented in[197],and more advanced ones in[63]using ideas 626

from[98];while they are shown to signi?cantly improve the quality of the generated schedules,this 627

feature makes UC markedly more complex to solve.

628

3.2.3Recent trends in MILP techniques

629

Recently,MIP(and in particular MILP)models have attracted a renewed attention due to a number 630

of factors.Perhaps the most relevant is the fact that MILP solvers have signi?cantly increased their 631

performances,so that more and more UC formulations can be solved by MILP models with reasonable 632

accuracy in running times compatible with actual operational use[75].Furthermore,selected nonlinear 633

features—in particular convex quadratic objective functions and their generalization,i.e.,Second-Order 634

Cone Constraints—are nowadays e?ciently integrated in many solvers,allowing to better represent some 635

of the features of the physical system.This is especially interesting because MIP models are much easier 636

to modify than custom-made solution algorithms,which—in principle—allow to quickly adapt the model 637

to the changing needs of the decision-makers.However,it has to be remarked that each modi?cation 638

to the model incurs a serious risk of making the problems much more di?cult to solve.Two somewhat 639

opposite trends have recently shown up.On one side,tighter formulations are developed that allow to 640

more e?ciently solve a given UC problem because the continuous relaxation of the model provides better 641

lower bounds.On the other hand,more accurate models are developed which better re?ect the real-world 642

behavior of the generating units and all the operational?exibility they possess(cf.e.g.[188,236,245]), 643

thereby helping to produce better operational decisions in practice.

644

On the?rst stream,the research has focused on?nding better representations of signi?cant fragments 645

of UC formulations.For instance,[257,282]develop better representations of the polyhedra describing 646

minimum up-and down-time constraints and ramping constraints,whereas[144,196,408]focus on better 647

piecewise-linear reformulations of the nonlinear(quadratic)power cost function of thermal units.Both 648

approaches(that can be easily combined)have been shown to increase the e?ciency of the MILP solver 649

for a?xed level of modeling detail.

650

The second stream rather aims at improving the accuracy of the models in representing the real-world 651

operating constraints of units,that are often rather crudely approximated in standard UC formulations. 652

For hydro units this for instance concerns technical constraints[83]and the already discussed water-653

to-produced-energy function,with its dependency from the water head of the downstream reservoir 654

[63,132,306].For thermal units,improvements in the model comprise the correct evaluation of the 655

power contribution of the start-up and shut-down power trajectories(when a unit is producing but no 656

modulation is possible)[17],which may make the model signi?cantly more di?cult unless appropriate 657

techniques are used[258],or a clearer distinction between the produced energy and the power trajectory 658

of the units[150,259].

659

In the OTS context(cf.§2.7),special care must be given when modeling the Kirchho?laws,as this leads 660

to logic constraints that,in MILP models,are typically transformed into“Big-M”(hence,weak)linear 661

constraints.Moreover,severe symmetry issues[283]must be faced[243,285],as these can signi?cantly 662

degrade the performances of the B&B approach.All these di?culties,not shared by UC with DC 663

or AC network constraints,require a nontrivial extension of the“classic”MILP UC models.Many 664

approaches use o?-the-shelf B&B solvers,while possibly reducing the search space of the OTS binary 665

variables[233,284,327]and using tight formulations for the thermal units constraints.All the references 666

use classic quadratic cost functions;one exception can be found in[243],where a direct MILP approach 667

is combined with a perspective cuts approximation[144]and a special perturbation of the cost function 668

that successfully breaks(part of the)symmetries.Together with heuristic branching priorities that give 669

precedence to the thermal UC status variables,this is shown to be much better than using a classic 670

quadratic function,with or without perturbations,for solving the IEEE118test case.

671

Table2Sources using MILP approaches

Basic UC Additional UC constraints

Must Trans Modul-Starts Hot/Cold Ramp Hydro-Water-Thermal-Fuel Emission

Run/Off.-OTS-ation Starts Rate Thermal head Stress [114,151,263][114][134,304][114][376][212][191,345][345,348][306,417][228][236][236] [61,115,376][144][236,243][75,145][114,304][63,83]

[171,304,348][145][176,177][236,282][145,274][132]

[88,191,212][298,327][144,257][144]

[245,345][280,285][17,196]

[233,284][150,258]

[207,232][150,259]

[174,175]

[420]

3.3Lagrangian and Benders Decomposition

672

UC possesses several forms of structure that can be algorithmically exploited;the most obvious one 673

is that(complex)units are usually coupled through demand and reserve requirements(the set X2in 674

(1)).Since these constraints are usually in limited number and“simple”,Lagrangian Decomposition(or 675

Relaxation,LR)[140,167,220]is an attractive approach and has been widely used.It is based on relaxing 676

these coupling constraints by moving them in the objective function,weighted by appropriate Lagrangian 677

multipliers,so that the relaxed problem then naturally decomposes into independent subproblems for 678

each individual unit(1UC);for an arbitrary set of Lagrangian multipliers,the solution of all the1UCs 679

provides a lower bound on the optimal value of(1).Moreover the mapping(called the dual function, 680

or Lagrangian function)assigning this optimal value to a given set of Lagrangian multipliers is concave; 681

maximizing it,i.e.,?nding the best possible lower bound,is therefore a convex optimization problem for 682

which e?cient algorithms exists.

683

Two technical points are crucial when developing a LR approach:

684

–how the maximization of the Lagrangian function,i.e.,the solution of the Lagrangian Dual(LD),is 685

performed;

686

–since(1)is in general nonconvex the approach cannot be expected to provide an optimal(or even 687

feasible)solution,so methods to recover one have to be developed.

688

Regarding the?rst point,one can rely on the available well-developed theory concerning minimiza-689

tion of convex nondi?erentiable functions.Standard approaches of this kind are subgradient meth-690

ods[100,270,308]and the cutting plane method(CP)[203],also known as the Dantzig-Wolfe decomposi-691

tion method[101].Early examples of the use of subgradient methods in UC are[29,47,135,248,262,427], 692

possibly with modi?cations such as successive approximation techniques[87]or variable metric ap-693

proaches[12].An early example of the use of CP is[2].The two approaches are rather di?erent:subgra-694

dient methods use very simple rules to compute the next dual iterate,whereas CP uses(possibly costly) 695

Linear Programming(LP)problems for the same task,although hybrid versions have been devised[369]. 696

This is necessary in practice because both approaches have convergence issues,for di?erent reasons:sub-697

gradient methods lack an e?ective stopping criterion,whereas CP tends to be unstable and converge 698

slowly.This is why variants of CP have been devised,e.g.,using Interior Point ideas to provide some 699

stabilizing e?ect[118];for an application to UC see[244].In[332]the KKT conditions of the Lagrange 700

function are used in order to update the Lagrange multipliers and improve on subgradient approaches. 701

In[319]CP is stabilized by a trust region.The latter turns out to be a special case of the most e?ective 702

family of approaches capable of dealing with this kind of problems,that is,(generalized[139])Bundle 703

methods[219,402].These can be seen as a“mix”between subgradient and CP[22]which inherits the 704

best properties of both[68].Several variants of Bundle approaches exist,see e.g.[18,221,222];a recent 705

development that is particularly useful for UC is that of methods that allow the inexact solution of the 706

Lagrangian relaxation[106,107,206].This feature is of particular interest if operational considerations 707

impose strong restrictions on the solution times for the subproblems.For early application of Bundle 708

methods to UC see e.g.,[64,65,128,159,223,242,421].

709

Regarding the second point,one important property of LDs of non-convex programs is that,while 710

they cannot be guaranteed to solve the original problem,they indeed solve a“convexi?ed version”of 711

it[140,220].In practice,this typically corresponds to a solution?x=(?p,?u)to(1)that is feasible for all 712

constraints except the integrality ones.That is,rather than feasible commitment decisions u i t∈{0,1}one 713

obtains pseudo-schedules?u i t∈[0,1]that satisfy the constraints with the production decisions?p.Such 714

a solution can be obtained basically for free by(appropriately instrumented versions of)subgradient 715

methods[10,28]and all other algorithms,most notably Bundle ones[128].The pseudo-schedule?x can 716

for instance be heuristically interpreted as the probability that unit i be on at instant t,and then be 717

used in this guise to devise primal recovery approaches to attain feasible solutions of(1),either by 718

appropriately modifying the objective function[99,119]or by a heuristic search phase that exploits both 719

?x and the integer solutions produced by the LR[31,143,333].

720

Along with early papers which address the bUC[47,135,248,262],we mention papers which address large-721

scale UC[47,248].The authors of[248]are among the?rst who tried to use LR to obtain a solution, 722

and not just to obtain lower bounds for B&B procedures,solving a problem of172units.In[212]the 723

duality gap problem is tackled by approximating the dual problem with a twice-di?erentiable mapping 724

which is then maximized by using a constrained Newton’s method,after which a heuristic is used to 725

recover a nearly optimal primal solution;a200units UC is solved in about10to12minutes.In a 726

subsequent work[348],a three-stage approach is proposed to deal with a—for the time—large-scale 727

hydro-thermal system(100thermal units and6hydro ones).The?rst stage is based on LR,with the 728

thermal1UCs solved using DP,while the hydro subproblems are solved by using a penalty multipliers 729

method[208]and a specially tailored Newton’s method.A“unit decommitment”method is suggested 730

in[225,373]where all units are considered online over all T and then,using the results of the LR,units 731

are decommitted one at a time.This method aims at providing feasible primal solutions?rst,whereas 732

most LR approaches would aim at optimality?rst.Further references using LR are[129,164,335,336], 733

which consider speci?c dedicated approaches in order to tackle the subproblems,elementary ways of 734

updating the dual and heuristics to recover a primal feasible solution.In[162]the units cost functions 735

are modi?ed in order to reduce the oscillating behavior of subgradient approaches.In[159]the authors 736

compare a primal MIP based approach with a LR-based approach:Bundle methods are used in order to 737

solve the LD and two Lagrangian heuristics are investigated for primal recovery.The?rst one searches 738

for time steps where demand constraints are most violated and employs a strategy proposed in[427]for 739

changing the commitment variables,while the second one exploits nearly optimal Lagrange multipliers 740

for?xing commitment decisions.In order to recover primal feasibility,both heuristics are followed by 741

solving an ED,wherein the commitment variables are?xed;this LR-based method is shown to be capable 742

of handling larger and more complex instances.In[366]the Lagrangian heuristic consists of formulating 743

a MIP that mixes solutions provided by the dual iterations,selecting the production schedule of a 744

speci?c unit among the primal solutions generated by the LD phase in such a way as to minimize 745

overall cost and satisfy(the dualized)demand constraints.The resulting MIP is then reformulated in 746

order to allow for an e?cient solution.A similar idea is exploited in[237],where the MIP is solved by 747

using Genetic Algorithms.In[128]the dual multipliers de?ning the pseudo-schedule are interpreted as 748

probabilities for randomly selecting commitment decisions after a LD phase;four derived Lagrangian 749

heuristics are investigated.In[34]a two step procedure is proposed,consisting of a LD phase followed 750

by an Augmented Lagrangian(AL)phase for primal recovery.The AL term is linearized in an ad-hoc 751

way and its penalty slowly sent to in?nity.Bundle methods,CP and sub-gradient methods are compared 752

for solving the LD phase;it is shown that Bundle methods outperform alternative approaches.Finally, 753

in[64]Lagrangian approaches are compared with Tabu Search heuristics,and an improved primal phase 754

is proposed in[65].The approach is later extended to the free-market regime[66]and to the handling 755

of ramping constraints[143]via the use of the specialized DP procedure of[142].An hybrid version also 756

using MILP techniques is presented in[145].

757

LR can be used to deal with ramp rate constraints,fuel related constraints and emission constraints 758

[12,87,369,413,427]by simply relaxing them(in Lagrangian fashion).Similarly,LR can be employed to 759

further decompose subproblems,in particular hydro ones;these ideas are explored in[131,132,165,272, 760

364,365].More speci?cally,the authors of[165]consider the LD related to the bounds on the reservoir 761

levels in the hydro subproblem,which e?ectively decomposes the problem in smaller MILPs that can 762

then be readily dealt with,through the use of DP in this speci?c case.The LD is optimized using a 763

subgradient approach,and heuristics are used to recover a primal feasible solution.A similar approach 764

is used in[272],where hydro units have discrete commitment decisions much like thermal ones.These 765

constraints are then relaxed in a Lagrangian way,resulting in continuous network?ow subproblems and 766

a pure integer problem.In[132],Lagrangian decomposition[168]is used to deal with forbidden zones 767

in complex hydro units.The idea is to use LR to decompose hydro valley subproblems further into 768

two parts:the?rst part deals with the?ow constraints and basically leads to a simple LP,while the 769

second part deals with the water-head e?ect and other combinatorial constraints and requires a speci?c 770

NLP approach(an SQP-based method and partial exhaustive enumeration).Two dual formulations are 771

considered which di?er from each other in that in the second one the NLP problem is further decomposed 772

through the use of auxiliary variables.The model is extended to consider network constraints in[364], 773

and di?erent relaxation schemes are explored in[365]and[131];in particular,the latter compares 774

Lagrangian relaxation and Lagrangian decomposition.In[413]a system with70thermal and7hydro 775

units is addressed.Ramp rate constraints are also dualized,and the DP approach of[163]is used to 776

optimize the thermal units,while a merit order allocation is employed for the hydro subproblem.In[427] 777

a three stage approach is proposed based on?rst solving the LR,then?nding a feasible solution for 778

reserve requirements and?nally solving an ED.In[274]a hydro-thermal system with a fairly realistic 779

model for hydro generation is considered that comprises forbidden zones(cf.§2.4)and the water head 780

e?ect.The o?er-demand equilibrium constraints and reservoir balance equations are dualized,and the 781

LD is maximized with a subgradient approach,with a heuristic step?xing the discrete hydro variables 782

to recover a primal feasible hydro solution.In[2]some transmission constraints are considered.In[228] 783

an alternative to ramping rate constraints in the model for thermal units,a so-called stress e?ect, 784

is proposed.Coupling o?er-demand equilibrium and reserve requirement constraints are dualized;the 785

corresponding LD is maximized using a subgradient approach,where the thermal subproblems are solved 786

using Simulated Annealing techniques.In[148]a ramp rate,fuel and emission constrained UC is solved. 787

Table3Sources using Lagrangian Relaxation

Basic UC Additional UC constraints

Must Fuel Ramp Suppl.Hydro-Emission Transmission

Run/O?Constr.Rate Reserve-Thermal

[2,12,87,248,262][413,427][12,369][87,148,413][2,87][12,365,413][148,158,209][2,364] [135,274,369,413,427][145][87,148][143,145][66,143,145]

[64,126,128,244,348][65,66][65,274,348]

[47,148,228][11,228][11,131,132]

A di?erent decomposition approach is the classic one due to Benders[44][62,Chapter11.1],which 788

rather focuses on complicating variables that,once?xed,allow to separate the problem into independent 789

(and,hopefully,easy)ones.Application of Benders’decomposition to UC is fairly recent.In[231,407] 790

techniques for improving the Benders’cuts production are described.In[146]a conceptual and nu-791

merical comparison is made,in the context of the security constrained UC,between LR and MILP 792

approaches(cf.§3.2)for the solution of master problem of Benders’decomposition.For the subprob-793

lems,involving the network constraints,the authors compare Benders’cuts and linear sensitivity factor 794

(LSF)approaches.

795

3.4Augmented Lagrangian Relaxation

796

One major downside of LR approaches is the di?culty in recovering a primal feasible solution.The use of 797

the Augmented Lagrangian(AL)method,whereby a quadratic penalization of the relaxed constraints is 798

added to the objective function alongside the linear penalization typical of standard LR,is known to be 799

a potential solution to this issue.Yet,because(1)is nonconvex it should be expected that in general the 800

AL approach leads to a local optimizer[157,240].Furthermore,the AL relaxation is no longer separable 801

into an independent subproblem for each unit,and therefore it is signi?cantly more di?cult to solve 802

(in practice,as di?cult as UC itself).This calls for some further approach to simplify the relaxation; 803

in[31,414]the use of the auxiliary problem principle[89,90]is suggested.The classic theory of the 804

auxiliary problem principe requires restrictive assumptions such as convexity and regularity,which do 805

not hold in practice;some recent advances have been made in the non-convex setting[19,317,374].In[35] 806

an alternative decomposition scheme based on block coordinate descent(e.g.[48,328])is proposed and 807

it is found to be more e?cient.The recent[249]includes in the UC formulation a DC network model 808

and bilateral contracts de?ning the nodal injections.The AL of the coupling constraints is formed and 809

then linearized in an ad-hoc way,while Bundle methods are employed for updating the dual multipliers. 810

Environmental constraints[399]and network transmission constraints[35,399]have also been tackled 811

with the AL approach.A common way to deal with additional constraints is variable duplication[153]. 812

Table4Sources using Augmented Lagrangian Approaches

Basic UC Additional UC constraints

Modulation Startup/shutdown Transmission Ramp Environ.Hydro-

curves Rate Const.-Thermal

[25,31,35,399][31][31][25,35,399][25,31][399][25,31]

3.5(Meta-)Heuristics

813

3.5.1Operator rule based:Priority Listing

814

This method de?nes a list of units which should logically be scheduled prior to other units,with merit 815

order scheduling being a special case.Priority listing was?rst employed on bUC in[26],where units 816

are listed according to their performance and the cost they yield(comprising maintenance costs).Must-817

on/must-o?and crew constraint have been added in[215],and a limit on the number of starts is included 818

in[216]through the use of a commitment utilization factor,which is claimed to provide a better list. 819

While the former two papers and[5]address bUC,there has been an endeavour to integrate other factors 820

such as multi-area constraints[217]and hydro-thermal systems[200]for large-scale UC.In the latter 821

paper a two-step heuristic procedure is used to solve a UC with100units:the?rst step uses rules from 822

real-world schedules(possibly enhanced by the use of UC software)to set up a priority list consisting 823

of feasible production schedules,while the second step optimizes locally around the current solution.A 824

very similar approach is investigated in[5].

825

Table5Sources using Priority Listing

Basic UC Additional UC constraints

No.Units Crew Must Multi-Hydro-No.Starts

Started Const.run/O?Area Thermal/Shutdowns

[5,26,200,215–217][200][215][215,217][217][200][216]

3.5.2Guided Random Exploration

826

Since solving the UC(1)to optimality is quite di?cult,many heuristic approaches such as Taboo search, 827

Simulated Annealing,Augmented Lagrange Hop?eld Networks,Nature Inspired(e.g.,particle swarms, 828

frog leaping,...)and Genetic Algorithms have also been employed.We refer to[127,337]for a discussion 829

of those approaches,and in this paper we by no means attempt to give a full overview of this sub?eld. 830

This is because heuristic approaches like these are typically di?cult to adapt to the Uncertain UC 831

case,which is the main focus of this survey,unless they are at least partly based on mathematical 832

programming techniques.We therefore concentrate mostly on“hybrid”approaches that use the latter 833

at least to a certain degree.For instance,in[237]genes are feasible schedules produced by a LR-based 834

scheme:the genetic algorithm then mixes the solutions up to form new feasible schedules in order to 835

hopefully produce a solution that better meets the demand constraints.In[428]the authors solve a100 836

thermal unit system by using Simulated Annealing and report that their approach outperforms a B&B 837

procedure,but fails to outperform a LR approach(although in the later[64]Taboo search has been 838

reported to be more competitive with LR).In[120,201]Evolutionary Programming is applied to adjust 839

the solution provided by a LR approach.In[241]a neural network approach is coupled to LR in order 840

to optimize a system with up to60units:the thermal subproblems are optimized using a neuron-based 841

DP algorithm.

842

In general,these approaches are not considered particularly competitive for UC;for instance,[368]states 843

that Simulated Annealing and Evolutionary Programming attempts have been unsuccessful.Also,usu-844

ally these approaches deal with bUC,with only a few sources considering ramp rate,crew,maintenance 845

or multi-area constraints,and hydro-thermal systems being very rarely dealt with.The likely reason is 846

that purely combinatorial heuristics are best apt at problems that exhibit a predominant and relatively 847

“simple”combinatorial structure to which the various elements of the heuristic(neighborhood(s)struc-848

ture in Simulated Annealing,Taboo list and aspiration criteria in Taboo search,mutation and crossover 849

operators in genetic algorithms,...)can be speci?cally tailored.UC is a fundamentally mixed combi-850

natorial and continuous program,since both the commitment and the dispatch have to be provided. 851

Furthermore,UC has several di?erent combinatorial structures,especially when“complex”constraints 852

have to be dealt with.Therefore,on the outset UC is best approached with mathematical programming 853

techniques.

854

Table6provides a(very partial)overview of heuristic approaches:

855

Table6Sources using(Meta-)Heuristic Approaches

Approach Basic UC Additional UC constraints

Ramp Crew Mainte-Multi-Area Hydro-Derating

Rate Constr.nance Const.Thermal

Simul.Annealing[8,358,428][358][8,246,428][428]

[246]

Tabu Search[246,260,387][246][247][246]

[64,230]

[247,314]

Neural Network[339,343,391][1,343][266][391]

[1,344,392][113,392]

[113,229,266]

[241]

Genetic Algorithm[363,403,404][350,403][86,315]

[86,378,415][313]

[313,315,350]

[120,201,415]

[102,237]

Nature Inspired[81,82,152][81,82,152][82]

Large-scale Unit Commitment under uncertainty-未发表

相关文档

最新文档