# Basic Concepts

Basic concepts

In this section you will find a number of basic concepts that are commonly used in stochastic programming. They will help you to unambiguously understand the stochastic programming facilities in AIMMS.

Stages

In stochastic programming *stages* define a collection of consecutive
periods of time. Stages are usually identified through positive integers
\(1,2,\dots\), and are characterized as follows:

during each stage one or more stochastic (i.e. uncertain) events take place, and

at the end of a stage decisions are taken, taking into account the specific outcomes of the stochastic events of this and previous stages.

Stochastic events may be such quantities as the demand realized during a
period. They are usually represented as input data used in the
deterministic model. Any variables in the deterministic model that are
modeled conceptually to take their value *at the beginning* of a period
(for instance, the stock at the beginning of a period), should be
considered as decisions taken at the end of the previous period/stage
within the stage concept.

Stages versus model periods

If the deterministic model already contains a `Horizon`

(see
Horizons) or any other set of time periods, the stages of
the stochastic model may naturally coincide with the time periods from
the deterministic model, but this certainly needs not be the case. A
single period model, possibly even without an explicit period set, but
with variables representing decisions taken at the beginning *and* at
the end of the period, may still constitute a two-stage stochastic
model. For a multi-period model, a single stage in the stochastic model
may consist of multiple time periods from the deterministic model, and
hence one can always construct a mapping from the deterministic period
set to stages in the stochastic model.

Variables and stages

Every individual stochastic variable in a stochastic model should be uniquely associated with a single stage. This stage represents the period at the end of which the variable conceptually takes it value

taking into consideration the

*specific*outcomes of stochastic events taking place during the stage at hand and during prior stages,but only taking into account the

*distribution*of possible outcomes of the stochastic events taking place in any further stage.

Even if model periods of the deterministic model and the stages of the stochastic model coincide, variables with an index into the period set do not have to be associated with the stage corresponding to the value of that index. As discussed above, variables that conceptually take their value at the beginning of a period, provide a first example of this behavior as they must be associated with the stage corresponding to the previous period within the stochastic model.

Examples

Other examples may arise, for instance, when the monthly productions of January, February and March should be decided upon prior to the beginning of January, regardless of the specific outcomes for the demands during these months. Conversely, if market research has delivered good estimates for the demand in January, February and March, the decisions for the production in these months should take into consideration the demand estimates of all three months. Hence the production variables for January, February and March should be part of the stage associated with March.

Scenarios

A *scenario* for a stochastic model is a collection of outcomes for all
the stochastic events taking place in the model, along with the
associated probability of the scenario to occur. For the event values
associated with each scenario, one could solve a deterministic model,
which would yield the optimal decisions for that particular scenario.
For different scenarios, however, the decisions resulting from solving
such deterministic models individually are, in general, completely
unrelated, even if the event outcomes of the scenarios are exactly the
same up to a certain stage. To address this problem, the scenarios of a
stochastic model must be organized into a scenario tree.

Scenario trees

A single scenario can be graphically represented as a simple tree illustrated in Fig. 4.

For multiple scenarios, the specific outcomes of the stochastic events up to a certain stage usually coincide for a subset of the scenarios. This gives rise to a scenario tree as illustrated in Fig. 5.

In such a scenario tree, the path from the root node of the tree to each
of its leaf nodes corresponds to a single scenario, and the event
outcomes for scenarios that pass through the same intermediate node are
identical for all stages up to that node. If a stage consists of
multiple time periods in the deterministic model, this means that the
stochastic events taking place during *all* periods associated with the
stage should coincide. The solution process of a stochastic model will
make sure that the decisions that are to be taken at the end of these
stages are identical for all the scenarios passing through the node, as
one would intuitively expect.

Scenario generation

The scenarios and the scenario tree used in a stochastic model are usually generated by using one of the following two techniques

generate scenarios by incrementally creating a scenario tree according to a given distribution for each stochastic event, or

given an externally created set of scenarios, create a scenario tree by grouping identical or similar scenarios at every level of the tree.

Distribution-based scenario generation

Given a leaf node in an intermediate scenario tree, for every stochastic
event that occurs during the stage directly following that node, a fixed
number of values is computed according to a given distribution (each
with its own relative probability of taking place). For each of these
values a new branch is added to the node. The process starts by adding
branches to the root node of the tree and ends when a tree is generated
for all stages. The total number of scenarios generated by the process
is the final number of leaf nodes generated. The probability of a
scenario is the multiplication of the relative probabilities associated
with each branch along the path from root to leaf node. The scenario
tree in Fig. 5 could be generated in this way, for
example, by choosing, at every intermediate node, a *high* or a *low*
level for the demand during the stage following that particular node.

Scenario-based tree generation

Another approach is to start from a given collection of scenarios with probabilities adding up to 1. Such a collection of scenarios can either be randomly generated or be the result of some external process. As a tree, they can be represented as a trivial scenario tree, as illustrated in Fig. 6.

This tree can be transformed into a scenario tree by bundling together identical or similar scenarios into a fixed or dynamic number of branches. The group of scenarios passing through a particular intermediate node in the scenario tree is analyzed and grouped into subgroups of scenarios with similar or identical outcomes of the stochastic events during the stage following that node. For every subgroup, the existing branches are bundled into a single branch, and the stochastic event outcomes are made identical for all scenarios in the subgroup. The process starts by analyzing all scenarios at the root node of the tree, and ends when every scenario is associated with a single leaf node.

Basic procedure for solving stochastic models

The implementation of stochastic programming in AIMMS closely follows the concepts described in this section. The basic procedure to create and solve a stochastic model in AIMMS is as follows:

indicate in your model which parameters and variables are to become stochastic,

for every stochastic variable in your model specify during which stage of the stochastic model the decision is to be taken,

generate scenarios, their stochastic data, and a scenario tree, using one of the techniques described above, and

generate and solve the stochastic model using the special methods available for this purpose in AIMMS.

Each of these steps is explained in more detail in the sections to follow. Note that changing parameters and variables in your model into stochastic parameters and variables, does in no way influence the possibility to solve the underlying deterministic model in its original form. Thus, the stochastic programming facilities in AIMMS always form a true extension of the functionality of the existing AIMMS application.