Large-scale Unit Commitment under uncertainty

Milad Tahanan, Wim van Ackooij, Antonio Frangioni, Fabrizio Lacalandra

► To cite this version:

Milad Tahanan, Wim van Ackooij, Antonio Frangioni, Fabrizio Lacalandra. Large-scale Unit Commitment under uncertainty. 4OR: A Quarterly Journal of Operations Research, 2015, 13 (2), pp.115-171. 10.1007/s10288-014-0279-y . hal-01340333

HAL Id: hal-01340333

https://hal.science/hal-01340333

Submitted on 3 Feb 2020

**HAL** is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>
Large-scale Unit Commitment under uncertainty

Milad Tahanan · Wim van Ackooij ·
Antonio Frangioni · Fabrizio Lacalandra

**Abstract** The Unit Commitment problem in energy management aims at finding the optimal productions schedule of a set of generation units while meeting various system-wide constraints. It has always been a large-scale, non-convex difficult 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 Uncertain 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 mathematical 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.

<footnote>M. Tahanan
Ecole Centrale Paris, Grande Voie des Vignes, Chatenay-Malabry, France
e-mail: miladtahanan@gmail.com</footnote>

<footnote>W. van Ackooij
OSIRIS, EDF R&D, Avenue du Général de Gaulle 1, 92141 Clamart Cedex, France
e-mail: wim.van-ackooij@edf.fr</footnote>

<footnote>A. Frangioni (✉)
Dipartimento di Informatica, Università di Pisa, Largo B. Pontecorvo 3, 56127 Pisa, Italy
e-mail: frangio@di.unipi.it</footnote>

<footnote>F. Lacalandra
QuanTek S.r.L., Via G. Marconi, 3, 40122 Bologna, Italy
e-mail: fabrizio.lacalandra@quantek.it</footnote>
# 1 Introduction

In electrical energy production and distribution systems, an important problem deals with computing the production schedule of the available generating units in order to meet their technical and operational constraints and to satisfy some system-wide constraints, e.g., global equilibrium between energy production and energy demand. The constraints of the units are very complex; for instance, some units may require up to 24 h to start. Therefore, such a schedule must be computed (well) in advance of real time. The resulting family of models is usually referred to as the *Unit Commitment problem* (UC), and its practical importance is clearly proven by the enormous amount of scientific literature devoted to its solution in the last four decades and more. Besides the very substantial practical and economical 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 and improves the performances of existing ones, thereby allowing to tackle previously unsolvable problems;

2. on the other hand, the large variety of different versions of UC corresponding to the disparate characteristics of electrical systems worldwide (free market vs. centralized, vast range of production 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 the need of continuously adapting to the ever-changing demands of practical operational environments, in turn caused by technological and regulatory changes which significantly alter the characteristics of the problem to be solved. Furthermore, UC is a large-scale, non-convex optimization problem that, due to the operational requirements, has to be solved in an “unreasonably” small time. Finally, as methodological and technological advances make previous versions of UC more accessible, practitioners have a chance to challenge the (very significant) simplifications that have traditionally been made, for purely computational reasons, about the actual behavior of generating units. This leads to the development of models incorporating considerable more detail than in the past, which can significantly stretch the capabilities of current solution methods.

A particularly relevant recent trend in electrical systems is the ever increasing use of intermittent (renewable) production sources such as wind and solar power. This has significantly increased the underlying *uncertainty* in the system, previously almost completely due to variation of users’ demand (which could however be forecasted quite effectively) and occurrence of faults (which was traditionally taken into account by requiring some amount of spinning reserve). Ignoring such a substantial increase in uncertainty levels w.r.t. the common existing models incurs an unacceptable risk that the computed production schedules be significantly more costly than anticipated, or even infeasible (e.g., Keyhani et al. 2010). However, incorporating the uncertainty in
the models is very challenging, in particular in view of the difficulty of the *deterministic* versions of UC.

Fortunately, optimization methods capable of dealing with uncertainty have been a very active area of research in the last decade, and several of these developments can be applied, and have been applied, to the UC problem. This paper aims at providing a survey of approaches for the *Uncertain* UC problem (UUC). To the best of our knowledge no such survey exists, while the literature is rapidly growing. This is easily explained, besides by the practical significance of UUC, by the combination of two factors: on one hand the diversity of operational environments that need to be considered, and on the other hand by the fact that the multitude of applicable solution techniques already available for UC (here and in the following we mean the deterministic version when UUC is not explicitly mentioned) is further compounded by the need of deciding *how uncertainty is modeled*. Indeed, the literature offers at least three approaches that have substantially different practical and computational requirements: *stochastic optimization* (SO), *robust optimization* (RO), and *chance-constrained optimization* (CCO). This modeling choice has vast implications on the actual form of UUC, its potential robustness in the face of uncertainty, the (expected) cost of the computed production schedules and the computational cost of determining them. Hence, UUC is even less “well-solved” than UC, and a thriving area of research. 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 on those for the uncertain version. This is necessary, as the last broad UC survey (Padhy 2004) dates back some 10 years, and is essentially an update of Sheble and Fahd (1994); neither of these consider UUC in a separate way as we do. The more recent survey (Farhat and El-Hawary 2009) provides some complements to Padhy (2004) but it does not comprehensively cover methods based on mathematical programming techniques, besides not considering the uncertain variants. The very recent survey (Saravanan et al. 2013) focuses mainly on nature-inspired or evolutionary computing approaches, most often applied to simple 10-units systems which can nowadays be solved optimally in split seconds with general-purpose techniques; furthermore these methods do not provide qualified bounds (e.g., optimality gap) that are most often required when applying SO, RO or CCO techniques to the solution of UUC. This, together with the significant improvement of solving capabilities of methods based on mathematical programming techniques (e.g., Lagrangian or Benders' decomposition methods, mixed integer linear programming approaches, ...), justifies why in the UC-part of our survey we mostly focus on the latter rather than on heuristic approaches.

Because the paper surveys such a large variety of material, we provide two different reading maps to the readers:

1. The first is the standard reading order of the paper, synthesized in the Table of Contents above. In Sect. 2 we describe the varied technical and operational constraints in (U)UC models which give rise to many different variants of UC problems. In Sect. 3 we provide an overview of methods that deal with the deterministic UC, focusing in particular onto methods dealing with large-scale systems and/or that can be naturally extended to UUC, at least as subproblems. In particular, in Sect. 3.1
we discuss dynamic programming approaches, in Sect. 3.2 we discuss integer and mixed integer linear programming (MILP) approaches, while in Sects. 3.3 and 3.4 we discuss decomposition approaches (Lagrangian, Benders' and Augmented Lagrangian), and finally in Sect. 3.5 we (quickly) discuss (Meta-)heuristics. UUC is then the subject of Sect. 4: in particular, Sect. 4.2 presents stochastic optimization (scenario-tree) approaches, Sect. 4.3 presents robust optimization approaches, and Sect. 4.4 presents chance-constrained optimization approaches. We end the paper with some concluding remarks in Sect. 5, and with a list of the most used acronyms in the “Appendix”.

2. The second map is centered on the different algorithmic approaches that have been used to solve (U)UC. The main ones considered in this review are:

- *Dynamic programming* approaches, which can be found in Sects. 3.1, 3.2.2, 3.3, 3.5.2, 4.1.1.1, 4.2.1, 4.2.3, 4.2.4 and 4.4;

- *Mixed-integer programming* approaches, which can be found in Sects. 3.2, 3.3, 4.1.2.2, 4.2, 4.2.1, 4.2.3, 4.2.4, 4.3 and 4.4;

- *Lagrangian relaxation* (decomposition) approaches, which can be found in Sect. 3.2.2, 3.3, 3.5.2, 4.2.1, 4.2.2, 4.2.3, 4.2.4 and 4.4;

- *Benders' decomposition* approaches, which can be found in Sect. 3.2.2, 3.3, 4.2, 4.2.1, 4.2.2, 4.2.3, 4.2.4 and 4.3;

- *Augmented Lagrangian* approaches, which can be found in Sect. 3.3, 3.4 and 4.4;

- other forms of *heuristic* approaches, which can be found in Sect. 3.1, 3.2.2, 3.3, 3.5, 4.1.2.1, 4.2.2 and 4.2.3.

## 2 Ingredients of the Unit Commitment problem

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

When the first UC models were formulated, the usual setting was that of a monopoli-
stic producer (MP). The MP was in charge of the electrical production, transmission
and distribution in one given area, often corresponding to a national state, comprised
the regulation of exchanges with neighbouring regions. In the liberalized markets that
are nowadays prevalent, the decision chain is instead decentralized and significantly
more complex, as shown in the (still somewhat simplified) scheme of Fig. 1. In a typical
setting, companies owning generation assets (GENCOs) have to bid their generation
capacity over one (or more) market operator(s) (MO). Alternatively, or in addition,
they can stipulate bilateral contracts (or contracts for differences, CfD) with final users
or with wholesales/traders. Once received the bids/offers, the MO clears the (hourly)
energy market and defines (equilibrium) clearing prices. A transmission system oper-
ator (TSO), in possession of the transmission infrastructure, then has the duty—acting
<figure><img src="image_2.png" /><figcaption>Fig. 1 Simplified electricity market structure</figcaption></figure>

in concert with the power exchange manager (PEM)—to ensure safe delivery of the energy, which in turns means different duties such as real time frequency-power balancing, spinning reserve satisfaction, voltage profile stability, and enforcing real-time network capacity constraints. The TSO typically operates in a different way programmable and non programmable units, since for instance only the former can participate to balancing markets.

This basic setting, which can be considered sufficient for our discussion, is only a simplification of the actual systems, which also vary depending on their geographical position. For instance, transmission (and distribution) assets may actually be in possession of different companies that have to offer them under highly regulated fair and non-discriminative conditions, leaving the TSO only a coordination role. Also, the TSO and the MO may or may not be the same entity, and so on. We leave aside these other factors, like how many and MOs there are and how exactly these are structured; we refer to Conejo and Prieto (2001), Harris (2011), Oren et al. (1997), Shahidehpour et al. (2002) and Conejo et al. (2010, Chapter 1) for a more detailed description. Because of this complexity, standard optimization models may not be entirely appropriate to deal with all the aspects of the problem, since the behavior of different/competing decision makers need be taken into account. This may require the use of other methodologies, such as the computation of equilibria or agent-based simulation. We will not deal with any of these aspects, the interested reader being referred to Ventosa et al. (2005), Harris (2011), Oren et al. (1997), Shahidehpour et al. (2002), Leveque (2002) and Gabriel et al. (2013) for further discussion.

## 2.1 A global view of UC

In broad terms, the (deterministic or uncertain) Unit Commitment problem (both UC in this section unless explicitly stated) requires to minimize the cost, or maximize the
benefit, obtained by the production schedule for the available generating units over a given time horizon. As such, the fundamental ingredients of UC are its objective function and its constraints. Of course, another fundamental ingredient is the time horizon itself; UC being a short-term model this is most often a day or two of operations, and up to a week. In the following we will denote it by $\mathcal{T}$, which is typically considered to be a discrete set corresponding to a finite number of time instants $t \in \mathcal{T}$, usually hours or half-hours (down to 15 or 5 min). Thus, the typical size of $\mathcal{T}$ varies from 24 to a few hundred.

In mathematical terms, UC has the general structure

$$ \min \{ f(x) : x \in X_1 \cap X_2, \} \qquad (1) $$

where $x \in \mathbb{R}^n$ is the decision making vector. Usually (most) elements of $x$ are indexed according to both the generating unit $i = 1, \dots, m$ and the time instant $t \in \mathcal{T}$ they refer to. Thus, one often speaks of the subvectors $x^t$ of all decisions pertaining to time $t$ and/or $x_i$ of all decisions pertaining to unit $i$. Also, entries of $x$ are typically split among:

1. *Commitment decision*, discrete variables that determine if a particular unit is on or off at any given time (often denoted by $u_i^t$);

2. *Production decision*, continuous variables that provide the amount of generated power by a specific unit at a given time (often denoted by $p_i^t$);

3. *Network decision*, such as these representing phase angle or voltage magnitudes, describing the state of the transmission or distribution network.

A UC problem not having commitment decisions is often called economic dispatch (ED) (e.g., Zhu 2009) or optimal power flow (OPF) when the network is considered, (e.g., Jabr 2008). It could be argued that commitment decisions can be easily derived from production decisions (each time a non-zero production output is present the unit has to be on), but for modeling purposed it is useful to deal with the two different concepts separately, cf. Sect. 3.2. Besides, the point is that in ED or OPF the commitment of units has already been fixed and cannot be changed. We remark that network decisions may also include binary variables that provide the open or close state of a particular line, as entirely closing a line is one of the few options that the physic of electrical networks allows for “routing” the electrical current (cf. Sect. 2.7). While ED can be expected to be simpler than UC, and in many cases it is a simple convex program that can nowadays be solved with off-the-shelf techniques, this is not always the case. ED was not only challenging in the past (e.g., Demartini et al. 1998 and the references therein), but can still be do so today. Indeed, even when commitment decisions are fixed, the electrical system is highly nonlinear and nonconvex, e.g., due to hydro units efficiency curves (cf. Sect. 2.4) or the transmission network characteristics (cf. Sect. 2.6), so that ED can still be a nontrivial problem that may require ad-hoc approaches (e.g., Heredia and Nabona 1995; Oliveira et al. 2005; Jabr 2006, 2008; Lavaei and Low 2012; Molzahn et al. 2013).

In Eq. (1), $X_1$ is the set modeling all technical/operational constraints of the individual units and $X_2$ are the system-wide constraints. The first set is by definition structured as a Cartesian product of smaller sets, i.e., $X_1 = \prod_{i=1}^m X_i^1$, with $X_i^1 \subseteq \mathbb{R}^{n_i}$
and $\sum_{i=1}^{m} n_i = n$. Moreover, the objective function $f$ typically also allows for a decomposition along the sets $X_i^1$, i.e., $f(x) = \sum_{i=1}^{m} f_i(x_i)$ and $x_i \in X_i^1$. Each of the sets $X_i^1$ roughly contains the feasible production schedules for one unit, that can differ very significantly between different units due to the specific aspects related to their technological and operational characteristics. In most models, $X_1$ is non-convex. However, units sharing the same fundamental operational principles often share a large part of their constraints as well. Because of this, these constraints are best described according to the type of the generating unit, i.e.,

1. thermal units (cf. Sect. 2.3);

2. hydro units (cf. Sect. 2.4);

3. renewable generation units (cf. Sects. 2.3–2.5).

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

The set $X_2$, which usually models at least the offer-demand equilibrium constraints, is most often, but not always, convex and even polyhedral. This set may also incorporate other system-wide constraints, such as emission constraints, network transmission constraints (cf. Sect. 2.6) or optimal transmission switching constraints (cf. Sect. 2.7).

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

<table><thead><tr><td>Data</td><td>Uncertain for</td><td>Severity</td></tr></thead><tbody><tr><td>Customer load</td><td>GENCOs, TSO</td><td>Low/medium</td></tr><tr><td>Reservoirs inflows</td><td>GENCOs, TSO</td><td>Medium</td></tr><tr><td>Renewable generation</td><td>GENCOs, TSO</td><td>High</td></tr><tr><td>Prices/quantities</td><td>GENCOs, traders, customers</td><td>Medium/high</td></tr><tr><td>Units/network failure</td><td>GENCOs, TSO</td><td>Medium</td></tr></tbody></table>

Various ways to incorporate uncertainty in (1) are discussed in Sect. 4.1. Obviously, solving (1) becomes more difficult when uncertainty is present, even when $n$ is small and $X_1$ relatively simple. Thus, properly exploiting the structure of the problem (the function $f$ and the sets $X_1$ and $X_2$) is crucial to obtain efficient schemes for UC, and even more so for UUC. This is why we now provide some detail on different modeling features for each of these components.
## 2.2 The objective function

The objective function of UC is one of the main factors reflecting the different types of decision-makers described in the previous section. In fact, when the production needs to be satisfied (as in the case of the MP, or of a GENCO having had a certain set of bids accepted) the objective function fundamentally aims at *minimizing energy production costs*; this is not necessarily obvious (cf. the case of hydro units below), but the principle is clear. However, in the free-market regime the aim is typically rather to *maximize energy production profits*. This again requires estimating the costs, so the same objective as in the MP case largely carries over, but it also requires estimating the revenues from energy selling, as it is the difference between the two that has to be maximized. In particular, if the GENCO is a *price maker* it may theoretically indulge in *strategic bidding* (David and Wen 2001), whereby the GENCO withdraws power from the market (by bidding it at high cost) in order to push up market prices, resulting in an overall diminished production from its units but higher profit due to the combined effect of decreased production cost and increased unitary revenue for the produced energy. Of course, the success of such a strategy depends on the (unknown) behavior of the other participants to the market, which thereby introduces significant uncertainty in the problem. The electrical market is also highly regulated to rule out such behavior of the market participants; in particular, larger GENCOs, being more easily price makers, are strictly observed by the regulator and bid all their available capacity on the market. Yet, the solution of *strategic bidding problems* is of interest at least to the regulators themselves, who need to identify the GENCOs who may in principle exercise market power and identify possible patterns of abuse. Even in the *price taker* case, i.e., a GENCO with limited assets and little or no capacity to influence market prices, uncertainty is added by the need of accurately predicting the selling price of energy for each unit and each $t \in T$ (Gil et al. 2012). This uncertainty must then be managed, e.g., with techniques such as those of robust optimization (Baringo and Conejo 2011).

Energy production costs for fuel-burning units are typically modeled (in increasing order of complexity) as linear, piecewise-linear convex, quadratic convex, or non-convex functions separable for each $t \in T$. In fact, while the fuel-consumption-to-generated-power curve can usually be reasonably well approximated with a piecewise linear function or a low-order polynomial one, other technical characteristics of generating systems introduce nonconvex elements. The simplest form is that of a *fixed cost* to be paid whenever the unit is producing at some $t \in T$, irrespective of the actual amount of generated power. In alternative, or in addition, *start-up costs* (and, less frequently, shut-down ones) are incurred when a unit is brought online after a period of inactivity. In their simplest form start-up costs can be considered fixed, but most often they significantly depend on the time the unit has been off before having been restarted, and therefore are not separable for each time instant. The dependency of the start-up cost on time can be rather complex, as it actually depends on the choice between the unit being entirely de-powered (cooling) or being kept at an appropriate temperature, at the cost of burning some amount of fuel during the inactivity period, to make the start-up cheaper (banking). Technically speaking, in the latter case one incurs in a higher *boiler cost* to offset part of the *turbine cost*. The choice between these two
alternatives can often be optimally made by simple formulæ once the amount of idle
time is known, but this is typically not true beforehand in UC since the schedule of the
unit is precisely the output of the optimization problem. Fortunately, some of the solu-
tion methods allow inclusion of the start-up cost at a relatively minor increase of the
computational complexity; this is the case e.g., of MILP formulations, cf. Sect. 3.2,
exploiting the fact that the optimal start-up cost is nondecreasing as the length of
the idle period increases (Nowak and Römisch 2000; Carrión and Arroyo 2006). In
other cases start-up cost have basically no additional computational cost, such as in DP
approaches, cf. Sect. 3.1. Other relevant sources of nonconvexity in the objective func-
tion are *valve points* (Wood and Wollemberg 1996), corresponding to small regions of
the feasible production levels where the actual working of the unit is unstable, e.g., due
to transitioning between two different configurations in a combined-cycle unit or other
technical reasons, and that therefore should be avoided.

Nuclear units are generally considered thermal plants, although they significantly
differ in particular for the objective function. Indeed, fuel cost has a different structure
and depends on many factors, not only technical but also political (e.g., Cour des
Comptes 2012). For convenience, formulæ similar to that of conventional thermal
plants are often used. However, these units incur additional significant *modulation
costs* whenever variations of power output are required; this cost is therefore again not
separable per time instant.

Hydro units are generally assumed to have zero energy production cost, although
they may in principle have crew and manning costs. In the self-scheduling case, where
profit has to be maximized, this would lead to units systematically depleting all the
available water due to the fact that a short-term model such as UC has no “visibility”
on what happens after the end of its time horizon $T$ (the so-called “border effect”).
Because of this, often a *value of water* coefficient is added to the objective function to
represent the expected value of reserves left in the reservoirs at the end of $T$. These
values, as well as the required reservoir levels (cf. 2.4), are usually computed by
means of specific mid-term optimization models. A very standard approach is to value
the differential between the initial and end volume of a reservoir against a volume-
dependent water value; we refer to van Ackooij et al. (2011) and Cerjan et al. (2011)
for details on various other modeling choices. A particular difficulty appears when we
wish to integrate the water head effect on turbining efficiency (e.g., Finardi and Silva
2006; Ramos et al. 2012), since this is typically a nonlinear and nonconvex relationship.

In general, the case of profit maximization requires knowledge of the selling and
buying price of energy at each $t \in T$. Because UC is solved ahead of actual operations,
possibly precisely with the aim of computing the bids that will contribute to the setting
of these prices (cf. e.g., Borghetti et al. 2003a; Bompard and Ma 2012; Kwon and
Frances 2012; Rocha and Das 2012), this requires nontrivial forecast models in order
to obtain reasonable estimates of the prices (e.g., Oudjane et al. 2006; Li et al. 2010;
Zareipour 2012). Depending on the time horizon and specific application, different
price models can be considered. These can be obtained from time series modeling
(e.g., Diongue 2005; Muñoz et al. 2010; Pedregal et al. 2012), mathematical finance
(e.g., Oudjane et al. 2006; Higgs and Worthington 2008; Benth et al. 2012; Nguyen-
Huu 2012; Pepper et al. 2012) or can be based on electricity fundamentals (e.g., van
Ackooij and Wirth 2007; Ea 2012). For the case where the producer is a *price taker*, that
is, small enough so that its production can be deemed to have little or no effect on the
realized prices, UC can typically be independently solved for each individual unit (thus
being styled as the *self-scheduling* problem), and it is therefore much easier (Arroyo
and Conejo 2000), although uncertainty in prices then becomes a critical factor (Conejo
et al. 2002b; Nogales et al. 2002; Baringo and Conejo 2011). Things are significantly
different in case the producer can exercise market power, that is, influence (increase)
the prices by changing (withdrawing) the power it offers to the market; modeling this
effect “ties” all the units back again into an unique UUC (Borghetti et al. 2003a; Conejo
et al. 2002a; Torre et al. 2002; Pereira et al. 2005). Uncertainty in this case is also very
relevant, with the behavior of competitors being one obvious primary source (Anderson
and Philpott 2002; Wen and David 2001; Vucetic et al. 2001; Pineau and Murto 2003;
Wang et al. 2007). The matter is further complicated by the fact that the structure of
the PE is usually complex, with more than one auction solved in cascade to account
for different kinds of generation (energy, reserve, ancillary services, ...) (Baillo et
al. 2004; Triki et al. 2005; Wang et al. 2005) and by the fact that tight transmission
constraints may create *zonal* or *even nodal prices*, thereby allowing producers who
may not have market power in the global context to be able to exercise it in a limited
region (Li and Shahidehpour 2005; Peng and Tomsovic 2003; Pereira et al. 2005).

2.3 Thermal units

A thermal power station is a power plant in which the prime mover is steam driven.
Technical/operational constraints can be classified as either *static* or *dynamic*: the
former hold on each time step, whereas the latter link different (most often adjacent)
time steps. Most typical static constraints are:

1. Offline: when the unit is offline, the power output is less than or equal to zero (negative power output refers to the power used by auxiliary installations, e.g., for nuclear plants).

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

3. Starting: the unit is ramping up to MSG. The ramping profile depends on the number of hours a unit has been offline (e.g., Le et al. 1990); see also in starting curve below. A unit in this state can in principle still be disconnected for a later start, but at a cost.

4. Stopping: the unit ramps down from MSG to the offline power output. As for starting, the ramping profile depends on the number of hours a unit has been online; see below in stopping curve.

5. Generation capacity: the production capacity of each unit. For some units the production output has to be selected among a discrete set of values.

6. Spinning reserve: the extra generating capacity that is available by increasing the power output of generators that are already connected to the power system. For most generators, this increase in power output is achieved by increasing the torque applied to the turbine's rotor. Spinning reserves can be valued separately from actively generated power as they represent the main mechanism that electrical systems have to cope with real-time variations in demand levels.
7. Crew constraint: number of operators available to perform the actions in a power plant.

Typical dynamic constraints instead are:

1. Minimum up/down time: a unit has to remain online/offline for at least a specific amount of time.

2. Operating ramp rate (also known as ramp-down and ramp-up rate): the increment and decrement of the generation of a unit from a time step to another, excluding start-up and shut-down periods, must be bounded by a constant (possibly different for ramp-up and ramp-down).

3. Minimum stable state duration: a unit that has attained a specific generation level has to produce at that level for a minimum duration of time.

4. Maximum numbers of starts: the number of starts can be limited over a specific time horizon (such a constraint is also implicitly imposed by minimum up/down time ones, and in fact the two are often alternatives).

5. Modulation and stability: these constraints are mainly applied to an online nuclear unit. A unit is *in modulation* if the output level changes in a time interval, whereas it is *stable* if the power level remains identical to that of the previous time step. The constraints ensure that the unit is “most often stable”, requiring that the number of modulations does not exceed a predefined limit over a given time span (say, 24 h).

6. Starting (stopping) Curve (also referred to in literature as start-up/shut-down ramp rate): in order to start (stop) a unit and move it from the offline (online) state to the online (offline) state, the unit has to follow a specific starting (stopping) curve, which links offline power output (zero, or negative for nuclear plants) to MSG (or vice-versa) over the course of several time steps. Each starting (stopping) curve implies a specific cost, and the chosen curve depends on the number of hours the plant has been offline (online). Starting (stopping) may take anything from several minutes (and therefore be typically irrelevant) up to 24 h (and therefore be pivotal for the schedule).

## 2.4 Hydro units

Hydro units are in fact entire hydro valleys, i.e., a set of connected reservoirs, turbines and pumps that influence each other through flow constraints. Turbines release water from uphill reservoirs to downhill ones generating energy, pumps do the opposite. Note that the power output of ROR units downstream to a reservoir (and up to the following reservoir, if any) must be counted together with that of the turbines at the same reservoir; usually it is possible to do this by manipulating the power-to-discharged-water curve of the unit at the reservoir, and thus ROR units in a hydro valley need not be explicitly modeled. We remark in passing that whether or not a unit is considered ROR depends on the time horizon of the problem: units with small reservoirs can be explicitly modeled in UC because they do have a degree of modulation over the short term, but they may be considered ROR in longer-term problems since the modulation is irrelevant over long periods of time.

As for thermal units, we distinguish constraints as being either static or dynamic. The typical ones of the first kind are:
1. Reservoir level: the level of water in each reservoir has to remain between a lower and upper bound. Frequently these bounds are used to reflect strategic decisions corresponding to optimal long-term use of water (cf. Sect. 2.2), and not necessarily reflect physical bounds. An alternative is to use a nonlinear cost of water that reflects the higher risk incurred in substantially depleting the reservoir level, as water in hydro reservoirs represents basically the only known way of efficiently storing energy on a large scale and therefore provides a crucial source of flexibility in the system. Yet, bounds on the level would ultimately be imposed anyway by physical constraints.

2. Bounds: turbines and pumps can operate only within certain bounds on the flowing water. In particular, some turbines might have a minimal production level akin to the MSG of thermal units.

The most common dynamic constraints are:

1. Flow equations: these equations involve the physical balance of the water level in each reservoir and connect the various reservoirs together. The reservoir levels get updated according to natural inflows, what is turbined downhill, what is spilled downhill (i.e., let go from the reservoir to the next without activating the turbines), and what is pumped from downhill to uphill. Spilling might not be allowed for all reservoirs, nor all have pumping equipment.

2. Flow delay: the water flowing (uphill or downhill) from each unit to the next reservoir will reach it after a given delay, that can possibly be of several hours (and occasionally even more Belloni et al. 2003).

3. Ramp rate: adjacent turbining levels have to remain sufficiently close to each other.

4. Smooth turbining: over a given time span (e.g., 1 h), turbining output should not be in a V-shape, i.e., first increase and immediately afterwards decrease (or vice-versa). This constraint is typically imposed to avoid excessive strain on the components, similarly to several constraints on thermal units such as minimum up/down time, maximum numbers of starts, modulation and stability.

5. Turbining/pumping incompatibility: some turbines are reversible and therefore pumping and turbining cannot be done simultaneously. Moreover, switching from turbining to pumping requires a certain delay (e.g., 30 min). Some of these constraints actually only refer to a single time instant and therefore they can be considered as static.

6. Forbidden zones: in complex hydro units, effects like mechanical vibrations and cavitation strongly discourage using certain intervals of turbined water, as these would result in low efficiency and/or high output variation (similarly to valve points in thermal units, cf. Sect. 2.2). Therefore, constraints that impose that the turbined water lies outside of these forbidden zones might have to be imposed (Finardi and Scuzziato 2013).

## 2.5 Renewable generation units

Renewable generation in UC mostly refers to wind farms, solar generation, stand alone ROR hydro units, and geothermal production. The fundamental characteristic of all these sources, as far as UC is concerned, is the fact that they cannot be easily
modulated: the produced energy, and even if energy is produced at all (in some wind farms energy is actually consumed to keep the blades in security when wind blows too strongly), is decided by external factors. Some of these sources, most notably solar and wind, are also characterized by their intermittency; that is, it is very difficult to provide accurate forecasts for renewable generation, even for short time horizons (say, day-ahead forecasts). Furthermore, in several cases renewable generation operates in a special regulatory regime implying that they cannot even be modulated by disconnecting them from the grid. This has (not frequently, but increasingly often) led to paradoxical situations where the spot price of energy is actually *negative*, i.e., one is paid to consume the energy that renewable sources have the right to produce (and sell at fixed prices) no matter what the demand actually is. All this has lead to significant changes in the operational landscape of energy production systems, that can be summarized by the following factors:

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

2. Renewable generation has high variance.

3. The correlation between renewable generation and the load can be negative, which is particularly troublesome when load is already globally low, since significant strain is added to conventional generation assets which may have to quickly ramp down production levels, only to ramp them up (again rapidly) not much later. This goes squarely against most of the standard operational constraints in classical UC (cf. Sects. 2.3 and 2.4).

In other words, in UC terms renewable generation significantly complicates the problem; not so much because it makes its size or structure more difficult, but because it dramatically increases the level of uncertainty of net load (the load after the contribution of renewables is subtracted), forcing existing generation units to serve primarily (or at least much more often than they were designed to) as backup production in case of fluctuations, rather than as primary production systems. This increases the need of flexible (hydro-)thermal units ready to guarantee load satisfaction at a short notice, which however typically have a larger operational cost. We refer to Bouffard and Galiana (2008), Siahkali and Vakilian (2010), Moura and Almeida (2010), Miranda et al. (2011) and Sayed (2005) for further discussion of the integration of renewable generation in UC.

## 2.6 System-wide constraints

The most common form of system-wide constraints are the load constraints guaranteeing that global energy demand is exactly satisfied for each $t \in T$. This kind of constraint is not present in the self-scheduling version of UC where each unit reacts independently to price signals, but global load satisfaction has to be taken into account, sooner or later, even in liberalized market regimes. For instance, in several countries, after the main energy market is cleared, GENCOs can swap demand between different units in order to better adjust the production schedules corresponding to the accepted bids to the operational constraints of their committed units, that are not completely represented in the auctions (Read 2010). Alternatively, or in addition, an *adjustment market* is ran where energy can be bought/sold to attain the same result (Palamarchuk
2012; Sauma et al. 2012). In both these cases the production schedules of all con-
cerned units need be taken into account, basically leading back to global demand
constraints. Also, in UC-based bidding systems the global impact of all the generation
capacity of a GENCO on the energy prices need to be explicitly modeled, and this
again leads to constraints linking the production levels of all units (at least, these of
the given GENCO) that are very similar to standard demand constraints. Conversely,
even demand constraints do not necessarily require the demand to be fully satisfied;
often, slacks are added so that small amounts of deviation can be tolerated, albeit at a
large cost (e.g., Dubost et al. 2005; Zaourar and Malick 2013).

Another important issue to be mentioned is that the demand constraints need in
general to take into account the shape and characteristics of the transmission network.
These are typically modeled at three different levels of approximation:

- The *single bus model*: basically the network aspects are entirely disregarded and the demand is considered satisfied as soon as the total production is (approximately) equal to the total consumption, for each time instant, irrespectively of where these happen on the network. This corresponds to simple linear constraints and it is the most common choice in UC formulations.

- The *DC model* where the network structure is taken into account, including the capacity of the transmission links, but a simplified version of Kirchhoff laws is used so that the corresponding constraints are still linear, albeit more complex than in the bus model (Lee et al. 1994; Jabr 2010; Fonoberova 2010). In Ardakani and Bouffard (2013) the concept of *umbrella constraints* is introduced to define a subset of the network DC constraints that are active in order to significantly reduce the size of these constraints.

- The *AC model* where the full version of Kirchhoff laws is used, leading to highly nonlinear and nonconvex constraints, so that even the corresponding ED becomes difficult (Murillo-Sanchez and Thomas 1998; Momoh et al. 1999a,b; Sifuentes and Vargas 2007a,b). A recent interesting avenue of research concerns the fact that the non-convex AC constraints can be written as quadratic relations (Jabr 2006, 2008; Lavaei and Low 2012), which paves the way for convex relaxations using semidefinite programming approaches (Molzahn et al. 2013). In particular, in the recent (Hijazi et al. 2013) a quadratic relaxation approach is proposed which builds upon the narrow bounds observed on decision variables (e.g., phase angle differences, voltage magnitudes) involved in power systems providing a formulation of the AC power flows equations that can be better incorporated into UC models with discrete variables, notably the ones of cf. Sect. 2.7. A recount of these recent developments can be found in Bienstock (2013).

Although market-based electrical systems have in some sense made network con-
straints less apparent to energy producers, they are nonetheless still very relevant
nowadays; not only in the remaining vertically integrated electrical systems, but also
for the TSO that handles network security and efficiency. This requires taking into
account a fully detailed network model, even considering security issues such as
*N* − 1 fault resilience, together with a reasonably detailed model of GENCOs’ units
(comprising e.g., infra-hour power ramps, start-up costs, and start-up/shut-down ramp
rate), when solving the Market Balancing problem. The latter is basically a residual
demand, bidding-based UC. From a different perspective, network constraints might also be important for GENCOs that are able to exercise market power in case *zonal* or *nodal pricing* is induced by the network structure (Price 2007).

Finally, both for vertically integrated system and in the TSO perspective, other relevant system-wide constraints are spinning reserve ones: the committed units must be able to provide some fraction (at least 3% according to Takriti et al. 1996) of the total load in order to cope with unexpected surge of demand or failures of generating units and/or transmission equipment. Other global constraints linking all units, or some subsets of them, exist: for instance, all (or specific subsets of) fossil-fuel burning units may have a maximum cap on the generation of pollutants (CO₂, SOₓ, NOₓ, particles, ...) within the time horizon (Hsu 1991; Fu et al. 2005; Gjengedal 1996; Kuloor et al. 1992; Wang et al. 1995). Alternatively, a cluster of geographically near units (a *plant*) burning the same fuel (typically gas) may be served by a unique reservoir, and can therefore share a constraint regarding the maximum amount of fuel that can be withdrawn from the reservoir within the time horizon (Aoki et al. 1989, 1987; Tong and Shahidehpour 1989; Fu et al. 2005; Cohen and Wan 1987). Finally, there may be constraints on the minimum time between two consecutive start-ups in the same plant (Dubost et al. 2005), e.g., due to crew constraints. If a plant comprises a small enough number of units it could alternatively be considered as a single “large” unit, so that these constraints become technical ones of this aggregated generator. The downside is that the problem corresponding to such a meta-unit then becomes considerably more difficult to solve.

## 2.7 Optimal transmission switching

Traditionally, in UC models the transmission network has been regarded as a “passive” element, whose role was just to allow energy to flow from generating units to demand points. This is also justified by the fact that electrical networks, unlike most other networks (logistic, telecommunications, gas, water, ...) are “not routable”: the current can only be influenced by changing nodal power injection, which is however partly fixed (at least as demand is concerned). Indeed, in traditional UC models there were no “network variables”, and the behavior of the transmission system was only modeled by constraints. However, as the previous paragraph has recalled, the transmission network is by far not a trivial element in the system, and separate network variables are required. Recently, the concept has been further extended to the case where the system behavior can be optimized by dynamically changing the *topology* of the network. This is a somewhat counterintuitive consequence of Kirchhoff laws: opening (interrupting) a line, maybe even a congested one, causes a global re-routing of electrical energy and may reduce the overall cost, e.g., by allowing to increase the power output of some cheaper (say, renewable) units (Fisher et al. 2008). This effect can be especially relevant in those parts of the network with a high fraction of renewables whose production is sometimes cut off because of network constraints.

Thus, a new class of problems, called optimal transmission switching (OTS) or system topology optimization (STO), has been defined whereby each line of the network
has an associated binary decision (for each $t \in T$) corresponding to the possibility of opening it. This makes the problem difficult to solve even with a very simple model of nodal injections and a simple network model such as the DC one (cf. Sect. 2.6); even more so with the AC model and a complete description of the generating units. The so-called UCOTS models (Fisher et al. 2008; Di Lullo 2013; Hedman et al. 2011a, b; Ruiz 2012; Bienstock and Verma 2011; Villumsen and Philpott 2011; Papavasiliou et al. 2013b; O'Neill et al. 2010; Ostrowski et al. 2012; Ostrowski and Wang 2012; Liu et al. 2012b, a; Korad and Hedman 2013; Hedman et al. 2010, 2009; Zhang and Wang 2014) extend UC: almost everything that can be said about UC is a fortiori valid for UCOTS, and therefore in the following we will not distinguish between the two unless strictly necessary.

# 3 Methods for the deterministic Unit Commitment

We now proceed with a survey of solution methods for (the deterministic) UC. Our choice to first focus on the case where the several forms of uncertainty arising in UC (cf. Sect. 2.1) are neglected is justified by the following facts:

- UC already being a rather difficult problem in practice, most work has been carried out in the deterministic setting;

- uncertainty can be taken into account through various “engineering rules”: for instance, spinning reserves allow to account for uncertainty on load, tweaking reservoir volumes might allow to account for uncertainty on inflows, and so on;

- methods for solving the deterministic UC are bound to provide essential knowledge when dealing with UUC.

As discussed in Sect. 2, UC is not one specific problem but rather a large family of problems exhibiting common features. Since the set of constraints dealt with in the UC literature varies from one source to another, we define what we will call a *basic Unit Commitment problem* (bUC) which roughly covers the most common problem type; through the use of tables we will then highlight which sources consider additional constraints. A bUC is a model containing the following constraints:

1. offer-demand equilibrium;

2. minimum up or down time;

3. spinning reserve;

4. generation capacities.

The UC literature review (Sheble and Fahd 1994), of which Padhy (2004) is essentially an update adding heuristic approaches, generally classify UC methodology in roughly eight classes. We will essentially keep this distinction, but regroup all heuristic approaches in “Meta-heuristics”, thus leading us to a classification in:

1. Dynamic programming;

2. MILP approaches;

3. Decomposition approaches;

4. (Meta-)heuristics approaches.

We will also add some of the early UC approaches in the Heuristic class such as priority listing. However, we will not delve much on that class of approaches, since
the recent surveys (Farhat and El-Hawary 2009; Saravanan et al. 2013) mainly focus on these, while providing little (or no) details on approaches based on mathematical programming techniques, that are instead crucial for us in view of the extension to the UUC case.

## 3.1 Dynamic programming

Dynamic Programming (DP, see e.g., Bellman and Dreyfus 1962; Bertsekas 2005, 2012) is one of the classical approaches for UC. As discussed below, it is nowadays mostly used for solving *subproblems* of UC, often in relation with Lagrangian-based decomposition methods (cf. Sect. 3.3); however, attempts have been made to solve the problem as a whole. There have been several suggestions to overcome the *curse of dimensionality* that DP is known to suffer from; we can name combinations of DP and priority listing (DP-PL) (Snyder et al. 1987; Hobbs et al. 1988), sequential combination (DP-SC) (Pang et al. 1981), truncated combination (DP-TC) (Pang and Chen 1976), sequential/truncated combination (DP-STC) (the integration of the two aforesaid methods) (Pang et al. 1981), variable window truncated DP (Ouyang and Shahidehpour 1991), approximated DP (Farias and Roy 2003) or even some heuristics such as the use of neural network (Ouyang and Shahidehpour 1991) or artificial intelligence techniques (Wang and Shahidehpour 1993). The multi-pass DP approach (Yang and Chen 1989; Erkmen and Karatas 1994) consists of applying DP iteratively, wherein in each iteration the discretization of the state space, time space and controls are refined around the previously obtained coarse solution; usually, this is applied to ED, i.e., once commitment decisions have been fixed. In Pang et al. (1981) three of the aforesaid methods, DP-PL, DP-SC, and DP-STC are compared against a priority list method on a system with 96 thermal units, showing that the DP-related approaches are preferable to the latter in terms of time and performance. The recent Singhal and Sharma (2011) performs a similar study on a bUC with 10 thermal units, but only DP approaches are investigated.

Despite its limited success as a technique for solving UC, DP is important because of its role in dealing with sub-problems in decomposition schemes like Lagrangian relaxation. These typically relax the constraints linking different unit together, so that one is left with single-Unit Commitment (1UC) problems, i.e., self-scheduling ones where the unit only reacts to price signals. In the “basic” case of time-independent startup costs 1UC can be solved in linear time on the size of $T$. When dealing with time-dependent startup costs instead, this cost becomes quadratic (Bard 1988; Zhuang and Galiana 1988). However, this requires that the optimal production decisions $p_t^i$ can be independently set for each time instant if the corresponding commitment decision $u_t^i$ is fixed, which is true in bUC but not if ramp rate constraints are present. It is possible to discretize power variables and keep using DP (Bechert and Kwatny 1972), but the approach is far less efficient and the determined solution is not guaranteed to be feasible. An efficient DP approach for the case of ramp rate constraints and time-dependent startup costs has been developed in Fan et al. (2002) under the assumption that the power production cost is piecewise linear. This has been later extended in Frangioni and Gentile (2006b) for general convex cost functions; under mild conditions (satisfied e.g., in the standard quadratic case), this procedure has
cubic cost in the size of *T*. DP has also been used to address hydro valley sub-problems in Siu et al. (2001) where a three stage procedure is used: first an expert system is used to select desirable solutions, then a DP approach is used on a plant by plant basis, and a final network optimization step resolves the links between the reservoirs. In Salam et al. (1991) expert systems and DP are also coupled in order to solve UC. We also mention the uses of expert systems in Mokhtari et al. (1988).

Most often DP approaches are applied to bUC; this is the case in Pang and Chen (1976); Pang et al. (1981); Ouyang and Shahidehpour (1991, 1992); Fan et al. (2002); Siu et al. (2001); Salam et al. (1991); Mokhtari et al. (1988); Singhal and Sharma (2011); Bechert and Kwatny (1972). Other constraints have been considered such Must Run/Off Pang and Chen (1976); Ouyang and Shahidehpour (1992), Fixed Generation Pang and Chen (1976), Crew Pang and Chen (1976), Ramp-Rate Frangioni and Gentile (2006b); Frangioni et al. (2008); Fan et al. (2002); Mokhtari et al. (1988); Wang and Shahidehpour (1993), Operating Reserve Siu et al. (2001), Maintnance Mokhtari et al. (1988), Hydro-Thermal Frangioni et al. (2008); Siu et al. (2001), Fuel Al-Kalaani et al. (1996), Emission Hsu (1991).

## 3.2 Integer and mixed integer linear programming

### 3.2.1 Early use: exhaustive enumeration

As its name implies, this approach focuses on a complete enumeration of the solution space in order to select the solution with the least cost. bUC is addressed in Kerr et al. (1966) and Hara et al. (1966), while in Hara et al. (1966) the cost function considers penalties for loss of load and overproduction. In Kerr et al. (1966) a set of 12 thermal units on a 2h basis is scheduled. In Hara et al. (1966) a problem with two groups, each of which has five thermal units is analyzed. This traditional approach obviously lacks scalability to large-scale systems. However, some enumeration may find its way into hybrid approaches such as decomposition methods under specific circumstances, like in Finardi and Silva (2006) where enumeration is used in some of the subproblems in a decomposed hydro valley system.

### 3.2.2 Modern use of MILP techniques

With the rise of very efficient MILP solvers, MILP formulations of UC have become common. In general, their efficiency heavily depends on the amount of modeling detail that is integrated in the problem. Early applications of MILP can be found in Garver (1962), Muckstadt and Wilson (1968) and Cohen and Yoshimura (1983), and in Cohen and Yoshimura (1983) it is stated that the model could be extended to allow for probabilistic reserve constraints. Hydro-thermal UC is considered in Dillon et al. (1978), Pereira and Pinto (1983) and Shaw et al. (1985) where constraints regarding hydro units such as flow equations, storage level of reservoirs, pump storage and min and max outflow of each reservoir are incorporated in the model.

Some specific constraints such as the number of starts in a day or particular cost functions with integrated banking costs can be found in Turgeon (1978) and Lauer
et al. (1982). In Lauer et al. (1982) the authors combine Lagrangian relaxation (e.g., Muckstadt and Koenig 1977) with a B&B procedure in order to derive valid bounds to improve the branching procedure. The upper bound is derived by setting up a dynamic priority list in order to derive feasible solutions of the UC and hence provide upper bounds. It is reported that a 250 unit UC was solved up to 1% of optimality in less than half an hour, a significant feat for the time. A similar approach is investigated in Parrilla and García-González (2006), where a heuristic approach using, among things, temporal aggregation is used to produce a good quality integer feasible solution to warm-start a B&B procedure.

While MILP is a powerful modeling tool, its main drawback is that it may scale poorly when the number of units increases or when additional modeling detail is integrated. To overcome this problem it has been combined with methods such as DP (Bond and Fox 1986), logic programming (Huang et al. 1998) and quadratic programming (QP) (Shafie-Khah and Parsa 2011). In Shafie-Khah and Parsa (2011) a hydro-thermal UC with various constraints is solved; a customized B&B procedure is developed wherein binary variables are branched upon according to their difference from bounds. The approach does not require any decomposition method, and it is reported to reduce solution time significantly in comparison to other methods. The paper builds upon Fu and Shahidehpour (2007), where a six-step solution is proposed to solve large-scale UC; the algorithm is reported to be capable of solving security-constrained problems with 169, 676 and 2,709 thermal units in 27 s, 82 s and 8 min, respectively. This so-called fast-security constraint Unit Commitment problem (F-SCUC) method is based on an ad-hoc way of fixing binary variables and gradually unlock them if needed, using Benders-type cuts to this effect. However, in Frangioni et al. (2008) it is reported that MILP models where the objective function is piecewise-linearly approximated are much more effective than the direct use of MIQP models, at least for one specific choice and version of the general-purpose MIQP solver. In Frangioni et al. (2011) MILP and Lagrangian methods are combined, solving problems with up to 200 thermal units and 100 hydro units in a few minutes if the desired accuracy is set appropriately.

Systems with a significant fraction of hydro generation require a specific mention due to a notable characteristic: the relationship between the power that can be generated and the level of the downstream reservoir (head-to-generated-power function), that can be highly nonlinear (Catalão et al. 2006), and in particular nonconvex. This can be tackled by either trying to find convex formulations for significant special cases (Yu et al. 2000), developing ad-hoc approximations that make the problem easier to solve (Catalão et al. 2010), or using the modeling features of MILP to represent this (and other nonconvex) feature(s) of the generating units (Piekutowki et al. 1994; Chang et al. 2001). However, developing a good approximation of the true behavior of the function is rather complex because it depends on both the head value of the reservoir and the water flow. MILP models for accurately representing this dependency have been presented in Jia and Guan (2011), and more advanced ones in Borghetti et al. (2008) using ideas from d'Ambrosio et al. (2010); while they are shown to significantly improve the quality of the generated schedules, this feature makes UC markedly more complex to solve.
### 3.2.3 Recent trends in MILP techniques

Recently, MIP (and in particular MILP) models have attracted a renewed attention due to a number of factors. Perhaps the most relevant is the fact that MILP solvers have significantly increased their performances, so that more and more UC formulations can be solved by MILP models with reasonable accuracy in running times compatible with actual operational use (Carrión and Arroyo 2006). Furthermore, selected nonlinear features—in particular convex quadratic objective functions and their generalization, i.e., second-order cone constraints—are nowadays efficiently integrated in many solvers, allowing to better represent some of the features of the physical system. This is especially interesting because MIP models are much easier to modify than custom-made solution algorithms, which—in principle—allow to quickly adapt the model to the changing needs of the decision-makers. However, it has to be remarked that each modification to the model incurs a serious risk of making the problems much more difficult to solve. Two somewhat opposite trends have recently shown up. On one side, tighter formulations are developed that allow to more efficiently solve a given UC problem because the continuous relaxation of the model provides better lower bounds. On the other hand, more accurate models are developed which better reflect the real-world behavior of the generating units and all the operational flexibility they possess (cf. e.g., Hobbs et al. 2001; Lu and Shahidehpour 2005; Makkonen and Lahdelma 2006), thereby helping to produce better operational decisions in practice.

On the first stream, the research has focused on finding better representations of significant fragments of UC formulations. For instance, Ostrowski et al. (2012) and Morales-España et al. (2013a) develop better representations of the polyhedra describing minimum up- and down-time constraints and ramping constraints, whereas Frangioni et al. (2009), Wu (2011) and Jabr (2012) focus on better piecewise-linear reformulations of the nonlinear (quadratic) power cost function of thermal units. Both approaches (that can be easily combined) have been shown to increase the efficiency of the MILP solver for a fixed level of modeling detail.

The second stream rather aims at improving the accuracy of the models in representing the real-world operating constraints of units, that are often rather crudely approximated in standard UC formulations. For hydro units this for instance concerns technical constraints (Chang et al. 2001) and the already discussed water-to-produced-energy function, with its dependency from the water head of the downstream reservoir (Piekutowki et al. 1994; Finardi and Silva 2006; Borghetti et al. 2008). For thermal units, improvements in the model comprise the correct evaluation of the power contribution of the start-up and shut-down power trajectories (when a unit is producing but no modulation is possible) (Arroyo and Conejo 2004), which may make the model significantly more difficult unless appropriate techniques are used (Morales-España et al. 2013b), or a clearer distinction between the produced energy and the power trajectory of the units (García-González and San 2007; Morales-España et al. 2014).

In the OTS context (cf. Sect. 2.7), special care must be given when modeling the Kirchhoff laws, as this leads to logic constraints that, in MILP models, are typically transformed into “Big-M” (hence, weak) linear constraints. Moreover, severe symmetry issues Ostrowski et al. (2010) must be faced (Di Lullo 2013; Ostrowski et al. 2012),
as these can significantly degrade the performances of the B&B approach. All these
difficulties, not shared by UC with DC or AC network constraints, require a nontrivial
extension of the “classic” MILP UC models. Many approaches use off-the-shelf B&B
solvers, while possibly reducing the search space of the OTS binary variables (Ruiz
2012; Ostrowski and Wang 2012; Liu et al. 2012b) and using tight formulations for
the thermal units constraints. All the references use classic quadratic cost functions;
one exception can be found in Di Lullo (2013), where a direct MILP approach is
combined with a perspective cuts approximation (Frangioni et al. 2009) and a special
perturbation of the cost function that successfully breaks (part of the) symmetries.
Together with heuristic branching priorities that give precedence to the thermal UC
status variables, this is shown to be much better than using a classic quadratic function,
with or without perturbations, for solving the IEEE 118 test case.

As far as the constraints are concerned, bUC has been addressed in Garver (1962); Muckstadt and Wilson (1968); Dillon et al. (1978); Dillon and Egan (1976); Bond and Fox (1986); Turgeon (1978); Pereira and Pinto (1983); Shaw et al. (1985); Habibollahzadeh and Bubenko (1986); Lauer et al. (1982); Cohen and Yoshimura (1983); Huang et al. (1998); Shafie-Khah and Parsa (2011); Makkonen and Lahdelma (2006). Many other constraints have been considered, such as Must Run/Off Dillon et al. (1978); Frangioni et al. (2009, 2011), Transmission (comprised OTS) Pereira and Pinto (1983); Fisher et al. (2008); Lu and Shahidehpour (2005); Di Lullo (2013); Hedman et al. (2011a, b); Ruiz (2012); Papavasiliou et al. (2013b); O’Neill et al. (2010); Ostrowski et al. (2012); Ostrowski and Wang (2012); Liu et al. (2012a, b); Korad and Hedman (2013); Hedman et al. (2009, 2010); Zhang and Wang (2014), Modulation Dillon et al. (1978), Starts Turgeon (1978), Hot/Cold Starts Lauer et al. (1982), Ramp Rate Huang et al. (1998); Shafie-Khah and Parsa (2011); Frangioni et al. (2011); Carrión and Arroyo (2006); Lu and Shahidehpour (2005); Ostrowski et al. (2012); Morales-España et al. (2013a); Frangioni et al. (2009); Jabr (2012); Arroyo and Conejo (2004); García-González and San (2007); Morales-España et al. (2013b); García-González and San (2007); Morales-España et al. (2014), Hydro-Thermal Shaw et al. (1985); Shafie-Khah and Parsa (2011); Dillon et al. (1978); Pereira and Pinto (1983); Nilsson and Sjelvgren (1996); Frangioni et al. (2009, 2011), Water head Yu et al. (2000); Piekutowki et al. (1994); Borghetti et al. (2008); Chang et al. (2001); Finardi and Silva (2006), Thermal Stress Li and Shahidehpour (2003), Fuel and Emission Lu and Shahidehpour (2005).

## 3.3 Lagrangian and benders decomposition

UC possesses several forms of structure that can be algorithmically exploited; the
most obvious one is that (complex) units are usually coupled through demand and
reserve requirements [the set X₂ in {1}]. Since these constraints are usually in limited
number and “simple”, Lagrangian Decomposition (or Relaxation, LR) Lemaréchal
(2001), Guignard (2003) and Frangioni (2005) is an attractive approach and has been
widely used. It is based on relaxing these coupling constraints by moving them in
the objective function, weighted by appropriate *Lagrangian multipliers*, so that the
relaxed problem then naturally decomposes into independent subproblems for each
individual unit (1UC); for an arbitrary set of Lagrangian multipliers, the solution of all the 1UCs provides a lower bound on the optimal value of (1). Moreover the mapping (called the dual function, or Lagrangian function) assigning this optimal value to a given set of Lagrangian multipliers is concave; maximizing it, i.e., finding the best possible lower bound, is therefore a convex optimization problem for which efficient algorithms exist.

Two technical points are crucial when developing a LR approach:

- how the maximization of the Lagrangian function, i.e., the solution of the *Lagrangian dual* (LD), is performed;

- since (1) is in general nonconvex the approach cannot be expected to provide an optimal (or even feasible) solution, so methods to recover one have to be developed.

Regarding the first point, one can rely on the available well-developed theory concerning minimization of convex nondifferentiable functions. Standard approaches of this kind are *subgradient methods* (Polyak 1977; Nesterov 2009; d'Antonio and Frangioni 2009) and the *cutting plane method* (CP) (Kelley 1960), also known as the *Dantzig-Wolfe decomposition method* (Dantzig and Wolfe 1960). Early examples of the use of subgradient methods in UC are Fisher (1973), Muckstadt and Koenig (1977), Bertsekas et al. (1983), Merlin and Sandrin (1983), Bard (1988) and Zhuang and Galiana (1988), possibly with modifications such as successive approximation techniques (Cohen and Wan 1987) or variable metric approaches (Aoki et al. 1987). An early example of the use of CP is Aganagic and Mokhtari (1997). The two approaches are rather different: subgradient methods use very simple rules to compute the next dual iterate, whereas CP uses (possibly costly) linear programming (LP) problems for the same task, although hybrid versions have been devised (Tong and Shahidehpour 1989). This is necessary in practice because both approaches have convergence issues, for different reasons: subgradient methods lack an effective stopping criterion, whereas CP tends to be unstable and converge slowly. This is why variants of CP have been devised, e.g., using interior point ideas to provide some stabilizing effect (du Merle et al. 1998); for an application to UC see Madrigal and Quintana (2000). In Ruzic and Rajakovic (1998) the KKT conditions of the Lagrange function are used in order to update the Lagrange multipliers and improve on subgradient approaches. In Redondo and Conejo (1999) CP is stabilized by a trust region. The latter turns out to be a special case of the most effective family of approaches capable of dealing with this kind of problems, that is, (generalized Frangioni 2002) *Bundle methods* (Lemaréchal 1975; Wolfe 1975). These can be seen as a “mix” between subgradient and CP (Bahiense et al. 2002) which inherits the best properties of both (Briant et al. 2008). Several variants of Bundle approaches exist, see e.g., Lemaréchal and Sagastizábal (1994), Lemaréchal et al. (1995) and Astorino et al. (2011); a recent development that is particularly useful for UC is that of methods that allow the inexact solution of the Lagrangian relaxation (Kiwiel 2012; de Oliveira and Sagastizábal 2014; de Oliveira et al. 2013). This feature is of particular interest if operational considerations impose strong restrictions on the solution times for the subproblems. For early application of Bundle methods to UC see e.g., Lemaréchal and Sagastizábal (1995), Luh and Tomastik (1998), Zhang et al. (1999), Gollmer et al. (1999), Feltenmark and Kiwiel (2000), Borghetti et al. (2001) and Borghetti et al. (2003a).
Regarding the second point, one important property of LDs of non-convex programs is that, while they cannot be guaranteed to solve the original problem, they indeed solve a “convexified version” of it (Lemaréchal 2001; Frangioni 2005). In practice, this typically corresponds to a solution $\tilde{x} = (\tilde{p}, \tilde{u})$ to (1) that is feasible for all constraints except the integrality ones. That is, rather than feasible commitment decisions $u_i^t \in \{0, 1\}$ one obtains pseudo-schedules $\tilde{u}_i^t \in [0, 1]$ that satisfy the constraints with the production decisions $\tilde{p}$. Such a solution can be obtained basically for free by (appropriately instrumented versions of) subgradient methods (Barahona and Anbil 2000; Anstreicher and Wolsey 2009) and all other algorithms, most notably Bundle ones (Feltenmark and Kiwiel 2000). The pseudo-schedule $\tilde{x}$ can for instance be heuristically interpreted as the probability that unit $i$ be on at instant $t$, and then be used in this guise to devise primal recovery approaches to attain feasible solutions of (1), either by appropriately modifying the objective function (Dubost et al. 2005; Daniilidis and Lemaréchal 2005) or by a heuristic search phase that exploits both $\tilde{x}$ and the integer solutions produced by the LR (Batut and Renaud 1992; Frangioni et al. 2008; Sagastizábal 2012).

Along with early papers which address the bUC (Muckstadt and Koenig 1977; Merlin and Sandrin 1983; Fisher 1973; Bertsekas et al. 1983), we mention papers which address large-scale UC (Merlin and Sandrin 1983; Bertsekas et al. 1983). The authors of Merlin and Sandrin (1983) are among the first who tried to use LR to obtain a solution, and not just to obtain lower bounds for B&B procedures, solving a problem of 172 units. In Lauer et al. (1982) the duality gap problem is tackled by approximating the dual problem with a twice-differentiable mapping which is then maximized by using a constrained Newton's method, after which a heuristic is used to recover a nearly optimal primal solution; a 200 units UC is solved in about 10–12 min. In a subsequent work (Shaw et al. 1985), a three-stage approach is proposed to deal with a—for the time—large-scale hydro-thermal system (100 thermal units and 6 hydro ones). The first stage is based on LR, with the thermal 1UCs solved using DP, while the hydro subproblems are solved by using a penalty multipliers method (Kort and Bertsekas 1972) and a specially tailored Newton's method. A “unit decommitment” method is suggested in Li et al. (1997) and Tseng et al. (2000) where all units are considered online over all $\mathcal{T}$ and then, using the results of the LR, units are decommitted one at a time. This method aims at providing feasible primal solutions first, whereas most LR approaches would aim at optimality first. Further references using LR are Ferreira (1994), Guan et al. (1994) and Salam et al. (1997, 1998), which consider specific dedicated approaches in order to tackle the subproblems, elementary ways of updating the dual and heuristics to recover a primal feasible solution. In Guan et al. (1995) the units cost functions are modified in order to reduce the oscillating behavior of subgradient approaches. In Gollmer et al. (1999) the authors compare a primal MIP based approach with a LR-based approach: Bundle methods are used in order to solve the LD and two Lagrangian heuristics are investigated for primal recovery. The first one searches for time steps where demand constraints are most violated and employs a strategy proposed in Zhuang and Galiana (1988) for changing the commitment variables, while the second one exploits nearly optimal Lagrange multipliers for fixing commitment decisions. In order to recover primal feasibility, both heuristics are followed by solving an ED, wherein the commitment variables
are fixed; this LR-based method is shown to be capable of handling larger and more
complex instances. In Takriti and Birge (2000) the Lagrangian heuristic consists of
formulating a MIP that mixes solutions provided by the dual iterations, selecting the
production schedule of a specific unit among the primal solutions generated by the
LD phase in such a way as to minimize overall cost and satisfy (the dualized) demand
constraints. The resulting MIP is then reformulated in order to allow for an efficient
solution. A similar idea is exploited in Lucas and Triboulet (2012), where the MIP
is solved by using Genetic Algorithms. In Feltenmark and Kiwiel (2000) the dual
multipliers defining the pseudo-schedule are interpreted as probabilities for randomly
selecting commitment decisions after a LD phase; four derived Lagrangian heuristics
are investigated. In Belloni et al. (2003) a two step procedure is proposed, consisting of
a LD phase followed by an augmented Lagrangian (AL) phase for primal recovery. The
AL term is linearized in an ad-hoc way and its penalty slowly sent to infinity. Bundle
methods, CP and sub-gradient methods are compared for solving the LD phase; it is
shown that Bundle methods outperform alternative approaches. Finally, in Borghetti
et al. (2001) Lagrangian approaches are compared with Tabu Search heuristics, and an
improved primal phase is proposed in Borghetti et al. (2003a). The approach is later
extended to the free-market regime (Borghetti et al. 2003b) and to the handling of
ramping constraints (Frangioni et al. 2008) via the use of the specialized DP procedure
of Frangioni and Gentile (2006b). An hybrid version also using MILP techniques is
presented in Frangioni et al. (2011).

LR can be used to deal with ramp rate constraints, fuel related constraints and emission constraints (Cohen and Wan 1987; Aoki et al. 1987; Yan et al. 1993; Tong and Shahidehpour 1989; Zhuang and Galiana 1988) by simply relaxing them (in Lagrangian fashion). Similarly, LR can be employed to further decompose sub-problems, in particular hydro ones; these ideas are explored in Guan et al. (1997), Ni et al. (1999), Finardi and Silva (2006), Takigawa et al. (2012), Takigawa et al. (2013) and Finardi and Scuzziato (2014). More specifically, the authors of Guan et al. (1997) consider the LD related to the bounds on the reservoir levels in the hydro subproblem, which effectively decomposes the problem in smaller MILPs that can then be readily dealt with, through the use of DP in this specific case. The LD is optimized using a subgradient approach, and heuristics are used to recover a primal feasible solution. A similar approach is used in Ni et al. (1999), where hydro units have discrete commitment decisions much like thermal ones. These constraints are then relaxed in a Lagrangian way, resulting in continuous network flow subproblems and a pure integer problem. In Finardi and Silva (2006), *Lagrangian decomposition* Guignard and Kim (1987) is used to deal with forbidden zones in complex hydro units. The idea is to use LR to decompose hydro valley subproblems further into two parts: the first part deals with the flow constraints and basically leads to a simple LP, while the second part deals with the water-head effect and other combinatorial constraints and requires a specific NLP approach (an SQP-based method and partial exhaustive enumeration). Two dual formulations are considered which differ from each other in that in the second one the NLP problem is further decomposed through the use of auxiliary variables. The model is extended to consider network constraints in Takigawa et al. (2012), and different relaxation schemes are explored in Takigawa et al. (2013) and Finardi and Scuzziato (2014); in particular, the latter
compares Lagrangian relaxation and Lagrangian decomposition. In Yan et al. (1993) a system with 70 thermal and 7 hydro units is addressed. Ramp rate constraints are also dualized, and the DP approach of Guan et al. (1991) is used to optimize the thermal units, while a merit order allocation is employed for the hydro subproblem. In Zhuang and Galiana (1988) a three stage approach is proposed based on first solving the LR, then finding a feasible solution for reserve requirements and finally solving an ED. In Nilsson and Sjelvgren (1996) a hydro-thermal system with a fairly realistic model for hydro generation is considered that comprises *forbidden zones* (cf. Sect. 2.4) and the water head effect. The offer-demand equilibrium constraints and reservoir balance equations are dualized, and the LD is maximized with a subgradient approach, with a heuristic step fixing the discrete hydro variables to recover a primal feasible hydro solution. In Aganagic and Mokhtari (1997) some transmission constraints are considered. In Li and Shahidehpour (2003) an alternative to ramping rate constraints in the model for thermal units, a so-called stress effect, is proposed. Coupling offer-demand equilibrium and reserve requirement constraints are dualized; the corresponding LD is maximized using a subgradient approach, where the thermal subproblems are solved using Simulated Annealing techniques. In Fu et al. (2005) a ramp rate, fuel and emission constrained UC is solved. Having been used for a very long time, Lagrangian relaxation has been applied in particular to bUC Aganagic and Mokhtari (1997); Muckstadt and Koenig (1977); Merlin and Sandrin (1983); Cohen and Wan (1987); Aoki et al. (1987); Yan et al. (1993); Tong and Shahidehpour (1989); Zhuang and Galiana (1988); Fisher (1973); Nilsson and Sjelvgren (1996); Fan et al. (2002); Shaw et al. (1985); Borghetti et al. (2001); Madrigal and Quintana (2000); Feltenmark and Kiwiel (2000); Fu et al. (2005); Bertsekas et al. (1983); Li and Shahidehpour (2003). However, other constraints have also been considered, such as Must Run/Off Yan et al. (1993); Zhuang and Galiana (1988); Frangioni et al. (2011), Fuel Aoki et al. (1987); Tong and Shahidehpour (1989); Fu et al. (2005); Cohen and Wan (1987), Ramp Rate Fu et al. (2005); Cohen and Wan (1987); Yan et al. (1993); Frangioni et al. (2008, 2011); Borghetti et al. (2003a, b); Li and Shahidehpour (2003); Aoki et al. (1989), Reserve Aganagic and Mokhtari (1997); Cohen and Wan (1987), Hydro-Thermal Aoki et al. (1987); Yan et al. (1993); Takigawa et al. (2013); Borghetti et al. (2003b); Frangioni et al. (2008, 2011); Borghetti et al. (2003a); Nilsson and Sjelvgren (1996); Shaw et al. (1985); Aoki et al. (1989); Finardi and Scuzziato (2014); Finardi and Silva (2006), Emission Fu et al. (2005); Gjengedal (1996); Kuloor et al. (1992), and Transmission Aganagic and Mokhtari (1997); Takigawa et al. (2012).

A different decomposition approach is the classic one due to Benders Benders (1962) and Bonnans et al. (2006, Chapter 11.1), which rather focuses on *complicating variables* that, once fixed, allow to separate the problem into independent (and, hopefully, easy) ones. Application of Benders' decomposition to UC is fairly recent. In Liu et al. (2010) and Wu (2013) techniques for improving the Benders' cuts production are described. In Fu et al. (2013) a conceptual and numerical comparison is made, in the context of the security constrained UC, between LR and MILP approaches (cf. Sect. 3.2) for the solution of the *master problem* of Benders' decomposition. For the subproblems, involving the network constraints, the authors compare Benders' cuts and linear sensitivity factor (LSF) approaches.
## 3.4 Augmented Lagrangian relaxation

One major downside of LR approaches is the difficulty in recovering a primal feasible solution. The use of the augmented Lagrangian (AL) method, whereby a quadratic penalization of the relaxed constraints is added to the objective function alongside the linear penalization typical of standard LR, is known to be a potential solution to this issue. Yet, because (1) is nonconvex it should be expected that in general the AL approach leads to a local optimizer (Gill et al. 1982; Luenberger and Ye 2010). Furthermore, the AL relaxation is no longer separable into an independent subproblem for each unit, and therefore it is significantly more difficult to solve (in practice, as difficult as UC itself). This calls for some further approach to simplify the relaxation; in Batut and Renaud (1992) and Yan et al. (1994) the use of the *auxiliary problem principle* Cohen (1980) and Cohen and Zhu (1984) is suggested. The classic theory of the auxiliary problem principle requires restrictive assumptions such as convexity and regularity, which do not hold in practice; some recent advances have been made in the non-convex setting (Attouch et al. 2010; Razaviyayn et al. 2012; Tseng 2001). In Beltran and Heredia (2002) an alternative decomposition scheme based on block coordinate descent (e.g., Ruszczyński 1995; Bertsekas 1999) is proposed and it is found to be more efficient. The recent Mezger and Almeida (2007) includes in the UC formulation a DC network model and bilateral contracts defining the nodal injections. The AL of the coupling constraints is formed and then linearized in an ad-hoc way, while Bundle methods are employed for updating the dual multipliers. Environmental constraints (Wang et al. 1995) and network transmission constraints (Beltran and Heredia 2002), Wang et al. (1995) have also been tackled with the AL approach. A common way to deal with additional constraints is variable duplication (Georges 1994). Augmented Lagrangian approaches have been applied to bUC in Batut and Renaud (1992); Beltran and Heredia (2002); Wang et al. (1995); Baldick (1995), while Modulation constraints and Startup/shutdown curves are considered in Batut and Renaud (1992), Transmission in Baldick (1995); Beltran and Heredia (2002); Wang et al. (1995), Ramp Rates in Baldick (1995); Batut and Renaud (1992), Environmental constraints in Wang et al. (1995), and Hydro-Thermal systems in Batut and Renaud (1992); Baldick (1995).

## 3.5 (Meta-)Heuristics

### 3.5.1 Operator rule based: priority listing

This method defines a list of units which should logically be scheduled prior to other units, with merit order scheduling being a special case. Priority listing was first employed on bUC in Baldwin et al. (1959), where units are listed according to their performance and the cost they yield (comprising maintenance costs). Must-on/must-off and crew constraint have been added in Lee (1988), and a limit on the number of starts is included in Lee (1991) through the use of a commitment utilization factor, which is claimed to provide a better list. While the former two papers and Amiri and Khanmohammadi (2013) address bUC, there has been an endeavour to integrate other
factors such as multi-area constraints (Lee and Feng 1992) and hydro-thermal systems (Johnson et al. 1971) for large-scale UC. In the latter paper a two-step heuristic procedure is used to solve a UC with 100 units: the first step uses rules from real-world schedules (possibly enhanced by the use of UC software) to set up a priority list consisting of feasible production schedules, while the second step optimizes locally around the current solution. A very similar approach is investigated in Amiri and Khanmohammadi (2013). Priority lists have been applied to bUC in Baldwin et al. (1959); Lee (1988, 1991); Amiri and Khanmohammadi (2013); Lee and Feng (1992); Johnson et al. (1971), but other constraints have been considered such as Number of Units Started Johnson et al. (1971), Crew Lee (1988), Must run/Off Lee (1988); Lee and Feng (1992), Multi-Area Lee and Feng (1992), Hydro-Thermal Johnson et al. (1971), and maximum number of starups/shutdowns Lee (1991).

### 3.5.2 Guided random exploration

Since solving the UC (1) to optimality is quite difficult, many heuristic approaches such as Taboo search, Simulated Annealing, Augmented Lagrange Hopfield Networks, Nature Inspired (e.g., particle swarms, frog leaping, ...) and Genetic Algorithms have also been employed. We refer to Farhat and El-Hawary (2009) and Saravanan et al. (2013) for a discussion of those approaches, and in this paper we by no means attempt to give a full overview of this subfield. This is because heuristic approaches like these are typically difficult to adapt to the Uncertain UC case, which is the main focus of this survey, unless they are at least partly based on mathematical programming techniques. We therefore concentrate mostly on "hybrid" approaches that use the latter at least to a certain degree. For instance, in Lucas and Triboulet (2012) genes are feasible schedules produced by a LR-based scheme: the genetic algorithm then mixes the solutions up to form new feasible schedules in order to hopefully produce a solution that better meets the demand constraints. In Zhuang and Galiana (1990) the authors solve a 100 thermal unit system by using Simulated Annealing and report that their approach outperforms a B&B procedure, but fails to outperform a LR approach (although in the later Borghetti et al. 2001 Taboo search has been reported to be more competitive with LR). In Duo et al. (1999) and Juste et al. (1999) Evolutionary Programming is applied to adjust the solution provided by a LR approach. In Luh et al. (1999) a neural network approach is coupled to LR in order to optimize a system with up to 60 units: the thermal subproblems are optimized using a neuron-based DP algorithm.

In general, these approaches are not considered particularly competitive for UC; for instance, Takriti et al. (2000) states that Simulated Annealing and Evolutionary Programming attempts have been unsuccessful. Also, usually these approaches deal with bUC, with only a few sources considering ramp rate, crew, maintenance or multi-area constraints, and hydro-thermal systems being very rarely dealt with. The likely reason is that purely combinatorial heuristics are best apt at problems that exhibit a predominant and relatively "simple" combinatorial structure to which the various elements of the heuristic (neighborhood(s) structure in Simulated Annealing, Taboo list and aspiration criteria in Taboo search, mutation and crossover operators in genetic algorithms, ...) can be specifically tailored. UC is a fundamentally mixed combinatorial and continuous program, since both the commitment and the dispatch have to be
provided. Furthermore, UC has several different combinatorial structures, especially when “complex” constraints have to be dealt with. Therefore, on the outset UC is best approached with mathematical programming techniques.

Heuristic approaches are most often applied to bUC; however, for each of them works considering some other constraints have been proposed. A (very partial) overview of the constraints considered in heuristic approaches is:

*   *Simulated Annealing*: bUC in Zhuang and Galiana (1990); Annakkage et al. (1995); Simopoulos et al. (February 2006); Mantawy et al. (1998), Ramp Rate in Simopoulos et al. (February 2006), Crew in Zhuang and Galiana (1990); Annakkage et al. (1995); Mantawy et al. (1998), and Maintenance in Zhuang and Galiana (1990);

*   *Taboo Search*: bUC in Mantawy et al. (1998); Victoire and Jeyakumar (2005); Mori and Matsuzaki (2001); Borghetti et al. (2001); Lin et al. (2002); Rajan et al. (2003); Mantawy et al. (2002), Crew and Derating in Mantawy et al. (1998), Hydro-Thermal in Mantawy et al. (2002);

*   *Neural Network*: bUC in Sendaula et al. (1991); Sasaki et al. (1992); Walsh and O'Malley (1997); Abdelaziz et al. (2010); Senthil-Kumar and Palanisamy (2007); Wang and Shahidehpour (1993); Dieu and Ongsakul (2008); Nayak and Sharma (2000); Liang and Kang (2000); Luh et al. (1999), Ramp Rate in Sendaula et al. (1991); Abdelaziz et al. (2010); Wang and Shahidehpour (1993); Dieu and Ongsakul (2008), Crew in Nayak and Sharma (2000), and Hydro-Thermal in Walsh and O'Malley (1997);

*   *Genetic Algorithm*: bUC in Wong and Wong (1996, 1994); Sudhakaran and Ajay-D-Vimal (2010); Valenzuela and Smith (2002); Yang et al. (1996); Chitra-Selvi et al. (2009); Rajan and Mohan (2004); Rajan et al. (2012); Sheble et al. (1996); Juste et al. (1999); Duo et al. (1999); Dasgupta and McGregor (1994); Lucas and Triboulet (2012), Ramp Rate in Sheble et al. (1996); Wong and Wong (1994); Rajan and Mohan (2004), and Multi-Area in Chitra-Selvi et al. (2009); Rajan et al. (2012);

*   *Nature Inspired*: Ramp Rate in Ge (2010); Chandrasekaran and Simon (2012a, b), and Multi-Area in Chandrasekaran and Simon (2012b).

## 4 Methods for the uncertain Unit Commitment

The complex nature of UC, due to its numerous technical constraints, forces the schedule to be determined quite ahead of time and consequently be given to the TSO 1 day in advance. This allows for uncertainty to have a significant impact on the system. Furthermore, intra-daily optimization processes and communication between the TSO and the GENCOs allow for recourse decisions. Thus, dealing with uncertainty has always been necessary in UC. We now discuss the approaches that have been proposed in the literature. To the best of our knowledge, this has never been done before specifically for the UC. The chapter (Wallace and Fleten 2003) provides a general overview of the ways in which uncertainty arises in Energy Management, but it is mainly focused on mid- and long-term problems, UC being only briefly addressed. Analogously, Conejo et al. (2010) offers a general survey on uncertainty issues in Energy Optimization, without a specific focus on UC. The chapter (Römisch and Vigerske 2010) offers a
general overview of properties of stochastic optimization problems and briefly provides some links to stochastic UC problems. The essential references used in these sources will be discussed below.

## 4.1 Dealing with uncertainty in UC

In most traditional approaches, load uncertainty is dealt with by computing the schedule corresponding to the worst scenario, i.e., typically that of peak demand in each period. This choice systematically overestimates demand and incurs the risk that significant ramp-down of the production is needed when the actual demand proves to be substantially smaller than the forecasted one, which can cause feasibility issues due to technical constraints like *ramp-down* ones (cf. Sect. 2.3). Another common approach has been to use spinning reserve constraints (cf. Sect. 2.6) (Wu et al. 2007; Anstine et al. 1963; Billinton and Karki 1999; Fotuhi-Firuzabad and Billinton 2000; Gooi et al. 1999); the advantage is that this protects against some degree of uncertainty while keeping the deterministic formulation. In general, the deterministic constraints can be “tweaked” heuristically in order to deal with uncertainty. For instance, in order to ensure that the solution can survive a certain degree of variability in the data we can underestimate the amount of water in a hydro reservoir and/or impose stricter ramp-rate constraints than justified by technical aspects. Obviously, this may result in a loss of optimality or control over feasibility. Worse, one may lose control over where the approximations have been made.

In order to overcome these weaknesses, methods where uncertainty is directly modeled have been investigated. These comprise stochastic optimization (scenario tree), robust optimization, and chance-constrained optimization.

### 4.1.1 Dealing with uncertainty in the model

#### 4.1.1.1 Stochastic optimization
Scenario tree based approaches (from now on denoted as SO, i.e., Stochastic Optimization) have been the subject of intense research in the last two decades; see e.g., Prékopa (1995, Chapter 13) Birge and Louveaux (1997), Louveaux and Schultz (2003), Kall and Mayer (2005) and Ruszczyński and Shapiro (2009a,b) among the many other general references. Their use in the UC context has been considered e.g., in Takriti et al. (1996), Carpentier et al. (1996), Ozturk et al. (2004), Wu et al. (2007) and Wong and Fuller (2007). The key advantage of using scenario trees is that uncertainty is assumed to be known in each node of the tree. Since moreover uncertainty is now discretized on the tree, essentially this amounts to solving a deterministic UC of very large scale. The authors of Tuohy et al. (2009) demonstrate the interest of SO over deterministic optimization using such a direct reformulation. According to Bertsimas et al. (2013), SO methods have two major drawbacks. First, obtaining an accurate probability distribution can be difficult, i.e., setting up an accurate tree is hard. Indeed, while generating scenarios for each individual uncertainty factor may be relatively straightforward, combining these to form a tree structure is not easy. Second, these solutions provide only probabilistic guarantees. The first difficulty can be partially tackled by the approaches considered
in Dupačová et al. (2003), Heitsch and Römisch (2003, 2011), Heitsch and Römisch (2009) and Eichhorn et al. (2010), that provide tools for systematically generating manageable trees. Classical approaches (e.g., Takriti et al. 1996) to form a tree are those that start out with a set of scenarios and progressively regroup similar scenarios to form the nodes, in each of which a representing scenario is selected. The use of physical models for generating uncertainty (e.g., Constantinescu et al. 2011) could also help improve the realism of the underlying scenario tree. The second difficulty can be tackled by using a hybrid approach that also considers spinning reserve requirements on the scenario tree (Ruiz et al. 2009; Wu et al. 2007), which can be used to account for events not modeled in the tree. We mention in passing that similar techniques can also be applied to longer-term problems, such as the management of an hydro reservoirs, that although not strictly pertinent to this paper are clearly strongly related. For a recent instance, a specialized Stochastic Dual DP algorithm is proposed in Guigues (2013).

### 4.1.1.2 Robust optimization
In order to be less demanding on the representation of uncertainty, robust optimization (RO) uses the notion of *uncertainty set*, which basically reunites the adverse events against which we wish to protect ourselves. For a comprehensive introduction to robust optimization we refer to Ben-Tal et al. (2009) and Bertsimas et al. (2011); other important references are Ben-Tal and Nemirovski (1998, 1999, 2000), El Ghaoui and Lebret (2006), El Ghaoui et al. (1998) and Bertsimas and Sim (2003, 2004). RO approaches might lead to a substantially higher costs of the proposed solution—a too high “price of robustness” (Bertsimas and Sim 2004)—w.r.t. SO ones when distributions of the uncertainty are sufficiently well characterized. This is mainly because RO protects against each event in the specified uncertainty set regardless of its probability, and therefore may have to account for extremely unlikely events. Several RO approaches have parameters (e.g., “budget of uncertainty”) that can be used to adjust the degree of protection offered by the model (Bertsimas and Sim 2003; Nemirovski and Shapiro 2006a; Chen et al. 2007); yet, in general tuning these parameters is far from trivial. To reduce the price of robustness associated with classical ellipsoidal and $\Gamma$-robustness uncertainty sets proposed in Ben-Tal and Nemirovski (1998), El Ghaoui et al. (1998) and Bertsimas and Sim (2004), subsequent studies have investigated alternative *soft* and *light* robustness models (Ben-Tal et al. 2010; Fischetti and Monaci 2009). Recently, *multiband robustness* (Büsing et al. 2012, 2013), has been proposed as a generalization of $\Gamma$-robustness that can support an improved and stratified representation of uncertainty and a reduction in conservatism, while maintaining the computational tractability and accessibility of $\Gamma$-robustness.

### 4.1.1.3 Chance-constrained optimization
Chance-Constrained Optimization provides an attractive way to select the trade-off between cost and robustness, using a notion—the probability of the selected solution to be feasible—that is easy for the decision-maker to understand and manage. We refer to Prékopa (1995, 2003) and Dentcheva (2009) for a modern introduction to probabilistic programming. In van Ackooij et al. (2011) the potentials for energy management applications, such as UC, are evaluated. However, a drawback of CCO is that probabilistic constraints can be nonconvex and hard to evaluate, thus making these approaches potentially computationally demanding.
4.1.1.4 The link between RO and CCO There actually is an important link between RO and CCO. Indeed, an intuitively appealing idea is to select the uncertainty set in such a way as to enforce a probabilistic constraint, so that the solutions produced by the RO approach are comparable with those produced by the CCO one. More generally, one may aim at replacing the probabilistic constraint with a convex, albeit possibly more restrictive, constraint. There are various ways of doing this (e.g., Nemirovski and Shapiro 2006a; Ben-Tal and Nemirovski 2009), often referred to as “safe-tractable approximation approaches” (a somewhat unfortunate terminology implicitly assum- ing that all CCO problems are intractable, which is not the case). Frequently, such convex outer approximations of the CCO-feasible set are derived by using individual probabilistic constraints, i.e., constraints that require that each individual inequality in the constraints system holds with high enough probability (e.g., Chen et al. 2007). Besides using a (not necessarily very tight) approximation, this approach gives little control over the joint violation of the constraints, although it does have the advan- tage that convexity makes the corresponding problems easier to solve. We refer to van Ackooij et al. (2010, 2014) for examples showing that individual probabilistic constraints may lead to an arbitrary number of violated constraints. We also refer to Bandi and Bertsimas (2012) and Guan and Wang (2014) for various other alternatives of building uncertainty sets. The scenario approximation approach (e.g., Calafiore and Campi 2005; Nemirovski and Shapiro 2004, 2006b) can be seen as a special case of RO with a discrete uncertainty set that arose by drawing random samples from the underlying distribution.

4.1.2 Modelling and solution choices

4.1.2.1 The choice of recourse decisions A crucial decision in all two-stage (or multi-stage) models, be they SO, RO or CCO, is which variables represent “here and now decisions” (first stage), to be taken before the uncertainty is revealed, and which represent “recourse actions” (second or later stages) that can change when the uncer- tain parameters are revealed. In multi-stage models a whole chain of decisions and observation of uncertainty needs to be worked out properly. This decision-observation chain may end with the observation of a last random realization offering no recourse actions. This could give rise to the need to consider multi-stage RO (CCO) approaches. When recourse is incomplete (i.e., can not guarantee feasibility of later stages regard- less of the random realizations) such a need may also arise.

In general, recourse formulations aim at minimizing the total cost of the here and now decisions and the expected cost of the possible recourse actions. These problems are typically very challenging from both the computational and theoretical point of view, especially if recourse actions are integer-valued (or otherwise belong to a non-convex set). In the integer setting, a general approach to deal with this formulation was introduced by Laporte and Louveaux (1993). In Løkketangen and Woodruff (1996) a progressive hedging algorithm and Taboo search are used to address multi-stage problems with mixed 0–1 variables. The approaches can become somewhat compu- tationally less demanding if recourse variables are instead continuous, which is often the case in UC. In fact, here commitment variable are typically first-stage decisions, to be taken well in advance, while the actual energy production (usually continuous).
is indeed managed in real time when the uncertain data (load, prices, ...) is revealed. Such a choice is made in Bertsimas et al. (2013) where RO is applied to UC with a two stage approach. Restricting commitment choices to a first stage is a convenient simplification but it does not fully represent reality, where (a few) changes to the commitment of units are in general possible. Accounting for recourse decisions, however, significantly increases the complexity of the problem, which justifies why restricting integer decisions to the first stage is the most common approach.

### 4.1.2.2 Direct approaches versus decomposition
Regardless of the simplifying assumptions on UUC, the resulting mathematical program is frequently a very-large-scale one, which means that decomposition approaches are especially attractive. In some special situations, direct use of MI(N)LP solvers remains possible. This is for instance the case of the *self-scheduling* of a single unit subject to uncertain prices, for which the deterministic problem has a low number of variables. Often, however, the deterministic equivalent (if any) of the uncertain problem is usually so large that it cannot be directly solved by use of MILP solvers, and decomposition is required. This can be achieved by variable duplication, relaxing non-anticipativity constraints, system wide constraints or by using Benders' decomposition. The resulting sub-problems are then CCO (e.g., van Ackooij 2014), RO, deterministic (e.g., Takriti et al. 1996) or stochastic programs (e.g., Carpentier et al. 1996).

We will now present more details on algorithms for Uncertain UC models using these three approaches.

## 4.2 Stochastic optimization (scenario-tree) approaches

In this section we will discuss four common solution approaches to solving scenario-tree based versions of UC: the direct MILP approach and three decomposition methods.

A SO program with scenario-tree structure can be decomposed in at least two ways. Perhaps the most natural one is to relax the so-called *non-anticipativity constraints* and solve as many deterministic UC problems as there are scenarios. This is called the *Scenario Decomposition* approach (Takriti et al. 1996) and includes well-known variants such as progressive hedging (Rockafellar and Wets 1991). The alternative is to dualize the offer demand equilibrium constraints in each node to form a LD (Carpentier et al. 1996) and solve as many stochastic programming problems as there are units. This can be referred to as *space decomposition*, *unit decomposition* or *stochastic decomposition*, because one is basically optimizing a stochastic function, which in this case just happens to have an underlying discrete distribution. We will use unit decomposition (UD), to have a different shorthand from the scenario decomposition (SD). The discretization can be carried out after having formed the LD in an appropriate Banach space setting ($L^1$-type spaces); see for instance Nürnberg and Römisch (2003). We refer to Ruszczyński (2003) for a thorough discussion on various alternatives.

A different applicable approach is Benders' decomposition, cf. Sect. 4.2.4. It exploits the *L*-shaped structure of the problem, whereby the second-stage (recourse) variables corresponding to each scenario are unrelated, and therefore the corresponding subproblems can be solved independently, once the first-stage variables are fixed (Slyke and Wets 1969). This corresponds to seeing the second (or later) stage(s) as
an aggregated expected cost function depending on first (or earlier) stage variables. Under appropriate hypotheses (e.g., no integer decisions in later stages) this expected cost function can be shown to be convex, and cutting planes based approximations can then be used to compute the solution of the master problem (e.g., Oliveira et al. 2011).

### 4.2.1 *Mixed integer linear programming*

In Valenzuela and Mazumdar (2003) the use of UC tools in a deregulated market is discussed. In particular, under the assumptions that prices are stochastic and there is no market power or transmission constraints, a GENCO can solve a self-scheduling UC for each of its units independently, which however should be a SO model due to uncertainty on prices. A MILP formulation for (a basic) UC is proposed, along with three DP approaches to solve it. These approaches are used to produce a cost-based method to generate a distribution of energy prices, based on the assumption that in a competitive market the price should be equal to the marginal cost of the most costly committed unit.

In Philpott and Schultz (2006) a two-stage model is considered where the first stage decisions consists of commitment decisions and an offer curve, while in the second stage the dispatch is computed. Single unit or identical unit systems are considered, although the model with several units can not cope with minimum up/down times. The focus is essentially on obtaining the offer-curve. A DP principle is presented, but no numerical experiments are provided. A very similar model is considered in Triki et al. (2011), wherein commitment decisions and offer curves are first-stage decisions and dispatch later stage decisions. The key focus of these papers is on the market mechanisms.

Hydro scheduling is looked at in a market-based setting in Fleten and Kristoffersen (2008). The problem integrates commitment decisions on the turbined output, which have minimal release rates. Expected gain from selling energy on the market is maximized, whereas volume-dependent water values are used in order to represent the cost of water as measured by the difference between the initial and final volume in the reservoir.

The authors of Beraldi et al. (2008) propose a two-stage formulation wherein the first stage variables consist of bilateral contracts. Once these contracts have been selected, the market price is observed and a bUC is solved in order to meet the resulting load. The objective function consists of Markovitz mean-variance model related to expected profits. A specialized B&B method is used in order to solve the corresponding MILP problem; the numerical experiences cover a GENCO with three thermal units and up to 15 scenarios.

In Cerisola et al. (2009) a weekly UC model is studied wherein profit of a GENCO depends on bids made on the market. The GENCO is assumed to have a non-linear non-convex effect on market prices, modeled through the use of piecewise linear functions and binary variables. The corresponding model is solved using a MILP solver, Lagrangian decomposition and two variants of Benders' decomposition (taken from Cerisola 2004). The computed production schedule is a first stage decision, whereas all other stages and nodes in the scenario tree refer to different realizations of market settling. The Benders-based decomposition approaches are found to be the most interesting, despite the substantial implementation effort.
In Corchero et al. (2013) a two-stage model is considered where commitment decisions and bid prices are first-stage decisions, while total generation and energy matched in the day-ahead market are second-stage decisions (continuous variables). Uncertainty is mainly relative to the spot price, that enters in the generators objective function. The formulated MIQP has a quadratic second-stage cost function, which is linearized by means of perspective cuts (Frangioni and Gentile 2006a). The resulting problem with 10 scenarios and 9 thermal units is solved with a MIQP solver. In this vein we also cite Wang et al. (2008), where the second stage economic dispatch problem, involving wind generation, is used for adding feasibility cuts to the first stage master problem. The main focus here is on deriving “robust” commitment decisions.

### 4.2.2 Scenario decomposition

In Takriti et al. (1996) progressive hedging is used to solve a large-scale bUC with 100 thermal units and 6 hydro ones. A SD scheme is presented in Carøe et al. (1997) and Carøe and Schultz (1998) for solving a two-stage bUC problem (with only a few thermal units), wherein integer variables are restricted to the first stage. The non-anticipativity constraints are dualized by using Lagrangian multipliers, and the overall scheme is inserted into a B&B procedure in order to ensure that an optimal solution is obtained. In Papavasiliou et al. (2011) a scenario decomposition is used, with the focus being on reserve requirements in a system with high wind penetration. In Papavasiliou and Oren (2012) the uncertain renewable production is coupled with the demand response in a market environment. In Papavasiliou et al. (2013a) SD is again used to solve a UUC where the uncertainty is caused by wind power generation, taking into account the network constraints. A decomposition approach mixing scenario and Benders’ decomposition is considered in van Ackooij and Malick (2014). The investigated approach relies heavily on classical tools in deterministic UC, such as Lagrangian decomposition, Lagrangian-based primal recovery heuristics and Bundle methods, but needs no specific assumptions on the set of technically feasible schedules. A real-life problem with 136 thermal units, 22 hydro valleys, 96 times steps and 50 scenarios is solved.

### 4.2.3 Unit (stochastic) decomposition

The standard UD approach is proposed in Carpentier et al. (1996) for a bUC with 50 thermal units; the demand constraints are relaxed, resulting in stochastic sub-problems which are then solved by DP.

In Römisch and Schultz (1996) a multi-stage hydro-thermal UC problem is considered with random customer load. The load is observed after having chosen the commitment decisions, but the actual generation levels (including continuous hydro generation) are determined once that the load is known. The demand constraint is dualized in a general probabilistic space setting, then the probability measure is discretized; no numerical results are presented.

A multi-stage stochastic programming is proposed in Nowak and Römisch (2000) to deal with a hydro-thermal UC with 25 thermal units and 7 hydro units. Load uncertainty is addressed through the use of UD and DP for solving the stochastic sub-
problems; Lagrangian heuristics are then used to recover a primal solution. Similar UD approaches are considered in Dentcheva and Römisch (1998), Nowak (2000) and Gröwe-Kuska et al. (2002).

In Takriti et al. (2000), three uncertainty factors are integrated in the UC problem: load, fuel and electricity prices. The fuel requirement problem basically becomes the second stage of the problem, the first one being a bUC formulation. A Benders' decomposition approach is used to plug the second-stage cost function into the first stage, and a LR approach is used for the first stage. This method is tested on a UUC with 33 thermal units and about 729 demand scenarios.

In Bacaud et al. (2001) a weekly (10 days up to a month) stochastic UC problem is considered. A UD approach is employed, where the LD is solved by a disaggregate Bundle method. The approach associates a set of weights with each node that effectively preconditions the LD; this preconditioning is reported to be crucial for performances. Problems having up to 2000 nodes are solved with the generating units of EDF.

A weekly two-stage UUC is also addressed in Schultz et al. (2003). Both stages have all time steps, and essentially each is a bUC problem; load, price and cost uncertainty are revealed between the two. The problem is decomposed using a LR-based approach that yields a stochastic programming problem for each unit. Lagrangian heuristics based on Zhuang and Galiana (1988) and Gollmer et al. (1999) are employed to recover a primal feasible solution. The authors also present a MILP for market price settling and bidding in a competitive environment. They suggest to incorporate both features into a single model by moving bid/offer decisions and first day commitment decisions in a first stage, while all other variables are moved to the second stage. In Ni et al. (2004) the authors consider a model, with focus on market mechanisms, wherein commitment decisions, while offer curves are first-stage decisions and dispatch are later stage decisions. The authors apply a global LR-based UD for solving the thus formulated problem.

In Nürnberg and Römisch (2003) stochastic Lagrange multipliers are used in order to decompose uncertain demand constraints that have to hold almost surely. The resulting dual function is the expectation of this stochastic Lagrange function. Uncertainty is then discretized into a finite set of random drawings in order to approximate the expectation, and Bundle approaches are used to solve the dual. In this two-stage procedure, integer variables remain present in the second stage.

In Shiina and Birge (2004) the UD approach to the stochastic bUC with uncertain demand is revisited in terms of Dantzig-Wolfe decomposition (the equivalence between this and a LR approach solved by CP being well-known). This results in a column generation approach where the Lagrangian subproblem, solved by DP on the scenario tree, generates schedules for each unit that are added to the restricted master problem.

### 4.2.4 Benders(-like) decomposition

The L-shaped method can be used to decompose UC problems with several stages. In its basic version a single cut is added to the first stage problem, whereas in advanced versions multiple cuts (e.g., one for each subproblem) can be added. This
may increase convergence speed at the cost of an increased master problem cost; we refer to the discussion in Birge and Louveaux (1988, 1997) on this topic. The recent on-demand accuracy Bundle methods (de Oliveira and Sagastizábal 2014) can be thought to provide a tradeoff between the multi-cut and mono-cut versions (Fábián 2013).

In Xiong and Jirutitijaroen (2011) another approach is proposed for finding such a trade-off. In this method, which is applied to a stochastic UC with load and generation uncertainty, scenarios are divided into (homogeneous) groups and cuts are derived for each group, as proposed in Trukhanova et al. (2010). Consequently, the dimension of the master problem is smaller in comparison with the classical multi-cut algorithm, while less information is lost compared to the single cut version. The authors also claim that heterogeneously grouping the scenarios may result in even better CPU time. Results are presented for a large-scale thermal UC with ramp rates and spinning reserves.

In Archibald et al. (1999) short-term cascaded reservoir management—as opposed to the more traditional approach where reservoir management is considered to be a mid-term problem—is considered wherein the gain function is explicitly given and depends on the water level and turbined quantity. Uncertainty is modeled as a Markov chain having six states per time step, which is expanded onto a scenario tree in order to allow for an LP formulation of the problem. This approach is compared with DP, nested Benders’ decomposition (closely related to SDDP) and a decomposed DP approach, which essentially efficiently samples the state space. Nested Benders’ decomposition is found to be computationally the most efficient approach.

Benders’ decomposition is compared with MILP approaches in Cerisola et al. (2009) (cf. Sect. 4.2.1) and proves to be in general preferable. In Wang et al. (2013a), Benders’ decomposition is used to address UC problems under wind uncertainty. The authors use sub-hourly time steps (10, 15 or 30 min) to account for rapid variations in renewable generation. They also modify the standard approach by adding some of the second stage constraints to the master problem.

In Zheng et al. (2013) a two-stage UC formulation is considered. Similarly to most approaches load is revealed in between the first and second stage and power output is determined in the second stage, but the latter also contains integer commitment decisions related to quick-start units. The quadratic costs functions are linearized to obtain a MILP formulation. Then, because the second stage contains integer variables, the approach of Sherali and Fraticelli (2002)—essentially a reformulation–linearization-techniques (Sherali and Adams 1998) with lift-and-project cuts (Balas et al. 1993)—is employed to construct an approximation of the convex hull of the second-stage problem, so that a multi-cut Benders approach can be used to approximate the second stage recourse cost function. A problem with five units, up to 2,000 scenarios and 16 time steps is solved.

In Papavasiliou and Oren (2013) both LR and Benders’ decomposition are used in a parallel high performance computing environment for solving a network constrained stochastic UC where uncertainty comes from different sources.
4.3 Robust optimization approaches

An early work using RO techniques is Sarić and Stankovic (2007), where a market clearing problem is considered under some UC-like constraints. The main idea is to use an *adaptive RO* approach which partitions the uncertainty set and allows decisions to be specific to each subset. The constraints are then weighed in the master problem. The results are compared with traditional RO and a worst-case fully anticipative approach.

In Wang et al. (2011) a RO approach is considered where the uncertainty set on the load is a simple interval, so that methods from interval LP (e.g., Chinneck and Ramadan 2000) can be employed together with Benders’ decomposition to solve the model. The main focus of the work is on network security. In Wu et al. (2012) a similar interval uncertainty approach is compared with a scenario-based approach. The results show that the former is very sensitive to the choice of the interval but is quickly solved, whereas the latter yields more accurate solutions but it is more costly to solve.

In Zhao and Zeng (2012) a 36 unit bUC with ramp rate constraints is considered which includes wind energy supply and demand behavior of the customers based on electricity prices. In this two-stage model, wind power enters under the guise of an uncertain budget constraint and the first stage is a day-ahead UC problem, while the second stage is performed once the wind supply is known. The problem is solved by applying Benders’ decomposing to the linearized problem along with a CP algorithm. It is claimed that this model significantly reduces the total cost and can fully exploit the available supply of wind energy. The same approach is employed in Jiang et al. (2010) to solve a 30 unit UC with ramp rates and transmission constraints where demand and supply are considered to be uncertain.

In Bertsimas et al. (2013) the model proposed in Zhao and Zeng (2012) and Jiang et al. (2010) is extended to incorporate spinning reserve constraints, transmission limits and ramping constraints. The focus is on gauging the impact of robustness of the solutions on the efficiency and operational stability of the system. A two-stage adaptive RO model is used where the uncertainty set concerns the nodal net injection at each time period. In the first stage an optimal commitment decision is reached by using Benders’ decomposition algorithm, while in the second stage the associated worst case dispatch cost is calculated. Results from empirical studies with 312 generators have been compared to those of deterministic models with reserve adjustments under three aspects: the average dispatch and total cost, the cost volatility, and the sensitivity of the costs to different probability distributions. The sensitivity of the results to changes in the uncertainty set is not investigated. A very simplified two-stage RO model is investigated in Ben-Salem (2011), where sensitivity to the choice of the uncertainty set is instead explicitly addressed. The recourse cost function is the worst case cost over a specific uncertainty set involving uncertainty on load; a simple recourse assumption makes the second stage trivial. In Minoux (2009, 2014) the model of Ben-Salem (2011) is expanded to take into account a huge uncertainty set which admits a representation as a “Markov chain”. A budget of uncertainty constraint restricts paths to be “not too extreme”; a comparison is made against stochastic programming approaches.

The authors of Street et al. (2011) consider RO for uncertainty on contingency constraints. The resulting optimization problem is reformulated as an equivalent MILP
and solved with standard solvers. This work is extended in Wang et al. (2013b) by including transmission capacity constraints and by considering a two-stage robust optimization setting. Commitment (and integer) variables are restricted to the first stage so that the second stage becomes a continuous optimization problem, further reduced to an LP by linearization techniques. A Bender's decomposition approach is used for solving the model. In Jiang et al. (2012) a similar model and solution approach can be found, integrating (interval) uncertainty on wind generation. A budget of uncertainty constraint limits conservativeness of the model. Demand response uncertainty is added in Zhao and Wang (2013); the three stages of the model are brought down to two stages by a reformulation. Commitment decisions are restricted to the first stage and Bender's decomposition is again used for solving the problem. In Zhao and Guan (2013) the authors add a convex combination of expected second stage cost and worst-case robust cost to the objective function. Uncertainty is restricted to load uncertainty and Bender's decomposition is employed for solving the model.

In Aïd et al. (2006) a RO approach to the management of electricity power genera-
tion is presented using concepts borrowed from classic risk management, i.e., value-at-
risk. In Guigues (2009) a RO with the affinely adjustable robust counterpart (AARC)
approach Ben-Tal et al. (2003) is proposed to the longer term electricity production
management. AARC is a restricted and more tractable version of the adjustable robust
counterpart (ARC), where recourse variables are allowed to depend on the values
of uncertain parameters, but only in an affine way. The same methods are looked at
for weekly hydro reservoir management under uncertainty on inflows in Apparigliato
(2008) and Babonneau et al. (2010). The hypotheses are set up in such a way that
the resulting problem has a MILP deterministic equivalent, which is then solved by
a MILP solver. Several comparisons with sliding deterministic approaches are pre-
sented. Finally, in Jabr (2013) an adjustable robust OPF is suggested.

4.4 Chance-constrained optimization approaches

In many optimization problems involving a final observation of uncertainty for which
no recourse actions exist, one cannot guarantee feasibility for all constraints. Rather,
one has to provide solutions which are “reasonably feasible” under all except the
most unlikely scenarios. This is also the case in UC, where, for instance, one cannot
actually guarantee that the demand constraints will never be violated. This is there-
fore an ideal setting for CCO, where the desired safety level can be specified under
the form of a probability. Two approaches are possible: either the safety level is set
for each constraint (e.g., time step) individually, giving an Individual CCO program,
or for the system as a whole, resulting in a Joint CCO program. While the ICCO is
obviously less robust than the JCCO (see the discussion in van Ackooij et al. 2014),
the latter is in general significantly more difficult to solve, especially if one wishes to
do this exactly (i.e., without artificially discretizing the underlying random vectors or
approximating the probabilistic constraint). This explains why CCO (either Individual
or Joint) models are the least employed in the literature on UC. However, it should be
noted that these approaches have indeed been used in related problems such as power
expansion and transmission ones (Sharaf and Berg 1982; Shiina 1999; Anders 1981),
which need be formulated on a much longer time horizon than commonly considered
in UC, and therefore crucially require taking uncertainty into account (Shiina 1999).

Individual CCO was applied for the first time in Ozturk et al. (2004) to solve a
100-units bUC where the uncertainty of load has to be met with a high probability.
The problem is then decomposed by using LR, and the subproblems are solved by DP.
The results show that solving the CCO UC produces better (less costly) solutions than
a deterministic UC with spinning reserves requirement.

In Ding (2010) a ICCO UC model is formulated where different sources of ran-
domness are considered. In particular, demand fluctuation, thermal units outage, uncer-
tainty of wind generation and the schedule of flexible generating units. The individual
chance constraints are converted into a deterministic model using the central limit
theorem to recover a Gaussian model of uncertainty for outages. A standard MILP
approach is then used to solve the problem. Again, the results are compared with these
of a deterministic UC formulation, and the authors claim that the proposed model
could be extended to basically any stochastic factor.

A stylized UC model for hydro thermal systems under joint probabilistic constraints has been considered first in Zorgati and van Ackooij (2011). The main focus there lies on dealing simultaneously with probabilistic constraints and binary variables, a signif- icant technical feat. The suggested approach relies on the fact that some inequalities in the random system are more likely to be binding than others. This provides an ad-hoc way of reducing the difficulty for the JCCO (the experiments of van Ackooij et al. 2014 provide a rationale behind this approach). The reduced joint probabilistic constraint is then outer approximated by individual probabilistic constraints selecting appropriate weights. Finally, by using Hoeffding's inequality an outer and inner approximation of these latter individual probabilistic constraint can be obtained. The resulting binary conic programming problem can be solved with a standard solver.

In Wang et al. (2012) a two-stage JCCO UC is considered with a joint prob-
abilistic constraint for the use of wind power. The probabilistic constraint is not
dealt with directly, but is discretized using a sample average approximation approach
(e.g., Luedtke and Ahmed 2008; Luedtke 2014).

Joint probabilistic constraints in UC are dealt with exactly for the first time in van Ackooij (2014). Two sources of uncertainty are considered: randomness on load and on inflows for hydro reservoirs. In order to solve the JCCO UC problem, various decomposition approaches are investigated, among which LR and various forms of AL approaches.

In Chertkov et al. (2014) a DC Optimal Power Flow using an individual CCO approach is proposed considering the uncertainty of renewable generation. Under appropriate assumptions on the underlying distribution of uncertainty, and by reformulating the bilateral individual probabilistic constraints to two unilateral ones, the resulting problem can be shown to be equivalent to a second order cone problem. The conic constraints are then linearized by using a cutting planes approach. A real life instance over the 2,746 bus Polish network is solved. It is interesting to note that such a network application with joint probabilistic constraints would give rise to differentiability issues, essential for the application of first-order methods; we refer to Henrion and Möller (2012) for a thorough discussion of differentiability and an application to a stylized network problem.
Finally, it is worthwhile to note that stability theory for CCO is developed in Römisch and Schultz (1991); for recent references on such stability results we refer to Römisch (2003), Henrion and Römisch (2004), Henrion et al. (2008, 2009) and references therein. In particular, the authors explicitly consider stability results for probabilistically constrained power dispatch models, showing that the models are stable for several underlying distributions of the load, such as discrete or multi-variate Gaussian. However, no computational results are presented.

# 5 Concluding remarks

The Unit Commitment problem could be considered an archetypal example of what makes optimization techniques both relevant and challenging.

UC regards the optimal use of a highly valuable resource, energy, whose importance has possibly never been more strongly felt than in the present times. On the one hand, energy is a primary driver of, and a necessary requirement for, economic growth and improvement of peoples' living conditions. On the other hand, fair and sustainable energy production and distribution raises enormous technical, economical, organizational, and even moral challenges. While optimization techniques (and in particular their strict subset regarding the UC problem) alone cannot clearly solve all these issues, they can indeed give a significant contribution to the improvement of the efficiency of the energy system, with a substantial positive economical and environmental impact.

From a technical perspective, UC arguably exhibits almost all possible characteristics that make an optimization problem extremely challenging. For a start it is not even a well-defined problem, but rather a large family of related problems that are as varied as the electrical systems worldwide. In almost all cases the problem is large-to very-large-scale, nonlinear, nonconvex and combinatorial. Thus, researchers continuously have to struggle between two contrasting needs: on the one hand providing more and more accurate models of the highly complex electrical systems, in order to allow better practical decisions, and on the other hand providing answers in the “unreasonably short” timeframe required by the actual operating environment. Furthermore, and perhaps more importantly for the present work, the operation of the electrical system requires a very articulate decision chain that spans from the decades (strategic decisions about the investments in new generation and transmission equipment, and even about funding of research capable of producing better ones) to the split-second range for on-line tracking of actual demand. This in turn means that uncertainty on the actual future status of the electrical system, and therefore on the consequences of the decisions that have to be taken here and now, is inherently present at all levels of the decision chain. This justifies the interest for techniques capable of dealing with uncertainty in energy optimization problems, and in particular in UC; whence the significance of this survey.

While UC cannot be presently considered a well-solved problem, and much less so UUCP (which has arguably been tackled only relatively recently), research on such an extremely challenging problem will likely have positive side-effects. Indeed, the tools and techniques that will be developed will almost surely find applications in many different fields, other than the optimal management of the energy system. This has already happened for the methodological and algorithmic developments of Prékopa
et al. (1978), Feltenmark and Kiwiel (2000), Daniilidis and Lemaréchal (2005) and Frangioni and Gentile (2006a), that were motivated by the study of UC, but have since been applied to a much broader set of problems. We are confident that the study of UUC will lead, together with practical improvements on the efficiency and safety of electrical systems, to an analogous development of new ideas and techniques that will be beneficial for many other fields. Therefore, as a small stepping stone for researchers interested in broadening their knowledge in UUC, we hope that this survey may prove useful.

**Acknowledgments** The first author would like to thank Afsaneh Salari and Maryam Arbabzadeh for their input and their intellectual support. The second and third author gratefully acknowledge the support of the Gaspard Monge program for Optimization and Operations Research (PGMO) Project "Consistent Dual Signals and Optimal Primal Solutions".

Appendix

<table><tr><td>UC</td><td>Unit Commitment problem</td></tr><tr><td>UUC</td><td>UC problem under Uncertainty</td></tr><tr><td>bUC</td><td>Basic UC problem (common modeling assumptions)</td></tr><tr><td>ED</td><td>Economic dispatch</td></tr><tr><td>GENCO</td><td>Generation Company</td></tr><tr><td>TSO</td><td>Transmission system operator</td></tr><tr><td>MP</td><td>Monopolistic producer</td></tr><tr><td>PE</td><td>Power exchange</td></tr><tr><td>PEM</td><td>PE manager</td></tr><tr><td>OTS</td><td>Optimal transmission switching</td></tr><tr><td>UCOTS</td><td>UC with OTS</td></tr><tr><td>MSG</td><td>Minimal stable generation</td></tr><tr><td>OPF</td><td>Optimal power flow</td></tr><tr><td>ROR</td><td>Run-of-river hydro unit</td></tr><tr><td>X<sub>1</sub></td><td>Set of technically feasible production schedules</td></tr><tr><td>X<sub>2</sub></td><td>Set of system wide constraints</td></tr><tr><td>T</td><td>Set of time steps</td></tr><tr><td>MILP</td><td>Mixed-integer linear programming</td></tr><tr><td>MQP</td><td>Mixed-integer quadratic programming</td></tr><tr><td>DP</td><td>Dynamic programming</td></tr><tr><td>SDDP</td><td>Stochastic dual DP B&B, B&C,</td></tr><tr><td>B&P</td><td>Branch and bound (cut, price, respectively)</td></tr><tr><td>AL</td><td>Augmented Lagrangian</td></tr><tr><td>LR</td><td>Lagrangian relaxation</td></tr><tr><td>LD</td><td>Lagrangian dual</td></tr><tr><td>CP</td><td>Cutting plane</td></tr><tr><td>SO</td><td>Stochastic optimization</td></tr><tr><td>SD</td><td>Scenario decomposition</td></tr><tr><td>UD</td><td>Unit decomposition (also called space decomposition or stochastic decomposition)</td></tr><tr><td>RO</td><td>Robust optimization</td></tr><tr><td>CCO</td><td>Chance-constrained optimization</td></tr><tr><td>ICCO</td><td>Chance-constrained optimization with individual probabilistic constraints</td></tr><tr><td>JCCO</td><td>Chance-constrained optimization with joint probabilistic constraints</td></tr></table>
References

Abdelaziz AY, Kamh MZ, Mekhamer SF, Badr MAL (2010) An augmented hopfield neural network for optimal thermal unit commitment. Int J Power Syst Optim 2(1):37-49

Aganagic M, Mokhtari S (1997) Security constrained economic dispatch using nonlinear Dantzig-Wolfe decomposition. IEEE Trans Power Syst 12(1):105-112

Aïd R, Guigues V, Ndiaye PM, Oustry F, Romanet F (2006) A value-at-risk approach for robust management of electricity power generation. Rapport de recherche, IMAG-LMC (submitted)

Al-Kalaani Y, Villaseca FE, Renovich F Jr (1996) Storage and delivery constrained unit commitment. IEEE Trans Power Syst 11(2):1059-1066

Amiri M, Khanmohammadi S (2013) A primary unit commitment approach with a modification process. Appl Soft Comput 13(2):1007-1015

Anders GJ (1981) Generation planning model with reliability constraints. IEEE Trans Power Appar Syst PAS-100(12):4901-4908

Anderson EJ, Philpott AB (2002) Optimal offer construction in electricity markets. Math Oper Res 27(1):82-100

Annakkage UD, Numnonda T, Pahalawaththa NC (1995) Unit commitment by parallel simulated annealing. IEE Proc Gener Transm Distrib 142(6):595-600

Anstine LT, Burke RE, Casey JE, Holgate R, John RS, Stewart HG (1963) Application of probability methods to the determination of spinning reserve requirements for the pennsylvania-new jersey-maryland interconnection. IEEE Trans Power Appar Syst 82(68):726-735

Anstreicher KM, Wolsey LA (2009) Two “well-known” properties of subgradient optimization. Math Program 120(1):213-220

Aoki K, Satoh T, Itoh M, Ichimori T, Masegi K (1987) Unit commitment in a large-scale power system including fuel constrained thermal and pumped-storage hydro. IEEE Trans Power Syst 2(4):1077-1084

Aoki K, Itoh M, Satoh T, Narah K, Kanezashi M (1989) Optimal long-term unit commitment in large scale systems including fuel constrained thermal and pumped storage hydro. IEEE Trans Power Syst 4(3):1065-1073

Apparigliato R (2008) Règles de décision pour la gestion du risque: Application à la gestion hebdomadaire de la production électrique. Ph.D. thesis, École Polytechnique, Juin

Archibald TW, Buchanan CS, McKinnon KIM, Thomas LC (1999) Nested benders decomposition and dynamic programming for reservoir optimisation. J Oper Res Soc 50(5):468-479

Ardakani AJ, Bouffard F (2013) Identification of umbrella constraints in dc-based security-constrained optimal power flow. IEEE Trans Power Syst 28(4):3924-3934

Arroyo JM, Conejo AJ (2000) Optimal response of a thermal unit to an electricity spot market. IEEE Trans Power Syst 15(3):1098-1104

Arroyo JM, Conejo AJ (2004) Modeling of start-up and shut-down power trajectories of thermal units. IEEE Trans Power Syst 19(3):1562-1568

Astorino A, Frangioni A, Gaudioso M, Gorgone E (2011) Piecewise quadratic approximations in convex numerical optimization. SIAM J Optim 21(4):1418-1438

Attouch H, Bolte J, Redont P, Soubeyran A (2010) Proximal alternating minimization and projection methods for nonconvex problems. An approach based on the Kurdyka-Lojasiewicz inequality. Math Oper Res 35(2):438-457

Babonneau F, Vial JP, Apparigliato R (2010) Robust optimization for environmental and energy planning. In: Filar JA, Haurie A (eds) Uncertainty and environmental decision making: a handbook of research and best practice, chap 3. International series in operations research & management science, vol 138. Springer, Heidelberg

Bacaud L, Lemaréchal C, Renaud A, Sagastizábal C (2001) Bundle methods in stochastic optimal power management: a disaggregate approach using preconditionners. Comput Optim Appl 20(3):227-244

Bahiense L, Maculan N. Sagastizábal C (2002) The volume algorithm revisited: relation with bundle methods. Math Program 94(1):41-69

Baillo A, Ventosa M, Rivier M, Ramos A (2004) Optimal offering strategies for generation companies operating in electricity spot markets. IEEE Trans Power Syst 19(2):745-753

Balas E, Ceria S, Cornuéjols G (1993) A lift-and-project cutting plane algorithm for mixed 0-1 programs. Math Program 58(1-3):295-324

Baldick R (1995) The generalized unit commitment problem. IEEE Trans Power Syst 10(1):465-475
Baldwin CJ, Dale KM, Dittrich RF (1959) A study of the economic shutdown of generating units in daily dispatch. Part III. Trans Am Inst Electr Eng Power Appar Syst 78(4):1272-1282

Bandi C, Bertsimas D (2012) Tractable stochastic analysis in high dimensions via robust optimization. Math Program 134(1):23-70

Barahona F, Anbil R (2000) The volume algorithm: producing primal solutions with a subgradient method. Math Program 87(3):385-399

Bard JF (1988) Short-term scheduling of thermal-electric generators using Lagrangian relaxation. Oper Res 36(5):765-766

Baringo L, Conejo AJ (2011) Offering strategy via robust optimization. IEEE Trans Power Syst 26(3):1418-1425

Batut J, Renaud A (1992) Daily scheduling with transmission constraints: a new class of algorithms. IEEE Trans Power Syst 7(3):982-989

Bechert TE, Kwatny HG (1972) On the optimal dynamic dispatch of real power. IEEE Trans Power Appar Syst PAS-91(1):889-898

Bellman RE, Dreyfus SE (1962) Applied dynamic programming. Princeton University Press, New Jersey

Belloni A, Diniz AL, Maceira ME, Sagastizábal C (2003) Bundle relaxation and primal recovery in unit-commitment problems. The brazilian case. Ann Oper Res 120(1-4):21-44

Beltran C, Heredia FJ (2002) Unit commitment by augmented lagrangian relaxation: testing two decomposition approaches. J Optim Theory Appl 112(2):295-314

Ben-Salem S (2011) Gestion Robuste de la production électrique à horizon court-terme. Ph.D. thesis, Ecole Centrale Paris, Mars

Ben-Tal A, Nemirovski A (1998) Robust convex optimization. Math Oper Res 23(4):769-805

Ben-Tal A, Nemirovski A (1999) Robust solutions of uncertain linear programs. Oper Res Lett 25(1):1-13

Ben-Tal A, Nemirovski A (2000) Robust solutions of linear programming problems contaminated with uncertain data. Math Program Ser A 88:411-424

Ben-Tal A, Nemirovski A (2009) On safe tractable approximations of chance-constrained linear matrix inequalities. Math Oper Res 34(1):1-25

Ben-Tal A, Goryashko A, Guslitzer E, Nemirovski A (2003) Adjustable robust counterpart of uncertain linear programs. Math Program Ser A 99:351-376

Ben-Tal A, El Ghaoui L, Nemirovski A (2009) Robust optimization. Princeton University Press, New Jersey

Ben-Tal A, Bertsimas D, Brown D (2010) A soft robust model for optimization under ambiguity. Oper Res 58(4):1220-1234

Benders JF (1962) Partitioning procedures for solving mixed-variables programming problems. Numer Math 4(1):238-252

Benth FE, Kiesel R, Nazarova A (2012) A critical empirical study of three electricity spot price models. Energy Econ 34(5):1589-1616

Beraldi P, Conforti D, Violi A (2008) A two-stage stochastic programming model for electric energy producers. Comput Oper Res 35:3360-3370

Bertsekas DP (1999) Nonlinear programming, 2nd edn. Athena Scientific, Cambridge

Bertsekas DP (2005) Dynamic programming and optimal control, vol I, 3rd edn. Athena Scientific, Cambridge

Bertsekas DP (2012) Dynamic programming and optimal control, vol II: approximate dynamic programming, 4th edn. Athena Scientific, Cambridge

Bertsekas D, Lauer G, Sandell-Jr NR, Posbergh TA (1983) Optimal short-term scheduling of large-scale power systems. IEEE Trans Autom Control 28(1):1-11

Bertsimas D, Sim M (2003) Robust discrete optimization and network flows. Math Program 98(1):49-71

Bertsimas D, Sim M (2004) The price of robustness. Oper Res 52(1):35-53

Bertsimas D, Brown D, Caramanis C (2011) Theory and applications of robust optimization. SIAM Rev 53(3):464-501

Bertsimas D, Litvinov E, Sun XA, Zhao J, Zheng T (2013) Adaptive robust optimization for the security constrained unit commitment problem. IEEE Trans Power Syst 28(1):52-63

Bienstock D (2013) Progress on solving power flow problems. Optima 93:1-8

Bienstock D, Verma A (2011) The *n-k* problem in power grids: new models, formulations and numerical experiments. SIAM J Optim 20(5):2352-2380. doi:10.1137/08073562X

Billinton R, Karki R (1999) Capacity reserve assessment using system well-being analysis. IEEE Trans Power Syst 14(2):433-438
Birge JR, Louveaux F (1988) A multicut algorithm for two-stage stochastic linear programs. Eur J Oper
Res 34(3):384–392

Birge JR, Louveaux F (1997) Introduction to stochastic programming. Springer, New York

Bompard E, Ma Y (2012) Models of strategic bidding in electricity markets under network constraints.
In: Sorokin A, Rebennack S, Pardalos PM, Iliadis NA, Pereira MVF (eds) Handbook of networks in
power systems, vol I. Springer, Heidelberg, pp 3–39

Bond SD, Fox B (1986) Optimal thermal unit scheduling using improved dynamic programming algorithm.
IEEE Proc C 133(1):1–5

Bonnans JF, Gilbert JC, Lemaréchal C, Sagastizábal C (2006) Numerical optimization: theoretical and practical aspects, 2nd edn. Springer, Heidelberg

Borghetti A, Frangioni A, Lacalandra F, Lodi A, Martello S, Nucci CA, Trebbi A (2001) Lagrangian relax-
ation and tabu search approaches for the unit commitment problem. In: IEEE Power Tech proceedings,
2001 Porto volume 3

Borghetti A, Frangioni A, Lacalandra F, Nucci CA (2003a) Lagrangian heuristics based on disaggregated bundle methods for hydrothermal unit commitment. IEEE Trans Power Syst 18:313–323

Borghetti A, Frangioni A, Lacalandra F, Nucci CA, Pelacchi P (2003b) Using of a cost-based unit com-
mitment algorithm to assist bidding strategy decisions. In: Borghetti A, Nucci CA, Paolone M (eds)
Proceedings IEEE 2003 Powertech, Bologna conference volume paper no. 547

Borghetti A, D'Ambrosio C, Lodi A, Martello S (2008) A MILP approach for short-term hydro scheduling and unit commitment with head-dependent reservoir. IEEE Trans Power Syst 23(3):1115–1124

Bouffard F, Galiana FD (2008) Stochastic security for operations planning with significant wind power generation. IEEE Trans Power Syst 23(2):306–316

Briant O, Lemaréchal C, Meurdesoif Ph, Michel S, Perrot N, Vanderbeck F (2008) Comparison of bundle and classical column generation. Math Program 113(2):299–344

Büsing C, D'Andreagiovanni F (2012) New results about multi-band uncertainty in robust optimization.
In: Klasing R (ed) Experimental algorithms—SEA 2012 volume 7276 of LNCS, pp 63–74

Büsing C, D'Andreagiovanni F (2013) Robust optimization under multi-band uncertainty—part i: theory.
Technical report ZIB-Report 13–10, Zuse-Institut Berlin (ZIB)

Calafiore GC, Campi MC (2005) Uncertain convex programs: randomized solutions and confidence levels.
Math Program 102(1):25–46

Carøe CC, Ruszczyński A, Schultz R (1997) Unit commitment under uncertainty via two-stage stochastic programming. In: Proceedings of NOAS 1997

Carøe CC, Schultz R (1998) A two-stage stochastic program for unit-commitment under uncertainty in a
hydro-thermal power system. Technical report, ZIB

Carpentier P, Cohen G, Culioli JC, Renaud A (1996) Stochastic optimization of unit commitment: a new decomposition framework. IEEE Trans Power Syst 11(2):1067–1073

Carrión M, Arroyo JM (2006) A computationally efficient mixed-integer linear formulation for the thermal unit commitment problem. IEEE Trans Power Syst 21(3):1371–1378

Catalão JPS, Mariano SJPS, Mendes VMF, Ferreira LAFM (2006) Parameterisation effect on the behavior of a head-dependent hydro chain using a nonlinear model. Electr Power Syst Res 76:404–412

Catalão JPS, Mariano SJPS, Mendes VMF, Ferreira LAFM (2010) Nonlinear optimization method for short-term hydro scheduling considering head-dependency. Eur Trans Electr Power 20:172–183

Cerisola S (2004) Benders decomposition for mixed integer problems: application to a medium term hydrothermal coordination problem. Ph.D. thesis, Instituto Investigación Tecnológica, Madrid

Cerisola S, Bañillo A, Fernández-López JM, Ramos A, Gollmer R (2009) Stochastic power generation unit commitment in electricity markets: a novel formulation and a comparison of solution methods. Oper Res 57(1):32–46

Cerjan M, Marcic D, Delimar M (2011) Short term power system planning with water value and energy trade optimisation. In: International conference on the European energy market (EEM)

Chandrasekaran K, Simon SP (2012a) Multi-objective scheduling problem: hybrid approach using fuzzy assisted cuckoo search algorithm. Swarm Evolut Comput 5:1–12

Chandrasekaran K, Simon SP (2012b) Network and reliability constrained unit commitment problem using binary real coded firefly algorithm. Electr Power Energy Syst 43:921–932

Chang GW, Aganagic M, Waight JG, Medina J, Burton T, Reeves S, Christoforidis M (2001) Experiences with mixed integer linear programming based approaches on short-term hydro scheduling. IEEE Trans Power Syst 16(4):743–749
Chen X, Sim M, Sun P (2007) A robust optimization perspective on stochastic programming. Oper Res 55(6):1058-1071

Chinneck JW, Ramadan K (2000) Linear programming with interval coefficients. J Oper Res Soc 51(2):209-220

Chitra-Selvi S, Kumundi-Devi RP, Asir-Rajan CC (2009) Hybrid evolutionary programming approach to multi-area unit commitment with import and export constraints. Int J Recent Trends Eng 1(3):223-228

Cohen G (1980) Auxiliairy problem principle and decomposition of optimization problems. J Optim Theory Appl 32(3):277-305

Cohen AI, Yoshimura M (1983) A branch-and-bound algorithm for unit commitment. IEEE Trans Power Appar Syst 102(2):444-451

Cohen G, Zhu DL (1984) Decomposition-coordination methods in large-scale optimization problems. The non-differentiable case and the use of augmented Lagrangians. In: Cruz JB (ed) Advances in large scale systems, vol I. JAI Press, Greenwich, Connecticut, pp 203-266

Cohen AI, Wan SH (1987) A method for solving the fuel constrained unit commitment problem. IEEE Trans Power Syst 2(3):608-614

Conejo AJ, Prieto FJ (2001) Mathematical programming and electricity markets. TOP 9(1):1-53

Conejo AJ, Contreras J, Arroyo JM, de la Torre S (2002a) Optimal response of an oligopolistic generating company to a competitive pool-based electric power market. IEEE Trans Power Syst 17(2):424-430

Conejo AJ, Nogales FJ, Arroyo JM (2002b) Price-taker bidding strategy under price uncertainty. IEEE Trans Power Syst 17(4):1081-1088

Conejo AJ, Carrión M, Morales JM (2010) Decision making under uncertainty in electricity markets, volume 153 of international series in operations research and management science, 1st edn. Springer, Heidelberg

Constantinescu EM, Zavala VM, Rocklin M, Lee S, Anitescu M (2011) A computational framework for uncertainty quantification and stochastic optimization in unit commitment with wind power generation. IEEE Trans Power Syst 26(1):431-441

Corchero C, Mijangos E, Heredia F-J (2013) A new optimal electricity market bid model solved through perspective cuts. TOP 21(1):84-108

Chertkov M, Bienstock D, Harnett S (2014) Chance-constrained dc-opf. Working paper (submitted)

Cour des Comptes (2012) Les coûts de la filière électronucléaire. Technical report, Cour des Comptes

d'Ambrosio C, Lodi A, Martello S (2010) Piecewise linear approximation of functions of two variables in MILP models. Oper Res Lett 38:39-46

d'Antonio G, Frangioni A (2009) Convergence analysis of deflected conditional approximate subgradient methods. SIAM J Optim 20(1):357-386

Daniildis A, Lemaréchal C (2005) On a primal-proximal heuristic in discrete optimization. Math Program Ser A 104:105-128

Dantzig GB, Wolfe P (1960) The decomposition principle for linear programs. Oper Res 8:101-111

Dasgupta D, McGregor DR (1994) Thermal unit commitment using genetic algorithms. IEEE Proc Gener Transm Distrib 141(5):459-465

David AK, Wen F (2001) Strategic bidding in competitive electricity markets: a literature survey. Proc IEEE PES Summer Meet 4:2168-2173

de Farias DP, Van Roy B (2003) The linear programming approach to approximate dynamic programming. Oper Res 51(6):850-865

de la Torre S, Arroyo JM, Conejo AJ, Contreras J (2002) Price maker self-scheduling in a pool-based electricity market: a mixed-integer LP approach. IEEE Trans Power Syst 17(4):1037-1042

de Oliveira W, Sagastizábal C (2014) Level bundle methods for oracles with on demand accuracy. Optim Methods Softw 29(6):1180-1209. doi:10.1080/10556788.2013.871282

de Oliveira W, Sagastizábal CA, Scheimberg S (2011) Inexact bundle methods for two-stage stochastic programming. SIAM J Optim 21(2):517-544

de Oliveira W, Sagastizábal C, Lemaréchal C (2013) Bundle methods in depth: a unified analysis for inexact oracles. http://www.optimization-online.org/DB_HTML/2013/02/3792.html

Demartini G, De Simone TR, Granelli GP, Montagna M, Robo K (1998) Dual programming methods for large-scale thermal generation scheduling. IEEE Trans Power Syst 13:857-863

Dentcheva D (2009) Optimisation models with probabilistic constraints. In: Shapiro A, Dentcheva D, Ruszczyński A (eds) Lectures on stochastic programming. Modeling and theory, chap 4. MPS-SIAM series on optimization, vol 9. SIAM and MPS, Philadelphia
Dentcheva D, Römisch W (1998) Optimal power generation under uncertainty via stochastic programming.
In: Marti K, Kall P (eds) Stochastic programming methods and technical applications, volume 458 of
lecture notes in economics and mathematical systems. Springer, Heidelberg, pp 22–56

Di Lullo M (2013) Modelli di ottimizzazione per lo unit commitment con optimal transmission switching: Analisi e implementazione. Master's thesis, Facoltá di Ingegneria dell'Informazione, Informatica e Statistica, Università di Roma La Sapienza, Piazzale Aldo Moro, 5 00185, Roma

Dieu VN, Ongsakul W (2008) Ramp rate constrained unit commitment by improved priority list and augmented Lagrange Hopfield network. Electr Power Syst Res 78(3):291–301

Dillon TS, Egan GT (1976) The application of combinatorial methods to the problems of maintenance scheduling and unit commitment in large power system. In: 1st IFAC symposium on large scale systems theory and applications, Udine, Italy

Dillon TS, Edwin KW, Kochs HD, Taud RJ (1978) Integer programming approach to the problem of optimal unit commitment with probabilistic reserve determination. IEEE Trans Power Appar Syst PAS-97(6):2154–2166

Ding X, Lee W-J, Jianxue W, Liu L (2010) Studies on stochastic unit commitment formulation with flexible generating units. Electr Power Syst Res 80:130–141

Diongue AK (2005) Modélisation longue mémoire multivariée : applications aux problématiques du producteur d'EDF dans le cadre de la libéralisation du marché européen de l'électricité. Ph.D. thesis ENS Cachan

du Merle O, Goffin J-L, Vial J-P (1998) On improvements to the analytic center cutting plane method.
Comput Optim Appl 11:37–52

Dubost L, Gonzalez R, Lemaréchal C (2005) A primal-proximal heuristic applied to french unit commitment problem. Math Program 104(1):129–151

Duo H, Sasaki H, Nagata T, Fujita H (1999) A solution for unit commitment using Lagrangian relaxation combined with evolutionary programming. Electr Power Syst Res 51(1):71–77

Dupačová J, Gröwe-Kuska N, Römisch W (2003) Scenario reduction in stochastic programming: an approach using probability metrics. Math Program 95(3):493–511

Ea K (2012) The electricity spot markets prices modeling: proposal for a new mathematical formulation taking into account the market player strategy. In: International conference on the European energy market (EEM)

Eichhorn A, Heitsch H, Römisch W (2010) Stochastic optimization of electricity portfolios: scenario tree modeling and risk management. In: Rebennack S, Pardalos PM, Pereira MVF, Iliadis N (eds) Handbook of power systems II. Springer, Heidelberg, pp 405–432

El Sayed MAH (2005) Solar supported steam production for power generation in Egypt. Energy Policy
33(10):1251–1259

El Ghaoui L, Lebret H (2006) Robust solutions to least-squares problems with uncertain data. SIAM J Matrix Anal Appl 18(4):1035–1064

El Ghaoui L, Oustry F, Lebret H (1998) Robust solutions to uncertain semidefinite programs. SIAM J Optim 9(1):33–52

Erkmen I, Karatas B (1994) Short-term hydrothermal coordination by using multi-pass dynamic programming with successive approximation. In: 7th Mediterranean electrotechnical conference, vol 3, pp 925–928

Fábián CI (2013) Computational aspects of risk-averse optimisation in two-stage stochastic models. Technical report, Institute of Informatics, Kecskemét College, Hungary, Optimization Online report

Fan W, Guan X, Zhai Q (2002) A new method for unit commitment with ramping constraints. Electr Power Syst Res 62(3):215–224

Farhat IA, El-Hawary ME (2009) Optimization methods applied for solving the short-term hydrothermal coordination problem. Electr Power Syst Res 79:1308–1320

Feltenmark S, Kiwiel KC (2000) Dual applications of proximal bundle methods, including Lagrangian relaxation of nonconvex problems. SIAM J Optim 10(3):697–721

Ferreira LAFM (1994) On the convergence of the classic hydro-thermal coordination algorithm. IEEE Trans Power Syst 9:1002–1008

Finardi EC, Da Silva EL (2006) Solving the hydro unit commitment problem via dual decomposition and sequential quadratic programming. IEEE Trans Power Syst 21(2):835–844

Finardi EC, Scuzziato MR (2013) Hydro unit commitment and loading problem for day-ahead operation planning problem. Electr Power Energy Syst 44:7–16
Finardi EC, Scuzziato MR (2014) A comparative analysis of different dual problems in the Lagrangian relaxation context for solving the hydro unit commitment problem. Electr Power Syst Res 107:221-229

Fischetti M, Monaci M (2009) Light robustness. In: Ahuja RK, Möhring R, Zaroliagis C (eds) Robust and online large-scale optimization, volume 5868 of LNCS, pp 61–84

Fisher ML (1973) Optimal solution of scheduling problems using Lagrange multipliers: part i. Oper Res 21(5):1114–1127

Fisher EB, O'Neill RP, Ferris MC (2008) Optimal transmission switching. IEEE Trans Power Syst 23(3):1346–1355

Fleten S-E, Kristoffersen TK (2008) Short-term hydropower production planning by stochastic programming. Comput Oper Res 35:2656–2671

Fonoberova M (2010) Algorithms for finding optimal flows in dynamic networks. In: Rebennack S, Pardalos PM, Pereira MVF, Iliadis N (eds) Handbook of power systems II. Springer, Heidelberg, pp 31–54

Fotuhi-Firuzabad M, Billinton R (2000) A reliability framework for generating unit commitment. Electr Power Syst Res 56(1):81–88

Frangioni A (2002) Generalized bundle methods. SIAM J Optim 13(1):117–156

Frangioni A (2005) About Lagrangian methods in integer optimization. Ann Oper Res 139(1):163–193

Frangioni A, Gentile C (2006a) Perspective cuts for a class of convex 0-1 mixed integer programs. Math Program 106(2):225–236

Frangioni A, Gentile C (2006b) Solving non-linear single-unit commitment problems with ramping constraints. Oper Res 54(4):767–775

Frangioni A, Gentile C, Lacalandra F (2008) Solving unit commitment problems with general ramp constraints. Int J Electr Power Energy Syst 30:316–326

Frangioni A, Gentile C, Lacalandra F (2009) Tighter approximated MILP formulations for unit commitment problems. IEEE Trans Power Syst 24(1):105–113

Frangioni A, Gentile C, Lacalandra F (2011) Sequential Lagrangian-MILP approaches for unit commitment problems. Int J Electr Power Energy Syst 33:585–593

Fu Y, Shahidehpour M (2007) Fast SCUC for large-scale power systems. IEEE Trans Power Syst 22(4):2144–2151

Fu Y, Shahidehpour M, Li Z (2005) Long-term security-constrained unit commitment: hybrid Dantzig-Wolfe decomposition and subgradient approach. IEEE Trans Power Syst 20(4):2093–2106

Fu Y, Li Z, Wu L (2013) Modeling and solution of the large-scale security-constrained unit commitment. IEEE Trans Power Syst 28(4):3524–3533

Gabriel SA, Conejo AJ, Fuller JD, Hobbs BF, Ruiz C (2013) Complementarity modeling in energy markets, volume 180 of international series in operations research and management science, 1st edn. Springer, Heidelberg

García-González J, San Roque AM, Campos FA, Villar J (2007) Connecting the intraday energy and reserve markets by an optimal redispatch. IEEE Trans Power Syst 22(4):2220–2231

Garver LL (1962) Power generation scheduling by integer programming-development of theory. Part III. Trans Am Inst Electr Eng Power Appar Syst 81(3):730–734

Ge W (2010) Ramp rate constrained unit commitment by improved priority list and enhanced particle swarm optimization. In: International conference on computational intelligence and software engineering (CiSE), 2010, pp 1–8

Georges D (1994) Optimal unit commitment in simulations of hydrothermal power systems: an augmented Lagrangian approach. Simul Pract Theory 1(4):155–172

Gil HA, Gómez-Quiles C, Gómez-Exposito A, Santos JR (2012) Forecasting prices in electricity markets: needs, tools and limitations. In: Sorokin A, Rebennack S, Pardalos PM, Iliadis NA, Pereira MVF (eds) Handbook of networks in power systems I. Springer, Heidelberg, pp 123–150

Gill PE, Murray W, Wright MH (1982) Practical optimization, 1st edn. Emerald Group Publishing, London

Gjengedal T (1996) Emission constrained unit-commitment (ECUC). IEEE Trans Energy Convers 11(1):132–138

Gollmer R, Moller A, Nowak MP, Romisch W, Schultz R (1999) Primal and dual methods for unit commitment in a hydro-thermal power system. In: Proceedings 13th power systems computation conference, pp 724–730

Gooi HB, Mendes DP, Bell KRW, Kirschen DS (1999) Optimal scheduling of spinning reserve. IEEE Trans Power Syst 14(4):1485–1492
Gröwe-Kuska N, Kiwiel KC, Nowak MP, Römisch W, Wegner I (2002) Power management in a hydro-thermal system under uncertainty by Lagrangian relaxation. In: Greengard C, Ruszczyński A (eds) Decision making under uncertainty, volume 128 of the IMA volumes in mathematics and its applications. Springer, New York, pp 39–70

Guan Y, Wang J (2014) Uncertainty sets for robust unit commitment. IEEE Trans Power Syst 29(3):1439–1440

Guan X, Luh PB, Houzhong Y, Amalfi JA (1991) Environmentally constrained unit commitment. In: Power industry computer application conference, Baltimore, MD

Guan X, Luh PB, Yan H, Rogan P (1994) Optimization-based scheduling of hydrothermal power systems with pumped-storage units. IEEE Trans Power Syst 9:1023–1031

Guan X, Luh PB, Zhang L (1995) Nonlinear approximation method in Lagrangian relaxation-based algorithms for hydrothermal scheduling. IEEE Trans Power Syst 10:772–778

Guan X, Ni E, Li R, Luh PB (1997) An optimization-based algorithm for scheduling hydrothermal power systems with cascaded reservoirs and discrete hydro constraints. IEEE Trans Power Syst 12:1775–1780

Guignard M (2003) Lagrangian relaxation. TOP 11(2):151–228

Guignard M, Kim S (1987) Lagrangian decomposition: a model yielding stronger Lagrangian bounds. Math Program 39:215–228

Guigues V (2009) Robust product management. Optim Eng 10(4):505–532

Guigues V (2013) SDDP for some interstage dependent risk-averse problems and application to hydro-thermal planning. Comput Optim Appl 10(4):505–532

Habibollahzadeh H, Bubenko JA (1986) Application of decomposition techniques to short-term operation planning of hydrothermal power system. IEEE Trans Power Syst 1(1):41–47

Hara K, Kimura M, Honda N (1966) A method for planning economic unit commitment and maintenance of thermal power systems. IEEE Trans Power Appar Syst PAS–85(5):427–436

Harris C (2011) Electricity markets: pricing, structures and economics, volume 565 of the Wiley finance series. Wiley, London

Hedman KW, O'Neill RP, Fisher EB, Oren SS (2009) Optimal transmission switching with contingency analysis. IEEE Trans Power Syst 24(3):1577–1586

Hedman KW, Ferris MC, O'Neill RP, Fisher EB, Oren SS (2010) Co-optimization of generation unit commitment and transmission switching with $n-1$ reliability. IEEE Trans Power Syst 25(2):1052–1063

Hedman KW, Oren SS, O'Neill RP (2011a) Optimal transmission switching: economic efficiency and market implications. J Regul Econ 40(3):111–140

Hedman KW, Oren SS, O'Neill RP (2011b) A review of transmission switching and network topology optimization. In: Power and energy society general meeting, 2011 IEEE. IEEE, pp 1–7

Heitsch H, Römisch W (2003) Scenario reduction algorithms in stochastic programming. Comput Optim Appl 24(2–3):187–206

Heitsch H, Römisch W (2009) Scenario tree reduction for multistage stochastic programs. CMS 6(2):117–133

Heitsch H, Römisch W (2011) Scenario tree generation for multi-stage stochastic programs. In: Bertocchi M, Consigli G, Dempster MAH (eds) Stochastic optimization methods in finance and energy: new financial products and energy market strategies volume 163 of international series in operations research and management science. Springer, Heidelberg, pp 313–341

Heredia FJ, Nabona N (1995) Optimum short-term hydrothermal scheduling with spinning reserve through network flows. IEEE Trans Power Syst 10:1642–1651

Henrion R, Römisch W (2004) Hölder and lipschitz stability of solution sets in programs with probabilistic constraints. Math Program 100:589–611

Henrion R, Möller A (2012) A gradient formula for linear chance constraints under Gaussian distribution. Math Oper Res 37:475–488

Henrion R, Küchler C, Römisch W (2008) Discrepancy distances and scenario reduction in two-stage stochastic integer programming. J Ind Manag Optim 4:363–384

Henrion R, Küchler C, Römisch W (2009) Scenario reduction in stochastic programming with respect to discrepancy distances. Comput Optim Appl 43:67–93

Higgs H, Worthington A (2008) Stochastic price modeling of high volatility, mean-reverting, spike-prone commodities: the Australian wholesale spot electricity market. Energy Econ 30(6):3172–3185

Hijazi HL, Coffrin C, Van Hentenryck P (2013) Convex quadratic relaxations of nonlinear programs in power systems (submitted)
Hobbs WJ, Hermon G, Warner S, Shelbe GB (1988) An enhanced dynamic programming approach for unit commitment. *IEEE Trans Power Syst* 3(3):1201-1205

Hobbs BF, Rothkopf M, O'Neill RP, Chao HP (2001) The next generation of electric power unit commitment models. Number 36 in international series in operations research and management science. Springer, Heidelberg

Hsu YY, Su C-C, Lin C-J, Huang C-T (1991) Dynamic security constrained multi-area unit commitment. *IEEE Trans Power Syst* 6(3):1049-1055

Huang KY, Yang HT, Huang CL (1998) A new thermal unit commitment approach using constraint logic programming. *IEEE Trans Power Syst* 13(3):936-945

Jabr RA (2006) Radial distribution load flow using conic programming. *IEEE Trans Power Syst* 21(3):1458-1459

Jabr RA (2008) Optimal power flow using an extended conic quadratic formulation. *IEEE Trans Power Syst* 23(3):1000-1008

Jabr RA (2010) Recent developments in optimal power flow modeling. In: Rebennack S, Pardalos PM, Pereira MVF, Iliadis N (eds) Handbook of power systems II. Springer, Heidelberg, pp 3-30

Jabr RA (2012) Tight polyhedral approximation for mixed-integer linear programming unit commitment formulations. *IET Gener Transm Distrib* 6(11):1104-1111

Jabr RA (2013) Adjustable robust OPF with renewable energy sources. *IEEE Trans Power Syst* 28(4):4741-4751

Jia J, Guan X (2011) Milp formulation for short-term scheduling of cascaded reservoirs with head effects. In: 2011 2nd international conference on artificial intelligence, management science and electronic commerce (AIMSEC), pp 4061-4064

Jiang R, Zhang M, Li G, Guan Yi (2010) Two-stage robust power grid optimization problem. Preprint: http://www.optimization-online.org/DB_HTML/2010/10/2769.html, pp 1-34

Jiang R, Wang J, Guan Y (2012) Robust unit commitment with wind power and pumped storage hydro. *IEEE Trans Power Syst* 27(2):800-810

Johnson RC, Happ HH, Wright WJ (1971) Large scale hydro-thermal unit commitment-method and results. *IEEE Trans Power Appar Syst* PAS-90(3):1373-1384

Juste KA, Kita H, Tanaka E, Hasegawa J (1999) An evolutionary programming solution to the unit commitment problem. *IEEE Trans Power Syst* 14(4):1452-1459

Kall P, Mayer J (2005) Stochastic linear programming: models, theory and computation. International series in operations research and management science, 1st edn. Springer, Heidelberg

Kelley JE (1960) The cutting-plane method for solving convex programs. J Soc Ind Appl Math 8(4):703-712

Kerr RH, Scheidt JL, Fontanna AJ, Wiley JK (1966) Unit commitment. *IEEE Trans Power Appar Syst* PAS-85(5):417-421

Keyhani A, Marwali MN, Dai M (2010) Integration of green and renewable energy in electric power systems, 1st edn. Wiley, London

Kiwiel KC (2012) Bundle methods for convex minimization with partially inexact oracles. Comput Opt Appl (to appear)

Korad K, Hedman AS (2013) Robust corrective topology control for system reliability. *IEEE Trans Power Syst* 28(4):1346-1355

Kort BW, Bertsekas DP (1972) A new penalty function method for constrained optimization. IEEE Conf Decis Control 1972:162-166

Kuloor S, Hope GS, Malik OP (1992) Environmentally constrained unit commitment. IEE Proc C Gener Transm Distrib 139(2):122-128

Kwon RH, Frances D (2012) Optimization-based bidding in day-ahead electricity auction markets: a review of models for power producers. In: Sorokin A, Rebennack S, Pardalos PM, Iliadis NA, Pereira MVF (eds) Handbook of networks in power systems I. Springer, Heidelberg, pp 41-60

Laporte G, Louveaux FV (1993) The integer l-shaped method for stochastic integer programs with complete recourse. Oper Res Lett 13(3):133-142

Lauer GS, Sandell NR, Bertsekas DP, Posbergh TA (1982) Solution of large-scale optimal unit commitment problems. *IEEE Trans Power Appar Syst* PAS-101(1):79-86

Lavaei J, Low S (2012) Zero duality gap in optimal power flow problem. *IEEE Trans Power Syst* 27(1):92-107

Le KD, Jackups RR, Feinstein J, Griffith JS (1990) Operational aspects of generation cycling. *IEEE Trans Power Syst* 5(4):1194-1203

Lee FN (1988) Short-term thermal unit commitment—a new method. *IEEE Trans Power Syst* 3(2):421-428
Lee FN (1991) The application of commitment utilization factor (CUF) to thermal unit commitment. IEEE Trans Power Syst 6(2):691-698

Lee FN, Feng Q (1992) Multi-area unit commitment. IEEE Trans Power Syst 7(2):591-599

Lee FN, Huang J, Adapa R (1994) Multi-area unit commitment via sequential method and a dc power flow network model. IEEE Trans Power Syst 9(1):287-297

Lemaréchal C (1975) An extension of davidon methods to nondifferentiable problems. Math Program Study 3:95-109

Lemaréchal C (2001) Lagrangian relaxation. In: Jünger M, Naddef D (eds) Computational combinatorial optimization: optimal or provably near-optimal solutions, chap 4. Lecture notes incomputer science. Springer, Heidelberg

Lemaréchal C, Sagastizábal C (1994) An approach to variable metric bundle methods. Lect Notes Control Inf Sci 197:144-162

Lemaréchal C, Sagastizábal C (1995) Application of bundle methods to the unit-commitment problem. Rapport Technique Nb 0184 INRIA, pp 1-19

Lemaréchal C, Nemirovskii A, Nesterov Y (1995) New variants of bundle methods. Math Program 69(1):111-147

Leveque F (2002) Competitive electricity markets and sustainability. Edward Elgar, Cheltenham

Li Z, Shahidehpour M (2003) Generation scheduling with thermal stress constraints. IEEE Trans Power Syst 18(4):1402-1409

Li T, Shahidehpour M (2005) Strategic bidding of transmission-constrained GENCOs with incomplete information. IEEE Trans Power Syst 20(1):437-447

Li C, Johnson RB, Svoboda AJ (1997) A new unit commitment method. IEEE Trans Power Syst 12(1):113-119

Li G, Lawarree J, Liu CC (2010) State-of-the-art of electricity price forecasting in a grid. In: Rebennack S, Pardalos PM, Pereira MVF, Iliadis N (eds) Handbook of power systems II. Springer, Heidelberg, pp 161-188

Liang R-H, Kang F-C (2000) Thermal generating unit commitment using an extended mean field annealing neural network. IEE Proc Gener Transm Distrib 147(3):164-170

Lin W-M, Cheng F-S, Tsay M-T (2002) An improved tabu search for economic dispatch with multiple minima. IEEE Trans Power Syst 17(1):108-112

Liu C, Shahidehpour M, Wu L (2010) Extended benders decomposition for two-stage SCUC. IEEE Trans Power Syst 25(2):1192-1194

Liu C, Wang J, Ostrowski J (2012a) Heuristic prescreening switchable branches in optimal transmission switching. IEEE Trans Power Syst 27(4):2289-2290

Liu C, Wang J, Ostrowski J (2012b) Static security in multi-period transmission switching. IEEE Trans Power Syst 27(4):1850-1858

Løkketangen A, Woodruff DL (1996) Progressive hedging and tabu search applied to mixed integer (0, 1) multistage stochastic programming. J Heuristics 2(2):111-128

Louveaux FV, Schultz R (2003) Stochastic integer programming. In: Ruszczyński A, Shapiro A (eds) Stochastic programming, chap 4. Handbooks in operations research and management science, vol 10. Elsevier, Amsterdam

Lu B, Shahidehpour M (2005) Unit commitment with flexible generating units. IEEE Trans Power Syst 20(2):1022-1034

Lucas J-Y, Triboulet T (2012) Hybridization of augmented lagrangian and genetic algorithm for day-to-day unit commitment problem. In: META 12: international conference on metaheuristics and nature inspired computing

Luedtke J (2014) A branch-and-cut decomposition algorithm for solving chance-constrained mathematical programs with finite support. Math Program 146:219-244

Luedtke J, Ahmed S (2008) A sample approximation approach for optimization with probabilistic constraints. SIAM J Optim 19:674-699

Luenberger DG, Ye Y (2010) Linear and nonlinear programming, volume 116 of international series in operations research and management science, 3rd edn. Springer, Heidelberg

Luh PB, Tomastik RN (1998) An algorithm for solving the dual problem of hydrothermal scheduling. IEEE Trans Power Syst 13:593-600

Luh PB, Wang Y, Zhao X (1999) Lagrangian relaxation neural network for unit commitment. In: IEEE Power Engineering Society 1999 winter meeting, vol 1, pp 490-495
Madrigal M, Quintana VH (2000) An interior-point/cutting-plane method to solve unit commitment problems. IEEE Trans Power Syst 15(3):1022-1027

Makkonen S, Lahdelma R (2006) Non-convex power plant modelling in energy optimisation. Eur J Oper Res 171:1113-1126

Mantawy AH, Abdel-Magid YL, Selim SZ (1998) A simulated annealing algorithm for unit commitment. IEEE Trans Power Syst 13(1):197-204

Mantawy AH, Soliman SA, El-Hawary ME (2002) A new tabu search algorithm for the long-term hydro scheduling problem. In: LESCOPE 02 large engineering systems conference on power engineering, pp 29-34

Merlin A, Sandrin P (1983) A new method for unit commitment at Electricité de France. IEEE Trans Power Appl Syst PAS-102:1218-1225

Mezger AJ, de Almeida KC (2007) Short term hydrothermal scheduling with bilateral transactions via bundle method. Electr Power Energy Syst 29:387-396

Minoux M (2009) Solving some multistage robust decision problems with huge implicitly defined scenario trees. Algorithm Oper Res 4(1):1-18

Minoux M (2014) Two-stage robust optimization, state-space representable uncertainty and applications. RAIRO Oper Res 48:455-475

Miranda J, Wanga A, Botterud R, Bessa H, Keko L, Carvalho D, Issicaba J, Sumaili V (2011) Wind power forecasting uncertainty and unit commitment. Appl Energy 88:4014-4023

Mokhtari S, Sing J, Wollenberg B (1988) A unit commitment expert system. IEEE Trans Power Syst 3(1):272-277

Molzahn DK, Holzer JT, Lesieutre BC, DeMarco CL (2013) Implementation of a large-scale optimal power flow solver based on semidefinite programming. IEEE Trans Power Syst 28(4):3987-3998

Momoh JA, Adapa R, El-Hawary ME (1999a) A review of selected optimal power flow literature to 1993. i. Nonlinear and quadratic programming approaches. IEEE Trans Power Syst 14:96-104

Momoh JA, Adapa R, El-Hawary ME (1999b) A review of selected optimal power flow literature to 1993. ii. Newton, linear programming and interior point methods. IEEE Trans Power Syst 14:105-111

Morales-España G, Latorre JM, Ramos A (2013a) Tight and compact MILP formulation for the thermal unit commitment problem. IEEE Trans Power Syst 28(4):4897-4908

Morales-España G, Latorre JM, Ramos A (2013b) Tight and compact MILP formulation of start-up and shut-down ramping in unit commitment. IEEE Trans Power Syst 28(2):1288-1296

Morales-España G, Ramos A, García-González J (2014) An MIP formulation for joint market-clearing of energy and reserves including ramp scheduling. IEEE Trans Power Syst 29(1):476-488

Mori H, Matsuzaki O (2001) Embedding the priority list into tabu search for unit commitment. In: IEEE Power Engineering Society winter meeting, vol 3, pp 1067-1072

Muckstadt JA, Koenig SA (1977) An application of Lagrangian relaxation to scheduling in power-generation systems. Oper Res 25(3):387-403

Moura PS, de Almeida AT (2010) Large scale integration of wind power generation. In: Rebennack S, Pardalos PM, Pereira MVF, Iliadis N (eds) Handbook of power systems I. Springer, Heidelberg, pp 95-120

Muckstadt JA, Wilson RC (1968) An application of mixed-integer programming duality to scheduling thermal generating systems. IEEE Trans Power Appar Syst PAS-87(12):1968-1978

Muñoz A, Sánchez Úbeda EF, Cruz A, Marín J (2010) Short-term forecasting in power systems: a guided tour. In: Rebennack S, Pardalos PM, Pereira MVF, Iliadis N (eds) Handbook of power systems II. Springer, Heidelberg, pp 129-160

Murillo-Sanchez C, Thomas RJ (1998) Thermal unit commitment including optimal ac power flow constraints. In: Thirty-First Hawaii international conference on system sciences, vol 3

Nayak R, Sharma JD (2000) A hybrid neural network and simulated annealing approach to the unit commitment problem. Comput Electr Eng 26(6):461-477

Nemirovski A, Shapiro A (2004) Scenario approximations of chance constraints. Preprint: http://www.optimization-online.org/DB_HTML/2004/11/1000.html, pp 1-45

Nemirovski A, Shapiro A (2006a) Convex approximations of chance constrained programs. SIAM J Optim 17(4):969-996

Nemirovski A, Shapiro A (2006b) Scenario approximations of chance constraints. In: Calafiore G, Dabbene F (eds) Probabilistic and randomized methods for design under uncertainty. Springer, Berlin

Nesterov Y (2009) Primal-dual subgradient methods for convex problems. Math Program 120(1):221-259

Nguyen-Huu A (2012) Valorisation financière sur les marchés d'électricité. Ph.D. thesis, Paris Dauphine
Ni E, Guan X, Li R (1999) Scheduling hydrothermal power systems with cascaded and head-dependent reservoirs. IEEE Trans Power Syst 14:1127-1132

Ni E, Luh PB, Rourke S (2004) Optimal integrated generation bidding and scheduling with risk management under a deregulated power market. IEEE Trans Power Syst 19(1):600-609

Nilsson O, Sjelvgren D (1996) Mixed-integer programming applied to short-term planning of a hydro-thermal system. IEEE Trans Power Syst 11(1):281-286

Nogales FJ, Contreras J, Conejo AJ, Espínola R (2002) Forecasting next-day electricity prices by time series models. IEEE Trans Power Syst 17(2):342-348

Nowak MP (2000) Stochastic Lagrangian relaxation in power scheduling of a hydrothermal system under uncertainty. Ph.D. thesis, Humboldt University, Berlin

Nowak MP, Römisch W (2000) Stochastic Lagrangian relaxation applied to power scheduling in a hydro-thermal system under uncertainty. Ann Oper Res 100(1-4):251-272

Nürnberg R, Römisch W (2003) A two-stage planning model for power scheduling in a hydro-thermal system under uncertainty. Optim Eng 3:355-378

Oliveira ARL, Soares S, Nepomuceno L (2005) Short term hydroelectric scheduling combining network flow and interior point approaches. Electr Power Energy Syst 27:91-99

O'Neill RP, Hedman KW, Krall EA, Papavasiliou A, Oren SS (2010) Economic analysis of the *n* − 1 reliable unit commitment and transmission switching problem using duality concepts. Energy Syst 1(2):165-195

Oren SS, Svoboda AJ, Johnson RB (1997) Volatility of unit commitment in competitive electricity markets. Int Conf Syst Sci 5:594-601

Ostrowski J, Wang J (2012) Network reduction in the transmission-constrained unit commitment problem. Comput Ind Eng 63(1):702-707

Ostrowski J, Vannelli A, Anjos MF (2010) Groupe d'études et de recherche en analyse des décisions (Montréal, Québec). Symmetry in Scheduling Problems. Groupe d'études et de recherche en analyse des décisions

Ostrowski J, Anjos MF, Vannelli A (2012) Tight mixed integer linear programming formulations for the unit commitment problem. IEEE Trans Power Syst 27(1):39-46

Ostrowski J, Wang J, Liu C (2012) Exploiting symmetry in transmission lines for transmission switching. IEEE Trans Power Syst 27(3):1708-1709

Oudjane N, Collet J, Duwig V (2006) Some non-Gaussian models for electricity spot prices. In: 9th international conference on probabilistic methods applied to power systems

Ouyang Z, Shahidehpour M (1991) An intelligent dynamic programming for unit commitment application. IEEE Trans Power Syst 6(3):1203-1209

Ouyang Z, Shahidehpour M (1992) A hybrid artificial neural network-dynamic programming approach to unit commitment. IEEE Trans Power Syst 7(1):236-242

Ozturk UA, Mazumdar M, Norman BA (2004) A solution to the stochastic unit commitment problem using chance constrained programming. IEEE Trans Power Syst 19(3):1589-1598

Padhy NP (2004) Unit commitment—a bibliographical survey. IEEE Trans Power Syst 19(2):1196-1205

Palamarchuk SI (2012) Compromise scheduling of bilateral contracts in electricity market environment. In: Sorokin A, Rebennack S, Pardalos PM, Iliadis NA, Pereira MVF (eds) Handbook of networks in power systems I. Springer, Heidelberg, pp 241-262

Pang CK, Chen HC (1976) Optimal short-term thermal unit commitment. IEEE Trans Power Appar Syst 95(4):1336-1346

Pang CK, Sheble GB, Albuyeh F (1981) Evaluation of dynamic programming based methods and multiple area representation for thermal unit commitments. IEEE Trans Power Appar Syst PAS-100(3):1212-1218

Papavasiliou A, Oren SS (2012) A stochastic unit commitment model for integrating renewable supply and demand response. In: Invited panel paper, proceeding of the IEEE PES GM, San Diego, CA, July 24-28, 2012

Papavasiliou A, Oren SS (2013) A comparative study of stochastic unit commitment and security-constrained unit commitment using high performance computing. In: Proceeding of the European control conference ECC 2013

Papavasiliou A, Oren SS, O'Neill R (2011) Reserve requirements for wind power integration: a scenario-based stochastic programming framework. IEEE Trans Power Syst 26(4):2197-2206

Papavasiliou A, Oren SS, O'Neill R (2013a) Multi-area stochastic unit commitment for high wind penetration in a transmission constrained network. Oper Res 61(3):578-592
Papavasiliou A, Oren SS, Yang Z. Balasubramanian P, Hedman KW (2013b) An application of high performance computing to transmission switching. In: IREP bulk power system dynamics and control symposium, Rethymnon, Greece, 2013

Parrilla E, García-González J (2006) Improving the B&B search for large-scale hydrothermal weekly scheduling problems. Electr Power Energy Syst 28:339–348

Pedregal DJ, Contreras J, Sanchez de la Nieta AA (2012) Ecotool: a general matlab forecasting toolbox with applications to electricity markets. In: Sorokin A, Rebennack S, Pardalos PM, Iliadis NA, Pereira MVF (eds) Handbook of networks in power systems I. Springer, Heidelberg, pp 151–171

Peng T, Tomsovic K (2003) Congestion influence on bidding strategies in an electricity market. IEEE Trans Power Syst 18(3):1054–1061

Pepper W, Ring BJ, Read EG, Starkey SR (2012) Short-term electricity market prices: a review of characteristics and forecasting methods. In: Sorokin A, Rebennack S, Pardalos PM, Iliadis NA, Pereira MVF (eds) Handbook of networks in power systems II. Springer, Heidelberg, pp 3–36

Pereira MVF, Pinto LMVG (1983) Application of decomposition techniques to the mid- and short-term scheduling of hydrothermal systems. IEEE Trans Power Appar Syst PAS–102(11):3611–3618

Pereira MV, Granville S, Fampa MHC, Dix R, Barroso LA (2005) Strategic bidding under uncertainty: a binary expansion approach. IEEE Trans Power Syst 11(1):180–188

Philpott A, Schultz R (2006) Unit commitment in electricity pool markets. Math Program Ser B 108:313–337

Piekutowki M, Litwinowcz T, Frowd R (1994) Optimal short-term scheduling for a large-scale cascaded hydro system. IEEE Trans Power Syst 9(2):805–811

Pineau PO, Murto P (2003) An oligopolistic investment model of the finnish electricity market. Ann Oper Res 121(1–4):123–148

Polyak BT (1977) Subgradient methods: a survey of soviet research. In: Lemaréchal C, Mifflin R (eds) Nonsmooth optimization, IIASA proceedings series. Pergamon Press, New York

Prékopa A (1995) Stochastic programming. Kluwer, Dordrecht

Prékopa A (2003) Probabilistic programming. In: Ruszczyński A, Shapiro A (eds) Stochastic programming, chap 5. Handbooks in operations research and management science, vol 10. Elsevier, Amsterdam

Prékopa A, Rapcsák T, Zsuffa I (1978) Serially linked reservoir system design using stochastic programming. Water Resour Res 14:672–678

Price JE (2007) Market-based price differentials in zonal and lmp market designs. IEEE Trans Power Syst 22(4):1486–1494

Rajan CCA, Mohan MR (2004) An evolutionary programming-based tabu search method for solving the unit commitment problem. IEEE Trans Power Syst 19(1):577–585

Rajan CCA, Mohan MR, Manivannan K (2003) Neural-based tabu search method for solving unit commitment problem. IEEE Proc Gener Transm Distrib 150(4):469–474

Rajan CCA, Selvi SC, Kumudini Devi RP (2012) Multi-area unit commitment with transmission losses using evolutionary iteration particle swarm optimization approach. Eur J Sci Res 76(4):672–691

Ramos A, Cerisola S, Latorre JM, Bellido R, Perea A, Lopez E (2012) A decision support model for weekly operation of hydrothermal systems by stochastic nonlinear optimization. In: Bertocchi M, Consigli G, Dempster MAH (eds) Stochastic optimization methods in finance and energy: new financial products and energy market strategies. Springer, Heidelberg, pp 143–162

Razaviyayn M, Hong M, Luo Z-Q (2012) A unified convergence analysis of block successive minimization methods for nonsmooth optimization. Technical report, University of Minnesota, Twin Cites

Read EG (2010) Co-optimization of energy and ancillary service markets. In: Rebennack S, Pardalos PM, Pereira MVF, Iliadis N (eds) Handbook of power systems I. Springer, Heidelberg, pp 307–330

Redondo NJ, Conejo AJ (1999) Short-term hydro-thermal coordination by Lagrangian relaxation: solution of the dual problem. IEEE Trans Power Syst 14:89–95

Rocha P, Das TK (2012) Finding joint bidding strategies for day-ahead electricity and related markets. In: Sorokin A, Rebennack S, Pardalos PM, Iliadis NA, Pereira MVF (eds) Handbook of networks in power systems I. Springer, Heidelberg, pp 61–88

Rockafellar RT, Wets Roger J-B (1991) Scenarios and policy aggregation in optimization under uncertainty. Math Oper Res 16(1):119–147

Römisch W (2003) Stability of stochastic programming problems. In: Ruszczyński A, Shapiro A (eds) Stochastic programming, chap 8. Handbooks in operations research and management science, vol 10. Elsevier, Amsterdam

Römisch W, Schultz R (1991) Distribution sensitivity for certain classes of chance-constrained models with application to power dispatch. J Optim Theory Appl 71:569–588
Römisch W, Schultz R (1996) Decomposition of a multi-stage stochastic program for power dispatch. In: SUPPL, vol 3, pp 29–32

Römisch W, Vigerske S (2010) Recent progress in two-stage mixed-integer stochastic programming with applications to power production planning. In: Rebennack S, Pardalos PM, Pereira MVF, Iliadis N (eds) Handbook of power systems I. Springer, Heidelberg, pp 177–208

Ruiz PA, Philbrick CR, Zak EJ, Cheung KW, Sauer PW (2009) Uncertainty management in the unit commitment problem. IEEE Trans Power Syst 24(2):642–651

Ruiz PA, Rudkevich A, Caramanis MC, Goldis E, Ntakou E, Philbrick CR (2012) Reduced MIP formulation for transmission topology control. In: Allerton conference. IEEE, pp 1073–1079

Ruszczyński A (1995) On convergence of an augmented Lagrangian decomposition method for sparse convex optimization. Math Oper Res 20(3):634–656

Ruszczyński A (2003) Decomposition methods. In: Ruszczyński A, Shapiro A (eds) Stochastic programming, chap 3. Handbooks in operations research and management science, vol 10. Elsevier, Amsterdam

Ruszczyński A, Shapiro A (2009a) Multi-stage problems. In: Shapiro A, Dentcheva D, Ruszczyński A (eds) Lectures on stochastic programming. Modeling and theory, chap 3. MPS-SIAM series on optimization, vol 9. SIAM and MPS, Philadelphia

Ruszczyński A, Shapiro A (2009b) Two stage problems. In: Shapiro A, Dentcheva D, Ruszczyński A (eds) Lectures on stochastic programming. Modeling and theory, chap 2. MPS-SIAM series on optimization, vol 9. SIAM and MPS, Philadelphia

Ruzic S, Rajakovic R (1998) Optimal distance method for Lagrangian multipliers updating in short-term hydro-thermal coordination. IEEE Trans Power Syst 13:1439–1444

Sagastizábal C (2012) Divide to conquer: decomposition methods for energy optimization. Math Program 134(1):187–222

Salam MS, Hamdan AR, Nor KM (1991) Integrating an expert system into a thermal unit-commitment algorithm. IEE Proc Gener Transm Distrib 138(6):553–559

Salam S, Nor KM, Hamdan AR (1997) Comprehensive algorithm for hydrothermal coordination. IEE Trans Gener Transm Distrib 144:482–488

Salam S, Nor KM, Hamdan AR (1998) Hydrothermal scheduling based Lagrangian relaxation approach to hydrothermal coordination. IEEE Trans Power Syst 13:226–235

Saravanan B, Das S, Sikri S, Kothari DP (2013) A solution to the unit commitment problem: a review. Front Energy 7(2):223–236

Sarić AT, Stankovic AM (2007) Finitely adaptive linear programming in robust power system optimization. In: Power Tech, 2007 IEEE Lausanne, pp 1302–1307

Sasaki H, Watanabe M, Kubokawa J, Yorino N, Yokoyama R (1992) A solution method of unit commitment by artificial neural networks. IEEE Trans Power Syst 7(3):974–981

Sauma E, Jerardino S, Barria C, Marambio R, Brugman A, Mejia J (2012) Electric interconnections in the andes community: threats and opportunities. In: Sorokin A, Rebennack S, Pardalos PM, Iliadis NA, Pereira MVF (eds) Handbook of networks in power systems I. Springer, Heidelberg, pp 345–366

Schultz R, Nowak M, Nürnberg R, Römisch W, Westphalen M (2003) Stochastic programming for power production and trading under uncertainty. In: Jvsger W, Krebs H-J (eds) Mathematics—key technology for the future. Springer, Heidelberg, pp 623–636

Sendaula MH, Biswas SK, Eltom A, Parten C, Kazibwe W (1991) Application of artificial neural networks to unit commitment. Proc First Int Forum Appl Neural Netw Power Syst 1991:256–260

Senthil-Kumar S, Palanisamy V (2007) A dynamic programming based fast computation Hopfield neural network for unit commitment and economic dispatch. Electr Power Syst Res 77(8):917–925

Shafie-Khah M, Parsa Moghaddam M, Sheikh-El-Eslami MK (2011) Unified solution of a non-convex SCUC problem using combination of modified branch-and-bound method with quadratic programming. Energy Convers Manag 52(12):3425–3432

Shahidehpour M, Yamin H, Li Z (2002) Market operations in electric power systems: forecasting, scheduling, and risk management. Wiley-IEEE Press, London

Sharaf TAM, Berg GJ (1982) Voltampere reactive compensation using chance-constrained programming. IEEE Proc C Gener Transm Distrib 129(1):24–29

Shaw JJ, Gendron RF, Bertsekas DP (1985) Optimal scheduling of large hydrothermal power systems. IEEE Power Eng Rev PER-5(2):32

Sheble GB, Fahd GN (1994) Unit commitment literature synopsis. IEEE Trans Power Syst 9(1):128–135
Sheble GB, Maifeld TT, Brittig K, Fahd G, Fukurozaki-Coppinger S (1996) Unit commitment by genetic algorithm with penalty methods and a comparison of Lagrangian search and genetic algorithm economic dispatch example. Int J Electr Power Energy Syst 18(6):339-346

Sherali HD, Adams WP (1998) A reformulation–linearization technique for solving discrete and continuous nonconvex problems, nonconvex optimization and its applications. Springer, Heidelberg

Sherali HD, Fraticelli BMP (2002) A modification of benders' decomposition algorithm for discrete sub-problems: an approach for stochastic programs with integer recourse. J Glob Optim 22:319-342

Shiina T (1999) Numerical solution technique for joint chance-constrained programming problem "an application to electric power capacity expansion". J Oper Res Soc Jpn 42(2):128-140

Shiina T, Birge JR (2004) Stochastic unit commitment problem. Int Trans Oper Res 11(1):19-32

Siahkali H, Vakilian M (2010) Stochastic unit commitment of wind farms integrated in power system. Electr Power Syst Res 80(9):1006-1017

Sifuentes W, Vargas A (2007a) Hydrothermal scheduling using benders decomposition: accelerating techniques. IEEE Trans Power Syst 22:1351-1359

Sifuentes W, Vargas A (2007b) Short-term hydrothermal coordination considering an ac network modeling. Int J Electr Power Energy Syst 29:488-496

Simopoulos DN, Kavatza SD, Vournas CD (2006) Unit commitment by an enhanced. IEEE Trans Power Syst 21(1):68-76

Singhal PK, Sharma RN (2011) Dynamic programming approach for large scale unit commitment problem. In: International conference on communication systems and network technologies (CSNT), pp 714-717

Siu TK, Nash GA, Shawwash ZK (2001) A practical hydro, dynamic unit commitment and loading model. IEEE Trans Power Syst 16(2):301-306

Snyder WL, Powell HD, Rayburn JC (1987) Dynamic programming approach to unit commitment. IEEE Trans Power Syst 2(2):339-348

Street A, Oliveira F, Arroya JM (2011) Contingency-constrained unit commitment with *n* − *k* security criterion: a robust optimization approach. IEEE Trans Power Syst 26(3):1581-1590

Sudhakaran M, Ajay-D-Vimal Raj P (2010) Integrating genetic algorithms and tabu search for unit commitment. Int J Eng Sci Technol 2(1):57-69

Takigawa FYK, da Silva EL, Finardi EC, Rodrigues RN (2012) Solving the hydrothermal scheduling problem considering network constraints. Electr Power Syst Res 88:89-97

Takigawa FYK, Finardi EC, da Silva EL (2013) A decomposition strategy to solve the short-term hydrothermal scheduling based on Lagrangian relaxation. J Algorithms Optim 1(1):13-24

Takriti S, Birge JR (2000) Using integer programming to refine Lagrangian-based unit commitment solutions. IEEE Trans Power Syst 15(1):151-156

Takriti S, Birge JR, Long E (1996) A stochastic model for the unit commitment problem. IEEE Trans Power Syst 11:1497-1508

Takriti S, Krasenbrink B, Wu LSY (2000) Incorporating fuel constraints and electricity spot prices into the stochastic unit commitment problem. Oper Res 48(2):268-280

Tong SK, Shahidehpour M (1989) Combination of Lagrangian-relaxation and linear-programming approaches for fuel-constrained unit-commitment problems. IEEE Proc Gener Transm Distrib 13(3):162-174

Triki C, Beraldi P, Gross G (2005) Optimal capacity allocation in multi-auction electricity markets under uncertainty. Comput Oper Res 32:201-217

Triki C, Conejo AJ, Garcés LP (2011) Short-term trading for electricity producers. In: Bertocchi M, Conigli G, Dempster MAH (eds) Stochastic optimization methods in finance and energy: new financial products and energy market strategies, volume 163 of international series in operations research and management science. Springer, Heidelberg, pp 181-202

Trukhanova S, Ntaimo L, Schaefer A (2010) Adaptive multicut aggregation for two-stage stochastic linear programs with recourse. Eur J Oper Res 206(2):395-406

Tseng P (2001) Convergence of a block coordinate descent method for nondifferentiable minimization. J Optim Theory Appl 109(3):475-494

Tseng CL, Li CA, Oren SS (2000) Solving the unit commitment problem by a unit decommitment method. J Optim Theory Appl 105(3):707-730

Tuohy A, Meibom P, Denny E, O'Malley MJ (2009) Unit commitment for systems with significant wind penetration. IEEE Trans Power Syst 24(2):592-601