Understanding L-shaped algorithm in a two-stage stochastic problem

Question

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}$$

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?

Answer 1

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.