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

Improve this question
$\endgroup$
0

1 Answer 1

Reset to default
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).

Improve this answer
$\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, 2016 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, 2016 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, 2016 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, 2016 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, 2016 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.