A long-term unit commitment problem with hydrothermal coordination for economic and emission control in large-scale electricity systems

The basic idea of our model formulation comes from Carrión and Arroyo (2006), Ostrowski et al. (2012) and Morales-España et al. (2013), who formulated the problem without energy storages. Particularly, the latter model is characterized as tight, due to a relatively small integrality gap, i.e., the LP relaxation is close to the convex hull of the feasible integer solutions. Therefore, we extended this tight model in order to manage the coordination between thermal and storage units (cf. Franz et al. 2019, where also explanations for the tightness of the described model are given). Furthermore, a reformulation and an adjustment of constraints (i.e., constraints for start-up processes and reserve capacity) are performed so that the resulting model provides near-optimal solutions significantly faster than the model formulation presented by Morales-España et al. (2013).

Let \(\mathcal {I}\) be the set of thermal plants and \(\mathcal {J}\) be the set of energy storages. For each thermal plant \(i\in {\mathcal {I}}\), we define the continuous power generation level \(p_{it}\) as well as the binary on/off status \(u_{it}\) at each point in time \(t\in {\mathcal {T}}\), where \(\mathcal {T}\) represents the set of hourly time periods \(({\mathcal {T}}:= \{1,\,2,\,\ldots ,\,T\})\). The power generation level \(p_{it}\) denotes the power level above the minimum power output \({\underline{P}}_i\). For each energy storage \(j\in {\mathcal {J}}\), we specify the continuous power generation level \(p^{{\text {g}}}_{jt}\) as well as the continuous pumping level \(p^{{\text {p}}}_{jt}\). We assume that \(p \ge 0\) is satisfied for all power-related decision variables.

The objective function of the problem is firstly chosen as the minimization of total operating costs, which covers thermal production costs, thermal start-up costs, and non-served energy costs. The thermal production cost for each unit \(i\in \mathcal {I}\) and point in time \(t\in \mathcal {T}\) is typically modeled using the convex heat consumption function \(Q(\cdot )\) for the overall power output \(p'_{it}=p_{it}+{\underline{P}}_i\), e.g., as\(c^{\text {pc}}_{i}\) represents a unit-specific fuel cost coefficient and \(q^{\text {a}}_{i}\), \(q^{\text {b}}_{i}\) as well as \(q^{\text {c}}_{i}\) are nonnegative heat coefficients relating to the respective technical efficiency of unit i. Please note that no further cost additives (e.g., for maintenance, lubricants etc.) are taken into account.

Function (1) can be linearized, where fixed operation costs \(c^{{{\text {fix}}}}\) and variable production costs \(c^{{{\text {var}}}}\) in accordance to the power output are used. A sophisticated linearization approach is, e.g., presented by Carrión and Arroyo (2006). In our study, we set \(q^{\text {c}}_{i} := 0\) for all plants \(i \in \mathcal {I}\), similar to Gollmer et al. (2000) and Martinez Diaz (2008), since the curvature of function (1) is typically quite small. As costs for generating the minimum power level can be integrated in the fixed costs (they always occur if a generator is running), function (1) simplify towhere variable costs \(c^{{{\text {var}}}}_{i}\) have to be considered for each megawatt \(p_{it}\) that is delivered above the minimum power level \({\underline{P}}_i\) [cf. constraints (6)]. Therefore, the variable and fixed cost components can be defined as \(c^{{{\text {var}}}}_{i}:=c^{\text {pc}}_{i} q^{\text {b}}_{i}\) and \(c^{{\text {fix}}}_{i}:= c^{\text {pc}}_{i} ( q^{\text {a}}_{i} + q^{\text {b}}_{i} \, {\underline{P}}_i )\), respectively.

The thermal start-up costs usually vary between warm and cold starts (cold starts of \(i \in \mathcal {I}\) are necessary after a downtime of at least \(\beta _i\) time periods). We introduce binary decision variables indicating whether or not plant i is started \((u^{\text {s}}_{it}=1)\) and performs a cold start \((u^{{\text {cs}}}_{it}=1)\) in \(t\in \mathcal {T}\). Then, start-up costs may be formulated as \(c^{{\text {ws}}}_{i} \, u^{\text {s}}_{it} + c^{{\varDelta }}_{i} \, u^{\text {cs}}_{it},\) where \(c^{{\text {ws}}}_{i}\) indicates warm start costs and \(c^{{\varDelta }}_{i}\) represents additional costs for a cold start. Both cost components result from reheating the plant’s boiler. An extension to continuously modeled start-up costs using an exponential heat consumption approach instead of the two-piece linearized one can be found in Wood et al. (2013).

A feasible solution must ensure that the net energy provision delivered by thermal plants and storages is equal to the (residual) demand \(D_t\), \(t\in \mathcal {T}\) [cf. constrains (4)]. In order to relax the demand balance conditions, a demand overfulfillment is permitted but penalized by higher production costs. Furthermore, non-served energy (e.g., in case of undercapacity of all units) is allowed by introducing nonnegative slack variables \(n_t\). Particularly for long-term planning horizons, \(n_t>0\) can be allowed for some t, since the resulting schedule is used for production planning purposes and not for real-time production control activities. The non-served energy is penalized in the objective function by \(c^{{\text {non}}} \, n_{t},\) with a penalty cost factor \(c^{{\text {non}}}\) (its value must be higher than the most expensive plant). Due to this trick, a first feasible solution (with \(n_{t}=D_t+R_t)\) can be found immediately by a standard solver like CPLEX or Gurobi that will have a positive impact on the computation time.

The entire UCP with hydrothermal coordination may now be formulated as followsIn objective function (3), total operating costs are minimized. The fulfillment of energy demands either by thermal or by hydro storages is ensured with system constraints (4). Let \({\overline{P}}_i\) be the maximum power level of thermal plant \(i\in {\mathcal {I}}\) and let \({\overline{P}}_j^{\text {g}}\) be the maximum hydropower output by turbining at storage j. Then, system constraints (5) provide a sufficient spinning reserve (in the event of an unpredictable failure) for each point in time. Constraints (6) ensure that power outputs can only be determined between a minimum and a maximum level. Once a thermal plant \(i\in {\mathcal {I}}\) is started (decommitted), it has to be online (offline) for at least its minimum uptime \(\pi _i\) (minimum downtime \(\delta _i\)), which is guaranteed by inequalities (7) and (8). Binary decision variables \(u_{it}^{{\text {d}}}\) indicate whether a plant i is decommitted in period t or not. Then, logical constraints (9) and (10) guarantee that all binary variables \(u\in \{0,1\}\) take appropriate values. For hydro storages, energy flow conservation constraints (11) are to be considered to determine the amount of energy \(e_{jt}\) maintained in each storage j in period t. The maintained energy \(e_{jt}\) corresponds to the maintained energy in period \(t-1\) plus the energy obtained by pumping and minus the power output for turbining, where respective efficiencies \(\eta _{j}^{\text {p}}\) and \(\eta _{j}^{\text {g}}\) are taken into account. Inequalities (12) refer to a lower \({\underline{E}}_j\) and an upper level \({\overline{E}}_j\) in energy storage \(j\in {\mathcal {J}}\). Moreover, inequalities (13) restrict the technical limits of generation and pumping levels. Finally, constraints (14) and (15) define feasible domains for all continuous and binary decision variables. For the sake of simplicity, constraints affecting the initial operating status are omitted. However, they can easily be added (cf., e.g., Morales-España et al. 2013) and are considered within our performance analysis (cf. Sect. 4).

A UCP–HT which addresses a minimization of costs and emissions can be formulated using the principle of the European Union Emissions Trading System (EU ETS). The EU ETS was established in 2005 to manage a systematic reduction in greenhouse gases. Particularly, it aims at limiting the overall \(\hbox {CO}_2\)-production (cap principle).² Therefore, each \(\hbox {CO}_2\)-emitting plant (i.e., thermal power plants for the electricity industry) has to buy allowances for the emission of each produced ton of \(\hbox {CO}_2\) by bidding on an auction infrastructure (trade principle). The resulting “cap-and-trade” mechanism provides time-dependent market clearing prices \(c^{{\mathrm{CO}_2}}_t\)\([\frac{\EUR}{\text {t} \ \text{CO}_2}]\), \(t\in \mathcal {T},\) for emission certificates (cf., e.g., Ellermann et al. 2010 or Kruger and Pizer 2010).

In order to enhance objective function (3) of the UCP–HT by environmental aspects, \(\hbox {CO}_2\)-related costs have to be added. These costs comprise emission costs for steady-state operationsand emission costs caused by start-up procedureswhere \(\epsilon _i\) represents the carbon dioxide content [\(\frac{\text {t}~\hbox {CO}_2}{\text{MWh}_\text {th}}]\) of each produced mega watt by power plant i. Please note that the emission factor \(\epsilon _i\) is mainly influenced by the fuel (e.g., lignite, hard coal, gas), its quality and plant parameters. As in Sect. 2.1, we again choose \(q^{\text {c}}_{i}:=0\) for all plants \(i \in \mathcal {I}\) within heat consumption function \(Q(\cdot )\). Consequently, expression (16) simplifies to \(c^{{\mathrm{CO}_2},\mathrm{fix}}_{it} \epsilon _i\, u_{it} + c^{{\mathrm{CO}_2},\mathrm{var}}_{it} \epsilon _i \,p_{it}\), similar to expression (2).

The resulting objective functionof the UCP–HT with economic and emission aspects contains two conflicting targets. Typically, gas-fired (e.g., combined cycle) power plants have high production costs and low \(\hbox {CO}_2\) emissions (since the emission factor \(\epsilon _i\) is small), whereas lignite fired power plants offer low production costs, but high \(\hbox {CO}_2\) emissions. Therefore, a highly cost-efficient dispatch increases the usage of emission-intensive power plant activities. For a more sustainable and environmentally friendly electricity provision, gas-fired plants should be preferred. The market price \(c^{{\mathrm{CO}_2}}_t\) for emission certificates in expressions (16) and (17) weights the two preferences, where \(c^{{\mathrm{CO}_2}}_t\) is exogenously given by the EU ETS and hence driven by market processes.

The thermal plant optimization preselects certain plants to fulfill the fluctuating residual demand as well as the spinning reserve requirements without using the energy storage operations of turbining or pumping. In detail, the following three steps are executed within the first stage (cf. Fig. 1):

Create start solution An initial solution is obtained by applying a greedy algorithm, assuming \(\delta _i=\pi _i=1\), \(i \in \mathcal {I}\). Thereby, all plants are sorted and ranked according to non-decreasing marginal costs (i.e., to their merit order). Then, for each point in time \(t \in \mathcal {T}\), a subset of plants is committed, i.e., plants are stepwise activated in the sequence of their merit order until the demand and reserve requirements \(\sum _{i\in \mathcal {I}} {\overline{P}}_i \, u_{it} \ge D_t + R_t\) are satisfied. Some plants might be skipped in the considered order to fulfill the following inequalities \(\sum _{i\in \mathcal {I}} {\underline{P}}_i \, u_{it} \le D_t\) which are necessary due to the power output specifications of all plants i. Within this first step, the power outputs \(p_{it}\) of all committed plants \(i \in \mathcal {I}\) (with \(u_{it}=1, t\in \mathcal {T})\) are always set to the maximum value \({\overline{P}}_i - {\underline{P}}_i\), except for the last committed plant \(i'\). This plant is typically characterized by high marginal costs and has to be operated at part-load to balance the demand. In the event that the part-load operation of plant \(i'\) is not sufficient for demand balancing, the power of the second last committed plant must also be reduced, and so on.

Repair infeasible solution Typically, the initial solution of the first step is infeasible and needs to be repaired with respect to the minimum up- and downtime requirements. In general, a fulfillment of minimum up- and downtime requirements of a unit \(i\in \mathcal {I}\) can be achieved by enlarging the corresponding operating phases or idle phases until constraints (7) and (8) are satisfied. This procedure is similar to that one in Delarue et al. (2013). An operating phase indicates that plant i is active (\(u_{it}=1\), \(t\in \mathcal {T}\)), whereas idle phases denote that plant i is inactive (\(u_{it}=0\), \(t\in \mathcal {T}\)).

Let \(\tau ^{\text {up}}_{i,t_1}\) be the duration of an operating phase of some unit \(i\in \mathcal {I}\) that starts at uptime \(t_1\). Moreover, let  \(\tau ^{\text {down}}_{i,t_2}\) be the duration of the following idle phase that starts at time \(t_2\) (cf. Fig. 2). In the case of a violation of the minimum uptime requirements [cf. constraints (7)], the duration \(\tau ^{\text {up}}_{i,t_1}\) may be extended to the right or left as long as the time boundaries of \(\mathcal {T}\) are observed. We first consider the extension of \(\tau ^{\text {up}}_{i,t_1}\) to the right (cf. Fig. 2a). This extension may only be performed if

In the event that the extension to the right is not sufficient to fulfill constraints (7), we extend the operating phase according to items (i) and (ii) as much as possible. Additionally, the repair procedure is carried out to the left. Thereby, the downtime duration of the previous idle phase must be taken into account [similar to (i) and (ii)]. Furthermore, if both attempts fail (and thus are not realized), the operating phase between \(t_1\) and \(t_2\) is connected to the successive operating phase, that starts at time \(t_3\) (i.e., the idle phase is eliminated, cf. Fig. 2b). In case the minimum uptime is still not fulfilled, the already extended operating phase is merged with the previous operating phase. This procedure will finally lead to an operating phase that is at least equal to the required minimum uptime.

Similar repair steps have to be executed for violations against the minimum downtime \(\delta _i\). In contrast to the repair procedure described above, an enlargement of an idle phase is only possible if constraints (4) and (5) are still satisfied. Otherwise, the idle phase must be eliminated.

Once a solution schedule is repaired, the power output of all active plants has to be adjusted. For this purpose, the plants’ power outputs are set according to the merit order. This means that the most expensive, active plants are operated at part-load again (cf. the first step of our heuristic). However, it might happen that the demand is overfulfilled [possible due to constraints (4)] and redundant plants exist which are decommitted within the next steps.

To economize plant operations in terms of start-up and fixed operation costs, quite short operating and idle phases are canceled, before the repair step is considered. In order to identify such a short operating or idle phase, it is reasonable to use the minimum uptime or downtime as a reference value, i.e., \(\tau ^{{\text {up}}}_{it} \le \xi \cdot \pi _i\) and \(\tau ^{{\text {down}}}_{it}\le \xi \cdot \delta _i\). Please note that a cancelation applies for the whole algorithm. A canceled operating phase can result in an energy shortage and a canceled idle phase in an energy overfulfillment. In the case of an energy shortage, additional plants (e.g., flexible peak plants) must be committed according to their minimum uptime and downtime requirements. In general, this action is significantly cheaper than a comprehensive enlargement of the current operating phase (which would be necessary while executing the repair step). In preliminary studies, \(\xi :=0.2\) produces the best results.

Let \(S^{\text {thermal}}\) be the current solution that considers thermal plants. The schedule is encoded in a binary \(|\mathcal {I}| \times |\mathcal {T}|\)-matrix, where for each plant \(i \in \mathcal {I}\) and point in time \(t \in \mathcal {T}\) the status variables \(u_{it}\) are included (cf. Fig. 3). All other relevant information like power outputs \(p_{it}\) and the amount of time periods operated in the current operating status (particularly \(\tau ^{\text {up}}_{it}\), cf. Fig. 2) can be calculated on the basis of the matrix entries (cf. “start solution” step).

For applying a neighborhood movement, a unit \(i\in \mathcal {I}\) (iteratively chosen in accordance to the merit order) and the first suitable operating phase of this unit are selected. Please note that it is generally not advantageous (in terms of solution time and quality) to swap plants with long operating phases. Therefore, we denote a plant with an operating phase that is smaller than a multiple \(\zeta\) of the minimum uptime as suitable for swapping. For our purposes, \(\zeta :=3\) performs best. If the operating phase of plant i is redundant (i.e., the demand can be fulfilled even without i), then, the operating phase is decommitted by updating the status variables within schedule \(S^{\text {thermal}}\). Otherwise, unit i is temporarily decommitted, where the decommitment of i has to be compensated by operating phases of one or several plants \(i' \in \mathcal {I}' \subset \mathcal {I}\,{\setminus }\{i\}\). Generally, several subsets \(\mathcal {I}'\) can be chosen that result in different objective function values determined by objective function (3). In order to limit the number of subsets, we generate all subsets \(\mathcal {I}'\) with a prescribed maximal cardinality k (e.g., \(k\le 3\)) consisting of units \(i'\), whereWhen all subsets are created, a subset \(\mathcal {I}'\) is further investigated in our neighborhood search if constraints (4) are satisfied without slack as well as constraints (5), (7), and (8) are fulfilled. Due to a best improve hill climbing approach, the (feasible) neighbor solution with the best objective function value replaces the current solution (in case it is better). Once the analysis of the current operating phase of plant i is completed, \(S^{\text {thermal}}\) is updated and the next suitable operating phase is selected.

Figure 3 shows the solution representation of a schedule \(S^{{\text {thermal}}}\) on the left-hand side. Moreover, the neighborhood movement for unit \(i=2\) is demonstrated, where the second operating phase starting at \(t=8\) is considered. We assume that the chosen operating phase is not redundant. Therefore, unit i is decommitted and subsets \(\mathcal {I}'=\{3\}\), \(\mathcal {I}'=\{4\}\), \(\mathcal {I}'=\{3, 4\}\) are investigated. Each of them leads to a fulfillment of the demand. The relevant excerpts of the three neighborhoods (a)–(c) are given on the right-hand side of Fig. 3. Please note that the current schedule \(S^{\text {thermal}}\) is feasible in our simple example and contains no overfulfillment. Therefore, the demand requires a commitment of at least two units in \(t\in \{8, 9\}\). Hence, the duration of the new operating phase of unit \(i=4\) in neighbor (b) is two periods (although \(\pi _4=1\)). In contrast, the operating phase of unit \(i=4\) in neighbor (c) equals the minimum uptime, as unit \(i=3\) fully covers the demand in \(t\in \{8, 9\}\). Since neighbor (c) results in an overfulfillment, the objective function values of (a) and (b) are always better. The solution with the best objective function values is considered as a new starting point for further neighborhood search steps.

The second stage in Fig. 1 improves the solution \(S^{\text {thermal}}\) determined in the first stage by implementing the “hydrothermal coordination” problem for pumped storages. Besides \(S^{\text {thermal}}\), a second schedule \(S^{\text {hydro}}\) for the hydro storage activities is introduced (i.e., generating electricity or retaining energy back to the storages). Analogous to the thermal schedule, \(S^{\text {hydro}}\) is encoded in a \(|\mathcal {J}| \times |\mathcal {T}|\)-matrix and contains information about energy levels \(e_{jt}\) for all \(j\in \mathcal {J}\) and \(t \in \mathcal {T}\). Please note that the corresponding power levels \(p^{\text {g}}_{jt}\) and \(p^{\text {p}}_{jt}\) can always be derived using constraints (11). In detail, the following two steps are executed in the second stage:

Shift demand using energy storages Energy storages represent a way to decouple the interdependency of demand and supply by shifting demands of one or several periods to other points in time. They can be operated in the state of generating energy due to turbining (generating phase), retaining energy due to pumping (retaining phase), and maintaining energy in the storage (cf. Fig. 4).

In our demand shift step, an allocation of energy storages is found by stepwise replacing operating phases of thermal plants by storage operations, i.e., by generating and retaining phases in order to achieve cost reductions. Typically, generating phases (starting at \(t^{\text {gen,s}}\) and ending at \(t^{\text {gen,d}}\)) can be identified in high energy demand intervals and retaining phases (starting at \(t^{\text {ret,s}}\) and ending at \(t^{\text {ret,d}}\)) in low energy demand intervals (cf. Fig. 4). Therefore, our basic idea is to search for demand maxima and minima. In a demand maximum, possible candidate plants for a decommitment are positioned (i.e., candidates for generating phases). Moreover, the already committed plants in a demand minimum may run at higher-power levels, i.e., these are possible candidates for retaining energy (an additional commitment of plants is usually connected with high fixed costs and therefore not suitable).

The principle of our algorithm is demonstrated in Fig. 5, where we select candidates of generating and retaining phases (referred to as \(turb\) and \(pump\)) in the identification part and suitably match them in the coordination part.

In the identification part, we move along the time-axis and search for situations in which \(D_{t-1}<D_t\ge D_{t+1}\) (generating phase) or \(D_{t-1}>D_t\le D_{t+1}\) (retaining phase) hold. Once such a point in time \(t\in \mathcal {T}\) is identified, a differentiated procedure is required for demand maxima and minima.

For a demand maximum (e.g., at time \(t^{\text {max}}\)), all at \(t^{\text {max}}\in \mathcal {T}\) committed plants have to be taken into account. An operating phase of a committed plant \(i\in \mathcal {I}\) (i.e., a phase between \(t^{\text {gen,s}}\) and \(t^{\text {gen,d}}\), see Fig. 4) is identified as a candidate for a generating phase ifFor a demand minimum (e.g., at time \(t^{\text {min}}\)), all at \(t^{\text {min}}\in \mathcal {T}\) committed plants have to be taken into account. A committed plant \(i\in \mathcal {I}\) is identified as a candidate for a retaining phase if the power level \(p_{i,t^{\text {min}}}\) in \(t^{\text {min}}\) is lower than \({\overline{P}}_i\). Then, \({\overline{P}}_i - \left( p_{i,t^{\text {min}}} + {\underline{P}}_i \right)\) can be utilized to retain energy in hydro storages. Furthermore, all time periods on the left- and on the right-hand side of \(t^{\text {min}}\) within the operating phase of i are also considered for retaining energy.

Within the identification part, the generating and retaining phases found previously are stored in separated lists (namely, \(L^{{\text {gen}}}\) and \(L^{{\text {ret}}}\)). Prior executing the coordination part, candidates in list \(L^{{\text {gen}}}\) are sorted according to non-increasing cost reductions and candidates in \(L^{{\text {ret}}}\) are sorted according to non-decreasing variable operating costs. Both costs relate to the changed use of thermal power plants through the incorporation of hydro storages. In the case of a generating phase, there are cost reductions in the amount of fixed and variable costs incurred if the thermal plant is possibly shutdown. In retaining phases, the higher-power output results in additional costs in the amount of variable operating costs. Algorithm 1 depicts the subsequent coordination part, where iteratively generating and retaining phases are selected and matched.

The first line of Algorithm 1 shows that we iterate over all elements in list \(L^{\text {gen}}\). Assuming that generating phase \(turb\) in \(L^{\text {gen}}\) is considered, which belongs to the operating phase of plant i with a start in time period \(t^{\text {gen,s}}\) and an end in \(t^{\text {gen,d}}\) (see also Fig. 4). In accordance to line 2, the realization of \(turb\), i.e., the decommitment of i and the compensation with hydro storage energy, has to be verified by ensuring the following prerequisites for each \(t\in \{t^{\text {gen,s}},t^{\text {gen,d}}\}\): If the prerequisites are fulfilled only until a time \(t'<t^{\text {gen,d}}\) with \(t'\in \mathcal {T}\), \(turb\) is shortened and realized in \(t^{\text {gen,s}},\ldots ,t'\).

In order to compensate an energy removal \(\varDelta E^{\text {gen,tot}}\) according to \(turb\) (cf. Fig. 6a), suitable retaining phases \(pump\) have to be selected in compliance with the sequence in list \(L^{\text {ret}}\) (lines 3 and 4 of Algorithm 1). Please note that according to item (i) (cf. previous enumeration) fully filled hydro storages were assumed in period \(t^{\text {gen,s}}\), which is not guaranteed in any case. Therefore, a specific amount \(\varDelta E^{\text {gen,pre}}\) (\(0\le E^{\text {gen,pre}} \le \varDelta E^{\text {gen,tot}}\), cf. Fig. 6b) has to be retained before period \(t^{\text {gen,s}}\) in order to guarantee that the level of no hydro storage falls below \({\underline{E}}\) in \(t\in \{t^{\text {gen,s}},t^{\text {gen,d}}\}\) or any other period. Using a specific phase \(pump\) in list \(L^{\text {ret}}\), a hydro storage \(j\in \mathcal {J}\) is filled as long as We start the procedure with the most efficient hydro storage \(j\in \mathcal {J}\). Once the second or third condition is satisfied for storage j, the next efficient storage is selected. If the first condition is fulfilled, the next period \(t'+1\) (in case \(t' < \min \{t^{\text {ret,d}}, t^{\text {gen,s}}\}\)) or the next \(pump\) in list \(L^{\text {ret}}\) (in case \(t' = \min \{t^{\text {ret,d}}, t^{\text {gen,s}}\}\)) is chosen. In the event that the fourth condition occurs, the procedure terminates. The remaining energy \(\varDelta E^{\text {gen,tot}} - \varDelta E^{\text {gen,pre}}\) (under consideration of efficiencies) can then be retained before time \(t^{\text {gen,s}}\) or after time \(t^{\text {gen,d}}\) in an analogous way to (i)–(iv).

After the selecting and matching step, all schedules must be updated if the energy removal \(\varDelta E^{\text {gen,tot}}\) can be compensated and cost savings can be achieved (cf. line 5 in Algorithm 1). The update (line 6) is performed as follows: unit i that corresponds to the selected phase \(turb\) has to be decommitted, i.e., we set \(u_{it}:=0\) for \(t\in \{t^{\text {gen,s}}, \ldots , t^{\text {gen,d}}\}\) in \(S^{\text {thermal}}\). Furthermore, according to the designated additional pumping power and the designated generating power (due to the selected and used \(pump\) and \(turb\) phases), the energy levels \(e_{jt}\), \(j\in \mathcal {J}\) (if used) and \(t\in \mathcal {T}\) are adjusted. We use the updated (and feasible) schedules \(S^{\text {thermal}}\) and \(S^{\text {hydro}}\) in order to start a new coordination iteration. Hence, the next phase \(turb\) in list \(L^{\text {gen}}\) is selected and matched with other phases \(pump\) (cf. Algorithm 1), where list \(L^{\text {ret}}\) has to be updated according to the already selected pump phases.

Finalize solution A last finalizing step is performed to replace or decommit (redundant) operating phases of thermal plants if cost savings are thereby achievable. The procedure is similar to the local optimization steps in the first stage of the algorithm visualized in Fig. 1. However, in addition to thermal plants, hydro storages for the provision of spinning reserve have to be taken into account. If excessive spinning reserve is provided (due to the updated schedules), further decommitments of thermal plants can be performed, always maintaining solution feasibility. Additionally, the provided energy of the fictitious plant that was introduced in the preprocessing (cf. Fig. 1) is replaced by variable \(n_t\) in each period t. Please note that the usage of the fictitious plant is reduced significantly due to the shift demand and improve/finalize steps.

The following study makes use of two test sets \(\hbox {T}_1\) and \(\hbox {T}_2\), where each set consists of 50 instances. Test set \(\hbox {T}_1\) was first introduced by Kazarlis et al. (1996), and it is commonly used for analyzing short-term UCP models (e.g., Ongsakul and Petcharaks 2004; Viana et al. 2008; Delarue et al. 2013, and Morales-España et al. 2013). All instances in \(\hbox {T}_1\) are based on the same plant system with 10 thermal units. Then, this 10-plant system is exactly replicated in order to obtain a system with 20,30,…,100 plants. Moreover, demand values for a planning horizon of 24 h are adopted by Kazarlis et al. (1996) and proportionally adjusted relatively to the total capacity of the replicated plant system. Since we need planning horizons for investigating our long-term problem, we copied the 24-h horizon in order to get instances of 1, 4, 12, and 20 weeks as well as 1 year (i.e., 24 to 8760 hourly time periods). Please note that on weekends only 80 % of the demand is chosen. The spinning reserve requirements are set to 10 % of the corresponding demand in each period. Test set \(\hbox {T}_2\) is derived from \(\hbox {T}_1\) by replacing the demand by a highly volatile residual demand that appeared in Germany in 2015 (relatively adjusted to the total thermal capacity). Furthermore, hydro storages are added to each instance of \(\hbox {T}_1\) and \(\hbox {T}_2\). Thereby, hydro storages had a share of about 7 % of the total thermal capacity (as it was the case in Germany in 2015).

All optimization runs are performed on an Intel i7-2760QM with 2.7 GHz and 16 GB RAM. The mixed-integer linear models were solved with CPLEX 12.6 (using GAMS) applying an optimality gap of 1 % and a time limit of 5 h. Under preliminary tests, we found out that flow-cover, Gomory fractional, and mixed-integer rounding cuts provided by CPLEX perform best and should be used (all other cuts are excluded). Our two-stage heuristic approach proposed in Sect. 3 has been implemented in C# (.NET 4.0).

Computational results for test sets \(\hbox {T}_1\) and \(\hbox {T}_2\) with 10–100 plants and planning horizons ranging from one week to one year are presented in Table 1.³ Columns 2–5 refer to test set \(\hbox {T}_1\) and columns 6–9 to test set \(\hbox {T}_2\). “Gap” displays the average gap [%] between the best integer solution found and the best lower bound obtained by CPLEX. The worst-case gap values are written in parentheses. “\(t^{\text {cpu}}\)” shows the average computation times in seconds [s].

Applying the MILP model, all instances in test set \(\hbox {T}_1\) with a planning horizon of up to 20 weeks are solved to (near-)optimality (i.e., a gap \(\le\) 1 % is reached) within the specified time limit of 5 h. For instances with a one-year planning horizon, the time limit often prevents good outcomes in terms of gap values. Instances in \(\hbox {T}_2\)-instances seem to be more difficult to solve, since the gap values are larger compared to the gaps of \(\hbox {T}_1\)-instances. Here, only instances with a planning horizon of up to 12 weeks can be tackled with gap values lower than 1 %. Moreover, average gaps for instances with a one-year planning horizon are quite high (approx. 63 %). The solution quality of the two-stage heuristic approach is comparable to MILP for all medium-term instances in \(\hbox {T}_1\) and \(\hbox {T}_2\), as gap values are lower or equal to 1 %. For long-term instances, that are mainly focused in this article, great differences between heuristic approach and MILP can be observed. The heuristic approach is always able to find significantly better solutions (even worst-case gap values are \(\le\) 1 % in contrast to the respective MILP gaps that are < 100 %) within considerable less computation time (\(t^{{\text {cpu}}} < 2\) minutes in contrast to MILP \(t^{{\text {cpu}}} \le 5\) h). Due to the fast run times (within which outstanding solutions are generated), the two-stage heuristic seems to be a good choice for practitioners.

A detailed analysis of the two-stage heuristic approach is illustrated in Table 2. Each optimization step (cf. Fig. 1) is evaluated individually using a third test set \(\hbox {T}_3\) with long-term instances. \(\hbox {T}_3\) consists of the ten one-year problem instances of \(\hbox {T}_1\), where the recurrent demand is again replaced by volatile residual demands. We here use the six yearly residual demands occurred in Germany from 2010 to 2015 (cf. ENTSO-E and German TSOs) and adjusted them proportionally to the total capacity of the respective plant system. Thus, 60 long-term instances are obtained with a 10 to 100 plant system. In Table 2, average solution times \(t^{{\text {cpu}}}\) and average relative improvements \(\varDelta\), compared to the respective previous optimization step, are presented. Hence, for the first step, i.e., the creation of a start solution, improvements do not exist. Negative improvements indicate a deterioration of the objective function value. In the transition from a created to repaired solution negative improvements occur. From there to the finalized solution, positive improvements are realized. Additionally, solution times given in milliseconds [ms] are negligibly small in all steps of the thermal plant optimization stage (cf. Sect. 3.1). Most of the overall solution time is spent within the integration of energy storages, in particular for larger systems. Performance gains, that are achieved within this hydrothermal coordination stage (cf. Sect. 3.2), strongly depend on the characteristics of the problem instances. More precisely, for instances with high demand differences, improvements are increasing. For instances with primarily base load situations (e.g., due to a low volatility or a low feed-in of the renewable sources), the smoothing effect of energy storages are negligible and only small improvements could be reached. Furthermore, the demand shifting offers the overall best improvements. Further improvements within the last step are generated by avoiding an excessive spinning reserve.

To further assess the solution quality of the heuristic approach, we isolated its first stage (cf. Sect. 3.1) and compared the objective function values to results of procedures devised by Kazarlis et al. (1996), Morales-España et al. (2013), and Ongsakul and Petcharaks (2004). Hence, a feasible production schedule for thermal plants is determined. The computational results of the wildly used Kazarlis et al. (1996) test set (for a 24 h planning horizon without hydro storages) are given in Table 3. For the solver solution process, a gap of less than or equal to 1% is chosen as a stopp criterion. Columns 2 and 3 state the objective function values generated by our procedures, whereas “MIP-MOR” illustrates the results using the mixed-integer linear programming approach by Morales-España et al. (2013). Column “DPLR” displays the results for a Lagrange relaxation combined with a dynamic programming approach for the economic dispatch problem given by Ongsakul and Petcharaks (2004). Finally, column “GA” represents objective function values using the genetic algorithm presented by Kazarlis et al. (1996). Since “DPLR” and “GA” use squared production costs [cf. Eq. (1)], we also considered those costs in our procedures (“MIP” and “Heuristic”) as well as in our implementation of “MIP-MOR” (same settings as in “MIP”) to facilitate comparability. Please note that due to the quadratic objective, our mixed-integer programming model is named “MIP” (in contrast to the “MILP” model in Table 1). Line “avg. gap” represents the average gap between the objective function values obtained by the respective procedure and the best-known objective function values (within this paper). Overall, the models “MIP” and “MIP-MOR” give the best results in terms of average gap, followed by the two-stage heuristic, which also provides a significantly lower computation time. Please note that only “MIP”, “MIP-MOR”, and “Heuristic” are comparable with respect to CPU-times, since “DPLR” and “GA” are solved on different computers (Ongsakul and Petcharaks 2004 present solution times of 2–3 minutes for “DPLR” and “GA” vs. less than a second for our “Heuristic”). To sum up, the first three steps within the first stage (cf. Sect. 3) seem to provide a quite good basis for our two-stage heuristic approach solving the UCP–HT.

The numerical results obtained in Sect. 4 make the heuristic procedure highly suitable for solving real-world energy problems. The following case study is based on the characteristics of the German electricity market that comprises of nearly 300 large-scale power plants with about 91 GW of thermal power in 2015. Moreover, 126.4 GW of volatile renewable units, 6.5 GW of pumped storages, and a cumulated net demand of 550 TWh are used. Furthermore, in 2015 the average price for \(\hbox {CO}_2\) emissions was \(c^{{\mathrm{CO}_2}}:=7.94\) € per ton \(\hbox {CO}_2\) (since \(c^{{\mathrm{CO}_2}}\) is an average price, period t in \(c^{{\mathrm{CO}_2}}_t\) is eliminated). We choose a long-term planning horizon of one year. In order to extensively assess the capability of the proposed heuristic for real-world instances, a scaling factor \(\psi\) is introduced. Thereby, the total thermal capacity \(\sum P_i^{{\text {max}}}\) [GW], the yearly demand \(\sum D_t\) [TWh], as well as the renewable feed-in \(\sum {\rm wind}_t\) and \(\sum pv_t\) [TWh] are multiplied by \(\psi \in \{0.25, 0.50, 0.75, 1.00, 1.50, 2.00, 3.00, 5.00\}\). Based on the scaled values, the thermal plant portfolio is derived such that it represents a \(\psi\)-adjusted electricity system of Germany. The portfolio of hydro storages comprises only storages that participate on the wholesale market (here, 6.5 GW of generating power) and is scaled accordingly. Realistic hourly values for the demand and for renewable feed-ins are derived by the methodology in Wagner (2014) applying the calibration data from 2010 to 2015 (cf. ENTSO-E and German TSOs). The stochastic Ornstein–Uhlenbeck process of Wagner (2014) is used to generate three scenarios for the demand as well as three scenarios for wind and solar infeeds, respectively. Consequently, 27 possible combinations are considered, with the residual demand specified in each combination (see Definition 3). This might have some small impacts on the results compared to a detailed modeling of renewable sources, where, e.g., each wind farm is considered individually. However, these small differences seem to be negligible against the background of the underlying long-term planning horizon and the fact that according to Wagner (2014), the behavior of the modeled renewable feed-ins is quite realistic. For run-of-river and biomass provided electricity, a constant monthly profile given by the ENTSO-E is utilized.

Results of our two-stage heuristic are depicted in Table 4. As expected, instances with a low scaling factor \(\psi\) are solved quite fast, but also for the entire German electricity system (\(\psi =1\)), solutions can be generated in about 2.5 min. Moreover, a feasible hourly production schedule for a system with a scaling of \(\psi =5\) (with almost 1500 plants and in terms of the demand nearly comparable to the system of the EU-28) is received in less than half an hour. Within the test set with one scaling factor, only small solution time variations are observed. The related solution quality is represented by gap values that are determined using the best MILP solution found within a time limit of 48 h. Here, gap values are always below 1.5 %, which results again in quite high solution qualities. For higher scaling factors (\(\psi \ge 1.50\)) no feasible MILP-solutions can be achieved in 48 h due to the rapidly increasing model size. Therefore, the LP-relaxations of our MILP-model are used to assess the solution quality. Note that the resulting gap values are not as tight as the previous values and are hence written in parentheses. However, they indicate the maximal deviation to the optimum (all deviations are lower than 7 %). For \(\psi =5\), “n.a.” means that CPLEX cannot provide solutions within the prescribed time limit. Considering the results, it can be concluded that the two-stage heuristic procedure provides not only outstanding results for theoretical test instances, but is also excellently for comprehensive practical purposes.

Furthermore, the proposed heuristic approach can be applied in order to receive trade-off results between the minimization of emission costs and the minimization of production costs. In what follows, the weighted-sum method is used (cf. Sect. 2.2), where weighting factors for \(\hbox {CO}_2\) emissions are set according to the market price \(c^{{\mathrm{CO}_2}}\). Trade-offs are approximated by varying the weight \(c^{{\mathrm{CO}_2}}\) from zero emission costs to high costs (e.g., 200 €/t \(\hbox {CO}_2\)). Figure 7 illustrates the resulting trade-off curve for the German electricity market with raising market prices \(c^{{\mathrm{CO}_2}}\). Please note that the corresponding solution times and solution gaps are comparable to the results in Table 4 for \(\psi =1.00\).

It might be deduced from Fig. 7 that a shift from coal- to gas-fired plants (with less \(\hbox {CO}_2\) emissions) appears with increasing \(\hbox {CO}_2\) prices and thereby \(\hbox {CO}_2\) emissions are reduced. Therefore, the principle of the EU ETS can generally be used to control the management of \(\hbox {CO}_2\) emissions. Reductions in \(\hbox {CO}_2\) emissions are only achieved by accepting much higher production costs. In our case study, a reduction of nearly 15 % due to increase in \(c^{{\mathrm{CO}_2}}\) from 7.94 to 140 € per ton \(\hbox {CO}_2\) results in a rise in total production cost of 350 % (from ca. 17 to 60 billion €). All in all, the presented technique offers a possibility to evaluate the effectiveness of the EU ETS.