# A Review on the Performance of Linear and Mixed Integer Two-Stage Stochastic Programming Software
## 4 Benders Decomposition Enhancement Strategies
### Reducing the Number of Iterations  
The number of iterations of the L-shaped algorithm is closely related to the tightness of the LP relaxation of the first-stage problem, as well as the strength of the optimality and feasibility cuts [27]. Better candidates are computed from improvements in the MP problem, especially in the strengthening of the representation of the recourse functions. Tighter formulations can be obtained by adding multiple cuts per iteration (multi-cut reformulation [37]); as well as through the use of heuristics to eliminate inactive cuts and to select the fittest dual variables to be inserted in the MP (size management techniques).  
Complementary strategies have been developed to generate cuts that are more efficient. One alternative is the reformulation of the subproblems to select non-dominant dual solutions from the set of optimal multipliers, known as Pareto-optimal cuts [27]. Recently, [PERSON]. [38] proposed a methodology to compute bundles of covering cuts, designed to involve most of the first-stage variables and to carry as much information as possible.  
Alternative methods tighten the MP to alleviate some of the drawbacks of BD: cross decomposition, for instance, avoids the generation of low-quality solutions, while quadratic stabilization methods provide a solution for the tailing-off effect. Cross decomposition [39] combines and alternates between iterations of BD and Lagrangian decomposition to provide an additional valid lower bound of the objective function and a set of feasible deterministic solutions \((x_{\omega},y_{\omega})\in G_{\omega}\), which are used to compute Lagrangian-based cuts to strengthen the MP.  
Quadratic methods have been proposed to stabilize BD, aiming to improve the quality of the initial iterations and reduce the oscillation that occurs when the algorithm is close to the optimal solution [31]. These methods penalize the distance of the first-stage candidates to the current best solution. Popular variants include regularized decomposition [16; 40], the trust-region method [41] and level decomposition [42], which are summarized below. It should be noted that Equations (12)-(14) are all variants of the large family of bundle method, which can be seen from chapters XIV and XV of [43].  
* **Regularized decomposition (also known as proximal bundle method)** \[x_{k+1}=\operatorname*{arg\,min}_{x,\theta_{\omega}}\{c^{T}x+\sum_{\omega\in \Omega}\tau_{\omega}\theta_{\omega}+\frac{1}{2t_{k}}\|x-\hat{x}_{k}\|_{2}^{2} \quad\text{s.t.}\quad(x,\theta_{\omega})\in V_{k}\}\] (12)
* **Trust-region method** \[x_{k+1}=\operatorname*{arg\,min}_{x,\theta_{\omega}}\{c^{T}x+\sum_{\omega\in \Omega}\tau_{\omega}\theta_{\omega}\quad\text{s.t.}\quad\|x-\hat{x}_{k}\|_{2}^ {2}\leq R_{k^{\prime}}(x,\theta_{\omega})\in V_{k}\}\] (13)
* **Level decomposition method** \[x_{k+1}=\operatorname*{arg\,min}_{x,\theta_{\omega}}\{\|x-\hat{x}_{k}\|_{2}^{2} \quad\text{s.t.}\quad c^{T}x+\sum_{\omega\in\Omega}\tau_{\omega}\theta_{\omega }\leq L_{k^{\prime}}(x,\theta_{\omega})\in V_{k}\}\] (14)  
where \(t_{k}\), \(R_{k}\) and \(L_{k}\) are real-valued, iteration-dependent parameters that balance the minimization of the relaxed MP and the distance to the stability center \(\hat{x}_{k}\). \(V_{k}\) represents the feasible region of the Benders master problem at each iteration, which is defined by the optimality (9d) and feasibility cuts (9c), as well by the first-stage constraints (9b). Stabilization methods were initially introduced for BD with no integer variables; nonetheless, recent improvements have adapted the method to mixed-integer problems [31].  
Two software packages using the Benders decomposition algorithm, GAMS-DECIS [44; 45] and FORTSPP [46] are described in the benchmark in Appendix C.