MULTISTAGE STOCHASTIC LINEAR PROGRAMMING WITH RECOURSE

Multistage stochastic programming formulations arise naturally as a generalization of two-stage models. At each stage, we gather new information and we make decisions accordingly, taking into account immediate costs and expected future recourse cost. The resulting decision process may be summarized as follows:²³

• At the beginning of the first time period (at time t = 0) we select the decision vector x₀; this decision has a deterministic immediate cost  and must satisfy constraints
• At the beginning of the second time period we observe random data (A₁₀, A₁₁, c₁, b₁) depending on event ω₁; then, on the basis of this information, we make decision x₁; this second decision has an immediate cost  and must satisfy the constraintNote that these data are not known at time t = 0, only at time t = 1; the new decision depends on the realization of these random variables and is also affected by the previous decision.
• We repeat the same scheme as above for time periods up to H − 1, where H is our planning horizon.
• At the beginning of the last time period H, we observe random data (A_{H,H − 1}, A_{H H}, c_H, b_H) depending on event ω_H;, then, on the basis this information we make decision x_H, which has an immediate cost  and must satisfy the constraint

From the point of view of time period t = 0, the decisions x₁, …, x_H are random variables, as they will be adapted to the realization of the stochastic process. However, the only information we may use in making each decision consists on the history so far. The resulting dynamic decision process can be appreciated by the following recursive formulation of the multistage problem:

In this formulation, we see that decision x_t depends directly only on the previous decisions x_t−1. In general, decisions may depend on all of the past history, leading to a slightly more complicated model. However, we may often introduce additional state variables, such that the above formulation applies. For instance, in a production planning model we may “forget” the past produced quantities if we know the current inventory levels. It should be noted that, in practice, the real output of the above model is the set of immediate decisions x₀. The remaining decision variables could be regarded as contingent plans, which are implemented in time, much in the vein of a feedback control policy; however, in a practical setting, it is more likely that the model will be solved again and again according to a rolling-horizon logic. While this formulation points out the dynamic optimization nature of multistage problems, we usually resort to deterministic equivalents based on discrete scenario trees. We illustrate the idea with a toy financial planning problem.

Fig. 13.10 Piecewise linear concave utility function.