Contents

1 Problem statement and data

We consider a dam manager intending to maximize the intertemporal payoff obtained by selling power produced by water releases, when the water inflows (rain, snowmelt, outflows from upper dams) are random and the energy prices are supposed to be deterministic.

1.1 Dam dynamics

We model the dynamics of the water volume in a dam by a function f defined as follows¹

where

• time t ∈ 𝕋 = {t_i,t_i + 1,…,t_f} is discrete (months in this case), and t denotes the beginning of the period [t,t + 1[; we call t_i the initial time and t_f the horizon;
• x(t) volume of water in the dam at the beginning of period [t,t + 1[, belonging to a finite set 𝕏 ⊂ [x,x], where x (resp. x) is the minimum (resp. maximum) dam volume;
• u(t) turbinated outflow volume during [t,t + 1[, decided at the beginning of the time period [t,t + 1[, and belonging to a finite set 𝕌 ⊂ [u,u], where u (resp. u) is the minimum (resp. maximum) volume which can be turbinated by time unit; we assume that the minimum value u is equal to zero:

  (2)

• w(t) inflow water volume (rain, snowmelt, etc.) during the time period [t− 1,t[, belonging to the finite set 𝕎(t) ⊂ [w(t),w(t)], where w(t) (resp. w(t)) is the minimum (resp. maximum) possible inflow at time t; we assume that w(t) ≥ 0 for all t; the dependence of the sets 𝕎(t) upon time t allows to take into account seasonal effects (e.g. more rain in autumn).

The dam manager is supposed to make a decision at each t ∈ 𝕋, here turbinating u(t) at the beginning of the period [t,t + 1[, before knowing the water inflow w(t + 1): such a setup is called decision-hazard setting. We add the following constraint on the turbinated water:

(3)

Constraint (3) ensures u(t) is feasible, that is, such that the dam volume remains greater or equal to its minimum value x (remember that any inflow w(t) is nonnegative).

1.2 Criterion: intertemporal payoff

The manager problem is one of payoff maximization. At each time t, the turbinated water u(t) produces electricity which is sold on markets at a price p(t). The associated financial income is modeled by a linear function L(t,u) = p(t)u, leading to the instantaneous payoff

(4)

Moreover, the volume x(t_f) remaining in the dam at the horizon t_f is valued (this is the so-called final value of water) using a quadratic function K, leading to the final payoff

(5)

Here, α is a coefficient and x_ref is a given reference volume for the dam at horizon t_f. The final payoff is negative if and only if x(t_f) < x_ref. From t_i to t_f, the payoffs sum up to

(6)

The sequence of prices p(t_i),…,p(t_f − 1) is supposed to be deterministic, hence known in advance at initial time t_i where the optimization problem is posed.

1.3 Probabilistic model for water inflows

A water inflow scenario is a sequence of inflows in the dam from time t_i up to t_f − 1

(7)

We model water inflow scenarios using a sequence of random variables with a known joint probability distribution ℙ such that

• the random variables w(t_i),…,w(t_f − 1) are independent,
• each random variable w(t) follows a uniform probability distribution² on the finite set 𝕎(t):

  (8)

Notice that the random variables w(t_i),…,w(t_f − 1) are independent, but that they are not identically distributed. Independence is a key assumption to obtain the dynamic programming equation (18) with state x.

1.4 Numerical data

Time. We consider a montly management (the interval [t,t + 1[ represents one month) over one year, so that

(9)

State and control. Concerning the dam volume and the turbinated water, we consider the following bounds:

(10)

We assume that the dam volume is discretized using a stepsize δx = 2 hm³, whereas the stepsize used for discretizing the control is δu = 8 hm³ (multiple of δx). Accordingly, the sets containing the possible values of the state and the control are

The water volume in the dam at time t_i is known and equal to x_i = 40 hm³, and the reference volume used to define the final payoff K in (5) is x_ref = 40 hm³.

Prices scenario. The price scenario  p(t_i),…,p(t_f − 1), known in advance, is shown in Figure 1.

---

---

Water inflow scenarios. At each time t, the range 𝕎(t) of the water inflow w(t) is obtained by discretizing an interval centered around a given mean value (see Figure 2). Each interval is discretized using a stepsize δw = 2 hm³ (multiple of δx). Consider for example time t = 1: the minimum (resp. maximum) inflow value is w(1) = 12 hm³ (resp. w(1) = 28 hm³), so that the finite support 𝕎(1) of the (uniform) probability distribution associated with the random variable w(1) is

the probability weight of each element w ∈ 𝕎(1) being 1∕9.

Knowing the probability distribution, it is easy to draw water inflow scenarios since we assumed that the random variables w(t) are independent.

---

---

Scilab code. The following Scilab code contains the data and macros corresponding to the numerical example described in §1.4.

2 Simulation and evaluation of given policies

In order to simulate (and then optimize) the dam behavior, we need to have the Scilab macros computing the dynamics (1) and the payoffs (4) and (5).

2.1 Evaluation of a turbining policy

An admissible policy γ : 𝕋 × 𝕏 → 𝕌 assigns a turbinated water amount u = γ(t,x) ∈ 𝕌 to any time t ∈ 𝕋 and to any dam volume x ∈ 𝕏, while respecting constraint (3), that ias,

Hence, by (2), we obtain that

Given an admissible policy γ and given an inflow scenario

(11)

we are able to build a dam volume trajectory

(12)

and a turbinated water trajectory

(13)

produced by the “closed-loop” dynamics initialized at the initial time t_i by

We also obtain the payoff associated to the inflow scenario w(⋅)

(15)

where x(⋅) and u(⋅) are given by (14c). The expected payoff associated with the policy γ is

(16)

where the expectation 𝔼 is taken with respect to the product probability ℙ, whose marginals are given by (8). The true expected value (16) is difficult to compute,³ and we evaluate it by the Monte Carlo method using N_s inflow scenarios w¹(⋅),…,w^N_s(⋅):

(17)

By the law of large numbers, the mean payoff (17) is a “good” approximation of the expected payoff(16) if the number of scenarios is “large enough”.

We propose the following Scilab code in order to evaluate the mean payoff associated to a policy given by the Scilab macro policy.

2.2 Simulation of a given policy

In order to test the Scilab macro simulation given above, consider the following code.

We now want to design new policies, writing Scilab macros following the model given by the macro below:

3 Resolution by the stochastic dynamic programming approach

In order to compute the optimal turbinated water policy, we provide the stochastic dynamic programming (or Bellman) equation associated with the problem of maximizing the expected payoff (16), as well as the corresponding Scilab code.

3.1 Stochastic dynamic programming equation

Since the water inflows w(t) are supposed to be independent random variables, Dynamic Programming applies and the equation associated with the problem of maximizing the expected payoff  (16) writes

for t varying from t_f − 1 to t_i. The expectation 𝔼 is taken with respect to the marginal probability distribution ℙ_w(t+1) given by (8), that is,

A difficulty when programming the Bellman equation is that we need to manipulate both the values (t,x) of the time and of the state, and the associated indices (t,i) in the table storing the values of the function V (t,x). In our application, the treatment of index t is obvious because t ∈ 𝕋 = {t_i,t_i + 1,…,t_f}, but we need a tool performing the conversion for the volume. The following Scilab macro state_index returns the index i associated to an element x in the finite set 𝕏 containing the possible values of the dam volume.

3.2 Scilab code for the dynamic programming equation

We provide the following code in order to compute the Bellman function.

3.3 Simulation of the optimal policy

Consider the following Scilab macro.

Here we assume that the values of optimal control have not be stored in the table Ubell, so that the only outcome of the macro sdp_solve is the table Vbell (Bellman values).

4 Possible extensions

In this section, we propose several developments and extensions for the dam management problem.

4.1 Hazard-decision framework

In the hazard-decision framework, the dam manager is supposed to make a decision, here turbining u(t) at the beginning of the period [t,t + 1[, knowing the water inflow w(t + 1) in advance.

The Bellman equation is now

Once the value function V (t,x) evaluated and stored for all time t and state x, the optimal control at time t starting from state x and observing the water inflow w is the arg max of

(21)

which leads to an optimal policy depending on the triplet (t,x,w).

4.2 Computation of a fair final value of water

Till now, the gain in leaving water in the dam at the end of the time horizon was arbitrarily fixed. Now, we provide a procedure to estimate a “ fair final value of water”, that is, a function xK(x) as in (5).

The intuition behind the procedure is that the final value of water is the value that a manager would put on the dam, were he to run it from the date t_f + 1 to infinity. The final value of water is the solution of an infinite horizon maximization problem. The procedure below mimicks an algorithm to find a fixed point by iterations.

First, we start with a zero final payoff function and obtain, by backward induction, the Bellman function at initial time t_i. Up to a translation — to account for the fact that an empty dam has zero final value of water — we identify the function with the new final value of water . Proceeding along, we expect that this loop converges towards a function xK^(∞)(x) which is a good candidate for the final value of water.

We design a loop for n = 1,…,N, starting with a zero final value of water

then solving the backward Bellman equation

and then closing the loop by choosing the new final value of water

(22)

as the Bellman function at the initial time t_i after a shift, so that K⁽ⁿ⁺¹⁾(x) = 0.

4.3 Robustness with respect to water inflow scenarios

An interesting point, which occurs in practical problems, is the following. In the case where the random variables w(t_i),…,w(t_f − 1) are correlated in time, it is always possible to obtain the marginal probability laws ℙ_w(t) of each w(t) and then compute the Bellman function as in §3. We thus obtain a feedback policy that would be optimal if the random inflow variables were uncorrelated. The loss of optimality may be evaluated by simulating the feedback policy along scenarios drawn using the “true” probability law ℙ of the process w(t_i),…,w(t_f − 1).

References