1 Introduction

For long-term planning of hydroelectric resources, decisions often need to be made under random water supply (reservoir inflows) presented as stochastic events (Loucks et al. 1981). For a hydropower system, the economic loss subjected to uncertain water supply against targeted electricity loads often need to be quantified. Multistage stochastic programming (MSP) is an effective technique to address this kind of uncertainty in hydropower planning (Pereira and Pinto 1991; Kenfack et al. 2001).

When a MSP model is used in long-term resources planning, a recourse feature that is generated by decision making under random uncertainty often needs to be described in the modeling approach (Loucks et al. 1981). In this case, a recourse-based stochastic programming model should be used, in which actions are often taken to rectify their prior decisions that are made before random events are known in order to optimize the objective. For a long-term hydroelectric resource planning problem, sequential decisions are often made in accordance with time, thus a recourse-based MSP can be developed in order to solve such a multistage decision problem.

In addition to uncertainty in inflows, other formats of uncertainty also exist in hydroelectric resource planning (McKay and Allsopp 1981; Linder et al. 1987). For example, it is often unreliable to obtain the probability density function (PDFs) of a random event with probability fit when inflow data are not long enough. However, such uncertain data are relatively easy to be expressed as interval numbers. In a hydroelectric planning problem, it is more direct to specify the system’s cost and benefit coefficients within an interval range.

Previously, many interval programming models have been developed to reflect the interval uncertainty (Ishibuchi and Tanaka 1989; Słowñski and Teghem 1990; Nakahara et al. 1992; Tong 1994; Sengupta et al. 2001). In particular, studies were reported incorporating interval programming into stochastic programming with recourse (Huang and Loucks 2000; Maqsood et al. 2005). An interval stochastic programming can in large reduce the computational load of a conventional stochastic programming when uncertain data are only expressed as PDFs. Thus, there is a need to couple the interval programming with recourse-based multistage stochastic programming for optimization modeling of long-term hydroelectric resources planning.

This study aims to develop a recourse-based multistage interval-stochastic programming for long-term hydroelectric resource planning, reflecting recourse features associated with random inflows and interval uncertainty in the system. The proposed model improves upon traditional MSP, allowing different levels of uncertain information to be presented within the modeling formulation. A solution method of the proposed model is also described. The model proposed is demonstrated with a hydroelectric planning problem.

2 The model and solution method

2.1 Interval linear programming

An interval number can be expressed as a  ± = [a −, a +] (a + ≥ a −), where a − is a number representing the low limit of the interval number, and a + is a number representing the upper limit (Alefeld and Herzberger 1983). For a linear programming (LP) with interval parameters in both model constraints and objective function, Tong (1994) suggests that an interval linear programming can be written as:

$$ \hbox{Min}\,f^{\pm} = {\sum\limits_{j = 1}^n} c_{j}^{\pm} x_{j} = {\sum\limits_{j = 1}^n} [c_{j}^{-}, c_{j}^{+}]x_{j} $$
(1a)
$$ \hbox{s.t}.\, {\sum\limits_{j = 1}^n} \left[a_{ij}^{-}, a_{ij}^{+}\right]x_{j} \geq \left[b_{i}^{-}, b_{j}^{+}\right], \forall i $$
(1b)
$$ x_{j} \geq 0 $$
(1c)

Here, \(a^{\pm} \in {\left\{{\Re}^{\pm} \right\}}^{m \times n},\;b^{\pm} \in {\left\{{\Re}^{\pm} \right\}}^{1 \times m},\) and \(c^{\pm} \in {\left\{{\Re}^{\pm} \right\}}^{n \times 1},\) where ℜ± is the set of all interval numbers; and i = 1, ..., m.

When variables in model (1) expressed as interval numbers are considered to non-negativity, the best and worst optimum can be obtained, with pre-defined most- and least-favorable sub-models. Suppose the best and worst optimum of model (1) as x′1, x′2, ..., x′ n , f + and x′′1, x′′2, ..., x′′2, f −, respectively. Then, the optimal solutions of model (1) can be expressed as:

$$ \left. \begin{aligned} f_{\rm opt}^{\pm} &= \left[f_{\rm opt}^{-}, f_{\rm opt}^{+}\right] \\ x_{j\,opt} &= (\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{x}_{j}, {\bar{x}}_{j}) \\ \end{aligned} \right\},\quad \forall j $$
(2)

Here, both \({\bar{x}}_{j}\) and \(\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{x}_{j}\) are not belonged to the interval set ℜ± .

2.2 Multistage interval-stochastic programming with recourse

For hydroelectric resource planning, the random water supply (inflow) often needs to be statistically analyzed in order to measure the long-term profit of a proposed plant. Meanwhile, economic suffers subjected to insufficient inflow against targeted electricity loads need to be reflected in such an analysis (Karamouz and Houck 1987). A MSP with recourse can be defined with its objective stated to maximize the expected value of the plant’s long-term net benefit (Robinson 1997). Due to the seasonal variations in inflow and load conditions, the problem under consideration can be given by:

$$ \hbox{Max}\,f = f_{1} (x_{1}) = a_{1} x_{1} + E_{{\tilde{q}}_{1}} \left[ - \max b_{1} {\tilde{y}}_{1} + \sigma_{2} (x_{2}, {\tilde{v}}_{1})\right] $$
(3a)
$$ \hbox{s.t}.\ 0 \leq x_{1} \leq x^{0}_{1} $$
$$ 0 \leq x_{1} - {\tilde{y}}_{1} \leq {\tilde{q}}_{1} + v_{0} $$
$$ {\tilde{v}}_{1} = \min \{v, {\tilde{q}}_{1} + v_{0} - x_{1} + {\tilde{y}}_{1} \} $$
$$ {\tilde{y}}_{1} \geq 0 $$

and for t = 2, ..., T,

$$ \sigma_{t} (x_{t}^{{\tilde{v}}_{t - 1}}, {\tilde{v}}_{t - 1}) = \max \,f_{t} (x_{t}^{{\tilde{v}}_{t - 1}}, {\tilde{v}}_{t - 1}) $$
(3b)
$$ \hbox{s.t}.\ 0 \leq x_{t}^{{\tilde{v}}_{t - 1}} \leq x_{t}^{o} $$
$$ 0 \leq x_{t}^{{\tilde{v}}_{t - 1}} -{\tilde{y}}_{t} \leq {\tilde{q}}_{t} + {\tilde{v}}_{t - 1} $$
$$ {\tilde{v}}_{t} = \min \{v, {\tilde{q}}_{t} + {\tilde{v}}_{t - 1} - x_{t}^{{\tilde{v}}_{t - 1}} + {\tilde{y}}_{t} \} $$
$$ {\tilde{y}}_{t} \geq 0, \,\hbox{a.s}., $$

where

$$ f_{t} (x_{t}) = a_{t} x_{t}^{{\tilde{v}}_{t - 1}} + E_{{\tilde{q}}_{t}} [ - \max b_{t} {\tilde{y}}_{t} + \sigma_{t + 1} (x_{t + 1}^{{\tilde{v}}_{t}}, {\tilde{v}}_{t})] $$
(3c)

and \(\sigma_{T + 1} (x_{T + 1}^{{\tilde{v}}_{t}}, \cdot ) = 0.\) Here, f is the expected value of long-term net-system benefit of the plant; a t is economic benefit of electricity generated per volume water in stage t; b t is economic loss per volume water shortage for electricity generation in stage \(t (b_{t} \geq a_{t});\;x_{t}^{{\tilde{v}}_{t - 1}}\) is target water release with respect to predicted electricity load in stage t, which depends on the storage from its previous stage; x 0 t is maximum electricity load measured with water volume in stage t; \({\tilde{y}}_{t}\) is water deficiency when target water release \(x_{t}^{{\tilde{v}}_{t - 1}}\) is not met under random inflow \({\tilde{q}}_{t}; {\tilde{v}}_{t}\) is effective reservoir storage in month t, which is a forward transition variable; v 0 is the initial reservoir storage in stage 1; v is maximum storage capacity available for electricity generation; T is total numbers of planning stages; and \(E_{{\tilde{\xi }}} [ \cdot ]\) represents the mathematical expectation with respect to the random variable \({\tilde{\xi}}.\)

Though model (3) reflects randomness in water supply, it cannot incorporate other uncertain data expressed as interval numbers. For instance, the coefficients a t and b t in model (3) are often presented as interval values. In this case, model (3) can be transformed into an interval model as:

$$ \hbox{Max}\,f^{\pm} = f_{1}^{\pm} (x_{1}) = ax_{1}^{\pm} x_{1} + E_{\tilde{q}^{\pm}_{1}} \left[- \max b_{1}^{\pm} {\tilde{y}}_{1} + \sigma_{2}^{\pm} (x_{2}, {\tilde{v}}_{1})\right] $$
(4a)
$$ \hbox{s.t}.\ 0 \leq x_{1} \leq x_{1}^{0} $$
$$ 0 \leq x_{1} - {\tilde{y}}_{1} \leq \tilde{q}_{1}^{\pm} + v_{0} $$
$$ {\tilde{v}}_{1} = \min \{v, {\tilde{q}}_{1}^{\pm} + v_{0} - x_{1} + {\tilde{y}}_{1} \} $$
$$ {\tilde{y}}_{1} \geq 0 $$

and for t = 2, ..., T,

$$ \sigma_{t}^{\pm} (x_{t}^{{\tilde{v}}_{t - 1}}, {\tilde{v}}_{t - 1}) = \max \,f_{t}^{\pm} (x_{t}^{{\tilde{v}}_{t - 1}}, {\tilde{v}}_{t - 1}) $$
(4b)
$$ \begin{aligned} \, & \hbox{s.t}.\ 0 \leq x_{t}^{{\tilde{v}}_{t - 1}} \leq x_{t}^{o} \\ \,& 0 \leq x_{t} - {\tilde{y}}_{t} \leq {\tilde{q}}_{t}^{\pm} + {\tilde{v}}_{t - 1} \\ \, & {\tilde{v}}_{t} = \min \{v, {\tilde{q}}_{t}^{\pm}+ {\tilde{v}}_{t - 1} - x_{t}^{{\tilde{v}}_{t - 1}} + {\tilde{y}}_{t} \} \\ \, & {\tilde{y}}_{t} \geq 0,\, \hbox{a.s}.,\\ \end{aligned} $$

where

$$ f_{t}^{\pm} (x_{t}^{{\tilde{v}}_{t - 1}}) = a_{t}^{\pm} x_{t}^{{\tilde{v}}_{t - 1}} + E_{{\tilde{q}}_{t}^{\pm}} \left[ - \max b_{t}^{\pm} {\tilde{y}}_{t} + \sigma_{t + 1}^{\pm} (x_{t + 1}^{{\tilde{v}}_{t}}, {\tilde{v}}_{t})\right] $$
(4c)

and \(\sigma_{T + 1}^{\pm}\,(x_{T + 1}^{{\tilde{v}}_{t}}, \cdot) = 0.\) Here, \(a_{t}^{\pm},\;b_{t}^{\pm},\;{\tilde{q}}_{t}^{\pm},\;f_{t}^{\pm},\) and f ± are interval numbers in the interval set \(\Re ^ \pm \). Inflow variable \({\tilde{q}}_{t}^{\pm}\) is also expressed as an interval number because a confidence level is allowed when fitting the PDF of \({\tilde{q}}_{t}^{\pm}.\) Model (4) is a recourse-based multistage interval-stochastic programming and its solution is based on that of model (3).

2.3 Solution of the recourse-based MSP

Model (3) has numeric solutions only when the discretization values of \({\tilde{q}}_{t}\) are known (Birge and Louveaux 1997). In planning stage t, when random variable \({\tilde{q}}_{t}\) takes a discretization value \(q_{t}^{k_{t}}\) under probability \(p_{t}^{k_{t}} (k_{t} = 1, \ldots,K_{t}),\) model (3) can be turned into a linear programming as follows (Birge and Louveaux 1997):

$$ \hbox{Max}\,f = f_{1} (x_{1}) = a_{1} x_{1} + {\sum\limits_{k_{1} = 1}^{K_{1}}} p_{1}^{k_{1}} \{- b_{1} y_{1}^{k_{1}} + \sigma_{2} (x_{2}^{k_{1}}, v_{1}^{k_{1}})\} $$
(5a)
$$ \begin{aligned} \, & \hbox{s.t}. \ 0 \leq x_{1} \leq x_{1}^{0} \\ \, & 0 \leq x_{1} - y_{1}^{k_{1}} \leq q_{1}^{k_{1}} + v_{0}\\ \, & v_{1}^{k_{1}} = \min \{v,q_{1}^{k_{1}} + v_{0} - x_{1} + y_{1}^{k_{1}} \} \\ \, & y_{1}^{k_{1}} \geq 0 \\ \end{aligned} $$

and for t = 2, ..., T,

$$ \sigma_{t} (x_{t}^{k_{1},\ldots,k_{t - 1}}, v_{t - 1}^{k_{1},\ldots,k_{t - 1}}) = \max \,f_{t} (x_{t}^{k_{1},\ldots,k_{t - 1}}, v_{t - 1}^{k_{1},\ldots,k_{t - 1}}) $$
(5b)
$$ \hbox{s.t}.\ 0 \leq x_{t}^{k_{1},\ldots,k_{t - 1}} \leq x_{t}^{0} $$
$$ 0 \leq x_{t}^{k_{1},\ldots,k_{t - 1}} - y_{t}^{k_{1},\ldots,k_{t}} \leq q_{t}^{k_{t}} + v_{t - 1}^{k_{1},\ldots,k_{t - 1}} $$
$$ v_{t}^{k_{1},\ldots,k_{t}} = \min \{v,q_{t}^{k_{t}} + v_{t - 1}^{k_{1},\ldots,k_{t - 1}} - x_{t} + y_{t}^{k_{1},\ldots,k_{t}} \} $$
$$ 0 \leq y_{t}^{k_{1},\ldots,k_{t}} $$

where

$$ f_{t} (x_{t}^{k_{1},\ldots,k_{t - 1}}) = a_{t} x_{t}^{k_{1},\ldots,k_{t - 1}} + {\sum\limits_{k_{t} = 1}^{K_{t}}} p_{t}^{k_{t}} \{- b_{t} y_{t}^{k_{1},\ldots,k_{t}} + \sigma_{t + 1} (x^{k_{1},\ldots,k_{t}}_{t + 1}, v_{t}^{k_{1},\ldots,k_{t}})\} $$
(5c)

and \(\sigma_{T + 1} (x_{T + 1}^{k_{1},\ldots,k_{t}}, \cdot) = 0.\) Here, constraints are written out explicitly for each possible realization of the data process indexed by k t  = 1, ..., K t at each time period t = 2, ..., T. Reformulate model (5), we have:

$$ \hbox{Max}\,f = F_{1} + F_{2} + \cdots + F_{t} + \cdots $$
(6a)

where

$$ F_{1} = a_{1} x_{1} - {\sum\limits_{k_{1} = 1}^{K_{1}}} b_{1} p_{1}^{k_{1}} y_{1}^{k_{1}} $$
(6b)
$$ F_{t} = {\sum\limits_{k_{1} = 1}^{K_{1}}} \cdot \cdot \cdot {\sum\limits_{k_{t - 1} = 1}^{K_{t - 1}}} p_{1}^{k_{1}} \cdots p_{t - 1}^{k_{t - 1}}\times \left(a_{t} x_{t}^{k_{1},\ldots,k_{t - 1}} - {\sum\limits_{k_{t} = 1}^{K_{t}}} b_{t} p_{t}^{k_{t}} y_{t}^{k_{1},\ldots,k_{t}}\right)\!\!,\; {t} = 2,\ldots, {T} $$
(6c)
$$ \begin{aligned} \, & \hbox{s.t}.\\ \, & 0 \leq x_{t}^{k_{1},\ldots,k_{t - 1}} \leq x_{t}^{o}, \,{t} = 1, 2, \ldots, {T}\\ \, & 0 \leq x_{1} - y_{1}^{k_{1}} \leq q_{1}^{k_{1}} + v_{0} \\ \, & 0 \leq x_{t}^{k_{1},\ldots,k_{t - 1}} - y_{t}^{k_{1},\ldots,k_{t}} \leq q_{t}^{k_{t}} + v_{t - 1}^{k_{1},\ldots,k_{t - 1}}, \, {t} = 2, \ldots, {T} \\ \, & v_{1}^{k_{1}} = \min \{v,q_{1}^{k_{1}} + v_{0} - x_{1} + y_{1}^{k_{1}} \} \\ \, & v_{t}^{k_{1},\ldots,k_{t}} = \min \{v,q_{t}^{k_{t}} + v_{t - 1}^{k_{1},\ldots,k_{t - 1}} - x_{t}^{k_{1},\ldots,k_{t - 1}} + y_{t}^{k_{1},\ldots,k_{t}} \}, \, {t} = 2, \ldots, {T} \\ \, & 0 \leq y_{t}^{k_{1},\ldots,k_{t}}, \, {t} = 1, 2, \ldots, {T} \\ \end{aligned} $$
(6d)

Figure 1 graphically depicts the scenario tree describing the hierarchy structure of model (6) in which a node is called a parent node when it has descendants. In general, the solution of a MSP can be approached through decomposition algorithms, by partitioning the MSP into simplified sub-problems (Birge et al. 1996; Edirisingle 1999; Blomvall and Lindberg 2002; Blomvall 2003; Liu and Sun 2004). For each node in the scenario tree of model (6), a similar sub-problem can be written as:

$$ \hbox{Max}\, z_{t} = a_{t} x_{t} - {\sum\limits_{j_{t} = 1}^{J_{t}}} b_{t} p_{t}^{j_{t}} y_{t}^{j_{t}} $$
(7a)

s.t.

$$ \left. \begin{aligned} \,& 0 \leq x_{t} \leq x_{t}^{0} \\ \,& 0 \leq x_{t} - y_{t}^{j_{t}} \leq q_{t}^{j_{t}}\\ \,& v_{t}^{j_{t}} = \min \{v,q_{t}^{j_{t}} + v_{t - 1}^{j_{t - 1}} - x_{t} + y_{t}^{j_{t}} \} \\ \,& 0 \leq y_{t}^{k_{t}} \\ \end{aligned} \right\} $$
(7b)
Fig. 1
figure 1

Scenario tree of a MSP problem

Full size image

Model (7) is a conventional two-stage stochastic programming (TSP) with recourse, which can be solved with the multicut L-shaped algorithm introduced by Birge and Louveaux (1988). Assuming its solutions as \(\{z_{t}^{*}, x_{t}^{*}, (y_{t}^{j_{t}})^{*}, (v_{t}^{j_{t}})^{*} | j_{t} = 1,\ldots, J_{t} \},\) when the values of \((v_{t}^{j_{t}})\) are known the value of F t can be expressed as:

$$ F_{t}^{*} = {\sum\limits_{j_{1} = 1}^{J_{1}}} \cdot \cdot \cdot {\sum\limits_{j_{t - 1} = 1}^{J_{t - 1}}} p_{1}^{j_{1}} \cdots p_{t - 1}^{j_{t - 1}} \cdot [z_{t}^{*} + a_{t} (v_{t - 1}^{j_{t - 1}})^{*}] $$
(8)

Since the solutions of model (6) also depend on transition variables \(v_{t}^{k_{1},\ldots,k_{t}} (t = 2, \ldots, T),\) the relation between \(v_{t - 1}^{k_{1},\ldots,k_{t - 1}}\) and z t in each TSP sub-problem should be identified before getting the optimum of model (6). A linear relation is found as introduced in the Appendix. Since the maximum value of each \(v_{t}^{k_{1},\ldots,k_{t}}\) that can be passed from stage t to its next stage is v, the maxima of F t * is given by:

$$ {\hat{F}}_{t} = {\sum\limits_{k_{1} = 1}^{K_{1}}} \cdot \cdot \cdot {\sum\limits_{k_{t - 1} = 1}^{K_{t - 1}}} p_{1}^{k_{1}} \cdots p_{t - 1}^{k_{t - 1}} [z_{t}^{*} + a_{t} v] $$
(9)

The optimized objective-function value of model (6) is thus within \([{\sum\nolimits_{t = 1}^T} F_{t}^{*}, {\sum\nolimits_{t = 1}^T} {\hat{F}}_{t}].\) When \(x_{t}^{*} = {\hat{x}}_{t}\) (see the definition of \({\hat{x}}_{t}\) in the appendix) exists in each stage, there will be no transfers of prime values though the scenario tree and then the optimum of model (6) can be easily obtained. Otherwise, the following procedure is used to obtain the solutions of model (6).

Step 1

Solve model (7) independently in each stage t. If the initial storage v 0 is 0 and there is no transfer in values of \(v_{t}^{k_{1},\ldots,k_{t}},\) the objective-function value of model (6) is:

$$ f^{(0)} = {\sum\limits_{t = 1}^T} F_{t}^{(0)} $$
(10a)
$$ F_{t}^{(0)} = {\sum\limits_{k_{1} = 1}^{K_{1}}} \cdot \cdot \cdot {\sum\limits_{k_{t - 1} = 1}^{K_{t - 1}}} p_{1}^{k_{1}} \cdots p_{t - 1}^{k_{t - 1}} z_{t}^{*},\quad {t} = 1, \ldots,{T} $$
(10b)

Step 2

Solve sub-model with objective function F 1 in stage 1 and constraints (6d) when t = 1; solve sub-model with objective function F 2 in stage 2 and constraints (6d) when t = 2, considering storage transferred from stage 1; and repeat this procedure to stage T. In the solution approach for each F t , solutions of each corresponding TSP sub-problem provide a basis in terms of its linear relations introduced in the Appendix. Assuming the solutions of sub-model F t in stage t as \(\{z_{t}^{**}, (x_{t}^{k_{1}, ...k_{t - 1} })^{**}, (y_{t}^{k_{1,\ldots,} k_{t}})^{*}, (v_{t}^{k_{1},\ldots,k_{t}})^{* *} \}.\) The objective-function value of model (6) becomes:

$$ f^{(1)} = {\sum\limits_{t = 1}^T} F_{t}^{(1)} $$
(11a)
$$ F_{t}^{(1)} = {\sum\limits_{k_{1} = 1}^{K_{1}}} \cdot \cdot \cdot {\sum\limits_{k_{t - 1} = 1}^{K_{t - 1}}} p_{1}^{k_{1}} \cdots p_{t - 1}^{k_{t - 1}} [z_{t}^{*} + a_{t} (v_{t - 1}^{k_{1},\ldots,k_{t - 1}})^{*}] $$
(11b)

The optimized objective-function value of model (6) is then within \([f^{(1)}, {\sum\nolimits_{t = 1}^T} {\hat{F}}_{t}].\) Owing to variations in a t , expression (11) should be further optimized in order to obtain the optimum of model (6)

Step 3

Based on the solutions in Step 2, in each stage t calculate the increase of F t when all \(x_{t}^{k_{1},\ldots,k_{t - 1}}\) have a same increase of Δx. Assuming the increase of F t as ΔF t (Δx) and rank the values of ΔF t (Δx). Transfer the value of ΔF t from the stage with lowest value of ΔF t to the stage with highest value of ΔF t . It should be noted that the maximum value of Δx is constrained by maximum storage v. Repeat such transfers with a global search until the optimum of model (6) is reached.

2.4 Solution of the interval model

In terms of model (6), the following format of model (4) can be written:

$$ \begin{aligned} \hbox{Max} \,f^{\pm} &= a_{1}^{\pm} x_{1} - {\sum\limits_{k_{1} = 1}^{K_{1}}} b_{1}^{\pm} p_{1}^{k_{1}} y_{1}^{k_{1}} + {\sum\limits_{k_{1} = 1}^{K_{1}}} p_{1}^{k_{1}}\times \left(a_{2}^{\pm} x_{2}^{k_{1}} - {\sum\limits_{k_{2} = 1}^{K_{2}}} b_{2}^{\pm} p_{2}^{k_{2}} y_{2}^{k_{1}, k_{2}}\right) \\ & \quad + \cdots + {\sum\limits_{k_{1} = 1}^{K_{1}}} \cdots {\sum\limits_{k_{t - 1} = 1}^{K_{t - 1}}} p_{1}^{k_{1}} \cdots\times p_{t - 1}^{k_{t - 1}} (a_{t}^{\pm} x_{t}^{k_{1},\ldots,k_{t - 1}} - {\sum\limits_{k_{t} = 1}^{K_{t}}} b_{t}^{\pm} p_{t}^{k_{t}} y_{t}^{k_{1},\ldots,k_{t}}) + \cdots \\ \end{aligned} $$
(12a)
$$ \left. \begin{aligned} \, &\hbox{s.t.}\\ \,& 0 \leq x_{t}^{k_{1},\ldots,k_{t - 1}} \leq x_{t}^{o} \\ \,& 0 \leq x_{1} - y_{1}^{k_{1}} \leq (q_{1}^{k_{1}})^{\pm} + v_{0} \\ \,& 0 \leq x_{t}^{k_{1},\ldots,k_{t - 1}} - y_{t}^{k_{1},\ldots,k_{t}} \leq (q_{t}^{k_{t}})^{\pm} + v_{t - 1}^{k_{1},\ldots,k_{t - 1}} \\ \,& v_{1}^{k_{1}} = \min \{v,(q_{1}^{k_{1}})^{\pm} + v_{0} - x_{1} + y_{1}^{k_{1}} \} \\ \,& v_{t}^{k_{1},\ldots,k_{t}} = \min \{v,(q_{t}^{k_{t}})^{\pm} + v_{t - 1}^{k_{1},\ldots,k_{t - 1}} - x_{t}^{k_{1},\ldots,k_{t - 1}} + y_{t}^{k_{1},\ldots,k_{t}} \}\\ \,& y_{t}^{k_{1},\ldots,k_{t}} \geq 0 \\ \end{aligned} \right\},\quad t = 2, \ldots, T $$
(12b)

According to model (7), the imbedded interval TSP model of model (12) in each planning stage can be stated as:

$$ \hbox{Max}\, z_{t}^{\pm} = a_{t}^{\pm} x_{t} - {\sum\limits_{j_{t} = 1}^{J_{t}}} b_{t}^{\pm} p_{t}^{j_{t}} y_{t}^{j_{t}} $$
(13a)
$$ \left. \begin{aligned} \, &\hbox{s.t.}\\ \,& 0 \leq x_{t} \leq x_{t}^{o} \\ \,& 0 \leq x_{t} - y_{t}^{j_{t}} \leq q_{t}^{j_{t}} \\ \,& v_{t}^{j_{t}} = \min \{v,q_{t}^{j_{t}} + v_{t - 1}^{j_{t - 1}} - x_{t} + y_{t}^{j_{t}} \} \\ \,& 0 \leq y_{t}^{j_{t}} \\ \end{aligned} \right\} $$
(13b)

Model (13) is an interval TSP linear model, and its most- and least-favorable optimum can be obtained based on the solutions of interval model (1). The solutions of model (13) will be used to solve model (12). To get the sub-models of model (12), define f − and f + as:

$$ \begin{aligned} f^{+} &= a_{1}^{+} x_{1} - {\sum\limits_{k_{1} = 1}^{K_{1}}} b_{1}^{-} p_{1}^{k_{1}} y_{1}^{k_{1}} + {\sum\limits_{k_{1} = 1}^{K_{1}}} p_{1}^{k_{1}} \left(a_{2}^{+} x_{2}^{k_{1}} - {\sum\limits_{k_{2} = 1}^{K_{2}}} b_{2}^{-} p_{2}^{k_{2}} y_{2}^{k_{1}, k_{2}}\right) \\ & \quad + \cdots + {\sum\limits_{k_{1} = 1}^{K_{1}}} \cdots {\sum\limits_{k_{t - 1} = 1}^{K_{t - 1}}} p_{1}^{k_{1}} \cdots p_{t - 1}^{k_{t - 1}} \left(a_{t}^{+} x_{t}^{k_{1},\ldots,k_{t - 1}} - {\sum\limits_{k_{t} = 1}^{K_{t}}} b_{t}^{-} p_{t}^{k_{t}}y_{t}^{k_{1},\ldots,k_{t}}\right) + \cdots \\ \end{aligned} $$
(14a)
$$ \begin{aligned} f^{-} &= a_{1}^{-} x_{1} - {\sum\limits_{k_{1} = 1}^{K_{1}}} b_{1}^{+} p_{1}^{k_{1}} y_{1}^{k_{1}} + {\sum\limits_{k_{1} = 1}^{K_{1}}} p_{1}^{k_{1}} \left(a_{2}^{-} x_{2}^{k_{1}} - {\sum\limits_{k_{2} = 1}^{K_{2}}} b_{2}^{+} p_{2}^{k_{2}} y_{2}^{k_{1}, k_{2}}\right) \\ & \quad + \cdots + {\sum\limits_{k_{1} = 1}^{K_{1}}} \cdots {\sum\limits_{k_{t - 1} = 1}^{K_{t - 1}}} p_{1}^{k_{1}} \cdots p_{t - 1}^{k_{t - 1}} \left(a_{t}^{-} x_{t}^{k_{1},\ldots,k_{t - 1}} - {\sum\limits_{k_{t} = 1}^{K_{t}}} b_{t}^{+} p_{t}^{k_{t}} y_{t}^{k_{1},\ldots,k_{t}}\right) + \cdots \\ \end{aligned} $$
(14b)

Given any solution x ≥ 0, obviously, f − (x) ≤ f(x) ≤ f + (x) exists. According to model (1), expressions (14a) and (14b) are the most- and least-favorable objective-functions of model (12), respectively. Since all constraints in model (12) are linear, the maximum value range inequalities (Tong 1994) of constraint (12b) can be obtained. Therefore, the most-favorable solutions of model (12) can be determined with:

$$ \begin{aligned}\hbox{Max}\,f^{+}& = a_{1}^{+} x_{1} - {\sum\limits_{k_{1} = 1}^{K_{1}}} b_{1}^{-} p_{1}^{k_{1}} y_{1}^{k_{1}} + {\sum\limits_{k_{1} = 1}^{K_{1}}} p_{1}^{k_{1}} \left(a_{2}^{+} x_{2}^{k_{1}} - {\sum\limits_{k_{2} = 1}^{K_{2}}} b_{2}^{-} p_{2}^{k_{2}} y_{2}^{k_{1}, k_{2}}\right) \\ & \quad + \cdots + {\sum\limits_{k_{1} = 1}^{K_{1}}} \cdots {\sum\limits_{k_{t - 1} = 1}^{K_{t - 1}}} p_{1}^{k_{1}} \cdots\times p_{t - 1}^{k_{t - 1}} \left(a_{t}^{+} x_{t}^{k_{1},\ldots,k_{t - 1}} - {\sum\limits_{k_{t} = 1}^{K_{t}}} b_{t}^{-} p_{t}^{k_{t}} y_{t}^{k_{1},\ldots,k_{t}}\right) + \cdots \\ \end{aligned} $$
(15a)
$$ \left. \begin{aligned} \, &\hbox{s.t.}\\ \,& 0 \leq x_{t}^{k_{1},\ldots,k_{t - 1}} \leq x_{t}^{0} \\ \,& 0 \leq x_{1} - y_{1}^{k_{1}} \leq (q_{1}^{k_{1}})^{+} + v_{0} \\ \,& 0 \leq x_{t}^{k_{1},\ldots,k_{t - 1}} - y_{t}^{k_{1},\ldots,k_{t}} \leq (q_{t}^{k_{1}})^{+} + v_{t - 1}^{k_{1},\ldots,k_{t - 1}} \\ \,& v_{1}^{k_{1}} = \min \{v,(q_{1}^{k_{1}})^{+} + v_{0} - x_{1} + y_{1}^{k_{1}} \} \\ \,& v_{t}^{k_{1},\ldots,k_{t}} = \min \{v,(q_{t}^{k_{t}})^{+} + v_{t - 1}^{k_{1},\ldots,k_{t - 1}} - x_{t}^{k_{1},\ldots,k_{t - 1}} + y_{t}^{k_{1},\ldots,k_{t}} \}\\ \,& y_{t}^{k_{1},\ldots,k_{t}} \geq 0 \\ \end{aligned} \right\},\quad{t} = 2, \ldots,{T} $$
(15b)

Sub-model (15) is a conventional MSP as model (6). Assuming its solutions as \(\{{\bar{x}}_{t}^{k_{1},\ldots,k_{t - 1}}, {\bar{y}}_{t}^{k_{1},\ldots,k_{t}}, f_{\rm opt}^{+} |\forall t\},\) where k 0 = 1. Obviously, f +opt  ≥ f + (x) holds. In similar, the least-favorable solutions of model (13) can be given by:

$$ \begin{aligned} \hbox{Max} \,f^{-} &= a_{1}^{-} x_{1} - {\sum\limits_{k_{1} = 1}^{K_{1}}} b_{1}^{+} p_{1}^{k_{1}} y_{1}^{k_{1}} + {\sum\limits_{k_{1} = 1}^{K_{1}}} p_{1}^{k_{1}} \left(a_{2}^{-} x_{2}^{k_{1}} - {\sum\limits_{k_{2} = 1}^{K_{2}}} b_{2}^{+} p_{2}^{k_{2}} y_{2}^{k_{1}, k_{2}}\right) \\ & \quad + \cdots + {\sum\limits_{k_{1} = 1}^{K_{1}}} \cdots {\sum\limits_{k_{t - 1} = 1}^{K_{t - 1}}} p_{1}^{k_{1}} \cdots\times p_{t - 1}^{k_{t - 1}} \left(a_{t}^{-} x_{t}^{k_{1},\ldots,k_{t - 1}} - {\sum\limits_{k_{t} = 1}^{K_{t}}} b_{t}^{+} p_{t}^{k_{t}} y_{t}^{k_{1},\ldots,k_{t}}\right) + \cdots \\ \end{aligned} $$
(16a)
$$ \left. \begin{aligned} \, &\hbox{s.t.}\\ \,& 0 \leq x_{t}^{k_{1},\ldots,k_{t - 1}} \leq x_{t}^{0} \\ \,& 0 \leq x_{1} - y_{1}^{k_{1}} \leq (q_{1}^{k_{1}})^{-} + v_{0} \\ \,& 0 \leq x_{t}^{k_{1},\ldots,k_{t - 1}} - y_{t}^{k_{1},\ldots,k_{t}} \leq (q_{t}^{k_{1}})^{-} + v_{t - 1}^{k_{1},\ldots,k_{t - 1}} \\ \,& v_{1}^{k_{1}} = \min \{v,(q_{1}^{k_{1}})^{-} + v_{0} - x_{1} + y_{1}^{k_{1}} \} \\ \,& v_{t}^{k_{1},\ldots,k_{t}} = \min \{v,(q_{t}^{k_{t}})^{-} + v_{t - 1}^{k_{1},\ldots,k_{t - 1}} - x_{t}^{k_{1},\ldots,k_{t - 1}} + y_{t}^{k_{1},\ldots,k_{t}} \}\\ \,& y_{t}^{k_{1},\ldots,k_{t}} \geq 0 \\ \end{aligned} \right\},\quad{t} = 2, \ldots,{T} $$
(16b)

Sub-model (16) is also a deterministic linear equivalent of MSP similar to model (6). Assuming its solutions as \(\{\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{x}_{t} ^{k_{1},\ldots,k_{t - 1}}, \underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{y}_{t} ^{k_{1},\ldots,k_{t}}, f_{\rm opt}^{+} |\forall t\}.\) Based on the solutions of sub-models (15) and (16), the solutions of model (13) can be written as:

$$ \left. \begin{aligned} \,& f_{\rm opt}^{\pm}= [f_{\rm opt}^{-}, f_{\rm opt}^{+}] \\ \, & (x_{t}^{k_{1},\ldots,k_{t - 1}})_{\rm opt} = (\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{x}_{t}^{k_{1}, ,\ldots,k_{t - 1}}, {\bar{x}}_{t}^{k_{1},\ldots,k_{t - 1}})\\ \,& (y_{t}^{k_{1},\ldots,k_{t}})_{\rm opt} = (\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{y}_{t}^{k_{1}, ,\ldots,k_{t}},{\bar{y}}_{t}^{k_{1},\ldots,k_{t}})\\ \,& (v_{t}^{k_{1},\ldots,k_{t}})_{\rm opt} = (\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{v}_{t}^{k_{1}, ,\ldots,k_{t}}, {\bar{v}}_{t}^{k_{1},\ldots,k_{t}}) \\ \end{aligned} \right\},\quad t = 1, \ldots, T $$
(17)

3 Working example

3.1 Problem statement

Consider a river basin where a hydropower plant is proposed. An economic analysis is required to estimate the long-term benefit of the proposed plant in which uncertain water supply (inflows) and electricity loads need to be reflected. For such a hydro-economic analysis, it is assumed that the proposed plant is optimally operated. The expected value of the plant’s annual net-benefit is used to measure the plant’s performance. In order to consider seasonal variations in both water supply and electricity load, the problem under consideration can be modeled with a MSP. However, many other technical and economic factors can only be expressed as interval numbers. The problem therefore can be solved with model (4). Here, T = 12 since only monthly variations in inflows and electricity load are considered. For simplicity, the initial reservoir storage (v 0) is assumed to be full. Table 1 lists the probabilities and corresponding inflow levels. Other uncertain technical and economic data are listed in Table 2.

Table 1 Monthly water supply (inflows) under different probability levels
Full size table
Table 2 Economic and technical data
Full size table

4 Results and discussion

Table 3 provides the solutions of each interval TSP sub-problem from Step 1 of the solution approach. The solutions show that under an optimized target water release \((x_{t}^{*})\) a deficiency of water supply \((y_{t}^{j_{t} })^{*}\) occurs when total inflow (q ± ij ) is low; however, a storage \((v_{t}^{j_{t}})^{*}\) can be saved for next stage use when total water supply is high. For example, in September when optimized target water release is 13 × 109 m3, water deficiency (4 × 109 m3) occurs when total inflow is low while storage can be stored (0.1 × 109 m3 or 3 × 109 m3) when total inflow is high.

Table 3 Solutions of the TSP sub-problems from Step 1
Full size table

Figure 2 illustrates the target water releases and objective-function values \(z_{t}^{*}\) from interval TSP sub-problems for each planning stage from Step 1 of the solution approach. It shows that both target water releases and objective-function values have the same trend. Provided as the basics of the solution approach, the solutions from the interval TSP sub-problems were further feed into the two sub-models (15) and (16). The most- and least-favorable solutions of model (4) were obtained following solutions Steps 1–3. The optimized net-system benefit of the study case is \(\$[5.745, 6.137] \times 10^{9}.\) Figure 3 further illustrates the net-system benefit in each planning stage. It shows that the maximum stage net-system benefit is in June. This is due to high value in a ± i resulting in water storages being transferred from previous planning stages.

Fig. 2
figure 2

Target water releases and objective values of interval TSP sub-problems

Full size image
Fig. 3
figure 3

Net-system benefits and TSP objective values in each planning stage

Full size image

If the problem under consideration is formulated as a traditional MSP by letting all interval inputs equal to their mid-values, the obtained solution is a set of deterministic values, which represents a decision under a deterministic input scenario. However, using the interval programming, the developed model can reflect uncertainties represented as interval inputs and then generate the degree of system changes articulated by the most- and least-favorable optimum.

An important step in the solution approach of the multistage interval-stochastic programming is to solve the imbedded interval TSP sub-problems. By piecewise linearization of the convex polyhedrom in a TSP, the TSP is transformed into a deterministic equivalent LP. Then, the recourse of model (4) is confined in each TSP in the scenario tree of the multistage model. Based on the linear features in each node of the TSP sub-problems, a global search was used to get the solutions of the multistage interval-stochastic programming model.

Modeling results show that the solution method of the developed model is effective with computational advantages. In a MSP, even if all PDFs of random variables are available, it is still extremely difficult to solve stochastic programming models (Birge and Louveaux 1997). In comparison, the developed interval MSP model can effectively reflect uncertainties (in interval formats) into the stochastic optimization framework, leading to simplified sub-models with reduced computational requirements.

Usually, hydroelectric resource planning problems are often formulated as linear programming models. However, a LP model becomes less effective when the randomness in inflows should be quantified, at the same time, uncertain data represented as intervals need to be reflected. The developed model provides an alternative technique for hydroelectric resources planning.

5 Summary and conclusions

A recourse-based multistage interval-stochastic programming model is developed for long-term hydroelectric resource planning based on interval programming and conventional MSP techniques. It can reflect penalties associated with random inflows and uncertainty presented as intervals. A decomposition solution method for the developed model, based on linear features of TSP sub-problems, is also introduced. The working example indicates that the developed model is effective in addressing uncertainties with various formats and the solution method alleviates the computational load in solving the multistage stochastic programming with recourse. Modeling results show that the developed model can provide an alternative tool in optimization modeling of long-term hydroelectric resource planning.