2
$\begingroup$

I am having a hard time understanding the very first example in "A Tutorial on Stochastic Programming".

More specifically the authors show that one can formulate the stochastic variant of (1.2) with Eq (1.8).

My question:

How should one interpret (1.8) (i.e. how do the new inequalities allow us to explore two different scenarios in the problem?)

The deterministic problem

enter image description here enter image description here

Stochastic re-formulation

enter image description here enter image description here

$\endgroup$
0
2
$\begingroup$

(1.8) is a simple reformulation of the deterministic LP (1.2) It's still a deterministic LP. This may be somewhat confusing since the authors are going back forth between a deterministic LP formulation (assuming that $d$ is known) and a stochastic LP formulation (in which we're minimizing the expected value over random values of $d$.) See (1.9) for the expected value formulation corresponding to the deterministic $d$ formulation in (1.8).

$\endgroup$
6
  • $\begingroup$ Thank you Brian! I understand it's still a deterministic LP, what I was/am struggling with is how the new variable $t$ and the new constraints work (i.e. what does $t$ represent, and how do these inequalities help us explore the two scenarios mentioned?) $\endgroup$ – Josh Jun 28 '16 at 17:43
  • 1
    $\begingroup$ This is a standard technique in deterministic LP formulation: You can minimize $\max(a,b)$ by minimizing $t$ subject to the constraints $t \geq a$ and $t \geq b$. Here $t$ is an auxilliary variable whose value ends up being the maximum of $a$ and $b$. $\endgroup$ – Brian Borchers Jun 28 '16 at 17:46
  • $\begingroup$ Thanks! That makes sense now. And how about the equivalence between (1.1) and (1.3)? I also fail that .. $\endgroup$ – Josh Jun 28 '16 at 18:51
  • 1
    $\begingroup$ Well, either $x \geq d$ (with $[x-d]_{+}=x-d$ and $[d-x]_{+}=0$) or $x<d$ (with $[d-x]_{+}=d-x$ and $[x-d]_{+}=0$.) In the first case where $x \geq d$, the value that you want is $cx+h(x-d)$. In the second where $x<d$, the value that you want is $cx+b(d-x)$. So, you take the maximum of $cx+h(x-d)$ and $cx+b(d-x)$. $\endgroup$ – Brian Borchers Jun 28 '16 at 20:02
  • 1
    $\begingroup$ The value of the expression in (1.1) is exactly $cx+h(x-d)$ if $x\geq d$, and the value is $cx+b(d-x)$ if $x < d$. Furthermore, if $x \geq d$, then $cx+h(x-d) \geq cx+b(d-x)$ (keep in mind that $h$ and $b$ are positive.) On the other hand, $x<d$, then $cx+b(d-x) \geq cx+h(x-d)$. $\endgroup$ – Brian Borchers Jun 28 '16 at 20:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.