Editing Stochastic programming (section)

=== Scenario construction ===
In practice it might be possible to construct scenarios by eliciting experts' opinions on the future. The number of constructed scenarios should be relatively modest so that the obtained deterministic equivalent can be solved with reasonable computational effort. It is often claimed that a solution that is optimal using only a few scenarios provides more adaptable plans than one that assumes a single scenario only. In some cases such a claim could be verified by a simulation. In theory some measures of guarantee that an obtained solution solves the original problem with reasonable accuracy. Typically in applications only the ''first stage'' optimal solution <math>x^*</math> has a practical value since almost always a "true" realization of the random data will be different from the set of constructed (generated) scenarios.

Suppose <math>\xi</math> contains <math>d</math> independent random components, each of which has three possible realizations (for example, future realizations of each random parameters are classified as low, medium and high), then the total number of scenarios is <math>K=3^d</math>. Such ''exponential growth'' of the number of scenarios makes model development using expert opinion very difficult even for reasonable size <math>d</math>. The situation becomes even worse if some random components of <math>\xi</math> have continuous distributions.

====Monte Carlo sampling and Sample Average Approximation (SAA) Method====

A common approach to reduce the scenario set to a manageable size is by using Monte Carlo simulation. Suppose the total number of scenarios is very large or even infinite. Suppose further that we can generate a sample <math>\xi^1,\xi^2,\dots,\xi^N</math> of <math>N</math> realizations of the random vector <math>\xi</math>. Usually the sample is assumed to be [[independent and identically distributed]] (i.i.d sample). Given a sample, the expectation function <math>q(x)=E[Q(x,\xi)]</math> is approximated by the sample average

<math>
\hat{q}_N(x) = \frac{1}{N} \sum_{j=1}^N Q(x,\xi^j)
</math>

and consequently the first-stage problem is given by

<math>
\begin{array}{rlrrr}
\hat{g}_N(x)=&\min\limits_{x\in \mathbb{R}^n}   & c^T x + \frac{1}{N} \sum_{j=1}^N Q(x,\xi^j)    &   \\
&\text{subject to} & Ax    &=&    b \\
&		    & x     &\geq& 0
\end{array}
</math>

This formulation is known as the ''Sample Average Approximation'' method. The SAA problem is a function of the considered sample and in that sense is random. For a given sample <math>\xi^1,\xi^2,\dots,\xi^N</math> the SAA problem is of the same form as a two-stage stochastic linear programming problem with the scenarios <math>\xi^j</math>., <math>j=1,\dots,N</math>, each taken with the same probability <math>p_j=\frac{1}{N}</math>.