Given the linear program: $Z = min_{x\geq 0}\ 2x_1 + x_2 + E_{\ k \ =\ (k_1, k_2)} \left\{\max(k_1 - x_1, 0) + \max\left\{max(k_1-x_1,0) + k_2 - x_2, 0\right\} + \max(k_1 - x_1, 0) + \max(k_2-x_2, 0)\right\}$

($k_1, k_2$ are random variables), and $x_1 + x_2\geq 1$.

Formulate the above problem into two-stage stochastic linear program with fixed recourse.

My attempt:

First, we consider all possible cases below

1st case. $k_1\geq x_1$ and $k_2\geq x_2$

$\Rightarrow Z = \min_{x\geq 0} x_1 + 2x_2 + E_{k}(k_1-x_1 + max(k_1-x_1+k_2-x_2, 0))$

$= \min_{x\geq 0} x_1 + 2x_2 + E_{k}[2(k_1-x_1) + k_2-x_2)]$ $(*)$

Now, from the constraint $x_1+x_2\geq 1$, we substract a surplus variable $x_3\geq 0$ from it to get equality: $x_1+x_2-x_3 = 1$. Then we could rewrite $(*)$ as a two-stage LP as follows:

$\min \ c^Tx + E_{k}(Q(x,k))$ where $c = (2,1, 1)$, $x = (x_1, x_2, x_3)$, and

$Q(x,k) = min_{y}\left\{q^Ty | Wy = h - Tx, y\geq 0\right\}$ where $q= (2,1)^{T}, W = (1, 1), h = (k_1, k_2)$ and $T = (1,1)$

We repeat the above process for all the other $5$ cases ($k_1\geq x_1$ and $k_2\leq x_2$ and $k_1-x_1+k_2-x_2\geq 0$, $k_1\geq x_1$ and $k_2\leq x_2$ and $k_1-x_1+k_2-x_2\leq 0$, $k_1\leq x_1$ and $k_2\leq x_2$, $k_1\leq x_1$ and $k_2\geq x_2$ and $k_1-x_1+k_2-x_2\geq 0$), and we see that for each of those cases, it is possible to write a 2-stage SLP with fixed recourse $W$. Also, some of these $5$ cases would require surplus and/or slack variables to be added to the 2nd-stage problem's constraints and objective function.

Thus, from all the $6$ possible cases, the original LP program can be formulated into a two-stage stochastic LP with fixed recourse (Q.E.D)

My question: Could someone please help let me know if my above arguments is correct, especially for the remaining 5 cases? Please help point out any mistakes you could find, as any inputs will be greatly appreciated.

  • $\begingroup$ Nobody minds helping me review my solution on this problem? $\endgroup$ – user177196 Mar 4 '18 at 15:57
  • 1
    $\begingroup$ In this case, you may add a bounty to your problem. $\endgroup$ – GNUSupporter 8964民主女神 地下教會 Mar 14 '18 at 16:31

Your Answer

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

Browse other questions tagged or ask your own question.