As defined by the stochastic programming community - COSP at [25] - Stochastic programming is a framework for modeling optimization problems that involves uncertainty. Whereas determin-istic optimization problems are formulated with known parameters. Real world problems almost invariably include some unknown parameters. When the parameters are known only within cer-tain bounds, one approach to tackling such problems is called robust optimization. Here the goal is to find a solution which is feasible for all such data and optimal in some sense. Stochastic pro-gramming models are similar in style but take advantage of the fact that probability distributions
2.3 Stochastic Programming 25
governing the data are known or can be estimated. The goal here is to find some policy that is feasible for all (or almost all) the possible data instances. It maximizes the expectation of some function of the decisions and the random variables. More generally, such models are formulated, solved analytically or numerically, and analyzed in order to provide useful information for a decision maker.
The most widely applied and studied stochastic programming models are two-stage linear pro-grams. Here the decision maker takes some action in the first stage, after which a random event occurs affecting the outcome of the first-stage decision. A recourse decision can then be made in the second stage that compensates for any bad effects that might have been experienced as a result of the first-stage decision. The optimal policy from such a model is a single first-stage policy and a collection of recourse decisions (a decision rule) defining which second-stage action should be taken in response to each random outcome. These results can later be extended into multi-stage stochastic programming.
More formally I have used the definitions as described by J.R. Birge and F. Louveaux in [2]. A deterministic linear program is defined as:
Minimize
z=cT
Subject To:
Ax= b
x≥0
wherexis an (n×1) vector of decisions andc,Aandbare known data of the sizes (n×1), (m×n) and (m×1). In this formulation all the first-stage decisions are captured by the variablex.
Let us look now at a two-stage problem with fixed recourse by G.B. Dantzig at [3] and Beale at
[1]:
Minimize
z=cTx+Eξ[minq(ω)Ty(ω)]
Subject To:
Ax= b
T(ω)x+Wy(ω)=h(ω)
x≥ 0,y(ξ)≥0 (2.1)
The first-stage decisions are represented by a familiar vector x which is an (n× 1) vector of decisions and c,A and b are known data of the sizes (n×1), (m×n) and (m×1). However, this model considers a representation of a number of random eventsω ∈ Ω. For a given realization ω the second-stage problem data q(ω),h(ω) and T(ω) become known, where q(ω) is n2 × 1, h(ω) is m2 ×1 and T(ω) is m2 ×n1. Each component ofq,h and T is thus a possible random variable. Piecing together all the stochastic components of the second-stage data and the vector ξT(ω) = (q(ω)T,h(ω)T,T1(ω), . . . ,Tm2(ω)) is obtained. The optimization model now considers future scenarios that are dependent upon different values of ξ in order to make the first-stage decision x.
According to Kaut and Wallace in [8] stochastic programming has gained increasing popularity within the mathematical programming community. Present computing power allows users to add stochasticity to models that had been as difficult to solve as deterministic models only a few years ago. In this context, a stochastic programming model can be viewed as a mathematical programming model with uncertainty about the values of some of the parameters. Instead of single values, these parameters are then described by distributions (in a single-period case), or by stochastic processes (in a multi-period case),
2.3 Stochastic Programming 27
where ξ is a random vector, whose distribution must be independent of the decision vector x.
Note that the formulation is far from complete we still need to specify the meanings of min and the constraints.
It is interesting to note that the special structure of the stochastic programming problems as different blocks of constraints are considered in different scenarios. These can be very useful for solving problems. When such a problem is created different solving heuristics that exploit this structure can perform better and faster than others. This is done by the several decomposition algorithms including the L-Shaped method.
Except for some trivial cases, the problem (2.1) can not be solved with continuous distributions.
Most solution methods need discrete distributions. In addition, the cardinality of the support of discrete distributions is limited by the available computing power, together with a complexity of the decision.
In the following report the scenario generator is used in order to find different likely values for ω∈Ω. These values can later be solved in an optimization model and be used as scenarios.
In that sense, the scenario generation process discretizes the stochasticity of the problem.
As described by Hochreiter at [26]. The field of multi-stage stochastic programming provides a rich modeling framework for tackling a broad range of real-world decision problems. In order to numerically solve such programs - once they get reasonably large - the infinite-dimensional optimization problem has to be discretized. The stochastic optimization program generally con-sists of an optimization model and a stochastic model. In the multi-stage case, the stochastic model is most commonly represented as a multi-variate stochastic process. There are different ways to represent scenarios and a few of them will be considered in the following section. The most common technique to calculate a usable discretization is to generate a scenario tree from the underlying stochastic process.