Hello.

I have a 4-stage scenario tree. At each stage , i have two branches. So in total I have 15 nodes. I solve this problem in its node-variable formulation and it takes a lot of time. Also the scenario-variable formulation takes time.

My question is: The deterministic equivalent of a problem is always a 2-stage stochastic problem with decision variables only in the first stage ?

If not, can you please describe how it will look like ? The theory is not helpful unfortunately for me.

asked 24 May '14, 07:25

spyimp's gravatar image

spyimp
4118
accept rate: 0%


  1. The DEP is not always a two-stage SP as you might have multiple planning stages (i.e., decisions and random parameters are determined over the course of time), in which case you have a multi-stage SP. A simple example is a stochastic multi-period production planning problem.
  2. If you don't take any decision in a subsequent stage (i.e., you cannot fix your decision after realization of random parameters), you would have no recourse. The drawback is that you might violate some constraints or incur too much cost. One way to deal with this to consider a penalty for risks and violating constraints. This is called simple recourse. You might also consider some recourse actions to deal with randomness. An example is to re-route vehicle in VRP in case of failing to satisfy customers' stochastic demands.
  3. Please see here for a brief introduction to strategies for dealing with stochastic problems.
link

answered 25 May '14, 03:06

Ehsan's gravatar image

Ehsan ♦
4.8k31122
accept rate: 16%

You are talking about a multi-stage stochastic problem. A multi-stage stochastic problem will never become a 2-stage one, since yours is inherently 4-stage. Lets consider in the following the scenario-based formulation.

The deterministic equivalent problem (DEP) of your multi-stage SP consists of two parts:

  • 8 blocks decomposed which correspond to the 8 scenarios;
  • 17 blocks which represent the non-anticipativity constraints (NACs).

Schematically your matrix would roughly look like the one below, although it cannot fully reflect your problem:

|x x x                               |
|x x x                               |
|      x x x                         |
|      x x x                         |
|            x x x                   |
|            x x x                   |
|                   x x x            |
|                   x x x            |
|                         .....      |
|                               x x x|
|                               x x x|
|x    x                              |
|x            x                      |
|     x             x                |
|....................................|
|                                x   |

The last constraints are called non-anticipativity because they exist to remind you that some of the decisions made in the past are binding for some scenarios that share the exact same past. For instance, decisions made at the first stage should all be identical for all scenarios, since all scenarios share the same first stage. Similarly, decisions at later stages are binding for certain scenarios which share the same past. This is very well depicted in your scenario tree. Imagine that tree - you have already sketched - unfolded by scenario. In this perspective, we create copies of decision variables at each stage. The original and the unfolded tree would look like the ones below:

           O    
          / 
         O  
        / \                       O----O----O----O
       /   O                      |    |    |
      O                           O----O----O----O
     / \   O                      |    |    
    /   \ /                       O----O----O----O
   /     O                        |    |    |
  /       \                       O----O----O----O
 /         O                      |         
O                      ===>       O----O----O----O
 \         O                      |    |    |
  \       /                       O----O----O----O
   \     O                        |    |
    \   / \                       O----O----O----O
     \ /   O                      |    |    |
      O                           O----O----O----O
       \   O    
        \ / 
         O  
          \ 
           O

The unfolded version of the tree is created out of your original tree. Every node marks a stage. Every row corresponds to each scenario. Note the vertical connections across scenarios. These depict the NACs. In your case, the NACs will consist of:

  • 7 blocks of rows coupling variables of scenarios 1-2, 2-3, 3-4, ... 7-8 at the first stage
  • 3 blocks of rows coupling variables of scenarios 1-2, 1-3, 1-4 at the second stage
  • 3 blocks of rows coupling variables of scenarios 5-6, 6-7, 7-8 at the second stage
  • 1 block of rows coupling variables of scenarios 1-2 at the third stage
  • 1 block of rows coupling variables of scenarios 3-4 at the third stage
  • 1 block of rows coupling variables of scenarios 5-6 at the third stage
  • 1 block of rows coupling variables of scenarios 7-8 at the third stage

At the fourth stage, for each scenario we are free to decide its own variables. Decisions at the last stage are not binding for the other scenarios.

Hope this clarifies the scene a bit.

link

answered 01 Jun '14, 13:12

red0nly's gravatar image

red0nly
1675
accept rate: 16%

edited 02 Jun '14, 03:30

Your answer
toggle preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "Title")
  • image?![alt text](/path/img.jpg "Title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported

Tags:

×58

Asked: 24 May '14, 07:25

Seen: 986 times

Last updated: 02 Jun '14, 03:30

OR-Exchange! Your site for questions, answers, and announcements about operations research.