While the term sounds advanced, it simply means that you cannot use information that you do not have. In the context of multi-stage stochastic programming it means the following:

1.If your stochastic program is based on a multi-period financial investment problem in, for example, the stock market, then the time-indexed decision variables that are associated with making an investment at time t cannot utilize any information that is revealed AFTER time t.

2. Similarly, if your investment problem deals with farming - how much to grow at a piece of land on your farm during a given time period, your model cannot utilize information about the weather AFTER that period. 

Simply said, you have no crystal ball that can reveal any information from the future. "Non-anticipativity" quite literally also means precisely that - you cannot see the future. And your mathematical model must include constraints that enforce that fact.

Dear Michael,

Many thanks for your prompt and convincing answer.

Regards,

Morteza

Dear Professor Stocia,

I am really grateful for your helpful comment.

As I am an Electrical Engineer, I am not as well as you and other mathematicians in OR (Operational Research). I would be thankful if you could tell me how I can learn stochastic programming in the simplest way?

Regards,

Morteza Shabanzadeh

There are two main approaches to solving multi-stage stochastic programs: Benders decomposition, which decomposes the problem by scenario, and Lagrangian decomposition, which decomposes it by time-stage instead.

The non-anticipativity constraints appear in the latter approach.  Basically, you have two copies of each variable, one representing the value it takes before you know the realisation of some random parameter, and the other representing the value it takes after you know the value.  In reality, the values of the two variables must be equal, since you have to fix the value of the variable before you know the realisation.  So non-anticipativity constraints are just equations stating that two variables must take equal values.

Now,  by relaxing all of the non-anticipativity constraints in Lagrangian fashion, you obtain a relaxation that decomposes into one independent subproblem per time-stage.  This gives a bound for your original problem.  Then, standard techniques (such as the subgradient method) can be used to solve the Lagrangian dual, i.e., find a collection of Lagrangian multipliers that give you the best bound.

Thank you George!

Morteza, you might find these tutorial papers useful:

J.L. Higle & S. Sen (1999) An introductory tutorial on stochastic linear programming models. Interfaces, 29, 33-61.

J.L. Higle (2006) Stochastic programming: optimization when uncertainty matters.  In Tutorials in Operations Research: Emerging Theory, Methods, and Applications. INFORMS; Hanover, MD.

Dear Professor Letchford,

I am really grateful for your worthwhile comments.

Sincerely,

Morteza Shabanzadeh

have a look,on this

http://people.brunel.ac.uk/~mastjjb/jeb/or/sp.html

That was an extremely interesting discussion. I myself had problems with understanding the methodologies used to solve stochastic problems and the resources mentioned above are extremely useful. Sincere thanks to all.

It is very simple, I teach it my students . I am giving it from John Beasley's Note , Professor of OR in UK that note I got from him

It means that As the above example has shown, scenarios with a common history must (logically) have the same set of decisions so that we have the complete set of non-anticipativity constraints as

Please read the whole text or send me mail [email protected]

------------You need 15 minutes ------

--------- NOTE STARTS------------------

We initially make a decision about how much to produce. At the second stage have two possible realisations of the stochastic demand:

• a demand of 500 with probability 0.6

• a demand of 700 with probability 0.4

After this realisation we make a decision as to how much to produce to meet demand in the next period (the third-stage).

At the third stage we again (as it is a binary scenario tree) have two possible realisations of the stochastic demand, but these are different depending upon the realisation at the second stage. For example if the realised demand at the second stage was 500 then the possible realisations at the third stage are:

• a demand of 600 with probability 0.3

• a demand of 700 with probability 0.7

Note here at each level in the scenario tree the appropriate probabilities must sum to one.

This two-level scenario tree actually represents 22=4 possible scenarios of the future:

Scenario Second stage Third stage Probability

1 500 600 0.6(0.3) = 0.18

2 500 700 0.6(0.7) = 0.42

3 700 900 0.4(0.2) = 0.08

4 700 800 0.4(0.8) = 0.32

Note here that these probabilities add to one (as they must as these 4 scenarios are the only possible futures that we can have).

To summarise then, as we move down the scenario tree (for any scenario) we have the following order of events:

• in the first stage a decision as to how much to produce; then

• in the second stage a realisation of the stochastic element (demand); then

• a decision as to the values of the recourse variables; then

• in the second stage a decision as to how much to produce; then

• in the third stage a realisation of the stochastic element (demand); and finally

• a decision as to the values of the recourse variables.

This order naturally extends if we have more than the three stages considered here.

As before, you need to be clear about the sequence that applies as you move down the tree in order to formulate the problem correctly.

In any SP it is important to be clear about the order that pertains as you move through a scenario. In particular you should be clear at each stage about which stochastic elements have been realised and which unrealised.

We can now formulate our three-stage SP. As before let:

x1 >= 0 be the number of units of X to produce now (at the first stage)

y2s >= 0 be the number of units of X to buy from the external supplier at the second stage in scenario s (s=1,...,4)

As discussed above, in this three-stage problem we have a decision to make at the second stage, namely the number of units of X to produce at this stage. So let:

x2s >= 0 be the number of units of X to produce at the second stage in scenario s (s=1,...,4)

Note here that (given the order of events we have specified above) this second stage decision is scenario dependent, i.e. dependent upon the observed realisation of the stochastic demand. For example we might well expect to make a different second stage decision if we have observed a customer demand of 700 than if we have observed a customer demand of 500.

We still need our recourse variables for the third-stage so let:

y3s >= 0 be the number of units of X to buy from the external supplier at the third stage in scenario s (s=1,...,4)

For simplicity we will leave the costs (2 for each unit of production, 3 for each unit bought from the external supplier) constant.

The relationship between the order we specified before and the variables is:

• in the first stage a decision as to how much to produce - x1

• in the second stage a realisation of the stochastic element (demand)

• a decision as to the values of the recourse variables - y2s

• in the second stage a decision as to how much to produce - x2s

• in the third stage a realisation of the stochastic element (demand)

• a decision as to the values of the recourse variables - y3s

Consider the first stage, the constraints to ensure customer demand is satisfied are:

x1 + y2s >= 500 (s=1,2)

x1 + y2s >= 700 (s=3,4)

Now at the second stage we will have units left over (i.e. inventory) to help meet future demand. This inventory level will be:

x1 + y2s - 500 (s=1,2)

x1 + y2s - 700 (s=3,4)

To ensure that demand is met in the third stage we have: inventory + amount produced + amount bought externally >= demand

x1 + y2s - 500 + x2s + y3s >= 600 (s=1)

x1 + y2s - 500 + x2s + y3s >= 700 (s=2)

x1 + y2s - 700 + x2s + y3s >= 900 (s=3)

x1 + y2s - 700 + x2s + y3s >= 800 (s=4)

Whilst these constraints might seem to capture all of the problem in fact there are further constraints that (logically) we need to add.

Consider the recourse variables y2s for s=1 and s=2. These are the amounts bought externally in scenarios 1 and 2 at the second stage. But how can we distinguish between scenario 1 and scenario 2 at the second stage? Both of these scenarios have a common history up to and including the second stage (a decision x1 at the first stage and an observed realisation of the demand at the second stage of 500). It is not until we have a realisation of demand at the third stage that scenarios 1 and 2 differ.

It would seem logical therefore that y21 and y22 must be equal, simply put we cannot have different recourse variables because we cannot distinguish between these scenarios. We can ensure y21 and y22 are equal by adding the constraint y21=y22 to the problem.

In SP constraints which enforce such conditions are called nonanticipativity constraints, implying we cannot anticipate the future.

--------------------important here-----

---NON ANTICIPATIVITY STARTS HERE ------------

As the above example has shown, scenarios with a common history must (logically) have the same set of decisions so that we have the complete set of nonanticipativity constraints as:

scenarios 1 and 2, second stage:

y21=y22

x21=x22

scenarios 3 and 4, second stage:

y23=y24

x23=x24

Note here that this is a key point - scenarios with a common history must have the same set of decisions - and must always be taken into account when formulating a scenario based decision problem.

We can now formulate our objective function. We have just one cost incurred with certainty, namely 2x1, all other costs are probabilistic.

-----NON ANTICIPAVITY ends here ----------------

The easiest way to summarise these costs is to look at each scenario in turn:

---

Scenario Probability Cost

1 0.18 2x21 + 3y21 + 3y31

2 0.42 2x22 + 3y22 + 3y32

3 0.08 2x23 + 3y23 + 3y33

4 0.32 2x24 + 3y24 + 3y34

Weighting each scenario cost by the associated scenario probability will give the expected cost. Hence we have the objective (minimise total expected cost) as:

minimise

2x1 + 0.18(2x21 + 3y21 + 3y31) + 0.42(2x22 + 3y22 + 3y32)

+ 0.08(2x23 + 3y23 + 3y33) + 0.32(2x24 + 3y24 + 3y34)

This completes our formulation of this particular three- stage stochastic program and for completeness we give the complete formulation below.

minimise

2x1 + 0.18(2x21 + 3y21 + 3y31) + 0.42(2x22 + 3y22 + 3y32)

+ 0.08(2x23 + 3y23 + 3y33) + 0.32(2x24 + 3y24 + 3y34)

subject to

x1 + y2s >= 500 (s=1,2)

x1 + y2s >= 700 (s=3,4)

x1 + y2s - 500 + x2s + y3s >= 600 (s=1)

x1 + y2s - 500 + x2s + y3s >= 700 (s=2)

x1 + y2s - 700 + x2s + y3s >= 900 (s=3)

x1 + y2s - 700 + x2s + y3s >= 800 (s=4)

y21=y22

x21=x22

y23=y24

x23=x24

all variables >=0

-------NOTE ENDS HERE ------------------

I hope it helps