Consider a scenario-tree, with 4 stages. The first stage is the root node. This root node has two children. So the second stage has 2 nodes. Each node of the scenario tree has 2 children. So in total we have: 15 nodes.

How many nodes will the deterministic equivalent of this have?

asked 25 May '14, 17:05

spyimp's gravatar image

accept rate: 0%

Stage is a reserved term in SP for decision-making milestones. I think you mean you have four parameters. Is that correct?

(26 May '14, 06:15) Ehsan ♦

Yes indeed. I do not mean decision milestones. I mean realizations of the uncertain parameter, usually illustrated with a circle.

So my tree has one uncertain parameter. And again, it has 15 circles (nodes). Ie it has 4 epochs. The first epoch has 1 root node. The second epoch has the 2 children of the root node. The third epoch has all the children of the previous epoch. And similarly for the fourth epoch. So the fourth epoch has 8 nodes.

My question is : if I decide to make the deterministic equivalent of this - how many circles (ie nodes) ie realizetions of the uncertain parameter will be ?

(26 May '14, 07:26) spyimp

I'm not sure I understand your scenario tree structure. Therefore, I would give a hypothetical example to help you understand the reasoning procedure. Let's assume your problem has three random parameters, each with two possible outcomes (let's say zero or one). First, note that the root node doe not represent any of the random parameters, and each column after the root node represents a random parameter. Consequently, columns #1, #2, and #3 would have 2, 4, and 8 child nodes. Ultimately, the probability space space, \(\Omega\) would have eight scenarios (equal to the number of nodes in the last column). Assuming that each parameters takes either zero or one with equal probability, the probability of each scenario would be \(0.5 \times 0.5 \times 0.5 = 0.125\).

$$ \Omega = \begin{Bmatrix} \xi_1=(0, 0, 0),p_1 = 0.125\\ \xi_2=(0, 0, 1),p_2 = 0.125\\ \xi_3=(0, 1, 0),p_3 = 0.125\\ \xi_4=(0, 1, 1),p_4 = 0.125\\ \xi_5=(1, 0, 0),p_5 = 0.125\\ \xi_6=(1, 0, 1),p_6 = 0.125\\ \xi_7=(1, 1, 0),p_7 = 0.125\\ \xi_8=(1, 1, 1),p_8 = 0.125 \end{Bmatrix} $$


answered 26 May '14, 08:17

Ehsan's gravatar image

Ehsan ♦
accept rate: 16%

edited 26 May '14, 08:28

I totally agree with everything.

So we can say ' minimize the expected cost under the uncertainty in ξ' , and we can solve this problem using stochastic programming.

So the question is : How would the probability space look for the 'deterministic equivalent' problem ?

(26 May '14, 14:32) spyimp

Any clues about the deterministic equivalent ?

(27 May '14, 23:06) spyimp

That's how the probability space looks for the DEP. To write the DEP, you have to replicate each constraint set with randomness for each scenario. Also, each objective function term with randomness would be summed over scenarios. If you don't know how to write the DEP, you might consult a book on SP. For example, the farmer example in Birge and Louveaux is a famous one. It's available in many lecture notes on the web (e.g., see here).

(28 May '14, 04:22) Ehsan ♦

So the DEP will be as follows:

  1. The scenario tree will have 4 columns , each having 1 child node.
  2. The constraints will be of the form of (Ax+b)p1 +(Ax+b)*p2 +... <= C , whereas in the stochastic program I had Ax+b<=C.

What do you think ?

(30 May '14, 14:17) spyimp
  1. For four random parameter, the tree would have four columns. One child node per column means that the corresponding random parameter takes only one value (i.e., it's certain). What you described means that there is four certain parameters (i.e., just one scenario).

  2. Assuming \(p_i\) denotes probability of scenarios, what you've written has no specific meaning. Suppose you have different \(\left \{ A,b,C \right \}\) for each scenario. The stochastic constraint \(AX+DY+b\leq C\) should be replicated for each scenario (i.e., \(A_s X_s + b_s \leq C_s - DY, \forall s \in S\)).

(30 May '14, 14:40) Ehsan ♦
Your answer
toggle preview

Follow this question

By Email:

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



Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text]( "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



Asked: 25 May '14, 17:05

Seen: 2,852 times

Last updated: 31 May '14, 03:31

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