import math
from dataclasses import dataclass
from plot import draw_prices, draw_schedule
from report import report_schedule
@dataclass
class Period:
price: float
inflow: float
@dataclass
class Turbine:
efficiency: float
min_discharge: float
max_discharge: float
min_production: float
max_production: float
@dataclass
class Plant:
periods: list[Period]
turbines: list[Turbine]
min_volume: float = 5e6
max_volume: float = 30e6
initial_volume: float = 25e6
final_volume: float = 25e6
a_head: float = 1e-7
b_head: float = 50.0
a_tail_q: float = 0.005
a_tail_s: float = 0.001
b_tail: float = 30.0
@property
def num_periods(self):
return len(self.periods)
@property
def num_turbines(self):
return len(self.turbines)
@dataclass
class Schedule:
revenue: float
discharge: list[list[float]]
production: list[list[float]]
volume: list[float]
headwater: list[float]
tailwater: list[float]
net_head: list[float]Hydro Unit Commitment
Schedule the water discharge of several turbines sharing one reservoir to maximize the revenue from selling generated hydropower.
Introduction
Given a set of production units, the unit commitment problem consists in determining the status (on/off) of each unit at each period as well as the quantity of electricity to produce, in order to maximize the profit or satisfy demands while minimizing operational costs.
Here, we focus on hydropower generation.
The powerhouse contains a turbine and a generator. The water goes from the upstream reservoir to the downstream river through the penstock, passing by the powerhouse. The flow of water through the blades of a turbine generates electricity which is then transferred from the generator to its final destination through the long distance power lines. The water that passes through the penstock is used to generate power, but water could also be released from the reservoir directly to the downstream river. This water is said to be spilled, as it is not used for production, but rather to avoid an overflow of the reservoir.
Image source: https://commons.wikimedia.org/wiki/File:Hydroelectric_dam-es.svg
How much electricity the water yields depends on how far it falls before reaching the turbine. That drop is measured between two water levels, the headwater of the upstream reservoir and the tailwater of the downstream river. Their difference is the net head, the effective height of the water column driving the turbine. Both levels move as the plant operates, the reservoir dropping as water leaves it and the river rising as discharged and spilled water arrive, so the net head changes from one period to the next.
The quantity of electricity \(p_{j, t}\) produced by turbine \(j\) at period \(t\) is a nonlinear function of the net head \(h^\text{net}_{t}\) and the water discharge \(q_{j,t}\):
\[ p_{j,t} = \eta_j \cdot q_{j,t} \cdot h^\text{net}_{t} \]
where \(\eta_j\) is called the efficiency of turbine \(j\), a coefficient that also carries the density of water, gravity and the conversion to megawatts.
That product of two variables is what makes the problem nonlinear, and it is also what ties the turbines together. They draw on one reservoir, so they share one net head, and water one of them discharges lowers what the others can produce later.
Problem description
Here, we consider a problem composed of several turbines and one reservoir. The objective is to maximize the revenue from selling generated power.
Input:
\(H\) periods; for each period \(t = 1, \dots, H\)
- a price \(R_t\) for selling a unit of electricity
- an inflow \(\Omega_t\)
\(N\) turbines; for each turbine \(j = 1, \dots, N\):
- a minimum discharge \(Q^\text{min}_j\)
- a maximum discharge \(Q^\text{max}_j\)
- a minimum production \(P^\text{min}_j\)
- a maximum production \(P^\text{max}_j\)
- an efficiency \(\eta_j\)
a minimum volume \(V^\text{min}\) for the reservoir
a maximum volume \(V^\text{max}\) for the reservoir
an initial volume \(V^\text{init}\) for the reservoir
a minimum final volume \(V^\text{final}\) for the reservoir
a function \(F^\text{head}(v) = A^\text{head} v + B^\text{head}\) that returns the headwater depending on the volume in the reservoir
a function \(F^\text{tail}(q, s) = A^\text{tail}_q q + A^\text{tail}_s s + B^\text{tail}\) that returns the tailwater depending on the water discharge and the spilled water
Problem: find the quantity of water to send through each turbine at each period such that:
The volume in the reservoir always stays in \([V^\text{min}, V^\text{max}]\)
The initial volume is equal to \(V^\text{init}\)
The final volume is greater than \(V^\text{final}\)
If a turbine is used
- the water discharge in this turbine belongs to \([Q^\text{min}, Q^\text{max}]\); otherwise, it is null.
- the production of this turbine belongs to \([P^\text{min}, P^\text{max}]\); otherwise, it is null.
Objective: maximize the revenue
Mixed-integer nonlinear program
Variables:
- \(x_{j, t} \in \{ 0, 1 \}\), \(j = 1, \dots, N\), \(t = 1, \dots, H\): \(x_{j, t} = 1\) iff turbine \(j\) is on at period \(t\), otherwise \(0\).
- \(q_{j, t} \in [0, Q_j^\text{max}]\), \(j = 1, \dots, N\), \(t = 1, \dots, H\): water discharge in turbine \(j\) at period \(t\).
- \(q^\text{tot}_t \in \mathbb{R}^+\), \(t = 1, \dots, H\): total water discharge at period \(t\).
- \(s_t \in \mathbb{R}^+\), \(t = 1, \dots, H\): water spilled at period \(t\).
- \(p_{j, t} \in [0, P_j^\text{max}]\), \(j = 1, \dots, N\), \(t = 1, \dots, H\): production of turbine \(j\) at period \(t\)
- \(v_t \in [V^\text{min}, V^\text{max}]\), \(t = 1, \dots, H\): volume in the reservoir at period \(t\)
- \(h^\text{head}_t \in \mathbb{R}\), \(t = 1, \dots, H\): head water at period \(t\)
- \(h^\text{tail}_t \in \mathbb{R}\), \(t = 1, \dots, H\): tail water at period \(t\)
- \(h^\text{net}_t \in \mathbb{R}^+\), \(t = 1, \dots, H\): net head at period \(t\)
Objective: maximize the revenue
\[ \max \sum_{t = 1}^H \sum_{j = 1}^N R_t p_{j, t} \]
Constraints:
- Initial and final volume:
\[ v_1 = V^\text{init} \]
\[ v_H \ge V^\text{final} \]
- Water balance: volume at \(t\) = volume at \(t - 1\) + inflow at \(t\) - consumption at \(t\). A period is one hour and the flows are per second, hence the factor 3600.
\[ \forall t = 2, \dots, H \qquad v_t = v_{t - 1} + 3600 \cdot \Omega_t - 3600 \cdot q^\text{tot}_t - 3600 \cdot s_t \]
- Water discharge limits
\[ \forall j = 1, \dots, N \quad \forall t = 1, \dots, H \qquad q_{j, t} \ge Q_j^\text{min} x_{j, t} \]
\[ \forall j = 1, \dots, N \quad \forall t = 1, \dots, H \qquad q_{j, t} \le Q_j^\text{max} x_{j, t} \]
- Production limits
\[ \forall j = 1, \dots, N \quad \forall t = 1, \dots, H \qquad p_{j, t} \ge P_j^\text{min} x_{j, t} \]
\[ \forall j = 1, \dots, N \quad \forall t = 1, \dots, H \qquad p_{j, t} \le P_j^\text{max} x_{j, t} \]
Both sides are gated by \(x_{j, t}\), so an idle turbine is held at zero discharge and zero production, and a running one is kept between its bounds.
- Total water discharge
\[ \forall t = 1, \dots, H \qquad q_t^\text{tot} = \sum_{j = 1}^N q_{j, t} \]
- Headwater
\[ \forall t = 1, \dots, H \qquad h_t^\text{head} = A^\text{head} v_t + B^\text{head} \]
- Tailwater
\[ \forall t = 1, \dots, H \qquad h_t^\text{tail} = A^\text{tail}_q q^\text{tot}_t + A^\text{tail}_s s_t + B^\text{tail} \]
- Net head
\[ \forall t = 1, \dots, H \qquad h_t^\text{net} = h_t^\text{head} - h_t^\text{tail} \]
- Hydropower production function
\[ \forall j = 1, \dots, N \quad \forall t = 1, \dots, H \qquad p_{j, t} = \eta_j \cdot q_{j,t} \cdot h^\text{net}_{t} \]
The model has the following properties:
- Continuous and binary variables
- Quadratic structures
- Non-convex
- Therefore, it is a non-convex MIQCQP
Input data
A Period carries what the horizon offers at one hour, the price a unit of electricity sells for and the inflow arriving at the reservoir. A Turbine carries its efficiency and the bounds it has to respect while it runs. A Plant holds those two lists plus everything that belongs to the reservoir rather than to any one turbine, namely the volume it must stay within, where it starts and where it has to end, and the coefficients of the two level functions.
A Schedule carries the revenue it earns, the discharge and production of every turbine at every period, and the four series the reservoir follows, namely volume, headwater, tailwater and net head.
The plant is generated rather than read from a file. Ten turbines draw on one reservoir over 168 hourly periods, a week of operation. Prices follow a daily cycle with noise on top, and the inflows are drawn flat. Each language draws with its own generator, so the plant scheduled here is not the one the Julia page schedules, and the two schedules cannot be compared hour by hour.
import random
def generate_plant(num_periods, num_turbines):
draw = random.Random(num_periods * num_turbines)
turbines = []
for _ in range(num_turbines):
min_production = draw.uniform(0, 10)
max_production = min_production + draw.uniform(0, 40)
min_discharge = draw.triangular(0, 100, 10)
max_discharge = draw.triangular(min_discharge, 100, max(min_discharge, 90))
turbines.append(
Turbine(
draw.uniform(0.5, 0.9) * 1e-6 * 1000 * 9.81,
min_discharge,
max_discharge,
min_production,
max_production,
)
)
periods = []
for t in range(num_periods):
inflow = draw.uniform(10, 100) * num_turbines
cycle = 40 * (1 + math.cos(t / 24 * 2 * math.pi)) + 10
periods.append(Period(cycle + draw.uniform(-10, 10), inflow))
return Plant(periods, turbines)
plant = generate_plant(168, 10)Every figure is a stack of panels sharing one time axis, so a period reads straight down from one panel to the next. The discharge panel is a step area per turbine stacked into the total, since a turbine holds its discharge for the whole hour rather than sliding to the next value, and every other panel is a line.
Prices are the input the schedule reacts to, so they come first. The cycle is daily, and the noise on top is what keeps the schedule from being the same day repeated seven times.
draw_prices(plant)Model implementation
import knitromaximize_revenue(plant) builds the model, solves it with Knitro, and returns a Schedule. The only nonlinear part is the production function, a product of two variables, so add_constraint takes every line of the model as written. The turbine limits are constraints rather than variable bounds, because each side is gated by the on/off variable, so an idle turbine is pinned to zero.
Proving optimality on a nonconvex problem of this size takes far longer than reaching a good schedule, so the branch and bound stops at the first integer feasible point.
def maximize_revenue(
plant, *, mip_terminate=knitro.KN_MIP_TERMINATE_FEASIBLE, num_threads=1
):
prob = knitro.Problem()
n, h = plant.num_turbines, plant.num_periods
periods, turbines = plant.periods, plant.turbines
x = {
(j, t): prob.add_variable(vtype=knitro.KN_VARTYPE_BINARY)
for j in range(n)
for t in range(h)
}
q = {(j, t): prob.add_variable(lb=0) for j in range(n) for t in range(h)}
p = {(j, t): prob.add_variable(lb=0) for j in range(n) for t in range(h)}
qtot = [prob.add_variable(lb=0) for _ in range(h)]
s = [prob.add_variable(lb=0) for _ in range(h)]
v = [prob.add_variable(lb=plant.min_volume, ub=plant.max_volume) for _ in range(h)]
h_head = [prob.add_variable() for _ in range(h)]
h_tail = [prob.add_variable() for _ in range(h)]
h_net = [prob.add_variable(lb=0) for _ in range(h)]
prob.add_objective(
prob.nsum(periods[t].price * p[j, t] for j in range(n) for t in range(h)),
goal=knitro.KN_OBJGOAL_MAXIMIZE,
)
for t in range(1, h):
inflow = periods[t].inflow
prob.add_constraint(v[t] == v[t - 1] + 3600 * (inflow - qtot[t] - s[t]))
for t in range(h):
for j in range(n):
turbine = turbines[j]
prob.add_constraint(p[j, t] >= turbine.min_production * x[j, t])
prob.add_constraint(p[j, t] <= turbine.max_production * x[j, t])
prob.add_constraint(q[j, t] >= turbine.min_discharge * x[j, t])
prob.add_constraint(q[j, t] <= turbine.max_discharge * x[j, t])
for t in range(h):
prob.add_constraint(qtot[t] == prob.nsum(q[j, t] for j in range(n)))
prob.add_constraint(h_head[t] == plant.a_head * v[t] + plant.b_head)
tailwater = plant.a_tail_q * qtot[t] + plant.a_tail_s * s[t] + plant.b_tail
prob.add_constraint(h_tail[t] == tailwater)
prob.add_constraint(h_net[t] == h_head[t] - h_tail[t])
for t in range(h):
for j in range(n):
prob.add_constraint(p[j, t] == turbines[j].efficiency * q[j, t] * h_net[t])
prob.add_constraint(v[0] == plant.initial_volume)
prob.add_constraint(v[h - 1] >= plant.final_volume)
prob.add_constraint(s[0] == 0)
for j in range(n):
prob.add_constraint(q[j, 0] == 0)
prob.set_param(knitro.KN_PARAM_MIP_TERMINATE, mip_terminate)
prob.set_param(knitro.KN_PARAM_NUMTHREADS, num_threads)
prob.solve()
revenue = prob.get_attr(knitro.KN_ATTR_OBJ_VALUE)
return Schedule(
revenue,
[[q[j, t].value for t in range(h)] for j in range(n)],
[[p[j, t].value for t in range(h)] for j in range(n)],
[v[t].value for t in range(h)],
[h_head[t].value for t in range(h)],
[h_tail[t].value for t in range(h)],
[h_net[t].value for t in range(h)],
)schedule = maximize_revenue(plant)=======================================
Commercial License
Artelys Knitro 16.0.0
=======================================
Knitro changing mip_method from AUTO to 1.
No start point provided -- Knitro computing one.
Knitro presolve eliminated 537 variables (9%) and 568 constraints (6%) in 0.02s.
concurrent_evals 0
feastol 1e-06
feastol_abs 1e-06
mip_terminate 1
numthreads 1
opttol 1e-06
opttol_abs 0.001
Knitro changing mip_root_nlpalg from AUTO to 1.
Knitro changing mip_node_nlpalg from AUTO to 1.
Knitro changing mip_branchrule from AUTO to 2.
Knitro changing mip_selectrule from AUTO to 2.
Knitro changing mip_mir from AUTO to 2.
Knitro changing mip_clique from AUTO to 0.
Knitro changing mip_zerohalf from AUTO to 0.
Knitro changing mip_liftproject from AUTO to 0.
Knitro changing mip_knapsack from AUTO to 2.
Knitro changing mip_gomory from AUTO to 0.
Knitro changing mip_cut_flowcover from AUTO to 2.
Knitro changing mip_cut_probing from AUTO to 1.
Knitro changing mip_rounding from AUTO to 3.
Knitro changing mip_heuristic_strategy from AUTO to 1.
Knitro changing mip_heuristic_feaspump from AUTO to 1.
Knitro changing mip_heuristic_misqp from AUTO to 0.
Knitro changing mip_heuristic_mpec from AUTO to 1.
Knitro changing mip_heuristic_diving from AUTO to 1926.
Knitro changing mip_heuristic_fixpropagate from AUTO to 62.
Knitro changing mip_heuristic_lns from AUTO to 0.
Knitro changing mip_heuristic_localsearch from AUTO to 1.
Knitro changing mip_pseudoinit from AUTO to 1.
WARNING: Problem appears to have nonlinear equalities and be non-convex.
The Knitro mixed integer solver is designed for convex problems.
For non-convex problems it is only a heuristic, and the reported
bounds and optimality claims cannot be verified.
Problem Characteristics | Presolved
-----------------------
Problem type: MIQCQP
Objective: maximize / linear
Number of variables: 6048 | 5511
bounds: lower upper range | lower upper range
3864 0 1848 | 3674 0 1836
free fixed | free fixed
336 0 | 1 0
cont. binary integer | cont. binary integer
4368 1680 0 | 3841 1670 0
Number of expressions: 29451 | 0
Number of constraints: 9252 | 8684
eq. ineq. range | eq. ineq. range
linear: 851 6721 0 | 334 6680 0
quadratic: 1680 0 0 | 1670 0 0
Number of nonzeros:
objective Jacobian Hessian | objective Jacobian Hessian
linear: 1680 18993 | 1670 17867
quadratic: 0 3360 1680 | 0 3340 1670
total: 1680 22353 1680 | 1670 21207 1670
Knitro using Branch and Bound method with 1 thread.
Initial points
--------------
No initial point provided for the root node relaxation.
No primal point provided for the MIP.
Coefficient range:
linear objective: [3e+00, 1e+02] | [3e+00, 1e+02]
linear constraints: [1e-07, 4e+03] | [1e-06, 9e+01]
quadratic objective: [0e+00, 0e+00] | [0e+00, 0e+00]
quadratic constraints: [5e-03, 9e-03] | [5e-03, 9e-03]
variable bounds: [1e+00, 3e+07] | [1e+00, 3e+07]
constraint bounds: [2e+07, 2e+07] | [2e+01, 8e+03]
Root node relaxation
--------------------
Iter Objective Feasibility Optimality Time
error error (secs)
---- --------- ----------- ---------- ------
0 248715. 827.453 97.4272 0.136
1 250017. 827.449 12.5865 0.169
2 253563. 827.436 12.5865 0.190
3 262815. 827.397 12.5865 0.210
4 292099. 827.212 14.3910 0.229
5 339894. 826.728 18.8064 0.245
6 418057. 824.853 31.5240 0.259
7 518313. 815.465 59.1240 0.271
8 589290. 788.667 226.099 0.284
9 604807. 412.907 1044.66 0.303
10 613056. 187.365 360.334 0.320
11 616015. 76.2603 168.927 0.341
12 617371. 47.8895 113.249 0.359
13 609548. 20.4970 207.772 0.384
14 577063. 1.21572 477.064 0.407
15 606190. 4.35848e-02 230.853 0.430
16 664813. 6.04176e-02 75.7822 0.448
17 686879. 0.289333 41.6802 0.464
18 715959. 5.78102e-02 4680.22 0.487
19 725402. 2.26190e-02 340.155 0.506
20 733647. 3.19979e-02 3.79774 0.527
30 739831. 2.67964e-06 1.64408e-02 0.759
40 739813. 8.08016e-04 4.08088e+08 1.861
50 739779. 6.43370e-05 86380.1 2.019
60 739601. 1.31404e-05 98.2572 2.193
70 721758. 4.81841e-05 97.9100 2.832
80 735524. 3.56255e-04 1647.21 3.147
90 735764. 5.21217e-02 681688. 3.337
100 734269. 7.46701e-02 51840.4 3.617
110 733881. 7.94475e-02 51840.4 3.955
120 733626. 2.53819e-02 51840.4 4.259
130 733339. 1.36249e-02 51840.4 4.576
140 733012. 6.94363e-03 51840.4 4.859
150 732791. 1.68331e-03 51840.4 5.198
160 732501. 1.07414e-03 51840.4 5.562
170 732401. 1.55446e-03 51705.4 6.027
180 733549. 6.40029e-03 28099.3 6.452
190 734537. 9.06848e-03 28099.3 6.696
200 735658. 1.37038e-02 28099.3 6.902
Tree search
-----------
Nodes Best solution Best bound Gap Time
Expl | Unexpl value value (secs)
--------------- ------------- ---------- --- ------
1 2 739673. FCRD inf 9.246
EXIT: Terminating at first integer feasible point.
HINT: The problem may be a non-convex mixed-integer problem. Set
mip_multistart=1 to enable a mixed-integer multistart heuristic,
which may improve the chances of finding the global solution.
Final Statistics for MIP
------------------------
Final objective value = 7.39673482859437354e+05
Final bound value = +inf
Final optimality gap (abs / rel) = inf / inf
# of root cutting plane rounds = 1
# of restarts = 0
# of nodes processed = 1 (7.467s)
# of strong branching evaluations = 0 (0.000s)
# of function evaluations = 0 (0.000s)
# of gradient evaluations = 0 (0.000s)
# of hessian evaluations = 0 (0.000s)
# of hessian-vector evaluations = 0
# of subproblems processed = 2 (9.142s)
Total program time (secs) = 9.24680 (9.255 CPU time)
Time spent in evaluations (secs) = 0.00000
Cuts statistics (gen / add)
---------------------------
Knapsack cuts = 0 / 0
Mixed-integer rounding cuts = 0 / 0
Flow-cover cuts = 0 / 0
Probing cuts = 0 / 0
Heuristics statistics (calls / successes / time)
------------------------------------------------
Feasibility pump = 0 / 0 / 0.000s
Rounding heuristic = 1 / 1 / 1.684s
MPEC heuristic = 0 / 0 / 0.000s
Local search heuristic = 0 / 0 / 0.000s
===========================================================================
Show the full outputHide the full output
Output visualization
What the schedule earns, and which turbines earn it:
report_schedule(plant, schedule)Revenue 739,673 over 168 hours
turbine hours on production revenue share
(MWh)
-----------------------------------------------
1 147 1,377 76,320 10.3%
2 157 2,187 115,938 15.7%
3 129 1,097 66,678 9.0%
4 0 0 0 0.0%
5 136 1,686 98,531 13.3%
6 144 1,686 94,640 12.8%
7 118 1,121 71,424 9.7%
8 155 1,971 104,212 14.1%
9 147 2,027 111,929 15.1%
10 0 0 0 0.0%
Reservoir 25.0M at the start, 25.0M at the end, 20.5M at its lowest
Net head 18.7m to 22.9m, so the same water is worth 1.22 times more at the top than at the bottomA turbine whose minimum production is more than its maximum discharge can reach at the heads the reservoir offers can never be switched on at all, so the model leaves it off for the whole week and it stands at zero hours in the table.
The schedule reads in four panels. They show the discharge of every turbine stacked into the total, the volume left in the reservoir, the production summed over the turbines, and the three water levels. The turbines run through the dear hours and idle through the cheap ones, refilling the reservoir while the water is worth less than it will be later. The levels follow. The headwater falls with the volume, the tailwater rises with what is discharged and spilled, and the net head, the gap between them, is what every unit of water is worth.
draw_schedule(plant, schedule)