# A Review on the Performance of Linear and Mixed Integer Two-Stage Stochastic Programming Software
## 3 L-Shaped Algorithm/Benders Decomposition  
If the second-stage variables are all continuous (i.e., \(Y=\left\{y:y_{j}\geq 0\ \forall j\in I\right\}\)), problem (\(P\)) can be solved with Benders decomposition. Benders decomposition (\(BD\)) was originally developed in 1962 by [PERSON] [19] to solve large-scale mixed-integer linear problems (MILP) with complicating variables. This concept has been extended to solve a broader range of optimization problems [20], including multistage, bilevel, and nonlinear programming. When applied to stochastic problems, it is commonly referred to as the L-shaped algorithm [7]. The L-shaped algorithm partitions the deterministic formulation (\(P\)) into multiple problems: (i) a master problem (\(MP\)) that contains all the first-stage constraints and variables, which can be mixed integer; and (ii) a collection of subproblems that include corrective future actions for the given first-stage solution. The master problem (\(MP\)) is derived from the projection of (\(P\)) on the variables \(x\):  
\[(MP) \min_{x} TC=c^{T}x+Q(x)\] (4a) s.t. \[Ax\leq b \tag{4b}\] \[x\in X \tag{4c}\]  
where \(Q(x)=\sum_{\omega\in\Omega}\tau_{\omega}\theta_{\omega}(x)\) is defined as the recourse function (or expected second-stage value function); and \(\theta_{\omega}(x)\) is defined by the primal second-stage program for scenario \(\omega\), \((BSPp_{\omega})\),  
\[(BSPp_{\omega}) \theta_{\omega}(x)=\min_{y_{\omega}}\ \ d_{\omega}^{T}y_{\omega}\] (5a) s.t \[W_{\omega}y_{\omega}\leq h_{\omega}-T_{\omega}x \tag{5b}\] \[y_{\omega}\geq 0 \tag{5c}\]  
The recourse functions \(\theta_{\omega}(x)\) and \(Q(x)\) are convex, differentiable, and piece-wise linear, characteristics that are exploited in the BD method [1]. These conditions do not hold when integer variables are included in the second-stage program. For the case of integer recourse, a logic-based Benders framework [21], second-stage convexificationtechniques [22; 23; 24], specialized branch-and-bound schemes [25; 26] or dual decomposition methods [16] may be applied to solve large stochastic problems. In this section, we only focus on Benders decomposition for SP with continuous second-stage variables. Formulation (\(BSPp_{\omega}\)) is a linear program for any given feasible value of \(x\). By the strong duality theorem, the second-stage program is equivalent to its dual (\(BSPd_{\omega}\)) if (\(BSPp_{\omega}\)) is feasible and bounded. Vector \(\pi_{\omega}\) represents the Lagrangian multipliers associated with the second-stage constraints given by Equation (5b):  
\[(BSPd_{\omega}) \theta_{\omega}(x)=\underset{\pi_{\omega}}{\text{min}}\ \ (h_{\omega}-T_{ \omega}x)^{T}\pi_{\omega}\] (6a) s.t. \[W_{\omega}^{T}\pi_{\omega}\leq d_{\omega} \tag{6b}\] \[\pi_{\omega}\geq 0 \tag{6c}\]  
BD introduces a set of piece-wise linear approximations of the recourse function in the problem MP, known as optimality cuts, which are built from dual solutions of the second-stage program. It is important to highlight that the dual feasible region does not depend on the value of \(x\). Thus, the exact representation of the expected cost consists of the computation of all the extreme points of problems (\(BSPd_{\omega}\)). However, the second-stage program may not be feasible for some values of \(x\). BD enforces second-stage constraints (5b) by adding feasibility cuts, which are valid inequalities that exclude infeasible first-stage solutions from the MP. Subproblem feasibility is evaluated by solving the following recourse reformulation for scenario \(\omega\):  
\[V_{\omega}(x)=\underset{y_{\omega},y^{-}}{\text{min}}\ \ e^{T}v^{-}\] (7a) s.t. \[Ax\leq b \tag{4b}\]0 \[Ax\leq b \tag{4b}\]1  
where \(e\in\mathbb{R}^{m_{2}}\) is a vector with all-1 entries, and \(v^{-}\in\mathbb{R}^{m_{2}}\) is the slack of constraints (5b). The objective function \(V_{\omega}(x)\) measures the amount by which these constraints are violated; thus, if \(V_{\omega}(x)\) equals zero, it implies that the original subproblem (5) is feasible.