# A Review on the Performance of Linear and Mixed Integer Two-Stage Stochastic Programming Software
## 3 L-Shaped Algorithm/Benders Decomposition
To derive feasibility cuts in terms of \(x\), BD considers the dual of problem (7) to generate an expression equivalent to Equation (7a). The optimal solution \(\mu\in\mathbb{R}^{m_{2}}\) of the dual feasibility problem (8) corresponds to one of the extreme rays (or directions) of the recourse subproblem (6):  
\[Ax\leq b \tag{4b}\]2 (8a) s.t. \[Ax\leq b \tag{4b}\]3 \[Ax\leq b \tag{4b}\]4  
The master problem (4) is linearized by (i) substituting function \(Q(x)\) with the weighted sum of the future cost estimation (6a), and (ii) applying feasibility cuts as needed. This reformulation is referred to as the multi-cut Benders master problem (BMP),  
\[Ax\leq b \tag{4b}\]5 (9a) s.t. \[Ax\leq b \tag{4b}\]6 \[Ax\leq b \tag{4b}\]7 (9c) \[Ax\leq b \tag{4b}\]8  
where variables \(\theta_{\omega}\in\mathbb{R}^{|\Omega|}\) represent the outer linearization of the second-stage cost \(\theta_{\omega}(x)\). Parameters \(\pi_{\omega}^{k}\) and \(\tilde{\mu}_{j}\) represent the extreme points and rays from the dual form of the recourse program (\(BSPd_{\omega}\)), which are stored in sets \(E\) and \(K\), respectively. Constraints (9c)and (9d) denote the feasibility and optimality cuts, \(j\in E\) and \(k\in K\) respectively. Matrices \(h_{j}\) and \(T_{j}\) correspond to the matrices \(h_{\omega}\) and \(T_{\omega}\) for the scenario where a feasibility cut can be found. The complete enumeration of the extreme points and rays of the dual second-stage program is impractical, if not impossible. Instead, the L-shaped algorithm relaxes the MP by initially considering a subset of the optimality and feasibility cuts. BD iteratively solves the relaxed problem to generate a candidate solution for the first-stage variables (\(\bar{x}\)), and then solves the collection of scenarios subproblems at fixed \(\bar{x}\) to generate a new group of optimality or feasibility cuts. This process is repeated until the optimal solution is found [26]. The optimal solution of the relaxed Benders master problem provides a valid lower estimation (\(TC_{d}\)) of the optimal total cost, TC. On the other hand, the solution of the second-stage programs (\(BSPd_{\omega}\)) at feasible \(\bar{x}\) yields an upper bound of the original objective function (\(TC_{p}\)), given by Equation (10). The solution procedure terminates when the difference between the bounds is closed, as implied by Equation (11). Algorithm 1 summarizes the procedure. \[Ax\leq b \tag{4b}\]9  
\[x\in X \tag{4c}\]0  
```
1 Set \(k\longleftarrow 0,z_{LB}\longleftarrow-\infty,z_{UB}\longleftarrow\infty,x^{k} \longleftarrow x_{o}\) and \(\epsilon>0\)while\(k<k_{max}\)do
2 SOLVE (6) to obtain \(\theta_{\omega}(x^{k})\) and \(\pi_{\omega}^{k}\) for given \(x^{k}\) for all \(\omega\in\Omega\)ifall subproblems (6) are feasiblethen
3 ADD new optimality cuts (9d) corresponding to \(\pi_{\omega}^{k}\) for all \(\omega\in\Omega\) compute \(TC_{p}\) from \(\theta(x^{k})\) and \(x^{k}\)if\(TC_{p}<z_{UB}\)then
4\(z_{UB}\longleftarrow TC_{p}\) (upper bound) \(x^{*}\longleftarrow x^{k}\)
5
6 else
7 SOLVE (8) to obtain \(\mu\) for given \(x^{j}\) and infeasible scenario \(j\in\Omega\)
8 ADD new feasibility cut (9c) corresponding to \(\mu\)
9 SOLVE (9) to obtain \((x^{k+1},\theta_{\omega}^{k+1})\) and \(TC_{d}\)if\(z_{LB}<TC_{d}\)then
10\(z_{LB}\longleftarrow TC_{d}\) (lower bound) \(\left(z_{UB}-z_{LB}\right)/\big{(}\max(|z_{UB}|,|z_{LB}|)+1e-10\big{)}<\epsilon\)then
11 break
12 Set \(k\longleftarrow k+1\)returnoptimal solution \(x^{*}\) and \(z_{LB}\)
```  
**Algorithm 1**Multi-cut Benders decomposition  
The L-shaped method is summarized in Algorithm 1. It is initialized with a guess of the first-stage solution \(x_{o}\) and considers two stopping criteria: (i) the optimality tolerance \(\epsilon\) that limits the relative gap between the dual \((z_{LB})\) and primal \((z_{UB})\) bounds of the objective function \((TC)\), and (ii) the maximum number of allowed iterations \((k_{max})\).