5
$\begingroup$

I am facing a problem understanding the L-shaped algorithm in a two-stage stochastic problem.

$$\operatorname{Min} z=100 x_1+150 x_2+E_{\xi}\left(q_1 y_1+q_2 y_2\right)$$ subject to $$ \begin{aligned} &x_1+x_2 \leq 120 \\ &6 y_1+10 y_2 \leq 60 x_1 \\ &8 y_1+5 y_2 \leq 80 x_2 \\ &x_1 \geq 40, x_2 \geq 20, y_1 \leq d_1, y_2 \leq d_2 \\ &y_1, y_2 \geq 0 \end{aligned} $$ where $\xi^T=\left(d_1, d_2, q_1, q_2\right)$ takes the values $(400,100,-20,-24)$ with probability $0.4$ and $(300,200,-24,-28)$ with probability $0.6$. Use an L-shaped algorithm and carry out one iteration.

I have the solution,

Step 1. Ignoring $\theta$, the master program is simply $z=\min \left\{100 x_1+150 x_2 \mid x_1+x_2 \leq\right.$ $\left.120, x_1 \geq 40, x_2 \geq 20\right\}$ with solution $x^1=(40,20)^T$ and $\theta^1=-\infty$. Step 3.

  • For $\xi=\xi_1$, solve the program $$ \begin{array}{r} w=\min \left\{-24 y_1-28 y_2 \mid 6 y_1+10 y_2 \leq 2400,8 y_1+5 y_2 \leq 1600,\right. \\ \left.0 \leq y_1 \leq 500,0 \leq y_2 \leq 100\right\} . \end{array} $$ The solution is $w_1=-6100, y^T=(137.5,100), \pi_1^T=(0,-3,0,-13)$.
  • For $\xi=\xi_2$, solve the program $$ \begin{array}{r} w=\min \left\{-28 y_1-32 y_2 \mid 6 y_1+10 y_2 \leq 2400,8 y_1+5 y_2 \leq 1600\right. \\ \left.0 \leq y_1 \leq 300,0 \leq y_2 \leq 300\right\} . \end{array} $$ The solution is $w_2=-8384, \quad y^T=(80,192), \quad \pi_2^T=(-2.32,-1.76$, $0,0)$. Using $h_1=(0,0,500,100)^T$ and $h_2=(0,0,300,300)^T$, one obtains $$ e_1=0.4 \cdot \pi_1^T \cdot h_1+0.6 \cdot \pi_2^T \cdot h_2=0.4 \cdot(-1300)+0.6 \cdot(0)=-520 . $$ The matrix $T$ is identical in the two scenarios. It consists of two columns $(-60,0,0,0)^T$ and $(0,-80,0,0)^T$. Thus, $$ \begin{aligned} E_1=0.4 \cdot \pi_1^T T+0.6 \cdot \pi_2^T T &=0.4(0,240)+0.6(139.2,140.8) \\ &=(83.52,180.48) \end{aligned} $$ Finally, as $x^1=(40,20)^T, w^1=-520-(83.52,180.48) \cdot x^1=-7470.4$. Thus, $w^1=-7470.4>\theta^1=-\infty$, add the cut $83.52x_1+180.48x_2+\theta ≥ −520 $

I couldn't understand the solution (Introduction to Stochastic Programming, 2nd edition. John R. Birge and Francois Louveaux. Springer, page: 185, Section: 5.1). There was no clear explanation.

What the algorithm was doing and how the steps were taken was unclear.


Update

To get the shadow price, $$\tau^T=c_B (A^B)^{-1}$$

image1

image2

Hence, I got,

$$ \begin{pmatrix}0&-24&0&-28\end{pmatrix}\begin{pmatrix}1&-0.75&0&0\\ \:\:0&0.125&0&0\\ \:\:0&-0.125&1&0\\ \:\:0&0&0&1\end{pmatrix}=\begin{pmatrix}0&-3&0&-28\end{pmatrix} $$

Where I did mistake to get the shadow price?

$\endgroup$
6
  • $\begingroup$ Any video/blog/article/book are welcome. I tried my best to get some resources where I could learn from scratch, but I failed. $\endgroup$
    – falamiw
    Commented Oct 27, 2022 at 19:53
  • $\begingroup$ what is your exact question? or are you looking for a general understanding of the L-Shaped method? This solution strictly follows the method described in Pages 182-184. It does not require the feasibility cut (equation 1.3 on page 183), but the optimality cut (equation 1.4) is necessary for the next iteration because $w^1 \geq \theta^1$ . Let me know and I might be able to write up an answer. $\endgroup$
    – mars
    Commented Oct 31, 2022 at 18:54
  • $\begingroup$ I want a general understanding of the L-shaped method. The problem is, I couldn't visualize what's the purpose and what we are doing in this method. I guess that will be enough for me. And thanks for your response. I am excited to see your solution @mars. TIA $\endgroup$
    – falamiw
    Commented Oct 31, 2022 at 18:58
  • $\begingroup$ Can you write the answer within 3 days? @mars I haven't enough reputation scores to donate after the bounty period end. I think you can write initially some hints and extend that from time to time. that is how I can give you the 50 reputation score. $\endgroup$
    – falamiw
    Commented Nov 3, 2022 at 6:20
  • $\begingroup$ my apology @falamiw. I was hoping to do it last weekend but looks like Simply op already gave a detailed answer! $\endgroup$
    – mars
    Commented Nov 7, 2022 at 13:40

1 Answer 1

2
+50
$\begingroup$

I will attempt to answer some of your questions. We can write the extensive form of the problem as:

$z = min\hspace{0.25cm} 100x_{1}+150x_{2}+\sum\limits_{s}P_{s}(q_{1,s}y_{1}+q_{2,s}y_{2})\\\\$

s.t. \begin{align} & x_{1}+x_{2} \leq 120 \\ & 6y_{1}+10y_{2} \leq 60x_{1} \\ & 8y_{1}+5y_{2} \leq 80x_{2} \\ & 0\leq y_{1} \leq d_{1,s}, 0\leq y_{2} \leq d_{2,s}, \forall s \\ & x_{1} \geq 40, x_{2} \geq 20 \\ \end{align} We are provided the following data:

Probabilty of scenarios: $P_{1} = 0.4, P_{2} = 0.6 \\\\$

$q_{1,1} = -24, q_{1,2} = -28, q_{2,1}= -28, q_{2,2} = -32\\\\$

$d_{1,1} = 500, d_{1,2} =300, d_{2,1} = 100, d_{2,2} = 300\\\\$

The extensive form simply means that we solve it as one large problem. The two set of variables bounds given by (4) would need to be set up for all the scenarios, i.e. (4) becomes:

$\\ y_{1} \leq d_{1,1}, y_{1} \leq d_{1,2}\\\\$ $y_{2} \leq d_{2,1}, y_{2} \leq d_{2,2}\\\\$

This problem has only two scenarios, so the extensive form is easy to solve. However, if the number of scenarios is large then methods such as L-shaped can be used. This requires separating the problem in to a master and sub-problems. The master problem is defined as: $\\ z = min\hspace{0.25cm} 100x_{1}+150x_{2}+\theta\\\\$

where $\theta$ is a variable that approximates subproblems.

The master problem generates a first stage decision $x$. The subproblems are the recourse problems and will take the $x$ from the master problem and then find the best recourse decisions. If all subproblems are optimal for given $x$, then optimality cut (a constraint) is added to the master problem. L-shaped method relies on an iterative procedure that solves for $x$ values without considering subproblems except through a set of cut constraints that are created and passed from subproblems to the master problem.

The matrix $T$ is the technology matrix describing the relationship between the variables $x$ and $y$ $\\ T=\begin{bmatrix} -60 & 0\\ 0 & -80\\ 0 & 0 \\ 0 & 0 \end{bmatrix}\\\\$

The matrix T contains coefficients of $x$ in the subproblem. If you rewrite constraints in the subproblem as below and create a matrix of coefficients of $x_{1}$ and $x_{2}$, this will give you T: \begin{align} & -60x_{1}+0x_{2}+6y_{1}+10y_{2} \leq 0 \tag{1}\\ & 0x_{1}-80x_{2}+8y_{1}+5y_{2} \leq 0 \tag{2}\\ & 0x_{1}+0x_{2}+y_{1} \leq d_{1,s} , \forall s\tag{3} \\ & 0x_{1}+0x_{2}+y_{2} \leq d_{2,s} , \forall s \tag{3} \end{align} The T is same in both scenarios as constraints (3) will contains $0$ as coefficient in both scenarios.

The matrix $h$ represents RHS of the uncertainty, i.e. data for $d_{1,s}$ and $d_{2,s}$: $h_{1} = \begin{bmatrix} 0\\ 0 \\ 500\\ 100 \end{bmatrix}$ , $h_{2} = \begin{bmatrix} 0\\ 0\\ 300\\ 300 \end{bmatrix}\\\\$

We start with solving the master problem considering constraint (1) only and ignoring $\theta$. We assume $\theta = -\infty$ initially. This gives $x_{1} = 40$ and $x_{2} = 20\\\\$

The values of $x$ are then substituted into constraints (2) and (3). The first subproblem is then given by: $w_{1} = min -24y_{1} - 28y_{2}$ \begin{align} & 6y_{1}+10y_{2} \leq 2400 \tag{2.1} \\ & 8y_{1}+5y_{2} \leq 1600 \tag{3.1} \\ & 0 \leq y_{1} \leq 500, 0 \leq y_{2} \leq 100 \tag{4.1} \end{align}

Similarly, the second subproblem is: $\\w_{2} = min-24y_{1}-28y_{2} \\ $ \begin{align} & 6y_{1}+10y_{2} \leq 2400 \tag{2.2} \\ & 8y_{1}+5y_{2} \leq 1600 \tag{3.2} \\ & 0 \leq y_{1} \leq 300, 0 \leq y_{2} \leq 300 \tag{4.2} \end{align} The vector $\tau$ contains the dual values of constraints and upper bounds on variables $y_{1}$ and $y_{2}$ To get the dual values, you can use Excel solver and generate the sensitivity report. It should show you the dual values or shadow prices for all of the constraints. For the first subproblem, we get: objective value $w_{1} = -6100$, $y_{1} = 137.5$, $y_{2} = 100$ and dual values $\tau^{T}_{1} = (0,-3,0-13)$

For the second subproblem, we get: objective value $w_{2} = -8384$, $y_{1} = 80.5$, $y_{2} = 192$ and dual values $\tau^{T}_{2} = (-2.32,-1.76,0,0)$

Given above solutions to the subproblems, we then calculate $e_{1}$ and $E_{1}\\\\$

$e_{1} = \sum\limits_{s}P_{s} \tau^{T}_{s}h_{k} = -520\\\\$

$E_{1} = \sum\limits_{s}P_{s} \tau^{T}_{s}T_{k} = (83.52,180.48)\\\\$ $\\ w^{1} = e_{1} - E_{1}x = -520 - (83.52x_{1}+180.48x_{2})=-520 - (83.52*40+180.48*20) = -7470.4\\\\$ As $w^{1} = -7470.4 > \theta = -\infty$ add a cut (constraint) to the master problem: $\\83.52x_{1}+180.48x_{2}+\theta \geq -520\\\\$

This constraint is defined as $w^{v} = e_{s+1} - E_{s+1}x^{v}$ in the book. You repeat the process with this additional constraint added to the master problem, finding values of $x$ in the master problem and substituting values of $x$ to subproblems. These iterations are repeated until the difference between $w_{k}$ as defined above and $\theta$ is within a tolerance- in the example the convergence is exact.

I suggest reading about linear programming duality, to understand how these cuts approximates the recourse function.

$\endgroup$
5
  • $\begingroup$ Thank you very much @Simplyop. Everything makes sense except how you construct the technology matrix $T$ and vector $\tau$ like I guess $T(\omega)x+W(\omega)y=h(\omega)$ is the standard form where $T$ is only considered for $x$. Did you mean that? Could you explain them a little bit? I will accept your answer after reading the answer for some time. Thanks again. $\endgroup$
    – falamiw
    Commented Nov 4, 2022 at 9:54
  • $\begingroup$ I calculate the $\tau$ vector and got $\tau_1^T=\begin{pmatrix}0&-3&0&-28\end{pmatrix}$. Where I do wrong? @Simplyop $\endgroup$
    – falamiw
    Commented Nov 5, 2022 at 18:07
  • $\begingroup$ I have added an explanation of how to construct the matrix T, and also the vector of duals $\tau$. I can't comment on why you get different results for duals-most likely you have made an error $\endgroup$
    – Jonn
    Commented Nov 5, 2022 at 20:36
  • $\begingroup$ I use simplex method to solve the problem by using online calculator. $\endgroup$
    – falamiw
    Commented Nov 6, 2022 at 2:19
  • $\begingroup$ I update the question and add the snippet of my calculation. Could you please check them and say me where I did wrong. Again, Thank you very much @Simplyop $\endgroup$
    – falamiw
    Commented Nov 6, 2022 at 2:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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