# The Benders by batch algorithm: design and stabilization of an enhanced algorithm to solve multicut Benders reformulation of two-stage stochastic programs

Xavier Blanchot, François Clautiaux, Boris Detienne, Aurélien Froger, Manuel Ruiz

► To cite this version:

Xavier Blanchot, François Clautiaux, Boris Detienne, Aurélien Froger, Manuel Ruiz. The Benders by batch algorithm: design and stabilization of an enhanced algorithm to solve multicut Benders reformulation of two-stage stochastic programs. European Journal of Operational Research, In press, 10.1016/j.ejor.2023.01.004. hal-03286135v4

HAL Id: hal-03286135

https://hal.science/hal-03286135v4

Submitted on 15 Dec 2022

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# The Benders by batch algorithm: design and stabilization of an enhanced algorithm to solve multicut Benders reformulation of two-stage stochastic programs

Xavier Blanchot<fnref n="1" />,<fnref n="2" />, François Clautiaux<fnref n="1" />, Boris Detienne<fnref n="1" />, Aurélien Froger<fnref n="1" />
Manuel Ruiz<fnref n="2" />

## Abstract

This paper introduces a new exact algorithm to solve two-stage stochastic linear programs. Based on the multicut Benders reformulation of such problems, with one subproblem for each scenario, this method relies on a partition of the subproblems into batches. The key idea is to solve at most iterations only a small proportion of the subproblems by detecting as soon as possible that a first-stage candidate solution cannot be proven optimal. We also propose a general framework to stabilize our algorithm, and show its finite convergence and exact behavior. We report an extensive computational study on large-scale instances of stochastic optimization literature that shows the efficiency of the proposed algorithm compared to nine alternative algorithms from the literature. We also obtain significant additional computational time savings using the primal stabilization schemes.

**Keywords**— Large-scale optimization, Benders Decomposition, Stochastic programming, Cut aggregation

## 1 Introduction

Large-scale two-stage stochastic linear programs arise in many applications such as network design, telecommunication network planning, air freight scheduling, power generation planning. In such problems, first-stage decisions (also called here-and-know decisions) are to be made before knowing the value taken by random parameters, then second-stage decisions (also called wait-and-see decisions) are made after observing the value taken by each random parameter. In practice, many approaches introduced to solve such problems are based on decomposition techniques (Ruszczyński, 1997).

In this paper, we study two-stage stochastic linear programs. We assume that the probability distribution is given by a finite set of scenarios and focus on problems with a large number of scenarios. We consider the following linear program with a scenario block structure:

$$ \left\{ \begin{array}{l} \min c^\top x + \sum_{s \in S} p_s g_s^\top y_s \\ \text{s.t. : } W_s y_s = d_s - T_s x, \quad \forall s \in S \\ \phantom{\text{s.t. : }} y_s \in \mathbb{R}_+^{n_2}, \quad \forall s \in S \\ \phantom{\text{s.t. : }} x \in X \end{array} \right. \qquad (1) $$

where $x \in \mathbb{R}^{n_1}$, $c \in \mathbb{R}^{n_1}$, $S$ is a finite set of scenarios, $p_s \in \mathbb{R}^+$ is a positive weight associated with a scenario $s \in S$ (e.g., a probability), $g_s \in \mathbb{R}^{n_2}$, $W_s \in \mathbb{R}^{m \times n_2}$, $T_s \in \mathbb{R}^{m \times n_1}$, $d_s \in \mathbb{R}^m$, and $X \subset \mathbb{R}^{n_1}$ is a polyhedral set. Variables $x$ are called first-stage variables and variables $y_s$ are called second-stage variables or recourse variables. Problem (1) is called the extensive formulation of a two-stage stochastic problem.

Email addresses: xavier.blanchot@u-bordeaux.fr (Xavier Blanchot), francois.clautiaux@math.u-bordeaux.fr (François Clautiaux), boris-detienne@math.u-bordeaux.fr (Boris Detienne), aurelien.froger@math.u-bordeaux.fr (Aurélien Froger), manuel.ruiz@rte-france.com (Manuel Ruiz)

<footnote n="1">¹ Université de Bordeaux, CNRS, INRIA, Bordeaux INP, IMB, UMR 5251, Talence, France</footnote>

<footnote n="2">² RTE, Paris La Défense, France</footnote>
When the number of scenarios is large, problem (1) becomes intractable for LP solvers. Its reformulation as

$$ \left\{ \begin{array}{l} \min c^\top x + \sum_{s \in S} p_s \phi(x, s) \\ \text{s.t. } x \in X \end{array} \right. \qquad (2) $$

where for every $s \in S$ and every $x \in X$,

$$ \phi(x, s) = \begin{cases} \min_y g_s^\top y \\ \text{s.t. } W_s y = d_s - T_s x \\ y \in \mathbb{R}_+^{n_2} \end{cases} \qquad (3) $$

makes the use of decomposition methods attractive. If we fix the first-stage variables to $\hat{x} \in X$, then the resulting problem becomes separable according to the scenarios. We denote by $(SP(\hat{x}, s))$ the subproblem associated with a scenario $s \in S$ and by $\phi(\hat{x}, s)$ its value.

Let $\Pi_s = \{\pi \in \mathbb{R}^m | W_s^\top \pi \le g_s\}$ be the polyhedron associated with the dual of $(SP(\hat{x}, s))$, which does not depend on first-stage variables $x$. We denote by $\text{Rays}(\Pi_s)$ the set of extreme rays of $\Pi_s$, and by $\text{Vert}(\Pi_s)$ the set of extreme points of $\Pi_s$. By Farkas' Lemma, we can write an expression of the domain of $\phi(\cdot, s)$ as $\text{dom}(\phi(\cdot, s)) = \{x \in \mathbb{R}^{n_1} | r_s^\top(d_s - T_s x) \le 0, \forall r_s \in \text{Rays}(\Pi_s)\}$. Then we can replace in formulation (2) the polyhedral mapping $x \mapsto \phi(x, s)$ by its outer linearization on its domain. Using an epigraph variable $\theta_s$ for every $s \in S$, we obtain the multicut Benders reformulation (Birge and Louveaux, 1988) of problem (1):

$$ \left\{ \begin{array}{l} \min_{x, \theta} c^\top x + \sum_{s \in S} p_s \theta_s \\ \text{s.t. : } \theta_s \ge \pi_s^\top (d_s - T_s x), \quad \forall s \in S, \quad \forall \pi_s \in \text{Vert}(\Pi_s) \quad (i) \\ 0 \ge r_s^\top (d_s - T_s x), \quad \forall s \in S, \quad \forall r_s \in \text{Rays}(\Pi_s) \quad (ii) \\ x \in X, \theta \in \mathbb{R}^{\text{card}(S)} \end{array} \right. $$

Constraints (i) are called optimality cuts, and constraints (ii), feasibility cuts. Without loss of generality, we assume that the problem has relatively complete recourse (i.e., $X \subset \text{dom}(\phi(\cdot, s))$ for every scenario $s \in S$), meaning that every subproblem is feasible for every $x \in X$. As a result, only optimality cuts are required in the Benders decomposition algorithm, and every $x \in X$ defines an upper bound on the optimal value of the problem. Every two-stage linear stochastic program can be reformulated to a problem satisfying this hypothesis by introducing slack variables with large enough coefficients in the objective function (see e.g. (Bodur and Luedtke, 2022) or (Shapiro and Nemirovski, 2005)).

The classic multicut Benders decomposition algorithm (see Algorithm 1 in the case of relatively complete recourse) consists of the relaxation of constraints (i) and (ii) and an iterative scheme to add them until convergence is proven. As the number of extreme rays and vertices of polyhedra $\Pi_s$ is finite, for every $s \in S$, the total number of optimality and feasibility cuts is finite. Then, this algorithm converges in a finite number of iterations. The relaxation of (4) at iteration $k$ of the algorithm is called the relaxed master program, denoted by $(RMP)^{(k)}$ and its solution is denoted by $(\tilde{x}^{(k)}, (\tilde{\theta}_s^{(k)})_{s \in S})$.

<caption>**Algorithm 1:** Classic multicut Benders decomposition algorithm</caption>

Parameters: $\epsilon \ge 0$ the selected optimality gap
1 Initialization: $k \leftarrow 0, UB^{(0)} \leftarrow +\infty, LB^{(0)} \leftarrow -\infty$
2 while $UB^{(k)} > LB^{(k)} + \epsilon$ do
3 $k \leftarrow k + 1$
4 Solve $(RMP)^{(k)}$ and retrieve $(\tilde{x}^{(k)}, (\tilde{\theta}_s^{(k)})_{s \in S})$
5 $LB^{(k)} \leftarrow c^\top \tilde{x}^{(k)} + \sum_{s \in S} p_s \tilde{\theta}_s^{(k)}$
6 for $s \in S$ do
7 Solve $(SP(\tilde{x}^{(k)}, s))$ and retrieve $\pi_s \in \text{Vert}(\Pi_s)$
8 Add $\theta_s \ge \pi_s^\top (d_s - T_s x)$ to $(RMP)^{(k)}$
9 $UB^{(k)} \leftarrow \min(UB^{(k-1)}, c^\top \tilde{x}^{(k)} + \sum_{s \in S} p_s \pi_s^\top (d_s - T_s \tilde{x}^{(k)}))$
10 $(RMP)^{(k+1)} \leftarrow (RMP)^{(k)}$
11 Return $\tilde{x}^{(k)}$

When the total number of subproblems is large, solving all the subproblems at each iteration, like in Algorithm 1,
can be time-consuming. To overcome this issue, we introduce a new exact algorithm to solve problem (1), referred to as the *Benders by batch* algorithm. The term *batch* refers to a given fixed partition of all subproblems into separate batches. We propose a new stopping criterion that allows us to identify that a solution cannot be proven optimal at the current iteration without necessarily having to solve all the subproblems. As a result, only a few subproblems are generally solved at a first-stage candidate solution. To prevent introducing too many cuts in the relaxed master program, the algorithm can use partial cut aggregation, thus generating a single cut from all subproblems that belong to an identical batch. If the number of batches is equal to one, the Benders by batch algorithm is equivalent to the classic Benders decomposition algorithm (multicut or monocut, depending on the use of cut aggregation). Several existing methods based on similar ideas require fixed recourse ($W_s = W, \forall s \in S$ in problem (1)) (Oliveira et al., 2011) and deterministic second-stage objective function ($g_s = g, \forall s \in S$ in problem (1)) (Wets, 1983; Dantzig and Infanger, 1991; Higle and Sen, 1991). Moreover, some of them do not have finite convergence (Higle and Sen, 1991), or are not exact (Dantzig and Infanger, 1991). The method proposed in this work is exact, has finite convergence, and does not require any assumption on the value of the random parameters $g_s, W_s, d_s, T_s$ in problem (1).

We also show how to stabilize the proposed algorithm. As the classical primal stabilization methods of the literature (Ben-Ameur and Neto, 2007; Lemaréchal et al., 1995) are designed for algorithms which solve all the subproblems at each iteration, it is not possible to apply them directly. They require the actual value of the recourse function at each iteration, at least to evaluate their stopping criterion. We therefore propose a generic framework to stabilize the Benders by batch algorithm and prove the finite convergence and exact behavior of the stabilized algorithm. Our algorithm is also compatible with classical dual stabilization techniques (Magnanti and Wong, 1981; Papadakos, 2008; Sherali and Lunday, 2013).

The contributions of the paper can be summarized as follows:

* We propose a new exact algorithm to solve the Benders reformulation of two-stage linear stochastic programs with finite probability distribution. This algorithm is based on a sequential stopping criterion relying on a partition of the subproblems. This stopping criterion allows the algorithm to solve only a few subproblems at most iterations by detecting that a first-stage candidate solution cannot be proven optimal early in the subproblems' solution process.

* We develop a general framework to apply primal stabilization to the Benders by batch algorithm, as classical primal stabilization methods cannot be applied if all the subproblems are not solved at each iteration. We state sufficient conditions for the stabilized algorithm to be exact and have finite convergence and provide two effective primal stabilization schemes.

* We perform an extensive numerical study showing the efficiency of the developed algorithm on some classical stochastic instances from the literature compared to implementations of the classic monocut and multicut Benders decomposition algorithm, with and without in-out stabilization, the static multicut aggregation approach of Trukhanov et al. (2010), and a level bundle method.

The paper is organized as follows. Section 2 reviews the literature on acceleration techniques for Benders decomposition, with a focus on the stochastic case, and on closely related methods. In section 3, we present the Benders by batch algorithm. Section 4 presents a general framework to stabilize our algorithm and two stabilization schemes: the first one based on the classical in-out separation scheme, and the second one based on exponential moving averages. Section 5 presents extensive computational experiments. Then, section 6 concludes and outlines perspectives.

## 2 Related work

The classic Benders decomposition algorithm can be slow to converge. Researchers have proposed several techniques to accelerate its convergence. We first present classical primal and dual stabilization methods, which are the most widespread and general methods to accelerate the Benders decomposition algorithm. We then present different methods specific to stochastic programming, with a focus on methods that avoid systematically solving all the subproblems.

A well-known downside of cutting-plane methods, and therefore of the Benders decomposition algorithm, is the oscillation of the first-stage variables (Nesterov, 2004; Pessoa et al., 2013). Because of the relaxation of all the constraints related to the subproblems, the solutions of the relaxed master programs might be far from the optimal solution to the initial problem. This might lead to a large amount of time spent in evaluating poor quality solutions in the early iterations. To our knowledge, successful methods proposed so far to avoid the presented drawbacks of cutting-plane methods are either inspired by bundle methods (Zverovich et al., 2012; Linderoth and Wright, 2003; Wolf et al., 2014),
or by in-out separation approaches (Ben-Ameur and Neto, 2007). Those methods try to restrict the search of an optimal solution to points close to a given first-stage solution. This solution is called stability center in the case of bundle methods, or in-point in the case of in-out stabilization. On the one hand, many authors proposed quadratic stabilization techniques, such as Ruszczyński (1986), who added a quadratic proximal term in the objective function of the relaxed master program, or Zverovich et al. (2012), Wolf et al. (2014) and van Ackooij et al. (2017), who used quadratic level stabilizations. Linderoth and Wright (2003) used a trust-region bundle method and proposed to use the infinity norm with an effective asynchronous parallelized framework. On the other hand, the in-out separation scheme performs a linear search between the in-point and the solution to the relaxed master program, and it can rely on the practical efficiency of linear programming solvers. The in-out separation approach has been applied successfully in a cutting-plane algorithm to solve a survivable network design problem (Ben-Ameur and Neto, 2007), in column generation (Pessoa et al., 2013), in a branch-and-cut algorithm based on a Benders decomposition approach to solve facility location problems (Fischetti et al., 2016), and in a cutting-plane algorithm applied to disjunctive optimization (Fischetti and Salvagnin, 2010).

Another family of acceleration techniques focuses on the quality of the optimality cuts. The polyhedral structure of the second-stage function implies a degeneracy of the dual subproblem. In the singular points of this function, many equivalent extreme dual solutions exist for the subproblem, each one defining a different optimality cut. The choice of a “good” dual solution can improve dramatically the convergence of the algorithm. Magnanti and Wong (1981) proposed to solve the dual of the subproblem twice in order to find the solution which maximizes the objective function at a fixed core point of the master problem. A different choice of the core point leads to a different cut. A cut derived in this framework is called a *Pareto-optimal cut*. Papadakos (2008) proposed a less restrictive way to choose the core point, and a practical framework to update it. Sherali and Lunday (2013) improved the method, bypassing the need to solve the subproblem twice.

In the case of stochastic programming, formulations rely either on one epigraph variable for every subproblem (see formulation (4)) or on a single epigraph variable for all the subproblems, also called *L-shaped method* (Van Slyke and Wets, 1969). The former formulation is referred to as the *multicut Benders reformulation*, whereas the latter is known as the *monocut Benders reformulation*. The *multicut Benders reformulation* was introduced by Birge and Louveaux (1988). You and Grossmann (2013) showed dramatic improvement both on computing time and number of iterations due to the *multicut reformulation* on two supply chain planning problems. The *multicut version* provides a tighter approximation of the second-stage function, and converges in less iterations than the *monocut one*. However the *master problem* might suffer from the large number of cuts added through the optimization process, and thus might become time-consuming to solve. The decision between using either the *monocut* or the *multicut version* of the algorithm is not straightforward. As far as we know, one of the major improvements proposed to improve pure *multicut Benders decomposition* was to use massive parallelization (Linderoth and Wright, 2003). Trukhanov et al. (2010) proposed a framework to aggregate some optimality cuts with the aim of finding a compromise between the *monocut* and pure *multicut* versions of the algorithm. Wolf et al. (2014) proposed to maintain both a *multicut model* and a *monocut model*. When, for a given first-stage solution $x$, they observe that the *monocut approximation* of the recourse function is substantially lower than the *multicut approximation*, they aggregate the active cuts from the *multicut model* to generate a cut in the *monocut one*. As this cut has, at $x$, the value given by the *multicut model*, this cut improves the *monocut approximation*, without having to solve any subproblem. They embed their algorithm in the general concept of *oracles with on-demand accuracy* (de Oliveira and Sagastizábal, 2014). The concept of *oracles with on-demand accuracy* might embed the core idea of the *Benders by batch algorithm* presented in this work. However, it requires that the oracle gives a subgradient which belongs to an approximate subdifferential of the objective function at each iteration which is not required in the *Benders by batch algorithm*, and may not be satisfied in the general case.

One of the major bottlenecks faced to solve two-stage stochastic programs is the large number of subproblems to solve at each iteration to compute *Benders cuts*. Researchers proposed some methods to avoid solving all the subproblems at each iteration of the *Benders decomposition algorithm*. In the case of stochastic problems with fixed recourse (i.e., $W_s = W$ for every $s \in S$ in problem (1)) where the second-stage objective function does not depend on the uncertainty (i.e., $g_s = g$ for every $s \in S$ in problem (1)), some authors, such as (Wets, 1983; Higle and Sen, 1991; Dantzig and Infanger, 1991; Infanger, 1992), used the fact that the duals of all the subproblems share the same constraint polyhedron: $\Pi_s = \Pi$, for every $s \in S$. Given an optimal dual solution $\pi_{s0}$ to a subproblem $s0 \in S$, *bunching* (Wets, 1983) consists in checking the primal feasibility of this solution for the other subproblems. This solution is optimal for all the subproblems for which this solution is primal feasible, and there is no need to solve them. Dantzig and Infanger (1991) and Infanger (1992) proposed to use *importance sampling* to compute a good approximation of the expected cut in the *monocut* formulation with only a few scenarios. Although the resulting algorithm is not exact, they report results with small confidence intervals on the objective value. Higle and Sen (1991) introduced *stochastic decomposition*. The method only
solves a few subproblems at each iteration and computes cuts with all the dual solutions obtained at previous iterations. Finally, Oliveira et al. (2011) proposed an algorithm which only requires the fixed recourse hypothesis ($W_s = W, \forall s \in S$). It adapts the dual solutions of a subset of subproblems to generate inexact cuts to the remaining subproblems. The methods of Oliveira et al. (2011), Dantzig and Infanger (1991) and Higle and Sen (1991) are designed for a monocut algorithm, but the method of Oliveira et al. (2011) can be adapted to a multicut algorithm.

Finally, among other techniques used to accelerate the solution time of two-stage stochastic programs, Crainic et al. (2020) proposed the so-called *Partial Benders decomposition*. Under the hypothesis $g_s = g, \forall s \in S$, and fixed recourse, they add one of the scenarios, or an artificial scenario computed as the expectation of the others, to the master problem. They showed major improvements on some instances, both in computing time and number of iterations, even if the master problem becomes way larger than the original one, and might be harder to solve at each iteration. Under the same assumptions ($g_s = g, W_s = W, \forall s \in S$), Song and Luedtke (2015) proposed an adaptative partition-based approach, which does not rely on Benders reformulation. Given a partition of the subproblems, they compute a relaxation of the initial deterministic reformulation by summing the matrices and right-hand-sides of the subproblems of each element of the partition. They showed the existence of a partition with the same optimal value as the initial problem and an iterative algorithm to find it. van Ackooij et al. (2017) proposed to use level stabilization with the adaptative partition-based approach and showed numerical experiments where the resulting algorithms largely outperform classic level bundle or Benders decomposition methods. Table 1 classifies the different methods discussed in this section.

<table><thead><tr><th>Paper</th><th>Randomness hypothesis*</th><th>Solve all SPs</th><th>Monocut or multicut</th><th>Exact method</th><th>Finite convergence</th><th>Cut aggregation</th><th>Stabilization</th></tr></thead><tbody><tr><td>(Crainic et al., 2020)</td><td>$g_s = g, W_s = W \forall s \in S$</td><td>Yes</td><td>Both</td><td>Yes</td><td>Yes</td><td>No</td><td>No</td></tr><tr><td>(Song and Luedtke, 2015)</td><td>$g_s = g, W_s = W \forall s \in S$</td><td>Yes</td><td>Not applicable</td><td>Yes</td><td>Yes</td><td>No</td><td>No</td></tr><tr><td>(van Ackooij et al., 2017)</td><td>$g_s = g, W_s = W \forall s \in S$</td><td>No</td><td>Both</td><td>Yes</td><td>Yes</td><td>No</td><td>Level</td></tr><tr><td>(Wets, 1983)</td><td>$g_s = g, W_s = W \forall s \in S$</td><td>No</td><td>Both</td><td>Yes</td><td>Yes</td><td>No</td><td>No</td></tr><tr><td>(Dantzig and Infanger, 1991)</td><td>$g_s = g, W_s = W \forall s \in S$</td><td>No</td><td>Monocut</td><td>No</td><td>Yes</td><td>No</td><td>No</td></tr><tr><td>(Higle and Sen, 1991)</td><td>$g_s = g, W_s = W \forall s \in S$</td><td>No</td><td>Monocut</td><td>Yes</td><td>No</td><td>No</td><td>No</td></tr><tr><td>(Trukhanov et al., 2010)</td><td>No</td><td>Yes</td><td>Multicut</td><td>Yes</td><td>Yes</td><td>Yes</td><td>No</td></tr><tr><td>(Linderoth and Wright, 2003)</td><td>No</td><td>Yes</td><td>Multicut</td><td>Yes</td><td>Yes</td><td>No</td><td>Trust-region</td></tr><tr><td>(Wolf et al., 2014)</td><td>No</td><td>All or none</td><td>Monocut and Multicut</td><td>Yes</td><td>Yes</td><td>No</td><td>Level</td></tr><tr><td>(Oliveira et al., 2011)</td><td>$W_s = W \forall s \in S$</td><td>No</td><td>Monocut</td><td>Inexact</td><td>Yes</td><td>No</td><td>Proximal bundle</td></tr><tr><td>This work</td><td>No</td><td>No</td><td>Multicut</td><td>Yes</td><td>Yes</td><td>Yes</td><td>In-out</td></tr></tbody></table>

<caption>Table 1: Comparison of stochastic methods to accelerate Benders decomposition. (SPs: subproblems)</caption>

## 3 The Benders by batch algorithm

We propose a new algorithm, hereafter referred to as the Benders by batch algorithm, to solve exactly the multicut Benders reformulation (4) of a two-stage stochastic linear program. The algorithm consists of solving the subproblems by batch and stopping solving subproblems at an iteration as soon as we identify that the current first-stage solution cannot be proven optimal. This is made possible by checking, after solving of a subset of subproblems, if the gap between their optimal values and their epigraph approximations in the relaxed master program already exceeds the optimality gap.

We first present some notations necessary to formally describe the algorithm. We consider an ordered set of scenarios $S = \{s_1, s_2, ..., s_{card(S)}\}$ and a given batch size $1 \le \eta \le card(S)$. We define $\kappa = [card(S)/\eta]$ as the number of batches of subproblems. For every $i \in [1, \kappa]$, the $i^{th}$ batch of subproblems $S_i$ is defined as $S_i = \{s_{(i-1)\eta+1}, ..., s_{(i-1)\eta+\eta_i}\}$, where $\eta_i$ is the size of batch $i$, $\eta_1 = \dots = \eta_{\kappa-1} = \eta$ and $\eta_\kappa = (card(S) \text{ mod } \eta)$. Family $(S_i)_{i \in [1, \kappa]}$ defines a partition of $S$. We restrict ourselves to batches of the same size, but the method remains valid for any partition of $S$. We denote by $(\tilde{x}^{(k)}, (\tilde{\theta}_s^{(k)})_{s \in S})$ the optimal solution to $(RMP)^{(k)}$ at iteration $k$ of the algorithm, where $\tilde{x}^{(k)}$ denotes the optimal value to the first-stage variables and $\tilde{\theta}_s^{(k)}$ the optimal value to the epigraph variable associated with scenario $s \in S$. A lower bound on the optimal value of problem (1) is then computed as $LB^{(k)} = c^\top \tilde{x}^{(k)} + \sum_{s \in S} p_s \tilde{\theta}_s^{(k)}$. For a first-stage solution $x \in X$, we denote by $UB(x) = c^\top x + \sum_{s \in S} p_s \phi(x, s)$ an upper bound on the optimal value of problem (1). Let $\epsilon \ge 0$ be the optimality gap of the algorithm. We first define the notion of *provable optimality* in cutting-planes methods.

**Definition 1.** Let $\epsilon \ge 0$ be the optimality gap of the algorithm and $k$ an iteration of the algorithm. We say that a first-stage solution $x \in X$ cannot be proven optimal at an iteration $k$ of the algorithm iff $UB(x) - LB^{(k)} > \epsilon$.

Saying that a first-stage solution $x$ cannot be proven optimal at an iteration $k$ of the algorithm means that, either $x$ is not an optimal solution to problem (1), or the current lower bound given by $(RMP)^{(k)}$ is too low to prove the optimality of an optimal solution. The classical stopping criterion $UB - LB \le \epsilon$ of the Benders decomposition algorithm is based on such an optimality proof, but cannot be directly applied if not all the subproblems are solved. Specifically,

<footnote>* in addition to random parameters having a discrete finite probability distribution</footnote>
an upper bound on the optimal value of the problem is only known after computing, for a first-stage solution $x \in X$, the optimal value $\phi(x, s)$ of every subproblem $(SP(x, s))$.

We propose hereafter a new stopping criterion, which detects, when it occurs, that the current first-stage solution $\tilde{x}^{(k)}$ to $(RMP)^{(k)}$ cannot be proven optimal without necessarily having to solve all the subproblems. If after having solved some batches of subproblems, the sum of the differences between their value and their epigraph approximation in $(RMP)^{(k)}$ already exceeds the optimality gap $\epsilon$, the algorithm does not solve the remaining batches of subproblems, as we already know that $\tilde{x}^{(k)}$ cannot be proven optimal (see Proposition 1). In this way, the Benders by batch algorithm is likely to explore more first-stage solutions than classic Benders decomposition algorithms as it tends to solve only a few subproblems at most iterations. The proposed stopping criterion is based on the concept of $\epsilon_i$-approximation that we define below.

**Definition 2** ($\epsilon_i$-approximation). Let $\epsilon \ge 0$ be the optimality gap of the algorithm, $k \in \mathbb{Z}^+$ an iteration and $\sigma$ a permutation of $[1, \kappa]$. For every $i \in [1, \kappa]$, we say that batch $S_{\sigma(i)}$ is $\epsilon_i$-approximated by $(RMP)^{(k)}$ if

$$ \sum_{s \in S_{\sigma(i)}} p_s \left( \phi(\tilde{x}^{(k)}, s) - \tilde{\theta}_s^{(k)} \right) \le \epsilon_i \quad (5) $$

$$ \text{with } \epsilon_i = \epsilon - \sum_{t=1}^{i-1} \sum_{s \in S_{\sigma(t)}} p_s \left( \phi(\tilde{x}^{(k)}, s) - \tilde{\theta}_s^{(k)} \right). $$

We refer to $\epsilon_i$ as the remaining gap of batch $S_{\sigma(i)}$ according to the permutation $\sigma$ and the optimality gap $\epsilon$. For every index $i \in [2, \kappa]$, we have $\epsilon_i = \epsilon_{i-1} - \sum_{s \in S_{\sigma(i-1)}} p_s \left( \phi(\tilde{x}^{(k)}, s) - \tilde{\theta}_s^{(k)} \right)$, which means that computing the successive remaining gaps consists in filling the gap $\epsilon$ with the differences between the true values of the subproblems and their epigraph approximations in $(RMP)^{(k)}$.

The following proposition shows that $\epsilon_i$-approximation can be used to derive a stopping criterion for the Benders by batch algorithm.

**Proposition 1.** Let $\epsilon \ge 0$ be the optimality gap of the algorithm, $k \in \mathbb{Z}^+$ an iteration of the algorithm, and $\sigma$ a permutation of $[1, \kappa]$. The first-stage solution $\tilde{x}^{(k)}$ is an optimal solution to problem (1) if and only if batch $S_{\sigma(i)}$ is $\epsilon_i$-approximated by $(RMP)^{(k)}$ for every index $i \in [1, \kappa]$.

*Proof of proposition 1.* See Appendix A.1 □

**Corollary 1.** Let $\epsilon \ge 0$ be the optimality gap of the algorithm, $k \in \mathbb{Z}^+$ an iteration, and $\sigma$ a permutation of $[1, \kappa]$. If there exists an index $i \in [1, \kappa]$ such that $\sum_{s \in S_{\sigma(i)}} p_s \left( \phi(\tilde{x}^{(k)}, s) - \tilde{\theta}_s^{(k)} \right) > \epsilon_i$, then $\tilde{x}^{(k)}$ cannot be proven optimal.

**Remark 1.** As stated in Proposition 1, the proposed stopping criterion is equivalent to the classical stopping criterion $UB-LB \le \epsilon$. This means that, given a relaxed master program with some Benders cuts, and a first-stage solution $\tilde{x}$, either $\tilde{x}$ can be proven optimal by both stopping criteria, or both will reject it and let the algorithm continue.

We now present the Benders by batch algorithm (Algorithm 2). The while loop from lines 3 to 20 will be referred hereafter as the *master loop*. Each pass of this loop corresponds to an iteration of the algorithm. At iteration $k$, the relaxed master program $(RMP)^{(k)}$ is solved to obtain a new first-stage solution $\tilde{x}^{(k)}$. A permutation $\sigma$ of $[1, \kappa]$ is then chosen. This permutation defines the order in which the batches of subproblems $(S_1, S_2, ..., S_\kappa)$ will be solved at the current first-stage solution. The while loop from lines 8 to 19 will be referred as the *optimality loop*. In each pass in this loop:

* the subproblems of the current batch $S_{\sigma(i)}$ are solved (lines 9 to 10). This part of the algorithm can be parallelized, as in the classic Benders decomposition algorithm, to accelerate the procedure.

* the cuts defined by the solutions of the subproblems are added to the relaxed master program (lines 11 to 15). We add a parameter `cutAggr` to the algorithm. If this parameter is set to `False`, the cuts of each subproblem are added independently to the relaxed master program, as it is the case in the classic multicut Benders decomposition algorithm. If this parameter is set to `True`, we add only one cut, computed as the weighted sum of all the cuts of the batch according to the probability distribution.

* the gap between the value of the subproblems and the value of their outer linearization is checked (line 16 to 19). If the batch is $\epsilon_i$-approximated by $(RMP)^{(k)}$, then $i$ is increased by one, and the boolean `stay_at_x` still equals `True`. The algorithm returns to line 8 and solves a new batch at the same first-stage solution, as $i$ has been incremented. If it reaches $i = \kappa + 1$, then all batches are $\epsilon_i$-approximated by $(RMP)^{(k)}$ according to permutation $\sigma$, and $\tilde{x}^{(k)}$ is
**Algorithm 2:** The Benders by batch algorithm

**Parameters:** $\epsilon \ge 0$, $\eta \in [1, \text{card}(S)]$ the batch size, $\text{cutAggr} \in \{\text{True, False}\}$

1 **Initialization:** $i \leftarrow 1$, $k \leftarrow 0$, $\text{stay\_at\_x} \leftarrow \text{True}$
2 Define a partition $(S_i)_{i \in [1, \kappa]}$ of the subproblems according to batch size $\eta$
3 **while** $i < \kappa + 1$ **do**
4 &nbsp;&nbsp;&nbsp;&nbsp; $k \leftarrow k + 1$
5 &nbsp;&nbsp;&nbsp;&nbsp; Solve $(RMP)^{(k)}$ and retrieve $(\tilde{x}^{(k)}, (\tilde{\theta}_s^{(k)})_{s \in S})$
6 &nbsp;&nbsp;&nbsp;&nbsp; $i \leftarrow 1$, $\epsilon_1 \leftarrow \epsilon$, $\text{stay\_at\_x} \leftarrow \text{True}$
7 &nbsp;&nbsp;&nbsp;&nbsp; Choose a permutation $\sigma$ of $[1, \kappa]$
8 &nbsp;&nbsp;&nbsp;&nbsp; **while** $\text{stay\_at\_x} = \text{True}$ and $i < \kappa + 1$ **do**
9 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; **for** $s \in S_{\sigma(i)}$ **do**
10 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; Solve $(SP(\tilde{x}^{(k)}, s))$ and retrieve $\phi(\tilde{x}^{(k)}, s)$ and $\pi_s \in \text{Vert}(\Pi_s)$
11 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; **if** $\text{cutAggr}$ **then**
12 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; Add $\sum_{s \in S_{\sigma(i)}} p_s \theta_s \ge \sum_{s \in S_{\sigma(i)}} p_s (\pi_s^{\top}(d_s - T_s x))$ to $(RMP)^{(k)}$
13 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; **else**
14 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; **for** $s \in S_{\sigma(i)}$ **do**
15 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; Add $\theta_s \ge \pi_s^{\top}(d_s - T_s x)$ to $(RMP)^{(k)}$
16 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; **if** $\sum_{s \in S_{\sigma(i)}} p_s (\phi(\tilde{x}^{(k)}, s) - \tilde{\theta}_s^{(k)}) \le \epsilon_i$ **then**
17 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; $\epsilon_{i+1} \leftarrow \epsilon_i - \sum_{s \in S_{\sigma(i)}} p_s (\phi(\tilde{x}^{(k)}, s) - \tilde{\theta}_s^{(k)})$
18 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; $i \leftarrow i + 1$
19 &nbsp;&nbsp;&nbsp;&nbsp; **else** $\text{stay\_at\_x} \leftarrow \text{False}$
20 &nbsp;&nbsp;&nbsp;&nbsp; $(RMP)^{(k+1)} \leftarrow (RMP)^{(k)}$
21 &nbsp;&nbsp;&nbsp;&nbsp; Return $\tilde{x}^{(k)}$

an optimal solution to problem (1). If one of the batches is not $\epsilon_i$-approximated by $(RMP)^{(k)}$, then $\tilde{x}^{(k)}$ cannot be proven optimal. Then there exists at least one of the cuts which excludes the solution $(\tilde{x}^{(k)}, (\tilde{\theta}_s^{(k)})_{s \in S})$ from the relaxed master program. The algorithm exits the optimality loop, and goes to line 3 to solve again the relaxed master program.

**Remark 2 (Partial cut aggregation).** One of the most important drawbacks of the multicut Benders decomposition algorithm is the large number of cuts added to the relaxed master program at each iteration. As this number of cuts increases, the time needed to solve the master program can increase dramatically. The Benders by batch algorithm might suffer from the same effect, even if this effect might be delayed by the method (it adds fewer cuts at each iteration). We propose to aggregate the cuts of a batch, and add only one cut computed as $\sum_{s \in S_{\sigma(i)}} p_s \theta_s \ge \sum_{s \in S_{\sigma(i)}} p_s (\pi_s^{\top}(d_s - T_s x))$. As the subproblems are linearly independent, this cut is the Benders cut associated with the problem created by concatenation of the subproblems of a batch. As the partition of the subproblems into batches is done prior to the algorithm, the cuts of the same subproblems are always aggregated together. This can be seen as the static cut aggregation strategy used in (Trukhanov et al., 2010).

The following proposition is related to the finite convergence of the algorithm.

**Proposition 2.** Let $\epsilon \ge 0$ be the optimality gap. The Benders by batch algorithm converges to an optimal solution to problem 1 in a finite number of iterations.

*Proof of proposition 2.* See Appendix A.2. □

We propose an *ordered strategy* to choose the permutation $\sigma$ at each iteration. We assume that there exists an initial and arbitrary ordering of the batches $S_1, S_2, ..., S_\kappa$ and $\sigma = \text{id}$ at the first iteration. When we choose a new permutation, at the beginning of a master loop, the *ordered strategy* consists of starting from the first batch of subproblems that has not been solved at the previous first-stage solution. We introduce the following cyclic permutation $\mu$ of the batches:

$$ \mu = \begin{pmatrix} 1 & 2 & \dots & \kappa - 1 & \kappa \\ 2 & 3 & \dots & \kappa & 1 \end{pmatrix} $$
Let N be the number of batches solved at the previous first-stage solution. Then, the ordered strategy consists of defining the new permutation σ at line 7 of Algorithm (2) as σ ← µ^N ◦ σ.

This strategy has a deterministic behavior and implies solving all the subproblems the same number of times during the optimization process. A pure random strategy, shuffling the set of batches at the beginning of each master loop, showed a high variance in the total number of iterations. In preliminary computational experiments, we observed factors up to two between the running times of the fastest and the longest run on the same instance. As such a behavior is not desirable, we did not pursue this path.

# 4 Stabilization of the Benders by batch algorithm

The Benders by batch algorithm introduced in the previous section (Algorithm 2) may suffer, as every cutting-plane algorithm, from strong oscillations of the first-stage variables, and thus may compute, in the early iterations, cuts that exclude solutions that are far away from the optimal solution (see e.g. (Vanderbeck, 2005) section 7). However, the classical primal stabilization procedures presented in Section 2 do not apply directly if we do not solve all the subproblems at each iteration as they require the value of the recourse function for the current first-stage solution. We propose in this section a general framework to stabilize our algorithm, and show a sufficient condition for the convergence of the stabilized algorithm.

## 4.1 The stabilized Benders by batch algorithm

Many effective primal stabilization methods for cutting-plane algorithms solve, at each iteration, a separation problem in a point $x^{(k)}$ (hereafter referred to as the separation point) that is different from the current optimal first-stage solution $\tilde{x}^{(k)}$ to the relaxed master program (Zverovich et al., 2012; Pessoa et al., 2013). We define hereafter formally a primal stabilization scheme, in which the separation point is computed as the image by a given mapping of a vector defining the state of the stabilization. Such a scheme must also incorporate a way to update this state vector.

**Definition 3 (Primal stabilization scheme).** A primal stabilization scheme is characterized by a triplet $(\mathcal{D}, \psi_1, \psi_2)$ where $\mathcal{D}$ is a stabilization state space and $(\psi_1, \psi_2)$ is a pair of mappings $\begin{cases} \psi_1 : X \times \mathcal{D} \to \mathcal{D} \\ \psi_2 : \mathcal{D} \to X \end{cases}$ such that $\psi_2$ is surjective.

At an iteration $k$ of the stabilized algorithm, mapping $\psi_1$ computes the state vector of the stabilization to be used at the current iteration from the precedent state vector and the optimal solution to the current relaxed master program. This state vector may contain some elements of $X$, such as the last optimal solution to the relaxed master program. An initial stabilization state vector $d^0 \in \mathcal{D}$ is required when using the primal stabilization scheme in the first iteration of our algorithm. From the current stabilization state vector, mapping $\psi_2$ is then responsible for generating a first-stage solution $x^{(k)}$ at which the subproblems are solved and cuts are generated. Function $\psi_2$ is required to be surjective to ensure that every first-stage solution can be separated.

We now present how to adapt the Benders by batch algorithm (Algorithm 2) when such a primal stabilization scheme is used. We generalize Definition 2 and Proposition 1 to take into account that the lower bound at a given iteration $k$ is computed based on the current optimal solution $\tilde{x}^{(k)}$ to RMP, while the subproblems are solved at a separation point $x$ that is usually different from $\tilde{x}^{(k)}$. As this difference between the first-stage solutions induces a difference in the first-stage cost, we subtract in the definition of the remaining gap $\epsilon_i$ the difference $c^\top(x - \tilde{x}^{(k)})$. Because $\tilde{\theta}_s^{(k)}$ is a lower bound on $\phi(\tilde{x}^{(k)}, s)$, but not on $\phi(x, s)$, we also need to account for cases where $\phi(x, s) - \tilde{\theta}_s^{(k)} < 0$.

**Definition 4** $(\epsilon_i(x)$-approximation at a first-stage solution $x)$. Let $\epsilon \ge 0$ be the optimality gap of the algorithm, $k \in \mathbb{Z}^+$ an iteration and $\sigma$ a permutation of $\llbracket 1, \kappa \rrbracket$. For every $i \in \llbracket 1, \kappa \rrbracket$, we say that batch $S_{\sigma(i)}$ is $\epsilon_i(x)$-approximated by $(RMP)^{(k)}$ at $x \in X$ if

$$ \left[ \sum_{s \in S_{\sigma(i)}} p_s \left( \phi(x, s) - \tilde{\theta}_s^{(k)} \right) \right]^+ \le \epsilon_i(x) $$

$$ \text{with } \epsilon_i(x) = \epsilon - c^\top(x - \tilde{x}^{(k)}) - \left[ \sum_{t=1}^{i-1} \sum_{s \in S_{\sigma(t)}} p_s \left( \phi(x, s) - \tilde{\theta}_s^{(k)} \right) \right]^+ \text{ and } \zeta^+ = \max\{\zeta, 0\} \text{ for any } \zeta \in \mathbb{R}. $$

**Remark 3.** Saying that a batch $S_{\sigma(i)}$ is $\epsilon_i(\tilde{x}^{(k)})$-approximated by $(RMP)^{(k)}$ is equivalent to saying that $S_{\sigma(i)}$ is $\epsilon_i$-approximated by $(RMP)^{(k)}$ in Algorithm 2.
The following proposition introduces a valid stopping criterion for our stabilized version of the Benders by batch algorithm.

**Proposition 3.** Let $\epsilon \ge 0$ be the optimality gap of the algorithm, $k \in \mathbb{Z}^+$ an iteration of the algorithm, and $\sigma$ a permutation of $\llbracket 1, \kappa \rrbracket$. If there exists a first-stage solution $x \in X$ such that batch $S_{\sigma(i)}$ is $\epsilon_i(x)$-approximated by $(RMP)^{(k)}$, for all $i \in \llbracket 1, \kappa \rrbracket$, then $x$ is an optimal solution to problem (1).

*Proof of proposition 3.* See Appendix A.3 □

<caption>**Algorithm 3:** The stabilized Benders by batch algorithm</caption>

**Parameters:** $\epsilon \ge 0$, $\eta \in \llbracket 1, \text{card}(S) \rrbracket$ the batch size, $\text{cutAggr} \in \{\text{True}, \text{False}\}$, a primal stabilization scheme ($\mathcal{D}, \psi_1, \psi_2$) and an initial stabilization state vector $d^{(0)} \in \mathcal{D}$.

1 Initialization: $i \leftarrow 1$, $k \leftarrow 0$, misprice $\leftarrow \text{False}$, stay\_at\_x $\leftarrow \text{True}$
2 Define a partition $(S_i)_{i \in \llbracket 1, \kappa \rrbracket}$ of the subproblems according to batch size $\eta$
3 while $i < \kappa + 1$ do
4 Solve $(RMP)^{(k+1)}$ and retrieve $(\tilde{x}^{(k+1)}, (\tilde{\theta}_s^{(k+1)})_{s \in S})$
5 do
6 $k \leftarrow k + 1$
7 $d^{(k)} \leftarrow \psi_1(\tilde{x}^{(k)}, d^{(k-1)})$
8 $x^{(k)} \leftarrow \psi_2(d^{(k)})$
9 $i \leftarrow 1$, $\epsilon_i \leftarrow \epsilon - c^\top(x^{(k)} - \tilde{x}^{(k)})$, stay\_at\_x $\leftarrow \text{True}$
10 Choose a permutation $\sigma$ of $\llbracket 1, \kappa \rrbracket$
11 misprice $\leftarrow \text{True}$
12 while stay\_at\_x = True and $i < \kappa + 1$ do
13 for $s \in S_{\sigma(i)}$ do
14 Solve $(SP(x^{(k)}, s))$ and retrieve $\phi(x^{(k)}, s)$ and $\pi_s \in \text{Vert}(\Pi_s)$
15 if cutAggr then
16 Add $\sum_{s \in S_{\sigma(i)}} p_s \theta_s \ge \sum_{s \in S_{\sigma(i)}} p_s (\pi_s^\top(d_s - T_s x))$ to $(RMP)^{(k)}$
17 else
18 for $s \in S_{\sigma(i)}$ do
19 Add $\theta_s \ge \pi_s^\top(d_s - T_s x)$ to $(RMP)^{(k)}$
20 if $\sum_{s \in S_{\sigma(i)}} [p_s(\phi(x^{(k)}, s) - \tilde{\theta}_s^{(k)})]^+ \le \epsilon_i$ then
21 $\epsilon_{i+1} \leftarrow \epsilon - c^\top(x^{(k)} - \tilde{x}^{(k)}) - \left[ \sum_{t=1}^i \sum_{s \in S_{\sigma(t)}} p_s(\phi(x^{(k)}, s) - \tilde{\theta}_s^{(k)}) \right]^+$
22 $i \leftarrow i + 1$
23 else
24 stay\_at\_x $\leftarrow \text{False}$
25 if cutAggr then
26 if $\sum_{s \in S_{\sigma(i)}} p_s \tilde{\theta}_s^{(k)} < \sum_{s \in S_{\sigma(i)}} p_s (\pi_s^\top(d_s - T_s \tilde{x}^{(k)}))$ then misprice $\leftarrow \text{False}$
27 else
28 for $s \in S_{\sigma(i)}$ do
29 if $\tilde{\theta}_s^{(k)} < \pi_s^\top(d_s - T_s \tilde{x}^{(k)})$ then misprice $\leftarrow \text{False}$
30 $(RMP)^{(k+1)} \leftarrow (RMP)^{(k)}$, $\tilde{x}^{(k+1)} \leftarrow \tilde{x}^{(k)}, (\tilde{\theta}_s^{(k+1)})_{s \in S} \leftarrow (\tilde{\theta}_s^{(k)})_{s \in S}$
31 while misprice
32 Return $x^{(k)}$

We now present the stabilized Benders by batch algorithm (Algorithm 3).

As, at each iteration, the cuts are now generated from a first-stage solution $x^{(k)}$ that may be different from the first-solution to $(RMP)^{(k)}$, there is no guarantee that the cuts added separate the solution to the relaxed master program $(\tilde{x}^{(k)}, (\tilde{\theta}_s^{(k)})_{s \in S})$. When there is no cut, among added cuts, that separates the solution to the relaxed master program, we say that first-stage solution $x^{(k)}$ induces a **mis-pricing** (Pessoa et al., 2013). We represent such a case in Figure 1. Then, there is no need to solve again the relaxed master program as its solution remains the same. A boolean variable misprice appears in Algorithm 3 to handle such a case.
The algorithm is structured in three nested while loops. The while loop from line 3 to 31 is called the master loop. In this loop, the relaxed master program is solved in order to define a new first-stage solution $\tilde{x}^{(k)}$. The while loop from line 5 to 31 is called the separation loop. This loop updates the current separation point $x^{(k)}$ while the solution to the relaxed master program $\tilde{x}^{(k)}$ remains constant. We increment the iteration counter $k$ each time a new separation point is calculated. The while loop from line 12 to 29 is called the optimality loop. In the optimality loop, the subproblems of current batch $S_{\sigma(i)}$ are solved in $x^{(k)}$. There are three possibilities at the end of this loop:

* **Case 1:** The current batch is $\epsilon_i(x^{(k)})$-approximated by $(RMP)^{(k)}$. It satisfies the condition of line 20 of Algorithm 3. Then, stay_at_x still equals True at the end of the loop, and $i$ is incremented by one. If the algorithm reaches $i = \kappa + 1$, then the algorithm stops, and $x^{(k)}$ is an optimal solution to the problem with an optimality gap $\epsilon \ge 0$. Otherwise, the algorithm solves the next batch of subproblems at the same first-stage solution.

* **Case 2:** The current batch $S_{\sigma(i)}$ is not $\epsilon_i(x^{(k)})$-approximated by $(RMP)^{(k)}$ and there exists no cut derived from this batch of subproblems, or a previous batch, which separates the solution $(\tilde{x}^{(k)}, (\tilde{\theta}_s^{(k)})_{s \in S})$ to the relaxed master program [see Figure 1]. The variable misprice still equals True. As the solution to the relaxed master program has not been cut, it is useless to solve the relaxed master program again. We exit the optimality loop, but stay in the separation loop. We define a new separation point $x^{(k)}$, a new permutation of $[1, \kappa]$, and begin a new optimality loop.

* **Case 3:** The current batch $S_{\sigma(i)}$ is not $\epsilon_i(x^{(k)})$-approximated by $(RMP)^{(k)}$ and at least one of the cuts derived from this batch of subproblems separates the solution $(\tilde{x}^{(k)}, (\tilde{\theta}_s^{(k)})_{s \in S})$ to the relaxed master program [see Figure 2]. This means that misprice is set to False. The variable stay_at_x is set to False and we exit the optimality loop. Since misprice equals False, we exit the separation loop. We then go to line 3, and solve again the relaxed master program.

<figure><img src="image_2.png" /><figcaption>Figure 1: The cut derived from first-stage solution $x^{(k)}$ does not separate the solution to the relaxed master program $(\tilde{x}^{(k)}, (\tilde{\theta}_s^{(k)})_{s \in S})$. The solution to $(RMP)^{(k)}$ remains the same. The separation point $x^{(k)}$ induces a mis-pricing.</figcaption></figure>

<figure><img src="image_3.png" /><figcaption>Figure 2: The cut derived from first-stage solution $x^{(k)}$ separates the solution to the relaxed master program $(\tilde{x}^{(k)}, (\tilde{\theta}_s^{(k)})_{s \in S})$.</figcaption></figure>

## 4.2 A sufficient condition for the convergence of the stabilized Benders by batch algorithm

In this section we prove that, if the sequence of separation points produced by the primal stabilization scheme converges to the solution to the relaxed master program when this latter solution remains constant over the iterations (i.e., during a mis-pricing sequence), then the stabilized Benders by batch algorithm (Algorithm 3) converges to an optimal solution to problem (1) in a finite number of iterations.

**Definition 5** (Convergence property and finite convergence property of a primal stabilization scheme). Let $(\mathcal{D}, \psi_1, \psi_2)$ be a primal stabilization scheme. For every $(x, d) \in X \times \mathcal{D}$ we define $(d_x^\ell)_{\ell \in \mathbb{N}^*}$ as

$$d_x^\ell = \begin{cases} \psi_1(x, d_x^{\ell-1}) & \ell > 1 \\ \psi_1(x, d) & \ell = 1 \end{cases} \quad \forall \ell \in \mathbb{N}^*$$
the sequence of stabilization state vectors obtained by successive applications of $\psi_1$ on a constant first-stage solution $x \in X$.

* We say that a primal stabilization scheme $(\mathcal{D}, \psi_1, \psi_2)$ satisfies the convergence property if:

$$ \forall (x, d) \in X \times \mathcal{D}, \lim_{\ell \to +\infty} \psi_2(d_x^\ell) = x $$

* We say that a primal stabilization scheme $(\mathcal{D}, \psi_1, \psi_2)$ satisfies the finite convergence property if:

$$ \forall (x, d) \in X \times \mathcal{D}, \exists \ell_0 \in \mathbb{N}^*, \psi_2(d_x^{\ell_0}) = x $$

We first need to prove the following intermediate results to show that the stabilized Benders by batch algorithm effectively converges to an optimal solution to problem (1).

**Proposition 4.** Let $\epsilon > 0$ (resp. $\epsilon \ge 0$) be the optimality gap of Algorithm 3, $k \in \mathbb{Z}^+$ an iteration, and $(\check{x}^{(k)}, (\check{\theta}_s^{(k)})_{s \in S})$ an optimal solution to $(RMP)^{(k)}$. If $(x^{(k+r)})_{r \in \mathbb{N}}$ is a sequence of elements of $X$ converging to $\check{x}^{(k)}$ (resp. converging to $\check{x}^{(k)}$ in a finite number of iterations) and $(\sigma^{(k+r)})_{r \in \mathbb{N}}$ a sequence of permutations of $\llbracket 1, \kappa \rrbracket$, then there exists $t \in \mathbb{N}$ such that one of the following assertions is true:

1. First-stage solution $x^{(k+t)}$ is proven to be an optimal solution to problem (1) with an optimality gap of $\epsilon > 0$ (resp. $\epsilon \ge 0$).

2. There exists a cut generated in $x^{(k+t)}$ which separates $(\check{x}^{(k)}, (\check{\theta}_s^{(k)})_{s \in S})$.

*Proof of proposition 4.* See Appendix A.4. $\square$

**Proposition 5.** If the primal stabilization scheme satisfies the convergence property (resp. finite convergence property) of Definition 5, then the stabilized Benders by batch algorithm converges to an optimal solution to problem (1) in a finite number of iterations, for every $\epsilon > 0$ (resp. $\epsilon \ge 0$).

*Proof of proposition 5.* Let $k \in \mathbb{Z}^+$ an iteration of the algorithm, $\sigma$ a permutation of $\llbracket 1, \kappa \rrbracket$, and $x^{(k)} \in X$ the separation point. There are three possible cases:

1. $\forall i \in \llbracket 1, \kappa \rrbracket$, batch $S_{\sigma(i)}$ is $\epsilon_i(x^{(k)})$-approximated by $(RMP)^{(k)}$. Then $x^{(k)}$ is an optimal solution to problem (1) with an optimality gap of $\epsilon > 0$ (resp. $\epsilon \ge 0$).

2. There exists an index $i \in \llbracket 1, \kappa \rrbracket$ such that solving the subproblems of batch $S_{\sigma(i)}$ generates a cut which separates the solution to $(RMP)^{(k)}$. As the total number of cuts is finite, we can only be in this situation a finite number of times.

3. There exists no cut derived at $x^{(k)}$ which separates the solution to $(RMP)^{(k)}$. Then, $x^{(k)}$ induces a mis-pricing. The solution to $(RMP)^{(k+1)}$ remains the same. Let suppose that this happens during an infinite number of consecutive iterations. Then, as the primal stabilization scheme satisfies the convergence property (resp. the finite convergence property), the sequence of separation points converges to $\check{x}^{(k)}$ (resp. in a finite number of iterations). Prop. 4 states that in that case, we end up in a finite number of iterations in case 1 or case 2.

In conclusion, the stabilized Benders by batch algorithm ends in a finite number of iterations in case 1, and finds an optimal solution to problem (1). $\square$

**Remark 4.** The classic Benders decomposition algorithm is equivalent to the Benders by batch algorithm with a batch size $\eta = \text{card}(S)$. Therefore, Algorithm 3 describes a valid way to add primal stabilization to the classic Benders decomposition algorithm (providing that the primal separation scheme satisfies the convergence property).

## 4.3 Two primal stabilization schemes satisfying the convergence property

We introduce in this section two primal stabilization schemes satisfying the convergence property, based on the in-out stabilization approach (Ben-Ameur and Neto, 2007). In the in-out approach, the stability center $\hat{x}^{(k)}$ at iteration $k$ is equal to the separation point (among those calculated so far) with the smallest objective function value: $\hat{x}^{(k)} = \arg \min_{j \in \llbracket 0, k-1 \rrbracket} \{c^\top x^{(j)} + \sum_{s \in S} p_s \phi(x^{(j)}, s)\}$. Then the separation point $x^{(k)}$ is then defined on the segment between $\hat{x}^{(k)}$ (in-point) and $\check{x}^{(k)}$ (out-point): $x^{(k)} = \alpha \check{x}^{(k)} + (1 - \alpha) \hat{x}^{(k)}$. The in-out approach creates a sequence of stability centers with decreasing objective values converging to an optimal solution to the problem. The definition of $\hat{x}^{(k)}$ requires
computing the value $\phi(x^{(j)}, s)$ for every scenario $s \in S$, meaning that all the subproblems need to be solved at every separation point. As we generally do not solve all the subproblems at a given iteration, the in-out stabilization approach needs to be adapted for use in the Benders by batch algorithm.

We present below two primal stabilization schemes.

**Scheme 1 - Basic stabilization:** Let $\alpha \in (0, 1]$ be a stabilization parameter. The separation point at iteration $k$ is computed as follows:

$$x^{(k)} = \alpha \tilde{x}^{(k)} + (1 - \alpha)x^{(k-1)}$$

for $k \ge 1$, and $x^{(0)} \in X$ is a feasible first-stage solution. This basically consists in doing 100$\alpha$% of the way from the previous separation point to the solution to the master program. This can be seen as an in-out stabilization, updating the stability center to the last separation point at each iteration. By convexity of $X$, $x^{(k)}$ belongs to $X$ for every $k \in \mathbb{N}$.

The basic stabilization scheme can be expressed according to Definition 3 as:

$$ \begin{array}{l} \mathcal{D} = X^2 \\ \psi_1 : \left\{ \begin{array}{l} X \times \mathcal{D} \rightarrow \mathcal{D} \\ x, (y, z) \mapsto (x, \alpha y + (1 - \alpha)z) \end{array} \right. \\ \psi_2 : \left\{ \begin{array}{l} \mathcal{D} \rightarrow X \\ (y, z) \mapsto \alpha y + (1 - \alpha)z \end{array} \right. \end{array} $$

with $d^0 = (x^{(0)}, x^{(0)})$ where $x^{(0)} \in X$ is a feasible first-stage solution. The vector of parameters $d^{(k)}$ computed at the iteration $k$ is equal to $(\tilde{x}^{(k)}, x^{(k-1)})$.

**Proposition 6.** The basic stabilization scheme satisfies the convergence property.

*Proof of proposition 6.* See Appendix A.5. □

**Scheme 2 - Solution memory stabilization:** This stabilization uses an exponentially weighted average of the previous master solutions to compute the separation point. We choose a stabilization parameter $\alpha \in (0, 1]$ and a memory parameter $\beta \in [0, 1)$. We also define the exponentially weighted averaged point $\tilde{x}^{(k)}$ on master solutions. The separation point is computed as follows:

$$ \left\{ \begin{array}{l} \tilde{x}^{(k)} = \beta \tilde{x}^{(k-1)} + (1 - \beta) \tilde{x}^{(k)} \\ x^{(k)} = \alpha \tilde{x}^{(k)} + (1 - \alpha)x^{(k-1)} \end{array} \right. $$

for $k \ge 1$, and $x^{(0)} = \tilde{x}^{(0)} \in X$ is a feasible first-stage solution. By convexity of $X$, $x^{(k)}$ belongs to $X$ for every $k \in \mathbb{N}$. This stabilization takes inspiration from the stochastic gradient algorithm with momentum (Polyak, 1964) that has proven its efficiency in solving large-scale stochastic programs in the field of deep learning (Sutskever et al., 2013).

The solution memory stabilization scheme can be expressed according to Definition 3 as:

$$ \begin{array}{l} \mathcal{D} = X^2 \\ \psi_1 : \left\{ \begin{array}{l} X \times \mathcal{D} \rightarrow \mathcal{D} \\ x, (y, z) \mapsto (\beta y + (1 - \beta)x, \alpha y + (1 - \alpha)z) \end{array} \right. \\ \psi_2 : \left\{ \begin{array}{l} \mathcal{D} \rightarrow X \\ (y, z) \mapsto \alpha y + (1 - \alpha)z \end{array} \right. \end{array} $$

with $d^0 = (x^{(0)}, x^{(0)})$ where $x^{(0)} \in X$ is a feasible first-stage solution. The vector of parameters $d^{(k)}$ computed at the iteration $k$ is equal to $(\tilde{x}^{(k)}, x^{(k-1)})$.

**Proposition 7.** The solution memory stabilization scheme satisfies the convergence property.

*Proof of proposition 7.* See Appendix A.6. □

It is possible to adapt both schemes so that they satisfy the finite convergence property. Specifically, the separation point should become equal to the solution to the relaxed master program in a finite number of iterations when there are successive iterations which induce a mis-pricing. For the basic stabilization scheme, this implies that the value of $\alpha$ should increase to become equal to one in a finite number of iterations if successive mis-pricings occur. If $t \in \mathbb{N}$ denotes the number of consecutive mis-pricings that have occurred before starting iteration $k$ of the algorithm, then computing $x^{(k)}$ replacing $\alpha$ by $\min\{1, \alpha(1 + t)\}$ works. For the solution memory stabilization scheme, in similar cases, the value of $\alpha$ should increase to become equal to one and the value of $\beta$ should decrease to become equal to zero in a finite number of iterations.
# 5 Experimental design and numerical results

We want to estimate the numerical performance of the presented algorithms. We first present the benchmark we use, and our instance generation method. We then explain the different algorithms that we used for comparison, and how we implemented them. Finally, we show and analyze the numerical results we obtained.

## 5.1 Instances

We use seven well studied instances from the literature. The first five, 20term (Mak et al., 1999), gbd (Dantzig, 1963), LandS (Louveaux and Smeers, 1988), ssn (Sen et al., 1994) and storm (Mulvey and Ruszczyński, 1995), are available from the following link: www.cs.wisc.edu/~swright/stochastic/sampling/. The problem 20term is taken from (Mak et al., 1999). It is a model of motor freight carrier's operations. The problem consists in choosing the position of some vehicles at the beginning of the day, the first-stage variables, and then to use those vehicles to satisfy some random demands on a network. Instance gbd has been created from chapter 28 of (Dantzig, 1963). It is an aircraft allocation problem. LandS has been created from an electrical investment planning problem described in (Louveaux and Smeers, 1988). In (Linderoth et al., 2006), the authors modified the problem to obtain an instance with $10^6$ scenarios. Problem ssn is a problem of telecommunication network design taken from (Sen et al., 1994) and storm is a cargo flight scheduling problem described by (Mulvey and Ruszczyński, 1995). The two last instances come from https://people.orie.cornell.edu/huseyin/research/research.html. The first one, product, is the large instance of the product distribution problem available at https://people.orie.cornell.edu/huseyin/research/sp_datasetsp datasets.html. The second one, Fleet20.3 was found at http://www.ie.tsinghua.edu.cn/lzhao/ which was itself taken from https://people.orie.cornell.edu/huseyin/research/research.html. It is a fleet-sizing problem, close to 20term, with a two-week planning horizon.

As those instances have a tremendous number of scenarios (see Table 2), we generate instances by sampling scenarios from the initial ones. We generated instances with sample sizes 1000, 5000, 10000, and 20000. Three random instances have been generated for each problem and each sample size $S$, with random seeds $S + k$, $k \in \{0, 1, 2\}$ so that two instances of different sample size should not share sub-samples. This leads to a benchmark of 84 different instances. In the following, we will refer to the instances of problem prob with \#scenarios scenarios as prob-N\#scenarios.

<table><caption>Table 2: Instances sizes, given in the format lines × columns</caption><thead><tr><td>problem</td><td>first-stage</td><td>second-stage</td><td>scenarios</td></tr></thead><tbody><tr><td>LandS</td><td>2 × 4</td><td>7 × 12</td><td>10<sup>6</sup></td></tr><tr><td>gbd</td><td>4 × 17</td><td>5 × 10</td><td>~ 10<sup>5</sup></td></tr><tr><td>20term</td><td>3 × 64</td><td>124 × 764</td><td>~ 10<sup>12</sup></td></tr><tr><td>ssn</td><td>1 × 89</td><td>175 × 706</td><td>~ 10<sup>70</sup></td></tr><tr><td>storm</td><td>185 × 121</td><td>528 × 1259</td><td>~ 10<sup>81</sup></td></tr><tr><td>Fleet20.3</td><td>3 × 60</td><td>321 × 1921</td><td>> 3<sup>200</sup></td></tr><tr><td>product</td><td>75 × 1500</td><td>700 × 1450</td><td>3<sup>450</sup></td></tr></tbody></table>

## 5.2 Experimental Design

In order to evaluate the numerical efficiency of our Benders by batch algorithm (BbB), we compare it to nine different methods.

The experimentations are run on one core (sequential mode), on an Intel® Xeon® Gold SKL-6130 processor at 2,1 GHz with 96 GB of RAM with the TURBO boost (up to 3.7 GHz). The time limit is fixed to twelve hours for every algorithm. The optimality gap is fixed to a relative gap of $10^{-6}$ for every algorithm. We set the lower bound on the epigraph variables associated with the subproblems to 0 as it is a valid lower bound on LandS, gbd, ssn, storm, Fleet20.3 and 20term instances and to $-10^{10}$ on product instances as 0 is not a valid lower bound on those instances.

First, we run IBM ILOG CPLEX 12.10 (IBM, 2019) to solve the deterministic reformulation with the barrier algorithm (CPLEX Barrier hereafter) and with its multicut Benders implementation (CPLEX Benders) (Bonami et al., 2020). We also compare to our implementation of the multicut Benders decomposition algorithm (Classic multicut) and our implementation of the monocut Benders decomposition algorithm (Classic monocut).
In order to evaluate the effect of primal stabilization, we also run our implementations of the level bundle method (Lemaréchal et al., 1995) using aggregated cut as in the monocut Benders decomposition algorithm (Level Bundle), our implementation of the multicut Benders decomposition algorithm with an in-out stabilization (In-out multicut) and our implementation of the monocut Benders decomposition algorithm with an in-out stabilization (In-out monocut). We describe these algorithms in Appendix B.

As the partial cut aggregation proposed in the Benders by batch algorithm can be seen as the static cut aggregation scheme described by Trukhanov et al. (2010), which have already shown improvements compared to pure monocut or multicut Benders decomposition algorithms, we also implement the Benders decomposition algorithm with the same cut aggregation level as the one used in the Benders by batch algorithms (Classic CutAggr). Given $(S_i)_{i=1,...,\eta}$ the same partition of the subproblems into batches than the one used in the Benders by batch algorithm, we solve all the subproblems at each iteration and add the following cuts $\sum_{s \in S_i} p_s \theta_s \ge \sum_{s \in S_i} p_s (\pi_s^\top (d_s - T_s x))$, $\forall i \in [1, \eta]$. Finally, we implement the Benders decomposition with static cut aggregation and in-out stabilization (In-out CutAggr).

CPLEX Benders is run with the following parameter values: benders strategy 2 (an annotation file contains the first-stage variables, and CPLEX automatically decomposes the subproblems), threads 1 (to run CPLEX using one core, as the other methods), timelimit 43200 (time limit of twelve hours). Classic multicut follows Algorithm 1. In Classic monocut and In-out monocut, we compute the cuts as $\sum_{s \in S} p_s \theta_s \ge \sum_{s \in S} p_s (\pi_s^\top (d_s - T_s x))$.

The subproblems are solved with the dual simplex algorithm for all methods. In all our implementations, the first-stage variables appear as variables in all the subproblems, and are fixed to the desired values during the optimization process. The coefficients of the cuts are computed as the reduced cost of those variables in an optimal solution to the subproblems.

In Level Bundle, In-out multicut, In-out monocut and In-out CutAggr and BbB with stabilization, the starting solution $x^{(0)}$ is obtained by solving the mean-value problem. We use a dynamic strategy to update the stabilization parameter $\alpha$ in In-out monocut, In-out multicut and In-out CutAggr. If $c^\top x^{(k)} + \sum_{s \in S} p_s \phi(s, x^{(k)}) < c^\top \hat{x}^{(k)} + \sum_{s \in S} p_s \phi(s, \hat{x}^{(k)})$, then the separation point has a lower cost than the current stability center. If we had separated farther, we could have found an even better point, so we increase $\alpha$ with the rule $\alpha \leftarrow \min\{1.0, 1.2\alpha\}$. If $c^\top x^{(k)} + \sum_{s \in S} p_s \phi(s, x^{(k)}) \ge c^\top \hat{x}^{(k)} + \sum_{s \in S} p_s \phi(s, \hat{x}^{(k)})$, we did not stabilize enough, and we therefore decrease the stabilization parameter $\alpha$ with the rule $\alpha \leftarrow \max\{0.1, 0.8\alpha\}$. We initialize $\alpha$ to 0.5. Such a procedure cannot be used in the stabilized Benders by batch algorithm as the actual value of the recourse function is required. Level Bundle is tested with a level parameter $\lambda = 0.5$ and a stability center tolerance $\kappa = 0.1$ as in (van Ackooij et al., 2017).

We also evaluate different parameters of BbB. We first run BbB without stabilization, and try different batch sizes with and without partial cut aggregation. Then, we evaluate the impact of the two proposed stabilization schemes, with different values for the stabilization parameters.

We coded all the methods using C++ and compiled them with GCC 9.3.0. Every stochastic linear program to solve is given as input to our program in the SMPS format (Gassmann and Schweitzer, 2001). Our implementation and the instances are accessible from this link: https://gitlab.inria.fr/edge/benders-by-batch.

## 5.3 Numerical results

This section shows the numerical results obtained on the 84 instances of our benchmark. When an algorithm is stopped at its time limit of 12 hours (43 200s), the computing time is denoted $+\infty$, and the ratio to the best time will be denoted $> \frac{43200}{\text{best time}}$ in the tables, which means that this algorithm is at least this ratio slower than the best algorithm present in the table. All the tables presented in this section show, for each method, the average computing time to solve the three instances of each size, and the time ratio with respect to the best time obtained in this table. Detailed results instance by instance are presented in Appendix E. We always present the average time on the three instances of each size for each problem, rounded to the second (when computing times are larger than one second).

We present the results with the performance profiles introduced by Dolan and Moré (2002). Let $\mathcal{P}$ be a set of problems, and $\mathcal{M}$ a set of methods. For any problem $p \in \mathcal{P}$ and method $m \in \mathcal{M}$, we denote as $t_{p,m}$ the computing time of method $m$ to solve problem $p$. We define the performance ratio of method $m \in \mathcal{M}$ on problem $p \in \mathcal{P}$ as:

$$r_{p,m} = \frac{t_{p,m}}{\min_{m' \in \mathcal{M}} \{t_{p,m'}\}}$$

The performance profile of a method $m \in \mathcal{M}$ is the cumulative distribution function of its performance ratios computed over a set of problems $\mathcal{P}$. It is defined as $\rho_m(\tau) = \text{card}(\{p \in \mathcal{P} : r_{p,m} \le \tau\})$

The ratios presented in the following tables are computed as the expectation of the performance ratios over the three
instances of each problem with the same number of subproblems.

### 5.3.1 Performance of BbB without stabilization

We first present the results of BbB without stabilization. We analyze the impact of the batch size, both without (Table 3) and with partial cut aggregation (Table 4). Each column of Tables 3 and 4 contains the average time in second to solve the instances and the ratio to the best time. We analyze batch sizes from 1% to 20% of the total number of subproblems (respectively denoted by BbB 1%, BbB 5%, BbB 10% and BbB 20%). The variants with cut aggregation are respectively designated by BbB 1% CutAggr, BbB 5% CutAggr, BbB 10% CutAggr and BbB 20% CutAggr.

In order to estimate only the effect of performing an optimality check after solving each batch of subproblems, we compare in Table 3 the Benders by batch algorithm without cut aggregation (BbB) to Classic multicut, which can be seen as the Benders by batch algorithm without cut aggregation with a batch size equal to the total number of subproblems. We compare in Table 4 the Benders by batch algorithm with cut aggregation (BbB CutAggr) to Classic CutAggr, which corresponds to the Benders by batch algorithm with partial cut aggregation, in which all subproblems are solved at each iteration. The same partition of subproblems is used in BbB 1% CutAggr and Classic 1% CutAggr, as well as in BbB 5% CutAggr and Classic 5% CutAggr. We also present the results of Classic monocut, as a classical alternative to Classic multicut in Table 3 and as a method where cuts are fully aggregated in Table 4.

<table><caption>Table 3: Results for the Benders by batch algorithm without partial cut aggregation, with batch sizes from 1% to 20% of the total number of subproblems.</caption><thead><tr><th rowspan="2">instance</th><th colspan="2">Classic monocut</th><th colspan="2">Classic multicut</th><th colspan="2">BbB 1%</th><th colspan="2">BbB 5%</th><th colspan="2">BbB 10%</th><th colspan="2">BbB 20%</th></tr><tr><th>time</th><th>ratio</th><th>time</th><th>ratio</th><th>time</th><th>ratio</th><th>time</th><th>ratio</th><th>time</th><th>ratio</th><th>time</th><th>ratio</th></tr></thead><tbody><tr><td>LandS-N1000</td><td>2</td><td>3.0</td><td>0.75</td><td>1.1</td><td>2</td><td>2.7</td><td>0.83</td><td>1.3</td><td>0.72</td><td>1.1</td><td><strong>0.66</strong></td><td><strong>1.0</strong></td></tr><tr><td>LandS-N5000</td><td>11</td><td>1.7</td><td>9</td><td>1.5</td><td>13</td><td>2.2</td><td>8</td><td>1.3</td><td>7</td><td>1.1</td><td><strong>6</strong></td><td><strong>1.0</strong></td></tr><tr><td>LandS-N10000</td><td>22</td><td>1.1</td><td>29</td><td>1.5</td><td>38</td><td>2.0</td><td>25</td><td>1.3</td><td>21</td><td>1.1</td><td><strong>20</strong></td><td><strong>1.0</strong></td></tr><tr><td>LandS-N20000</td><td><strong>45</strong></td><td><strong>1.0</strong></td><td>105</td><td>2.3</td><td>130</td><td>2.9</td><td>89</td><td>2.0</td><td>80</td><td>1.8</td><td>72</td><td>1.6</td></tr><tr><td>gbd-N1000</td><td>2</td><td>3.3</td><td>0.94</td><td>1.4</td><td>2</td><td>3.6</td><td><strong>0.65</strong></td><td><strong>1.0</strong></td><td>0.84</td><td>1.3</td><td>0.96</td><td>1.5</td></tr><tr><td>gbd-N5000</td><td>12</td><td>1.9</td><td>10</td><td>1.7</td><td>16</td><td>2.5</td><td><strong>6</strong></td><td><strong>1.0</strong></td><td>7</td><td>1.1</td><td>8</td><td>1.3</td></tr><tr><td>gbd-N10000</td><td>23</td><td>1.2</td><td>33</td><td>1.7</td><td>47</td><td>2.5</td><td><strong>19</strong></td><td><strong>1.0</strong></td><td>22</td><td>1.2</td><td>25</td><td>1.3</td></tr><tr><td>gbd-N20000</td><td><strong>48</strong></td><td><strong>1.0</strong></td><td>121</td><td>2.5</td><td>96</td><td>2.0</td><td>61</td><td>1.3</td><td>71</td><td>1.5</td><td>87</td><td>1.8</td></tr><tr><td>ssn-N1000</td><td>2408</td><td>611.6</td><td>7</td><td>1.8</td><td>6</td><td>1.6</td><td><strong>4</strong></td><td><strong>1.0</strong></td><td>4</td><td>1.1</td><td>5</td><td>1.2</td></tr><tr><td>ssn-N5000</td><td>13460</td><td>590.1</td><td>57</td><td>2.5</td><td>32</td><td>1.4</td><td><strong>24</strong></td><td><strong>1.0</strong></td><td>28</td><td>1.2</td><td>32</td><td>1.4</td></tr><tr><td>ssn-N10000</td><td>25901</td><td>444.1</td><td>188</td><td>3.2</td><td>71</td><td>1.2</td><td>79</td><td>1.3</td><td><strong>59</strong></td><td><strong>1.0</strong></td><td>79</td><td>1.3</td></tr><tr><td>ssn-N20000</td><td>+∞</td><td>>364.8</td><td>488</td><td>4.1</td><td><strong>145</strong></td><td><strong>1.2</strong></td><td>274</td><td>2.3</td><td>624</td><td>5.2</td><td>2821</td><td>24.9</td></tr><tr><td>storm-N1000</td><td>24</td><td>3.7</td><td>11</td><td>1.7</td><td>21</td><td>3.2</td><td>8</td><td>1.3</td><td><strong>6</strong></td><td><strong>1.0</strong></td><td>8</td><td>1.3</td></tr><tr><td>storm-N5000</td><td>114</td><td>2.1</td><td>106</td><td>1.9</td><td>175</td><td>3.2</td><td>60</td><td>1.1</td><td><strong>55</strong></td><td><strong>1.0</strong></td><td>65</td><td>1.2</td></tr><tr><td>storm-N10000</td><td>224</td><td>1.4</td><td>496</td><td>3.2</td><td>492</td><td>3.2</td><td><strong>156</strong></td><td><strong>1.0</strong></td><td>159</td><td>1.0</td><td>189</td><td>1.2</td></tr><tr><td>storm-N20000</td><td><strong>458</strong></td><td><strong>1.0</strong></td><td>2370</td><td>5.2</td><td>1390</td><td>3.0</td><td>580</td><td>1.3</td><td>672</td><td>1.5</td><td>588</td><td>1.3</td></tr><tr><td>20term-N1000</td><td>577</td><td>15.2</td><td>757</td><td>19.9</td><td><strong>38</strong></td><td><strong>1.0</strong></td><td>82</td><td>2.2</td><td>49</td><td>1.3</td><td>74</td><td>1.9</td></tr><tr><td>20term-N5000</td><td>3506</td><td>5.6</td><td>24429</td><td>38.6</td><td><strong>634</strong></td><td><strong>1.0</strong></td><td>2101</td><td>3.3</td><td>1335</td><td>2.1</td><td>2247</td><td>3.6</td></tr><tr><td>20term-N10000</td><td>6901</td><td>3.0</td><td>+∞</td><td>>19.9</td><td><strong>2270</strong></td><td><strong>1.0</strong></td><td>10733</td><td>4.7</td><td>6199</td><td>2.7</td><td>10413</td><td>4.6</td></tr><tr><td>20term-N20000</td><td><strong>13687</strong></td><td><strong>1.3</strong></td><td>+∞</td><td>>6.2</td><td>20625</td><td>1.7</td><td>+∞</td><td>>4.2</td><td>+∞</td><td>>4.2</td><td>+∞</td><td>>4.2</td></tr><tr><td>Fleet20_3-N1000</td><td>533</td><td>9.1</td><td>225</td><td>3.9</td><td>145</td><td>2.5</td><td>95</td><td>1.7</td><td>102</td><td>1.7</td><td><strong>74</strong></td><td><strong>1.2</strong></td></tr><tr><td>Fleet20_3-N5000</td><td>2757</td><td>1.5</td><td>5330</td><td>2.9</td><td>2417</td><td>1.3</td><td>1950</td><td>1.0</td><td><strong>1873</strong></td><td><strong>1.0</strong></td><td>2097</td><td>1.1</td></tr><tr><td>Fleet20_3-N10000</td><td><strong>5710</strong></td><td><strong>1.0</strong></td><td>28933</td><td>5.1</td><td>9903</td><td>1.7</td><td>19913</td><td>3.4</td><td>8537</td><td>1.5</td><td>21383</td><td>3.7</td></tr><tr><td>Fleet20_3-N20000</td><td><strong>11300</strong></td><td><strong>1.0</strong></td><td>+∞</td><td>>4.1</td><td>34900</td><td>3.1</td><td>+∞</td><td>>3.8</td><td>+∞</td><td>>3.9</td><td>+∞</td><td>>3.9</td></tr><tr><td>product-N1000</td><td>1947</td><td>19.0</td><td>186</td><td>1.8</td><td>270</td><td>2.6</td><td>123</td><td>1.2</td><td>105</td><td>1.0</td><td><strong>103</strong></td><td><strong>1.0</strong></td></tr><tr><td>product-N5000</td><td>10467</td><td>7.6</td><td>3497</td><td>2.5</td><td>3730</td><td>2.7</td><td>1873</td><td>1.4</td><td>1483</td><td>1.1</td><td><strong>1377</strong></td><td><strong>1.0</strong></td></tr><tr><td>product-N10000</td><td>20200</td><td>3.7</td><td>15200</td><td>2.8</td><td>13300</td><td>2.5</td><td>6893</td><td>1.3</td><td>5583</td><td>1.0</td><td><strong>5397</strong></td><td><strong>1.0</strong></td></tr><tr><td>product-N20000</td><td>43000</td><td>1.9</td><td>+∞</td><td>>2.0</td><td>+∞</td><td>>1.9</td><td>29700</td><td>1.3</td><td>24733</td><td>1.1</td><td><strong>23067</strong></td><td><strong>1.0</strong></td></tr></tbody></table>

We first notice in Table 3 that BbB 1% solves all the instances, except Fleet20_3-N20000 where it only succeeds to solve one out of three problems, whereas Classic Multicut fails to solve optimally four groups of instances. As the algorithm avoids solving many subproblems and adding cuts in the relaxed master program, it overcomes the issue of the time spent in solving subproblems and delays the size growth of the relaxed master program. However, as we still add one cut for each solved subproblem in the Benders by batch algorithm, it still does not scale well when the number of subproblems becomes large. Classic monocut outperforms BbB on large-scale instances such as 20term with 20000 subproblems or Fleet20_3 with 20000 subproblems.

Table 4 shows that when partial cut aggregation is used, all the presented methods clearly outperform Classic monocut. As we aggregate the cuts over each batch, the size of the relaxed master program remains reasonable, and as the cuts are only computed on samples of subproblems, the algorithms avoid many symmetries due to the sum of the cuts over the subproblems. The table shows also that the best batch sizes are 1% and 5% (respectively BbB 1% CutAggr and BbB 5% CutAggr), except for two small instances. The two methods can be up to 25 times faster than Classic 1% CutAggr and more than 58 times faster than Classic 5% CutAggr.
<table><caption>Table 4: Results for the Benders by batch algorithm with partial cut aggregation, with batch sizes from 1% to 20% of the total number of subproblems.</caption><thead><tr><th rowspan="2">instance</th><th colspan="2">Classic monocut</th><th colspan="2">Classic 1% CutAggr</th><th colspan="2">Classic 5% CutAggr</th><th colspan="2">BbB 1% CutAggr</th><th colspan="2">BbB 5% CutAggr</th><th colspan="2">BbB 10% CutAggr</th><th colspan="2">BbB 20% CutAggr</th></tr><tr><th>time</th><th>ratio</th><th>time</th><th>ratio</th><th>time</th><th>ratio</th><th>time</th><th>ratio</th><th>time</th><th>ratio</th><th>time</th><th>ratio</th><th>time</th><th>ratio</th></tr></thead><tbody><tr><td>LandS-N1000</td><td>2</td><td>2.5</td><td>1</td><td>1.3</td><td>1</td><td>1.7</td><td>2</td><td>2.1</td><td>0.88</td><td>1.1</td><td><strong>0.78</strong></td><td><strong>1.0</strong></td><td>0.89</td><td>1.1</td></tr><tr><td>LandS-N5000</td><td>11</td><td>2.6</td><td>7</td><td>1.8</td><td>8</td><td>2.0</td><td>9</td><td>2.3</td><td>5</td><td>1.1</td><td><strong>4</strong></td><td><strong>1.0</strong></td><td>4</td><td>1.1</td></tr><tr><td>LandS-N10000</td><td>22</td><td>2.7</td><td>16</td><td>2.0</td><td>19</td><td>2.3</td><td>16</td><td>2.0</td><td><strong>8</strong></td><td><strong>1.0</strong></td><td>8</td><td>1.0</td><td>9</td><td>1.2</td></tr><tr><td>LandS-N20000</td><td>45</td><td>2.6</td><td>34</td><td>1.9</td><td>39</td><td>2.3</td><td>44</td><td>2.6</td><td><strong>17</strong></td><td><strong>1.0</strong></td><td>18</td><td>1.0</td><td>20</td><td>1.2</td></tr><tr><td>gbd-N1000</td><td>2</td><td>3.6</td><td>1</td><td>2.0</td><td>2</td><td>2.7</td><td>2</td><td>2.7</td><td><strong>0.61</strong></td><td><strong>1.0</strong></td><td>0.78</td><td>1.3</td><td>0.93</td><td>1.5</td></tr><tr><td>gbd-N5000</td><td>12</td><td>3.6</td><td>9</td><td>2.6</td><td>10</td><td>3.0</td><td>9</td><td>2.7</td><td><strong>3</strong></td><td><strong>1.0</strong></td><td>4</td><td>1.1</td><td>4</td><td>1.3</td></tr><tr><td>gbd-N10000</td><td>23</td><td>3.7</td><td>19</td><td>3.1</td><td>21</td><td>3.3</td><td>15</td><td>2.3</td><td><strong>6</strong></td><td><strong>1.0</strong></td><td>8</td><td>1.3</td><td>9</td><td>1.5</td></tr><tr><td>gbd-N20000</td><td>48</td><td>3.6</td><td>41</td><td>3.0</td><td>46</td><td>3.4</td><td>41</td><td>3.1</td><td><strong>14</strong></td><td><strong>1.0</strong></td><td>15</td><td>1.1</td><td>19</td><td>1.4</td></tr><tr><td>ssn-N1000</td><td>2408</td><td>175.8</td><td>24</td><td>1.8</td><td>142</td><td>10.5</td><td><strong>14</strong></td><td><strong>1.0</strong></td><td>61</td><td>4.5</td><td>134</td><td>9.8</td><td>242</td><td>17.7</td></tr><tr><td>ssn-N5000</td><td>13460</td><td>150.6</td><td>399</td><td>4.5</td><td>1582</td><td>17.7</td><td><strong>89</strong></td><td><strong>1.0</strong></td><td>322</td><td>3.6</td><td>659</td><td>7.4</td><td>1322</td><td>14.8</td></tr><tr><td>ssn-N10000</td><td>25901</td><td>140.4</td><td>1246</td><td>6.7</td><td>4858</td><td>26.1</td><td><strong>185</strong></td><td><strong>1.0</strong></td><td>707</td><td>3.8</td><td>1423</td><td>7.7</td><td>2914</td><td>15.8</td></tr><tr><td>ssn-N20000</td><td>+∞</td><td>>98.4</td><td>8603</td><td>20.0</td><td>26122</td><td>58.9</td><td><strong>441</strong></td><td><strong>1.0</strong></td><td>1615</td><td>3.7</td><td>3386</td><td>7.7</td><td>6757</td><td>15.4</td></tr><tr><td>storm-N1000</td><td>24</td><td>3.8</td><td>12</td><td>2.0</td><td>15</td><td>2.4</td><td>12</td><td>1.9</td><td><strong>6</strong></td><td><strong>1.0</strong></td><td>7</td><td>1.1</td><td>9</td><td>1.5</td></tr><tr><td>storm-N5000</td><td>114</td><td>3.4</td><td>72</td><td>2.1</td><td>94</td><td>2.8</td><td>52</td><td>1.5</td><td><strong>34</strong></td><td><strong>1.0</strong></td><td>36</td><td>1.1</td><td>55</td><td>1.6</td></tr><tr><td>storm-N10000</td><td>224</td><td>3.0</td><td>164</td><td>2.2</td><td>198</td><td>2.7</td><td>110</td><td>1.5</td><td><strong>74</strong></td><td><strong>1.0</strong></td><td>82</td><td>1.1</td><td>104</td><td>1.4</td></tr><tr><td>storm-N20000</td><td>458</td><td>2.9</td><td>369</td><td>2.3</td><td>423</td><td>2.6</td><td>226</td><td>1.4</td><td><strong>163</strong></td><td><strong>1.0</strong></td><td>169</td><td>1.1</td><td>238</td><td>1.5</td></tr><tr><td>20term-N1000</td><td>577</td><td>39.4</td><td>272</td><td>18.5</td><td>313</td><td>21.4</td><td><strong>15</strong></td><td><strong>1.0</strong></td><td>37</td><td>2.5</td><td>68</td><td>4.6</td><td>141</td><td>9.6</td></tr><tr><td>20term-N5000</td><td>3506</td><td>50.3</td><td>1604</td><td>23.2</td><td>1945</td><td>28.0</td><td><strong>70</strong></td><td><strong>1.0</strong></td><td>193</td><td>2.8</td><td>395</td><td>5.7</td><td>839</td><td>12.1</td></tr><tr><td>20term-N10000</td><td>6901</td><td>53.2</td><td>3364</td><td>26.0</td><td>4840</td><td>37.4</td><td><strong>130</strong></td><td><strong>1.0</strong></td><td>402</td><td>3.1</td><td>898</td><td>6.9</td><td>1978</td><td>15.3</td></tr><tr><td>20term-N20000</td><td>13687</td><td>49.1</td><td>7032</td><td>25.2</td><td>16287</td><td>57.3</td><td><strong>280</strong></td><td><strong>1.0</strong></td><td>914</td><td>3.3</td><td>2051</td><td>7.3</td><td>18312</td><td>65.2</td></tr><tr><td>Fleet20.3-N1000</td><td>533</td><td>18.9</td><td>125</td><td>4.4</td><td>222</td><td>7.9</td><td><strong>28</strong></td><td><strong>1.0</strong></td><td>42</td><td>1.5</td><td>74</td><td>2.6</td><td>131</td><td>4.7</td></tr><tr><td>Fleet20.3-N5000</td><td>2757</td><td>25.7</td><td>903</td><td>8.4</td><td>1530</td><td>14.3</td><td><strong>107</strong></td><td><strong>1.0</strong></td><td>211</td><td>2.0</td><td>358</td><td>3.3</td><td>649</td><td>6.1</td></tr><tr><td>Fleet20.3-N10000</td><td>5710</td><td>26.9</td><td>2000</td><td>9.4</td><td>3460</td><td>16.3</td><td><strong>212</strong></td><td><strong>1.0</strong></td><td>440</td><td>2.1</td><td>721</td><td>3.4</td><td>1310</td><td>6.2</td></tr><tr><td>Fleet20.3-N20000</td><td>11300</td><td>27.0</td><td>5053</td><td>12.1</td><td>7860</td><td>18.8</td><td><strong>419</strong></td><td><strong>1.0</strong></td><td>876</td><td>2.1</td><td>1520</td><td>3.6</td><td>2777</td><td>6.6</td></tr><tr><td>product-N1000</td><td>1947</td><td>20.0</td><td>190</td><td>2.0</td><td>431</td><td>4.4</td><td><strong>98</strong></td><td><strong>1.0</strong></td><td>141</td><td>1.5</td><td>253</td><td>2.6</td><td>505</td><td>5.2</td></tr><tr><td>product-N5000</td><td>10467</td><td>28.9</td><td>1523</td><td>4.2</td><td>3323</td><td>9.2</td><td><strong>362</strong></td><td><strong>1.0</strong></td><td>773</td><td>2.1</td><td>1567</td><td>4.3</td><td>2873</td><td>7.9</td></tr><tr><td>product-N10000</td><td>20200</td><td>25.0</td><td>3827</td><td>4.8</td><td>7757</td><td>9.7</td><td><strong>823</strong></td><td><strong>1.0</strong></td><td>1523</td><td>1.9</td><td>3053</td><td>3.8</td><td>5530</td><td>6.9</td></tr><tr><td>product-N20000</td><td>43000</td><td>25.7</td><td>9963</td><td>6.0</td><td>19367</td><td>11.6</td><td><strong>1693</strong></td><td><strong>1.0</strong></td><td>3367</td><td>2.0</td><td>6320</td><td>3.8</td><td>12500</td><td>7.5</td></tr></tbody></table>

<figure><img src="image_4.png" /><figcaption>Figure 3: Number of subproblems solved at each iteration by BbB 1% CutAggr and Classic 1% CutAggr (left plots). For Classic monocut, Classic multicut, BbB 1% CutAggr, Classic 1% CutAggr, the total number of relaxed master programs and subproblems solved, as well as the associated solution time (right plots). Symbol ">" means that the time limit is reached without proven optimality. To the sum of the time needed to solve the relaxed master programs and the subproblems, one must add the time needed for the other operations (e.g., solving the mean-value problem to obtain $x^{(0)}$, cut computation and their addition to (RMP), configuration of the subproblems for each new first-stage solution).</figcaption></figure>
The better performance of the Benders by batch algorithm with partial cut aggregation can be explained by Figure 3. We see that in most of the iterations, the algorithm solves only one batch of subproblems to show that the current first-stage solution cannot be proven optimal and to separate it. Despite the greater number of iterations performed by **BbB 1% CutAggr** due to its explorative nature, we observe that it needs to solve less subproblems than **Classic 1% CutAggr** to converge. Specifically, for a 20term instance with 20000 subproblems and a product instance with 20000 subproblems, **BbB 1% CutAggr** solves respectively 23 times less and 7 times less subproblems than **Classic 1% CutAggr** to converge. Although **Classic 1% CutAggr** evaluates almost three times less first-stage solutions for the 20term instance (and more than 10 times less for the product instance), it takes ultimately more time to converge than **BbB 1% CutAggr**: 7375 seconds for **Classic 1% CutAggr** compared to 261 seconds for **BbB 1% CutAggr** to solve the 20term instance, and 9820 seconds for **Classic 1% CutAggr** compared to 1790 seconds for **BbB 1% CutAggr** to solve the product instance. This can be explained by the fact that the relaxed master program contains fewer cuts at most iterations in **BbB 1% CutAggr** than in **Classic 1% CutAggr**. We observe that the time spent in solving the subproblems represents most of the computing time for the 20term instance and most of the computing time for the product instance. All of the above suggests that the smaller the first-stage problem is, the more efficient the Benders by batch algorithm is.

### 5.3.2 Impact of the stabilization on BbB

We now present the results obtained when the two stabilization schemes presented in §4.3 are applied to the most competitive versions of Bbb (batch sizes of 1% and 5%, and with partial cut aggregation). Figures 4 and 5 show the performance profiles of **BbB CutAggr** with and without stabilization. We present the results with basic stabilization for $\alpha \in \{0.1, 0.5, 0.9\}$ and with solution memory stabilization for $\alpha \in \{0.1, 0.5, 0.9\}$ and $\beta \in \{0.1, 0.5, 0.9\}$. Each stabilized method is denoted by **BbB 1% CutAggr** or **BbB 5% CutAggr** followed by the values for the parameters.

<figure><img src="image_5.png" /><figcaption>Figure 4: Performance profiles of the stabilized Benders by batch algorithm with batch size of 1% and cut aggregation.</figcaption></figure>

Figure 4 shows that the proposed stabilization schemes accelerate **BbB 1% CutAggr**, and can be up to 70% faster than the unstabilized algorithm. Four stabilizations are more efficient on the tested instances and give similar results, namely the basic stabilization with $\alpha = 0.5$, and the solution memory stabilization with $(\alpha, \beta) \in \{(0.5, 0.1), (0.5, 0.5), (0.9, 0.5)\}$.

Figure 5 shows similar results for **BbB 5% CutAggr**. The same four methods are the most efficient and equivalent to each other. The algorithm with a solution memory stabilization parameterized by $(\alpha, \beta) = (0.1, 0.9)$ is less efficient than **BbB 5% CutAggr**. In this case, a small step size ($\alpha = 0.1$) and a high memory parameter ($\beta = 0.9$) slow down the convergence. For all the other cases, the use of a primal stabilization scheme accelerates the algorithm.

To conclude, results show no clear difference between the two proposed stabilization schemes. The solution memory stabilization does efficiently stabilize the algorithm, but the basic stabilization might be the method of choice as it is much simpler and provides similar computational results for the tested instances.
<figure><img src="image_6.png" /><figcaption>Figure 5: Performance profiles of the stabilized Benders by batch algorithm with batch size of 5% and cut aggregation.</figcaption></figure>

<table><caption>Table 5: Final results, the best stabilized Benders by batch algorithm compared to all stabilized benchmark methods.</caption><thead><tr><th rowspan="2">instance</th><th colspan="2">CPLEX Barrier</th><th colspan="2">Level Bundle</th><th colspan="2">In-out multicut</th><th colspan="2">In-out monocut</th><th colspan="2">In-out 1% CutAggr</th><th colspan="2">In-out 5% CutAggr</th><th colspan="2">BbB 1% CutAggr α = 0.5</th></tr><tr><th>time</th><th>ratio</th><th>time</th><th>ratio</th><th>time</th><th>ratio</th><th>time</th><th>ratio</th><th>time</th><th>ratio</th><th>time</th><th>ratio</th><th>time</th><th>ratio</th></tr></thead><tbody><tr><td>LandS-N1000</td><td><strong>0.07</strong></td><td><strong>1.0</strong></td><td>1</td><td>17.3</td><td>0.89</td><td>12.4</td><td>1</td><td>20.0</td><td>0.71</td><td>9.7</td><td>0.98</td><td>13.4</td><td>0.96</td><td>13.2</td></tr><tr><td>LandS-N5000</td><td><strong>1</strong></td><td><strong>1.0</strong></td><td>7</td><td>9.0</td><td>8</td><td>10.5</td><td>9</td><td>10.5</td><td>5</td><td>6.0</td><td>6</td><td>7.2</td><td>5</td><td>6.7</td></tr><tr><td>LandS-N10000</td><td><strong>1</strong></td><td><strong>1.0</strong></td><td>14</td><td>14.0</td><td>24</td><td>23.6</td><td>16</td><td>15.6</td><td>10</td><td>9.7</td><td>11</td><td>11.1</td><td>9</td><td>9.0</td></tr><tr><td>LandS-N20000</td><td><strong>5</strong></td><td><strong>1.0</strong></td><td>27</td><td>6.8</td><td>62</td><td>16.5</td><td>41</td><td>10.4</td><td>22</td><td>5.6</td><td>22</td><td>5.5</td><td>21</td><td>5.4</td></tr><tr><td>gbd-N1000</td><td><strong>0.04</strong></td><td><strong>1.0</strong></td><td>2</td><td>61.2</td><td>1</td><td>36.6</td><td>2</td><td>58.8</td><td>1</td><td>33.6</td><td>2</td><td>44.8</td><td>0.88</td><td>25.6</td></tr><tr><td>gbd-N5000</td><td><strong>0.17</strong></td><td><strong>1.0</strong></td><td>10</td><td>60.1</td><td>10</td><td>60.9</td><td>10</td><td>64.0</td><td>7</td><td>41.8</td><td>8</td><td>47.1</td><td>4</td><td>24.8</td></tr><tr><td>gbd-N10000</td><td><strong>0.35</strong></td><td><strong>1.0</strong></td><td>24</td><td>69.5</td><td>23</td><td>67.5</td><td>21</td><td>61.7</td><td>16</td><td>45.7</td><td>17</td><td>50.3</td><td>8</td><td>22.2</td></tr><tr><td>gbd-N20000</td><td><strong>0.91</strong></td><td><strong>1.0</strong></td><td>44</td><td>48.8</td><td>82</td><td>89.8</td><td>54</td><td>60.6</td><td>30</td><td>34.3</td><td>34</td><td>39.1</td><td>17</td><td>18.5</td></tr><tr><td>ssn-N1000</td><td>32</td><td>6.0</td><td>90</td><td>17.1</td><td><strong>6</strong></td><td><strong>1.0</strong></td><td>137</td><td>27.3</td><td>10</td><td>1.8</td><td>19</td><td>3.6</td><td>8</td><td>1.5</td></tr><tr><td>ssn-N5000</td><td>310</td><td>10.6</td><td>657</td><td>22.2</td><td><strong>31</strong></td><td><strong>1.0</strong></td><td>795</td><td>27.4</td><td>70</td><td>2.4</td><td>133</td><td>4.5</td><td>47</td><td>1.6</td></tr><tr><td>ssn-N10000</td><td>1223</td><td>20.3</td><td>1501</td><td>25.2</td><td><strong>63</strong></td><td><strong>1.0</strong></td><td>1464</td><td>23.3</td><td>171</td><td>2.9</td><td>312</td><td>5.2</td><td>91</td><td>1.5</td></tr><tr><td>ssn-N20000</td><td>2619</td><td>13.7</td><td>3109</td><td>16.3</td><td>243</td><td>1.3</td><td>2861</td><td>15.2</td><td>400</td><td>2.1</td><td>736</td><td>3.9</td><td><strong>191</strong></td><td><strong>1.0</strong></td></tr><tr><td>storm-N1000</td><td>41</td><td>5.8</td><td>15</td><td>2.1</td><td>9</td><td>1.3</td><td>14</td><td>2.1</td><td>8</td><td>1.1</td><td>9</td><td>1.4</td><td><strong>7</strong></td><td><strong>1.0</strong></td></tr><tr><td>storm-N5000</td><td>316</td><td>9.7</td><td>76</td><td>2.3</td><td>41</td><td>1.3</td><td>62</td><td>1.9</td><td>49</td><td>1.5</td><td>52</td><td>1.6</td><td><strong>33</strong></td><td><strong>1.0</strong></td></tr><tr><td>storm-N10000</td><td>764</td><td>11.8</td><td>145</td><td>2.3</td><td>125</td><td>1.9</td><td>201</td><td>3.1</td><td>99</td><td>1.5</td><td>110</td><td>1.7</td><td><strong>65</strong></td><td><strong>1.0</strong></td></tr><tr><td>storm-N20000</td><td>2390</td><td>17.4</td><td>288</td><td>2.1</td><td>573</td><td>4.2</td><td>252</td><td>1.8</td><td>211</td><td>1.5</td><td>232</td><td>1.7</td><td><strong>137</strong></td><td><strong>1.0</strong></td></tr><tr><td>20term-N1000</td><td>14</td><td>1.3</td><td>217</td><td>20.9</td><td>36</td><td>3.5</td><td>114</td><td>10.8</td><td>27</td><td>2.6</td><td>44</td><td>4.3</td><td><strong>10</strong></td><td><strong>1.0</strong></td></tr><tr><td>20term-N5000</td><td>82</td><td>1.7</td><td>1044</td><td>21.2</td><td>482</td><td>9.7</td><td>681</td><td>13.8</td><td>197</td><td>4.0</td><td>269</td><td>5.5</td><td><strong>50</strong></td><td><strong>1.0</strong></td></tr><tr><td>20term-N10000</td><td>199</td><td>2.0</td><td>2450</td><td>24.4</td><td>2805</td><td>27.9</td><td>1190</td><td>11.8</td><td>474</td><td>4.7</td><td>593</td><td>5.9</td><td><strong>100</strong></td><td><strong>1.0</strong></td></tr><tr><td>20term-N20000</td><td>455</td><td>2.3</td><td>4843</td><td>24.7</td><td>10992</td><td>56.0</td><td>1754</td><td>8.9</td><td>1010</td><td>5.1</td><td>1371</td><td>7.0</td><td><strong>197</strong></td><td><strong>1.0</strong></td></tr><tr><td>Fleet20.3-N1000</td><td>23</td><td>1.3</td><td>107</td><td>6.2</td><td>50</td><td>2.9</td><td>93</td><td>5.4</td><td>26</td><td>1.5</td><td>41</td><td>2.4</td><td><strong>17</strong></td><td><strong>1.0</strong></td></tr><tr><td>Fleet20.3-N5000</td><td>269</td><td>3.6</td><td>500</td><td>6.7</td><td>719</td><td>9.6</td><td>473</td><td>6.3</td><td>184</td><td>2.4</td><td>250</td><td>3.3</td><td><strong>75</strong></td><td><strong>1.0</strong></td></tr><tr><td>Fleet20.3-N10000</td><td>809</td><td>5.5</td><td>1004</td><td>6.9</td><td>3747</td><td>25.6</td><td>1029</td><td>7.0</td><td>435</td><td>3.0</td><td>590</td><td>4.0</td><td><strong>146</strong></td><td><strong>1.0</strong></td></tr><tr><td>Fleet20.3-N20000</td><td>2446</td><td>7.9</td><td>2730</td><td>8.8</td><td>17000</td><td>54.7</td><td>1780</td><td>5.8</td><td>1018</td><td>3.3</td><td>1313</td><td>4.2</td><td><strong>310</strong></td><td><strong>1.0</strong></td></tr><tr><td>product-N1000</td><td>179</td><td>2.3</td><td>625</td><td>8.2</td><td>81</td><td>1.1</td><td>513</td><td>6.7</td><td>113</td><td>1.5</td><td>183</td><td>2.4</td><td><strong>76</strong></td><td><strong>1.0</strong></td></tr><tr><td>product-N5000</td><td>2121</td><td>6.7</td><td>3200</td><td>10.3</td><td>1127</td><td>3.6</td><td>2690</td><td>8.7</td><td>787</td><td>2.5</td><td>1380</td><td>4.4</td><td><strong>312</strong></td><td><strong>1.0</strong></td></tr><tr><td>product-N10000</td><td>4397</td><td>8.0</td><td>7173</td><td>13.0</td><td>5357</td><td>9.8</td><td>5730</td><td>10.4</td><td>1970</td><td>3.6</td><td>3133</td><td>5.7</td><td><strong>552</strong></td><td><strong>1.0</strong></td></tr><tr><td>product-N20000</td><td>15463</td><td>13.6</td><td>14300</td><td>12.5</td><td>+∞</td><td>>40.5</td><td>12333</td><td>10.8</td><td>4887</td><td>4.3</td><td>7983</td><td>7.0</td><td><strong>1140</strong></td><td><strong>1.0</strong></td></tr></tbody></table>

### 5.3.3 Comparison with state-of-the-art methods

We now compare the stabilized Benders by batch algorithm to classical methods of the literature. We show in Table 5 the times and ratios of CPLEX Barrier and all the stabilized methods of our benchmark, In-out monocut, In-out multicut, Level bundle, In-out 1% CutAggr and In-out 5% CutAggr with the best performing stabilized Benders by batch BbB 1% CutAggr $\alpha = 0.5$. We first observe that, on the small instances LandS and gbd, CPLEX Barrier converges faster than all the other methods. As those instances have very few variables both in first and second stages, they remain small even with 20000 subproblems, and are solved very efficiently by CPLEX Barrier. However, we can notice that even for these small instances, BbB 1% CutAggr $\alpha = 0.5$ is the best method among all the cutting planes algorithms. Table 5 shows clearly that the stabilized Benders by batch algorithm outperforms all the other methods on the large instances, and can be up to more than 25 times faster than Level Bundle or 15 times faster than In-out
**monocut.** We also show that, even if **In-out 1% CutAggr** outperforms other classical stabilized methods from the literature, the stabilized Benders by batch algorithm can be up to 5 times faster. This shows that, firstly, using a static cut aggregation combined with primal stabilization allows to speed up classical methods used to benchmark algorithms from the literature, and secondly, that not solving systematically all the subproblems allows to further improve the computing times on the test instances.

As for the unstabilized case, we observe in our experiments that **BbB 1% CutAggr α = 0.5** needs to solve way less subproblems than other methods to converge, and that the time spent in solving the subproblems represents almost all the computing time in all presented methods (see Appendix C).

Figure 6 shows the evolution of the relative gap between the lower bound and the optimal value, of twodifferent algorithms, on four different instances, according to the time. We see that adding only a few cuts at each iterations allows the lower bound to converge faster to the optimal value to the problem. Moreover, we observe that, on three of the four presented instances, **BbB 1% CutAggr α = 0.5** reaches a relative gap of $10^{-6}$ while all the other algorithms still have a large relative gap (e.g. $10^0$ on ssn or $10^{-1}$ on Fleet). Although **BbB 1% CutAggr α = 0.5** adds less cuts at each iteration, its lower bound value is usually larger than the one computed in the other algorithms, when compared for the same computing time, except for some very short time intervals early in the solution process where the lower bound in **In-Out 1% CutAggr** is better. This suggests that the cuts generated when the approximation of the subproblem value function is coarse, not only take time to be computed, but also do not help much to improve the value of the lower bound.

<figure><img src="image_7.png" /><figcaption>Figure 6: Evolution of the relative gap between the lower bound and the optimal value as a function of time, on a two instances with 20000 subproblems (20term-N20000-s20000 and product-N20000-s20000)</figcaption></figure>

### 5.3.4 Sensitivity of BbB to the initial order of the subproblems

We performed several experiments testing different initial orders of the subproblems to assess the sensitivity of the computing time of our method to this choice. We ran **BbB 1% CutAggr α = 0.5**, for 500 different initial orders, on one instance with 5000 subproblems and one with 10000 subproblems for each tested problem. We report in Table 6 the minimum and maximum times observed, the median, and the first and ninth decile on computing times. We observe that the initial order has usually a limited impact on the efficiency of our algorithm. We also remark that the stabilized Benders by batch algorithm present lower computing times than **In-out 1% CutAggr**, the best performing method used as comparison in the numerical results, even for the maximum time observed. Although the impact is in general limited, we observe that the initial order can have an impact on the computing time for some instances, such as LandS or gbd. However, the computing times observed are almost always smaller than the computing times of **In-out 1% CutAggr**, the best performing method in the literature to which BbB is compared to in the paper.

We also evaluated the impact of the optimality gap on the convergence of the algorithm. We see expected results (see Appendix D), that is, a smaller optimality gap induces larger computing times on the largest instances of our test set, but this would also be the case with the other algorithms.
<table><caption>Table 6: Computing times for BbB 1% CutAggr $\alpha$ = 0.5 on 500 different initial orders of the subproblems</caption><thead><tr><th rowspan="2">instance</th><th colspan="2">Min Time</th><th colspan="2">10%</th><th colspan="2">50%</th><th colspan="2">90%</th><th colspan="2">Max Time</th><th colspan="2">In-out 1% CutAggr</th></tr><tr><th>time</th><th>ratio</th><th>time</th><th>ratio</th><th>time</th><th>ratio</th><th>time</th><th>ratio</th><th>time</th><th>ratio</th><th>time</th><th>ratio</th></tr></thead><tbody><tr><td>LandS-N5000</td><td><strong>4.1</strong></td><td><strong>1.0</strong></td><td>4.5</td><td>1.1</td><td>5.3</td><td>1.3</td><td>6.2</td><td>1.5</td><td>7.3</td><td>1.8</td><td>5.0</td><td>1.2</td></tr><tr><td>LandS-N10000</td><td><strong>8.3</strong></td><td><strong>1.0</strong></td><td>9.2</td><td>1.1</td><td>10.2</td><td>1.2</td><td>11.9</td><td>1.4</td><td>15.6</td><td>1.9</td><td>10.0</td><td>1.2</td></tr><tr><td>gbd-N5000</td><td><strong>3.1</strong></td><td><strong>1.0</strong></td><td>3.5</td><td>1.1</td><td>4.1</td><td>1.3</td><td>5.0</td><td>1.6</td><td>7.1</td><td>2.3</td><td>7.0</td><td>2.3</td></tr><tr><td>gbd-N10000</td><td><strong>6.0</strong></td><td><strong>1.0</strong></td><td>7.2</td><td>1.2</td><td>8.3</td><td>1.4</td><td>10.3</td><td>1.7</td><td>14.0</td><td>2.3</td><td>16.0</td><td>2.7</td></tr><tr><td>ssn-N5000</td><td><strong>40.2</strong></td><td><strong>1.0</strong></td><td>44.3</td><td>1.1</td><td>46.8</td><td>1.2</td><td>49.8</td><td>1.2</td><td>54.1</td><td>1.3</td><td>70.0</td><td>1.7</td></tr><tr><td>ssn-N10000</td><td><strong>82.5</strong></td><td><strong>1.0</strong></td><td>87.3</td><td>1.1</td><td>92.5</td><td>1.1</td><td>102.0</td><td>1.2</td><td>122.4</td><td>1.5</td><td>171.0</td><td>2.1</td></tr><tr><td>storm-N5000</td><td><strong>28.0</strong></td><td><strong>1.0</strong></td><td>29.8</td><td>1.1</td><td>31.4</td><td>1.1</td><td>34.5</td><td>1.2</td><td>43.5</td><td>1.6</td><td>49.0</td><td>1.8</td></tr><tr><td>storm-N10000</td><td><strong>58.0</strong></td><td><strong>1.0</strong></td><td>60.5</td><td>1.0</td><td>64.2</td><td>1.1</td><td>69.7</td><td>1.2</td><td>83.2</td><td>1.4</td><td>99.0</td><td>1.7</td></tr><tr><td>20term-N5000</td><td><strong>43.5</strong></td><td><strong>1.0</strong></td><td>47.8</td><td>1.1</td><td>54.1</td><td>1.2</td><td>61.6</td><td>1.4</td><td>77.2</td><td>1.8</td><td>197.0</td><td>4.5</td></tr><tr><td>20term-N10000</td><td><strong>82.0</strong></td><td><strong>1.0</strong></td><td>91.5</td><td>1.1</td><td>103.2</td><td>1.3</td><td>115.0</td><td>1.4</td><td>136.2</td><td>1.7</td><td>474.0</td><td>5.8</td></tr><tr><td>Fleet20.3-N5000</td><td><strong>72.5</strong></td><td><strong>1.0</strong></td><td>74.7</td><td>1.0</td><td>76.6</td><td>1.1</td><td>78.7</td><td>1.1</td><td>83.3</td><td>1.1</td><td>184.0</td><td>2.5</td></tr><tr><td>Fleet20.3-N10000</td><td><strong>142.0</strong></td><td><strong>1.0</strong></td><td>148.0</td><td>1.0</td><td>152.0</td><td>1.1</td><td>157.0</td><td>1.1</td><td>166.0</td><td>1.2</td><td>435.0</td><td>3.1</td></tr><tr><td>product-N5000</td><td><strong>268.0</strong></td><td><strong>1.0</strong></td><td>279.0</td><td>1.0</td><td>292.0</td><td>1.1</td><td>315.0</td><td>1.2</td><td>355.0</td><td>1.3</td><td>787.0</td><td>2.9</td></tr><tr><td>product-N10000</td><td><strong>528.0</strong></td><td><strong>1.0</strong></td><td>553.0</td><td>1.0</td><td>573.0</td><td>1.1</td><td>603.0</td><td>1.1</td><td>679.0</td><td>1.3</td><td>1970.0</td><td>3.7</td></tr></tbody></table>

# 6 Conclusion

We proposed in this paper the Benders by batch algorithm to solve two-stage stochastic linear programming problems with finite probability distribution. This algorithm solves only a few subproblems at most iterations. The algorithm is exact and does not need a fixed recourse or a deterministic objective function. We showed that performing an optimality check after the resolution of a very few subproblems, each 1% of the numbers of subproblems in our tests, allows to significantly improve the solution time.

To avoid strong oscillations of the first-stage variables, we also introduced a stabilized version of the algorithm. This algorithm is based on a primal stabilization scheme responsible for generating the points at which the subproblems are solved. We presented a sufficient condition for a primal stabilization scheme that ensures the convergence of the Benders by batch algorithm and proposed two schemes satisfying it. The stabilized Benders by batch algorithm can be up to 25 times faster than the level bundle method, or 5 times faster than Benders decomposition with in-out stabilization and static partial cut aggregation of (Trukhanov et al., 2010).

Applying dual stabilization (Magnanti and Wong, 1981; Sherali and Lunday, 2013) to the Benders by batch algorithm is straightforward and could improve the results. The algorithm can be parallelized and may benefit from effective parallelized methods, such as the asynchronous method of Linderoth and Wright (2003). The use of more advanced cut aggregation strategies is also a path worth exploring. Finally, an interesting perspective is to adapt the Benders by batch algorithm to solve mixed-integer master programs within a Branch&Cut framework.

# Acknowledgments

This project has been funded by RTE (Réseau de Transport d'Electricité), French company in charge of the electricity network management, through the projects Antares and Antares Xpansion: https://github.com/AntaresSimulatorTeam/antares-xpansion, which are used for long-term adequacy studies. Computer time for this study was provided by the computing facilities MCIA (Mésocentre de Calcul Intensif Aquitain) of the Université de Bordeaux and of the Université de Pau et des Pays de l'Adour.

We thank the anonymous referees, whose comments helped improve and clarify this paper.

# References

* Ben-Ameur, W. and Neto, J. (2007). Acceleration of cutting-plane and column generation algorithms: Applications to network design. *Networks*, 49(1):3–17.

* Birge, J. R. and Louveaux, F. (1988). A multicut algorithm for two-stage stochastic linear programs. *European Journal of Operational Research*, 34(3):384–392.

* Bodur, M. and Luedtke, J. R. (2022). Two-stage linear decision rules for multi-stage stochastic programming. *Mathematical Programming*, 191(1):347–380.

* Bonami, P., Salvagnin, D., and Tramontani, A. (2020). Implementing Automatic Benders Decomposition in a Modern MIP Solver. In *Integer Programming and Combinatorial Optimization*, volume 12125, pages 78–90. Springer International Publishing, Cham.
Crainic, T. G., Hewitt, M., Maggioni, F., and Rei, W. (2020). Partial Benders Decomposition: General Methodology and Application to Stochastic Network Design. *Transportation Science*.

Dantzig, G. B. (1963). *Linear Programming and Extensions*. Princeton, New Jersey, princeton university press edition.

Dantzig, G. B. and Infanger, G. (1991). Large-Scale Stochastic Linear Programs: Importance Sampling and Benders Decomposition: Technical report, Defense Technical Information Center, Fort Belvoir, VA.

de Oliveira, W. and Sagastizábal, C. (2014). Level bundle methods for oracles with on-demand accuracy. *Optimization Methods and Software*, 29(6):1180–1209.

Dolan, E. D. and Moré, J. J. (2002). Benchmarking optimization software with performance profiles. *Mathematical Programming*, 91(2):201–213.

Fischetti, M., Ljubić, I., and Sinnl, M. (2016). Redesigning Benders Decomposition for Large-Scale Facility Location. *Management Science*, 63(7):2146–2162.

Fischetti, M. and Salvagnin, D. (2010). An In-Out Approach to Disjunctive Optimization. In *Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems*, volume 6140, pages 136–140. Springer Berlin Heidelberg, Berlin, Heidelberg.

Gassmann, H. I. and Schweitzer, E. (2001). A comprehensive input format for stochastic linear programs. *Annals of Operations Research*, 104(1):89–125.

Higle, J. L. and Sen, S. (1991). Stochastic Decomposition: An Algorithm for Two-Stage Linear Programms with Recours. *Mathematics of Operations Research*, 16(3):447–669.

IBM (2019). IBM ILOG CPLEX 12.10 User's Manual (IBM ILOG CPLEX Division, Incline Village, NV).

Infanger, G. (1992). Monte Carlo (importance) sampling within a benders decomposition algorithm for stochastic linear programs. *Annals of Operations Research*, 39(1):69–95.

Lemaréchal, C., Nemirovskii, A., and Nesterov, Y. (1995). New variants of bundle methods. *Mathematical Programming*, 69(1-3):111–147.

Linderoth, J., Shapiro, A., and Wright, S. (2006). The empirical behavior of sampling methods for stochastic programming. *Annals of Operations Research*, 142(1):215–241.

Linderoth, J. and Wright, S. (2003). Decomposition Algorithms for Stochastic Programming on a Computational Grid. *Computational Optimization and Applications*, 24(2):207–250.

Louveaux, F. and Smeers, Y. (1988). Optimal Investments for Electricity Generation: A Stochastic Model and a Test-Problem. In *Numerical Techniques for Stochastic Optimization*, Y. Ermoliev and R.J.-B. Wets (Eds.), pages 445–454, Berlin. Springer-Verlag,.

Magnanti, T. L. and Wong, R. T. (1981). Accelerating Benders Decomposition: Algorithmic Enhancement and Model Selection Criteria. *Operations Research*, 29(3):464–484.

Mak, W.-K., Morton, D. P., and Wood, R. (1999). Monte Carlo bounding techniques for determining solution quality in stochastic programs. *Operations Research Letters*, 24(1-2):47–56.

Mulvey, J. M. and Ruszczyński, A. (1995). A New Scenario Decomposition Method for Large-Scale Stochastic Optimization. *Operations Research*, 43(3):477–490.

Nesterov, Y. (2004). Nonsmooth Convex Optimization. In Nesterov, Y., editor, *Introductory Lectures on Convex Optimization: A Basic Course*, pages 111–170. Springer US, Boston, MA.

Oliveira, W., Sagastizábal, C., and Scheimberg, S. (2011). Inexact Bundle Methods for Two-Stage Stochastic Programming. *SIAM Journal on Optimization*, 21(2):517–544.

Papadakos, N. (2008). Practical enhancements to the Magnanti-Wong method. *Operations Research Letters*, 36(4):444–449.
Pessoa, A., Sadykov, R., Uchoa, E., and Vanderbeck, F. (2013). In-Out Separation and Column Generation Stabilization by Dual Price Smoothing. In *Experimental Algorithms*, volume 7933, pages 354–365. Springer Berlin Heidelberg, Berlin, Heidelberg.

Polyak, B. T. (1964). Some methods of speeding up the convergence of iteration methods. *USSR Computational Mathematics and Mathematical Physics*, 4(5):1–17.

Ruszczyński, A. (1986). A regularized decomposition method for minimizing a sum of polyhedral functions. *Mathematical Programming*, 35(3):309–333.

Ruszczyński, A. (1997). Decomposition methods in stochastic programming. *Mathematical Programming*, 79(1):333–353.

Sen, S., Doverspike, R. D., and Cosares, S. (1994). Network planning with random demand. *Telecommunication Systems*, 3(1):11–30.

Shapiro, A. and Nemirovski, A. (2005). On Complexity of Stochastic Programming Problems. In Jeyakumar, V. and Rubinov, A., editors, *Continuous Optimization: Current Trends and Modern Applications*, Applied Optimization, pages 111–146. Springer US, Boston, MA.

Sherali, H. D. and Lunday, B. J. (2013). On generating maximal nondominated Benders cuts. *Annals of Operations Research*, 210(1):57–72.

Song, Y. and Luedtke, J. (2015). An Adaptive Partition-Based Approach for Solving Two-Stage Stochastic Programs with Fixed Recourse. *SIAM Journal on Optimization*, 25(3):1344–1367.

Sutskever, I., Martens, J., Dahl, G., and Hinton, G. (2013). On the importance of initialization and momentum in deep learning. volume 28 of *Proceedings of Machine Learning Research*, pages 1139–1147, Atlanta, Georgia, USA. PMLR.

Trukhanov, S., Ntaimo, L., and Schaefer, A. (2010). Adaptive multicut aggregation for two-stage stochastic linear programs with recourse. *European Journal of Operational Research*, 206(2):395–406.

van Ackooij, W., de Oliveira, W., and Song, Y. (2017). Adaptive Partition-Based Level Decomposition Methods for Solving Two-Stage Stochastic Programs with Fixed Recourse. *INFORMS Journal on Computing*, 30(1):57–70.

Van Slyke, R. M. and Wets, R. (1969). L-Shaped Linear Programs with Applications to Optimal Control and Stochastic Programming. *SIAM Journal on Applied Mathematics*, 17(4):638–663.

Vanderbeck, F. (2005). Implementing Mixed Integer Column Generation. In Desaulniers, G., Desrosiers, J., and Solomon, M. M., editors, *Column Generation*, pages 331–358. Springer US, Boston, MA.

Wets, R. (1983). Stochastic Programming: Solution Techniques and Approximation Schemes. In *Mathematical Programming: The State of the Art*, pages 566–603. Springer Berlin Heidelberg, Berlin, Heidelberg.

Wolf, C., Fábián, C. I., Koberstein, A., and Suhl, L. (2014). Applying oracles of on-demand accuracy in two-stage stochastic programming – A computational study. *European Journal of Operational Research*, 239(2):437–448.

You, F. and Grossmann, I. E. (2013). Multicut Benders decomposition algorithm for process supply chain planning under uncertainty. *Annals of Operations Research*, 210(1):191–211.

Zverovich, V., Fábián, C. I., Ellison, E. F. D., and Mitra, G. (2012). A computational study of a solver system for processing two-stage stochastic LPs with enhanced Benders decomposition. *Mathematical Programming Computation*, 4(3):211–238.
# A Proofs

## A.1 Proof of Proposition 1

*Proof.* (⇒) Assume that $\tilde{x}^{(k)}$ is an optimal solution to problem 1. We have:

$$ 
\begin{aligned}
& UB(\tilde{x}^{(k)}) - LB^{(k)} \le \epsilon \\
& \iff c^\top \tilde{x}^{(k)} + \sum_{s \in S} p_s \phi(\tilde{x}^{(k)}, s) - \left( c^\top \tilde{x}^{(k)} + \sum_{s \in S} p_s \tilde{\theta}_s^{(k)} \right) \le \epsilon \\
& \iff \sum_{s \in S} p_s \left( \phi(\tilde{x}^{(k)}, s) - \tilde{\theta}_s^{(k)} \right) \le \epsilon
\end{aligned}
$$

As family $(S_{\sigma(1)}, S_{\sigma(2)}, ..., S_{\sigma(\kappa)})$ defines a partition of S, the previous equation gives:

$$ 
\begin{aligned}
& \sum_{t=1}^{\kappa} \sum_{s \in S_{\sigma(t)}} p_s \left( \phi(\tilde{x}^{(k)}, s) - \tilde{\theta}_s^{(k)} \right) \le \epsilon \\
& \iff \sum_{t=i}^{\kappa} \sum_{s \in S_{\sigma(t)}} p_s \left( \phi(\tilde{x}^{(k)}, s) - \tilde{\theta}_s^{(k)} \right) \le \epsilon_i, \quad \forall i \in \{1, \dots, \kappa\}
\end{aligned}
$$

As $p_s \ge 0$, $\forall s \in S$, and as $(RMP)^{(k)}$ is a relaxation of problem 1, by independence of the batches, we have:

$$ \sum_{s \in S_{\sigma(t)}} p_s \left( \phi(\tilde{x}^{(k)}, s) - \tilde{\theta}_s^{(k)} \right) \ge 0, \forall t \in \{1, \dots, \kappa\}. $$

$$ \sum_{s \in S_{\sigma(i)}} p_s \left( \phi(\tilde{x}^{(k)}, s) - \tilde{\theta}_s^{(k)} \right) \le \epsilon_i, \quad \forall i \in \{1, \dots, \kappa\} $$

which is the definition of batch $S_{\sigma(i)}$ being $\epsilon_i$-approximated by $(RMP)^{(k)}$.

(↔) Assume that for every index $i \in [1, \kappa]$, we have $\sum_{s \in S_{\sigma(i)}} p_s \left( \phi(\tilde{x}^{(k)}, s) - \tilde{\theta}_s^{(k)} \right) \le \epsilon_i$ and therefore:

$$ \sum_{s \in S_{\sigma(\kappa)}} p_s \left( \phi(\tilde{x}^{(k)}, s) - \tilde{\theta}_s^{(k)} \right) \le \epsilon_{\kappa} \qquad (6) $$

By definition of $\epsilon_\kappa$ we have:

$$ 
\begin{aligned}
& \epsilon_\kappa = \epsilon - \sum_{i=1}^{\kappa-1} \left[ \sum_{s \in S_{\sigma(i)}} p_s \left( \phi(\tilde{x}^{(k)}, s) - \tilde{\theta}_s^{(k)} \right) \right] \\
& \iff \epsilon_\kappa + \sum_{i=1}^{\kappa-1} \left[ \sum_{s \in S_{\sigma(i)}} p_s \left( \phi(\tilde{x}^{(k)}, s) - \tilde{\theta}_s^{(k)} \right) \right] = \epsilon
\end{aligned}
$$

Then, using equation (6), we have:

$$ 
\begin{aligned}
& \sum_{i=1}^{\kappa} \left[ \sum_{s \in S_{\sigma(i)}} p_s \left( \phi(\tilde{x}^{(k)}, s) - \tilde{\theta}_s^{(k)} \right) \right] \le \epsilon \\
& \iff UB(\tilde{x}^{(k)}) - LB^{(k)} \le \epsilon
\end{aligned}
$$

which implies that $\tilde{x}^{(k)}$ is an optimal solution to problem 1. $\square$

## A.2 Proof of Proposition 2

*Proof.* We solve each subproblem at most once for every optimal solution to $(RMP)^{(k)}$ because $(S_1, S_2, ..., S_\kappa)$ defines a partition of S. Then if there exists a cut violated by $(\tilde{x}^{(k)}, (\tilde{\theta}_s^{(k)})_{s \in S})$, we find it in at most $card(S)$ iterations in the optimality loop. Then, as the total number of optimality cuts is finite and equal to $\sum_{s \in S} card(\text{Vert}(\Pi_s))$, this algorithm converges in at most $card(S) \times \sum_{s \in S} card(\text{Vert}(\Pi_s))$ iterations. When the cuts are aggregated, if the cut of a subproblem separates the solution to the relaxed master program $(\tilde{x}^{(k)}, (\tilde{\theta}_s^{(k)})_{s \in S})$, then the aggregated cut of the batch also separates it, and the result remains true. $\square$
## A.3 Proof of Proposition 3

*Proof.* Let $x \in X$ be a first-stage solution such that batch $S_{\sigma(i)}$ is $\epsilon_i(x)$-approximated by $(RMP)^{(k)}$, for all $i \in [1, \kappa]$. Then, $S_{\sigma(\kappa)}$ is $\epsilon_\kappa(x)$-approximated by $(RMP)^{(k)}$. This means:

$$ 
\begin{aligned}
& \left[ \sum_{s \in S_{\sigma(\kappa)}} p_s(\phi(x, s) - \tilde{\theta}_s^{(k)}) \right]^+ \le \epsilon - c^\top(x - \tilde{x}^{(k)}) - \sum_{t=1}^{\kappa-1} \left[ \sum_{s \in S_{\sigma(t)}} p_s(\phi(x, s) - \tilde{\theta}_s^{(k)}) \right]^+ \\
& \Rightarrow \left[ \sum_{s \in S_{\sigma(\kappa)}} p_s(\phi(x, s) - \tilde{\theta}_s^{(k)}) \right]^+ + \left[ \sum_{t=1}^{\kappa-1} \sum_{s \in S_{\sigma(t)}} p_s(\phi(x, s) - \tilde{\theta}_s^{(k)}) \right]^+ \le \epsilon - c^\top(x - \tilde{x}^{(k)})
\end{aligned}
$$

As $\zeta \le \zeta^+$ for any $\zeta \in \mathbb{R}$, we have:

$$ 
\begin{aligned}
& \sum_{t=1}^{\kappa} \sum_{s \in S_{\sigma(t)}} p_s(\phi(x, s) - \tilde{\theta}_s^{(k)}) \le \epsilon - c^\top(x - \tilde{x}^{(k)}) \\
& \Rightarrow \sum_{s \in S} p_s(\phi(x, s) - \tilde{\theta}_s^{(k)}) \le \epsilon - c^\top(x - \tilde{x}^{(k)}) \\
& \Rightarrow (c^\top x + \sum_{s \in S} p_s \phi(x, s)) - (c^\top \tilde{x}^{(k)} + \sum_{s \in S} p_s \tilde{\theta}_s^{(k)}) \le \epsilon \\
& \Rightarrow UB(x) - LB^{(k)} \le \epsilon
\end{aligned}
$$

and $x$ is an optimal solution to problem (1).

□

## A.4 Proof of Proposition 4

*Proof.* The proof consists of two cases:

1. $\epsilon > 0$ and $(x^{(k+r)})_{r \in \mathbb{N}}$ converges to $\tilde{x}^{(k)}$

2. $\epsilon \ge 0$ and $(x^{(k+r)})_{r \in \mathbb{N}}$ converges to $\tilde{x}^{(k)}$ in a finite number of iterations

*Case 1:* Let $\epsilon > 0$ be the optimality gap and $(x^{(k+r)})_{r \in \mathbb{N}}$ be a sequence of elements of $X$ converging to $\tilde{x}^{(k)}$. We focus on the solution $(\tilde{x}^{(k)}, (\tilde{\theta}_s^{(k)})_{s \in S})$ to the relaxed master program. There are two possible sub-cases:

- **Sub-case 1.1** There exists $t_0 \in \mathbb{N}$ such that for all $l \ge t_0$ and for each index $i \in [1, \kappa]$, batch $S_{\sigma(k+l)(i)}$ is $\epsilon_i(\tilde{x}^{(k)})$-approximated by $(RMP)^{(k)}$ with an optimality gap of $\epsilon/4$

- **Sub-case 1.2** For all $t_0 \in \mathbb{N}$, there exists $l \ge t_0$ and an index $i \in [1, \kappa]$ such that batch $S_{\sigma(k+l)(i)}$ is not $\epsilon_i(\tilde{x}^{(k)})$-approximated by $(RMP)^{(k)}$ with an optimality gap of $\epsilon/4$

**Sub-case 1.1:** Assume that there exists $t_0 \in \mathbb{N}$ such that for all $l \ge t_0$ and for each index $i \in [1, \kappa]$, batch $S_{\sigma(k+l)(i)}$ is $\epsilon_i(\tilde{x}^{(k)})$-approximated by $(RMP)^{(k)}$ with an initial gap of $\epsilon/4$. This means that for every $l \ge t_0$ and for every index $i \in [1, \kappa]$,

$$ \left[ \sum_{s \in S_{\sigma(k+l)(i)}} p_s(\phi(\tilde{x}^{(k)}, s) - \tilde{\theta}_s^{(k)}) \right]^+ \le \frac{\epsilon}{4} - \left[ \sum_{t=1}^{i-1} \sum_{s \in S_{\sigma(k+l)(t)}} p_s(\phi(\tilde{x}^{(k)}, s) - \tilde{\theta}_s^{(k)}) \right]^+ \quad (7) $$

As the number of permutations of $[1, \kappa]$ is finite, as for every $l \ge t_0$ and for each index $i \in [1, \kappa]$, the application $x \mapsto [\sum_{s \in S_{\sigma(k+l)(i)}} p_s(\phi(x, s) - \tilde{\theta}_s^{(k)})]^+$ is continuous, and as sequence $(x^{(k+r)})_{r \in \mathbb{N}}$ converges to $\tilde{x}^{(k)}$, there exists $t_1 \in \mathbb{N}, t_1 \ge t_0$ such that, for every $l \ge t_1$ and for every index $i \in [1, \kappa]$:

$$ \left[ \sum_{s \in S_{\sigma(k+l)(i)}} p_s(\phi(x^{(k+l)}, s) - \tilde{\theta}_s^{(k)}) \right]^+ \le \left[ \sum_{s \in S_{\sigma(k+l)(i)}} p_s(\phi(\tilde{x}^{(k)}, s) - \tilde{\theta}_s^{(k)}) \right]^+ + \frac{\epsilon}{4} \quad (8) $$

Moreover, as for every $l \ge t_0$ and for every index $i \in [1, \kappa]$, the application $x \mapsto$

$$ \left[ \sum_{t=1}^{i-1} \sum_{s \in S_{\sigma(k+l)(i)}} p_s(\phi(x, s) - \tilde{\theta}_s^{(k)}) \right]^+ \text{ is continuous, there exists } t_2 \in \mathbb{N}, t_2 \ge t_0 \text{ such that, for every } l \ge t_2 \text{ and for every index } i \in [1, \kappa]: $$

$$ \left[ \sum_{t=1}^{i-1} \sum_{s \in S_{\sigma(k+l)(i)}} p_s(\phi(x^{(k+l)}, s) - \tilde{\theta}_s^{(k)}) \right]^+ - \frac{\epsilon}{4} \le \left[ \sum_{t=1}^{i-1} \sum_{s \in S_{\sigma(k+l)(t)}} p_s(\phi(\tilde{x}^{(k)}, s) - \tilde{\theta}_s^{(k)}) \right]^+ $$
$$ \Rightarrow - \left[ \sum_{t=1}^{i-1} \sum_{s \in S_{\sigma(k+l)}(i)} p_s \left( \phi(\tilde{x}^{(k)}, s) - \tilde{\theta}_s^{(k)} \right) \right]^+ \le - \left[ \sum_{t=1}^{i-1} \sum_{s \in S_{\sigma(k+l)}(t)} p_s \left( \phi(x^{(k+l)}, s) - \tilde{\theta}_s^{(k)} \right) \right]^+ + \frac{\epsilon}{4} \quad (9) $$

And, as $(x^{(k+r)})_{r \in \mathbb{N}}$ converges to $\tilde{x}^{(k)}$, there exists $t_3 \in \mathbb{N}$ such that, $\forall l \ge t_3$, $0 \le \frac{\epsilon}{4} - c^T(x^{(k+l)} - \tilde{x}^{(k)})$.

Then, by setting $t_4 = \max\{t_1, t_2, t_3\}$, and jointly using (7), (8) and (9), we have, for every $l \ge t_4$ and for every index $i \in [1, \kappa]$:

$$ \left[ \sum_{s \in S_{\sigma(k+l)}(i)} p_s \left( \phi(x^{(k+l)}, s) - \tilde{\theta}_s^{(k)} \right) \right]^+ \le \frac{\epsilon}{4} + \frac{\epsilon}{4} + \frac{\epsilon}{4} - \left[ \sum_{t=1}^{i-1} \sum_{s \in S_{\sigma(k+l)}(t)} p_s \left( \phi(x^{(k+l)}, s) - \tilde{\theta}_s^{(k)} \right) \right]^+ $$

$$ \Rightarrow \left[ \sum_{s \in S_{\sigma(k+l)}(i)} p_s \left( \phi(x^{(k+l)}, s) - \tilde{\theta}_s^{(k)} \right) \right]^+ \le \frac{3\epsilon}{4} - \left[ \sum_{t=1}^{i-1} \sum_{s \in S_{\sigma(k+l)}(t)} p_s \left( \phi(x^{(k+l)}, s) - \tilde{\theta}_s^{(k)} \right) \right]^+ $$

$$ \Rightarrow \left[ \sum_{s \in S_{\sigma(k+l)}(i)} p_s \left( \phi(x^{(k+l)}, s) - \tilde{\theta}_s^{(k)} \right) \right]^+ \le \epsilon - c^T(x^{(k+l)} - \tilde{x}^{(k)}) - \left[ \sum_{t=1}^{i-1} \sum_{s \in S_{\sigma(k+l)}(t)} p_s \left( \phi(x^{(k+l)}, s) - \tilde{\theta}_s^{(k)} \right) \right]^+ $$

And for every index $i \in [1, \kappa]$, batch $S_{\sigma(k+t_4)}(i)$ is $\epsilon_i(x^{(k+t_4)})$-approximated by $(RMP)^{(k)}$ with an optimality gap of $\epsilon$, which implies, by Proposition 3, that $x^{(k+t_4)}$ is an optimal solution to problem (1).

**Sub-case 1.2:** Now assume that for all $t_0 \in \mathbb{N}$, there exists $l \ge t_0$ and an index $i \in [1, \kappa]$ such that batch $S_{\sigma(k+l)}(i)$ is not $\epsilon_i(\tilde{x}^{(k)})$-approximated by $(RMP)^{(k)}$ with an initial optimality gap of $\frac{\epsilon}{4}$. This means, that for all $t_0 \in \mathbb{N}$, there exists $l \ge t_0$ and an index $i \in [1, \kappa]$ such that:

$$ \left[ \sum_{s \in S_{\sigma(k+l)}(i)} p_s \left( \phi(\tilde{x}^{(k)}, s) - \tilde{\theta}_s^{(k)} \right) \right]^+ > \frac{\epsilon}{4} - \left[ \sum_{t=1}^{i-1} \sum_{s \in S_{\sigma(k+l)}(t)} p_s \left( \phi(\tilde{x}^{(k)}, s) - \tilde{\theta}_s^{(k)} \right) \right]^+ \quad (10) $$

Then, there exists $\delta > 0$ such that, for all $t_0 \in \mathbb{N}$, there exists $l \ge t_0$ and an index $i \in [1, \kappa]$ (the first index such that (10) occurs) such that:

$$ \sum_{s \in S_{\sigma(k+l)}(i)} p_s \left( \phi(\tilde{x}^{(k)}, s) - \tilde{\theta}_s^{(k)} \right) > \delta \quad (11) $$

Let $g_i^{(k+\tau)} \in \mathbb{R}^{n_1}$ be a subgradient associated with the function $x \mapsto \sum_{s \in S_{\sigma(k+\tau)}(i)} p_s \phi(x^{(k+\tau)}, s)$ at point $x^{(k+\tau)}$. The aggregated cut obtained after solving batch $S_{\sigma(k+\tau)}(i)$ can be written as follows:

$$ g_i^{(k+\tau)\top}(x - x^{(k+\tau)}) + \sum_{s \in S_{\sigma(k+\tau)}(i)} p_s \phi(x^{(k+\tau)}, s) \le \sum_{s \in S_{\sigma(k+\tau)}(i)} p_s \theta_s $$

By continuity of $\phi(\cdot, s)$ for all $s \in S$ and as the total number of cuts is finite, there exists $L > 0$ such that for every $l \in \mathbb{N}$ and for every $i \in [1, \kappa]$, $||g_i^{(k+l)}||_2 \le L$. Then, as sequence $(x^{(k+r)})_{r \in \mathbb{N}}$ converges to $\tilde{x}^{(k)}$, there exists $t_1 \in \mathbb{N}$ such that for all $l \ge t_1$ and for all $i \in [1, \kappa]$,

$$ |g_i^{(k+l)\top}(\tilde{x} - x^{(k+l)})| < \frac{\delta}{3} \quad (12) $$

Moreover, as sequence $(x^{(k+r)})_{r \in \mathbb{N}}$ converges to $\tilde{x}^{(k)}$ and by continuity of $\phi(\cdot, s)$, there exists $t_2 \in \mathbb{N}$ such that for all $l \ge t_2$ and for each index $i \in [1, \kappa]$:

$$ \sum_{s \in S_{\sigma(k+l)}(i)} p_s \phi(\tilde{x}^{(k)}, s) < \sum_{s \in S_{\sigma(k+l)}(i)} p_s \phi(x^{(k+l)}, s) + \frac{\delta}{3} \quad (13) $$

Then, let $t_3 = \max\{t_1, t_2\}$. Let $i \in [1, \kappa]$ and $l_0 \ge t_3$ be the first indices such that (11) occurs. By combining (11), (12) and (13), we have:

$$ g_i^{(k+l_0)\top}(\tilde{x}^{(k)} - x^{(k+l_0)}) + \sum_{s \in S_{\sigma(k+l_0)}(i)} p_s \phi(x^{(k+l_0)}, s) - \sum_{s \in S_{\sigma(k+l_0)}(i)} p_s \tilde{\theta}_s^{(k)} > \frac{\delta}{3} $$

Then, at $x^{(k+l_0)}$, the aggregated cut of the batch $S_{\sigma(k+l_0)}(i)$ separates the solution to the relaxed master program, as its value at $\tilde{x}^{(k)}$ is strictly larger than the outer linearization given by the relaxed master program. If `cutAggr = False`, there exists at least one of the cuts associated with a subproblem of the batch which separates the solution to the relaxed
master program.

* **Case 2:** Let $\epsilon \ge 0$ be the optimality gap and $(x^{(k+r)})_{r \in \mathbb{N}}$ be a sequence of elements of $X$ converging to $\tilde{x}^{(k)}$ in a finite number of iterations.

As $(x^{(k+r)})_{r \in \mathbb{N}}$ converges to $\tilde{x}^{(k)}$, the proof of case 1 holds also in this case for every $\epsilon > 0$. We need to prove that the proposition is true if $\epsilon = 0$. Let $t_0$ be the first iteration such that $x^{(k+t_0)} = \tilde{x}^{(k)}$. Either, for each index $i \in [1, \kappa]$, batch $S_{\sigma^{(k+t_0)}(i)}$ is $\epsilon_i(\tilde{x}^{(k)})$-approximated by $(RMP)^{(k)}$ with an optimality gap of 0, and by proposition 3, $x^{(k+t_0)}$ is an optimal solution to problem (1) with an optimality gap $\epsilon = 0$, or there exists a batch which is not $\epsilon_i(\tilde{x}^{(k)})$-approximated by $(RMP)^{(k)}$, and the aggregated cut derived from this batch separates the solution to the relaxed master program.

□

## A.5 Proof of Proposition 6

*Proof.* Let $(x, (y, z)) \in X \times \mathcal{D}$. We have:

$$d_x^1 = (x, \alpha y + (1 - \alpha)z)$$

$$d_x^2 = (x, \alpha x + (1 - \alpha)\alpha y + (1 - \alpha)^2 z)$$

Let $u = \alpha y + (1 - \alpha)z - x$, we have $d_x^2 = (x, x + (1 - \alpha)u)$. Then, by induction,

$$\forall \ell \ge 2, \quad d_x^\ell = (x, x + (1 - \alpha)^{\ell-1} u)$$

And $\forall \ell \ge 2$, $\psi_2(d_x^\ell) = x + (1 - \alpha)^\ell u$. Finally, $\lim_{\ell \to +\infty} \psi_2(d_x^\ell) = x$.

□

## A.6 Proof of Proposition 7

*Proof.* Let $(x, (y, z)) \in X \times \mathcal{D}$. We have:

$$d_x^1 = (x + \beta(y - x), \alpha y + (1 - \alpha)z)$$

$$d_x^2 = (x + \beta^2(y - x), x - (1 - \alpha)x + \alpha\beta(y - x) + (1 - \alpha)\alpha y + (1 - \alpha)^2 z)$$

We define $u = y - x$ and $v = \alpha y + (1 - \alpha)z - x$. Then

$$d_x^2 = (x + \beta^2 u, x + \alpha \beta u + (1 - \alpha) v)$$

$$d_x^3 = (x + \beta^3 u, x + \alpha(\beta^2 + \beta(1 - \alpha))u + (1 - \alpha)^2 v)$$

By induction, we have

$$d_x^\ell = (x + \beta^\ell u, x + \alpha(\sum_{i=1}^{\ell-1} \beta^i (1 - \alpha)^{\ell-i-1})u + (1 - \alpha)^{\ell-1} v), \forall \ell \ge 2$$

We define $\delta = \max\{\beta, (1 - \alpha)\}$. For all $i \ge 0$ and for all $l \ge 2$, $\beta^i \le \delta^i$ and $(1 - \alpha)^{l-i-1} \le \delta^{l-i-1}$. Then

$$\sum_{i=1}^{\ell-1} \beta^i (1 - \alpha)^{\ell-i-1} \le (\ell - 1)\delta^{\ell-1}$$

Then, $\lim_{\ell \to +\infty} \sum_{i=1}^{\ell-1} \beta^i (1 - \alpha)^{\ell-i-1} = 0$ and $\lim_{\ell \to +\infty} d_x^\ell = (x, x)$. Finally, $\lim_{\ell \to +\infty} \psi_2(d_x^\ell) = x$.

□
B Detailed benchmark algorithms

Algorithm 4 describes our implementation of **In-out monocut** (cutAggr=True) and **In-out multicut** (cutAggr=False).

<caption>**Algorithm 4:** The Benders decomposition algorithm with in-out stabilization</caption>

**Parameters:** $\epsilon \ge 0$, $x^{(0)} \in X$, cutAggr $\in \{\text{True, False}\}$, $\alpha \in (0; 1]$ 
**Initialization:** $k \leftarrow 0$, $\hat{x}^{(1)} \leftarrow x^{(0)}$, $UB^{(0)} \leftarrow c^\top x^{(0)} + \sum_{s \in S} p_s \pi_s^\top (d_s - T_s x^{(0)})$, $LB^{(0)} \leftarrow -\infty$, $\alpha_1 \leftarrow \alpha$ 
**while** $UB^{(k)} > LB^{(k)} + \epsilon$ **do** 
3 &nbsp;&nbsp;&nbsp;&nbsp; $k \leftarrow k + 1$ 
4 &nbsp;&nbsp;&nbsp;&nbsp; Solve $(RMP)^{(k)}$ and retrieve $(\tilde{x}^{(k)}, (\tilde{\theta}_s^{(k)})_{s \in S})$ 
5 &nbsp;&nbsp;&nbsp;&nbsp; $LB^{(k)} \leftarrow c^\top \tilde{x}^{(k)} + \sum_{s \in S} p_s \tilde{\theta}_s^{(k)}$ 
6 &nbsp;&nbsp;&nbsp;&nbsp; $x^{(k)} \leftarrow \alpha_k \tilde{x}^{(k)} + (1 - \alpha_k) \hat{x}^{(k)}$ 
7 &nbsp;&nbsp;&nbsp;&nbsp; **for** $s \in S$ **do** 
8 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; Solve $(SP(x^{(k)}, s))$ and retrieve $\pi_s$ an extreme point of $\Pi_s$ 
9 &nbsp;&nbsp;&nbsp;&nbsp; **if** cutAggr **then** 
10 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; Add $\sum_{s \in S} p_s \theta_s \ge \sum_{s \in S} p_s \pi_s^\top (d_s - T_s x)$ 
11 &nbsp;&nbsp;&nbsp;&nbsp; **else** 
12 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; **for** $s \in S$ **do** 
13 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; Add $\theta_s \ge \pi_s^\top (d_s - T_s x)$ to $(RMP)^{(k)}$ 
14 &nbsp;&nbsp;&nbsp;&nbsp; **if** $UB^{(k-1)} > c^\top x^{(k)} + \sum_{s \in S} p_s \pi_s^\top (d_s - T_s x^{(k)})$ **then** 
15 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; $UB^{(k)} \leftarrow c^\top x^{(k)} + \sum_{s \in S} p_s \pi_s^\top (d_s - T_s x^{(k)})$ 
16 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; $\hat{x}^{(k+1)} \leftarrow x^{(k)}$ 
17 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; $\alpha_{k+1} \leftarrow \min\{1.0, 1.2\alpha_k\}$ 
18 &nbsp;&nbsp;&nbsp;&nbsp; **else** 
19 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; $\hat{x}^{(k+1)} \leftarrow \hat{x}^{(k)}, UB^{(k)} \leftarrow UB^{(k-1)}$ 
20 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; $\alpha_{k+1} \leftarrow \max\{0.1, 0.8\alpha_k\}$ 
21 &nbsp;&nbsp;&nbsp;&nbsp; $(RMP)^{(k+1)} \leftarrow (RMP)^{(k)}$ 
22 &nbsp;&nbsp;&nbsp;&nbsp; **Return** $\hat{x}^{(k+1)}$

We now describe the level bundle method. We first define the quadratic master program. Let $\lambda \in (0, 1)$ denote the level parameter, $LB$ a lower bound on the optimal value of the problem, and $UB$ an upper bound. We define $f_{lev} = (1 - \lambda)UB + \lambda LB$ and a stability center $\hat{x}$ as in the in-out stabilization approach. The quadratic master program $(QMP)(\hat{x}, f_{lev})$ parametrized by $\hat{x}$ and $f_{lev}$ is the following:

$$
\left\{
\begin{array}{l}
\min_{x, \theta} \frac{1}{2} \|x - \hat{x}\|_2^2 \\
\\
\text{s.t. : } \sum_{s \in S} p_s \theta_s \ge \sum_{s \in S} p_s \pi_s^\top (d_s - T_s x), \forall s \in S, \forall \pi_s \in \text{Vert}(\Pi_s) \\
\\
c^\top x + \sum_{s \in S} p_s \theta_s \le f_{lev} \\
\\
x \in X, \theta \in \mathbb{R}^{\text{Card}(S)}
\end{array}
\right.
$$

We denote by $(RQMP)^{(k)}(\hat{x}, f_{lev})$ its relaxation at iteration $k$ of the algorithm and by $\kappa \in (0, \lambda)$ a acceptation tolerance to update the stability center. Algorithm 5 describes our implementation of **Level bundle**.
<caption>**Algorithm 5: Level bundle method**</caption>

**Parameters:** $\epsilon \ge 0$, $x^{(0)} \in X$, $\lambda \in [0, 1)$, $LB^{(0)}$ a valid lower bound on the objective value, $\kappa \in (0, \lambda)$

**Initialization:** $k \leftarrow 0$, $UB^{(0)} \leftarrow c^\top x^{(0)} + \sum_{s \in S} p_s \pi_s^\top (d_s - T_s \hat{x}^{(0)})$, $\hat{x}^{(1)} \leftarrow x^{(0)}$

**while** $UB^{(k)} > LB^{(k)} + \epsilon$ **do**
3 &nbsp;&nbsp;&nbsp;&nbsp; $k \leftarrow k + 1$
4 &nbsp;&nbsp;&nbsp;&nbsp; $f_{lev}^{(k)} = (1 - \lambda)UB^{(k-1)} + \lambda LB^{(k-1)}$
5 &nbsp;&nbsp;&nbsp;&nbsp; Solve $(RQMP)^{(k)}(\hat{x}^{(k)}, f_{lev}^{(k)})$
6 &nbsp;&nbsp;&nbsp;&nbsp; **if** $(RQMP)^{(k)}(\hat{x}^{(k)}, f_{lev}^{(k)})$ **is infeasible** **then**
7 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; $LB^{(k)} \leftarrow f_{lev}^{(k)}$
8 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; $\hat{x}^{(k+1)} \leftarrow \hat{x}^{(k)}$
9 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; $UB^{(k)} \leftarrow UB^{(k-1)}$
10 &nbsp;&nbsp;&nbsp;&nbsp; **else**
11 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; Retrieve $x^{(k)}$ solution to $(RQMP)^{(k)}(\hat{x}^{(k)}, f_{lev}^{(k)})$
12 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; **for** $s \in S$ **do**
13 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; Solve $(SP(x^{(k)}, s))$ and retrieve $\pi_s$ an extreme point of $\Pi_s$
14 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; Add $\sum_{s \in S} p_s \theta_s \ge \sum_{s \in S} p_s \pi_s^\top (d_s - T_s x)$
15 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; **if** $c^\top x^{(k)} + \sum_{s \in S} p_s \pi_s^\top (d_s - T_s x^{(k)}) < (1 - \kappa)UB^{(k-1)} + \kappa f_{lev}^{(k)}$ **then**
16 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; $UB^{(k)} \leftarrow c^\top x^{(k)} + \sum_{s \in S} p_s \pi_s^\top (d_s - T_s x^{(k)})$
17 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; $\hat{x}^{(k+1)} \leftarrow x^{(k)}$
18 &nbsp;&nbsp;&nbsp;&nbsp; **else**
19 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; $\hat{x}^{(k+1)} \leftarrow \hat{x}^{(k)}$
20 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; $UB^{(k)} \leftarrow UB^{(k-1)}$
21 &nbsp;&nbsp;&nbsp;&nbsp; $LB^{(k)} \leftarrow LB^{(k-1)}$
22 &nbsp;&nbsp;&nbsp;&nbsp; $(RQMP)^{(k+1)} \leftarrow (RQMP)^{(k)}$
23 &nbsp;&nbsp;&nbsp;&nbsp; **Return** $\hat{x}^{(k+1)}$
## C Impact of the stabilization on BbB - additional analysis

For 8 different instances, we show the total time spent solving the relaxed master programs and the subproblems, as well as the total number of subproblems solved for each of the following methods: Level bundle, In-out monocut, In-out 1% CutAggr and BbB 1% CutAggr $\alpha = 0.5$.

<figure><img src="image_8.png" /><figcaption>Figure 7: Time spent in solving the master program and the subproblems, for 8 different instances, solved by Level bundle, In-out monocut, In-out 1% CutAggr and BbB 1% CutAggr $\alpha = 0.5$. The total number of solved subproblems is written vertically on the top of each bar.</figcaption></figure>

## D Sensitivity of BbB to the optimality gap

We analyze the impact of the optimality gap on the convergence of the algorithm. The choice of a different optimality gap $\epsilon$ in the Benders by batch algorithm might have an impact on the number of batches that would be solved at each iteration. With a larger optimality gap, the algorithm tends to solve more batches at each iteration, and to add more cuts. As this might have an impact on the first-stage iterates, and then on the computing times, we show on Figure 8 the cumulative distribution of the computing times to solve our 84 instances with BbB 1% CutAggr $\alpha = 0.5$ with four different optimality gaps $\{10^{-3}, 10^{-4}, 10^{-5}, 10^{-6}\}$. The figure shows that different optimality gaps have a negligible impact on the computing times on most instances. A smaller optimality gap induces larger computing times on the largest instances of our test set, but this would also be the case with other classical algorithms.
<figure><img src="image_9.png" /><figcaption>Figure 8: Cumulative distribution of the computing times on our 84 instances, for BbB with cut aggregation and base stabilization with $\alpha = 0.5$, and with optimality gaps in $\{10^{-3}, 10^{-4}, 10^{-5}, 10^{-6}\}$</figcaption></figure>

E Detailed numerical results

This section gives the detailed numerical results of our experiments.
<table><caption>Table 7: Results for the Benders by batch algorithm without aggregation, with batch sizes from 1% to 20% of the total number of subproblems.</caption><thead><tr><th rowspan="2">instance</th><th colspan="2">Classic multicut</th><th colspan="2">Classic monocut</th><th colspan="2">BbB 1%</th><th colspan="2">BbB 5%</th><th colspan="2">BbB 10%</th><th colspan="2">BbB 20%</th></tr><tr><th>time</th><th>ratio</th><th>time</th><th>ratio</th><th>time</th><th>ratio</th><th>time</th><th>ratio</th><th>time</th><th>ratio</th><th>time</th><th>ratio</th></tr></thead><tbody><tr><td>LandS-N1000-s1000</td><td>2</td><td>3.2</td><td>0.81</td><td>1.3</td><td>2</td><td>2.8</td><td>0.91</td><td>1.5</td><td>0.75</td><td>1.2</td><td><strong>0.62</strong></td><td><strong>1.0</strong></td></tr><tr><td>LandS-N1000-s1001</td><td>2</td><td>2.9</td><td>0.72</td><td>1.0</td><td>2</td><td>2.4</td><td>0.86</td><td>1.2</td><td>0.74</td><td>1.1</td><td><strong>0.70</strong></td><td><strong>1.0</strong></td></tr><tr><td>LandS-N1000-s1002</td><td>2</td><td>3.0</td><td>0.72</td><td>1.1</td><td>2</td><td>2.9</td><td>0.71</td><td>1.1</td><td><strong>0.65</strong></td><td><strong>1.0</strong></td><td>0.66</td><td>1.0</td></tr><tr><td>LandS-N5000-s5000</td><td>11</td><td>1.6</td><td>9</td><td>1.3</td><td>12</td><td>1.9</td><td>8</td><td>1.2</td><td>7</td><td>1.1</td><td><strong>7</strong></td><td><strong>1.0</strong></td></tr><tr><td>LandS-N5000-s5001</td><td>10</td><td>1.6</td><td>10</td><td>1.6</td><td>15</td><td>2.5</td><td>8</td><td>1.3</td><td>6</td><td>1.1</td><td><strong>6</strong></td><td><strong>1.0</strong></td></tr><tr><td>LandS-N5000-s5002</td><td>11</td><td>1.9</td><td>9</td><td>1.5</td><td>13</td><td>2.2</td><td>8</td><td>1.3</td><td>7</td><td>1.2</td><td><strong>6</strong></td><td><strong>1.0</strong></td></tr><tr><td>LandS-N10000-s10000</td><td>22</td><td>1.1</td><td>26</td><td>1.3</td><td>41</td><td>2.0</td><td>25</td><td>1.2</td><td><strong>20</strong></td><td><strong>1.0</strong></td><td>21</td><td>1.0</td></tr><tr><td>LandS-N10000-s10001</td><td>22</td><td>1.1</td><td>30</td><td>1.5</td><td>36</td><td>1.8</td><td>25</td><td>1.2</td><td>22</td><td>1.1</td><td><strong>20</strong></td><td><strong>1.0</strong></td></tr><tr><td>LandS-N10000-s10002</td><td>20</td><td>1.1</td><td>30</td><td>1.7</td><td>37</td><td>2.0</td><td>25</td><td>1.4</td><td>22</td><td>1.2</td><td><strong>18</strong></td><td><strong>1.0</strong></td></tr><tr><td>LandS-N20000-s20000</td><td><strong>49</strong></td><td><strong>1.0</strong></td><td>96</td><td>1.9</td><td>134</td><td>2.7</td><td>86</td><td>1.7</td><td>78</td><td>1.6</td><td>71</td><td>1.4</td></tr><tr><td>LandS-N20000-s20001</td><td><strong>43</strong></td><td><strong>1.0</strong></td><td>119</td><td>2.8</td><td>130</td><td>3.0</td><td>92</td><td>2.1</td><td>77</td><td>1.8</td><td>71</td><td>1.7</td></tr><tr><td>LandS-N20000-s20002</td><td><strong>44</strong></td><td><strong>1.0</strong></td><td>99</td><td>2.2</td><td>125</td><td>2.8</td><td>90</td><td>2.0</td><td>85</td><td>1.9</td><td>73</td><td>1.7</td></tr><tr><td>gbd-N1000-s1000</td><td>2</td><td>2.7</td><td>0.95</td><td>1.4</td><td>2</td><td>3.3</td><td><strong>0.68</strong></td><td><strong>1.0</strong></td><td>0.78</td><td>1.1</td><td>0.95</td><td>1.4</td></tr><tr><td>gbd-N1000-s1001</td><td>2</td><td>3.7</td><td>0.90</td><td>1.4</td><td>2</td><td>3.8</td><td><strong>0.65</strong></td><td><strong>1.0</strong></td><td>0.90</td><td>1.4</td><td>0.94</td><td>1.5</td></tr><tr><td>gbd-N1000-s1002</td><td>2</td><td>3.6</td><td>0.96</td><td>1.6</td><td>2</td><td>3.7</td><td><strong>0.62</strong></td><td><strong>1.0</strong></td><td>0.83</td><td>1.3</td><td>0.99</td><td>1.6</td></tr><tr><td>gbd-N5000-s5000</td><td>13</td><td>2.0</td><td>10</td><td>1.7</td><td>18</td><td>2.9</td><td><strong>6</strong></td><td><strong>1.0</strong></td><td>7</td><td>1.2</td><td>8</td><td>1.4</td></tr><tr><td>gbd-N5000-s5001</td><td>11</td><td>1.9</td><td>10</td><td>1.7</td><td>14</td><td>2.3</td><td><strong>6</strong></td><td><strong>1.0</strong></td><td>7</td><td>1.1</td><td>8</td><td>1.3</td></tr><tr><td>gbd-N5000-s5002</td><td>12</td><td>1.8</td><td>11</td><td>1.6</td><td>15</td><td>2.4</td><td><strong>6</strong></td><td><strong>1.0</strong></td><td>7</td><td>1.1</td><td>9</td><td>1.3</td></tr><tr><td>gbd-N10000-s10000</td><td>24</td><td>1.2</td><td>34</td><td>1.8</td><td>54</td><td>2.8</td><td><strong>19</strong></td><td><strong>1.0</strong></td><td>21</td><td>1.1</td><td>26</td><td>1.4</td></tr><tr><td>gbd-N10000-s10001</td><td>24</td><td>1.3</td><td>32</td><td>1.7</td><td>41</td><td>2.2</td><td><strong>19</strong></td><td><strong>1.0</strong></td><td>24</td><td>1.3</td><td>26</td><td>1.4</td></tr><tr><td>gbd-N10000-s10002</td><td>23</td><td>1.2</td><td>32</td><td>1.7</td><td>46</td><td>2.4</td><td><strong>19</strong></td><td><strong>1.0</strong></td><td>22</td><td>1.1</td><td>24</td><td>1.2</td></tr><tr><td>gbd-N20000-s20000</td><td><strong>48</strong></td><td><strong>1.0</strong></td><td>119</td><td>2.5</td><td>97</td><td>2.0</td><td>63</td><td>1.3</td><td>71</td><td>1.5</td><td>86</td><td>1.8</td></tr><tr><td>gbd-N20000-s20001</td><td><strong>51</strong></td><td><strong>1.0</strong></td><td>120</td><td>2.3</td><td>100</td><td>2.0</td><td>64</td><td>1.2</td><td>73</td><td>1.4</td><td>90</td><td>1.8</td></tr><tr><td>gbd-N20000-s20002</td><td><strong>47</strong></td><td><strong>1.0</strong></td><td>125</td><td>2.7</td><td>92</td><td>2.0</td><td>57</td><td>1.2</td><td>70</td><td>1.5</td><td>85</td><td>1.8</td></tr><tr><td>ssn-N1000-s1000</td><td>2279</td><td>552.2</td><td>7</td><td>1.7</td><td>6</td><td>1.3</td><td><strong>4</strong></td><td><strong>1.0</strong></td><td>5</td><td>1.1</td><td>5</td><td>1.2</td></tr><tr><td>ssn-N1000-s1001</td><td>2720</td><td>679.7</td><td>7</td><td>1.8</td><td>6</td><td>1.6</td><td><strong>4</strong></td><td><strong>1.0</strong></td><td>4</td><td>1.0</td><td>5</td><td>1.2</td></tr><tr><td>ssn-N1000-s1002</td><td>2226</td><td>602.8</td><td>7</td><td>1.8</td><td>6</td><td>1.8</td><td><strong>4</strong></td><td><strong>1.0</strong></td><td>4</td><td>1.1</td><td>5</td><td>1.3</td></tr><tr><td>ssn-N5000-s5000</td><td>13425</td><td>580.9</td><td>62</td><td>2.7</td><td>31</td><td>1.3</td><td><strong>23</strong></td><td><strong>1.0</strong></td><td>33</td><td>1.4</td><td>33</td><td>1.4</td></tr><tr><td>ssn-N5000-s5001</td><td>14260</td><td>631.1</td><td>45</td><td>2.0</td><td>33</td><td>1.5</td><td><strong>23</strong></td><td><strong>1.0</strong></td><td>27</td><td>1.2</td><td>31</td><td>1.4</td></tr><tr><td>ssn-N5000-s5002</td><td>12695</td><td>558.4</td><td>64</td><td>2.8</td><td>31</td><td>1.4</td><td>25</td><td>1.1</td><td><strong>23</strong></td><td><strong>1.0</strong></td><td>31</td><td>1.4</td></tr><tr><td>ssn-N10000-s10000</td><td>26559</td><td>420.0</td><td>185</td><td>2.9</td><td><strong>63</strong></td><td><strong>1.0</strong></td><td>123</td><td>2.0</td><td>64</td><td>1.0</td><td>79</td><td>1.3</td></tr><tr><td>ssn-N10000-s10001</td><td>26228</td><td>449.1</td><td>193</td><td>3.3</td><td>72</td><td>1.2</td><td><strong>58</strong></td><td><strong>1.0</strong></td><td>59</td><td>1.0</td><td>78</td><td>1.3</td></tr><tr><td>ssn-N10000-s10002</td><td>24916</td><td>463.1</td><td>187</td><td>3.5</td><td>80</td><td>1.5</td><td>56</td><td>1.0</td><td><strong>54</strong></td><td><strong>1.0</strong></td><td>79</td><td>1.5</td></tr><tr><td>ssn-N20000-s20000</td><td>+∞</td><td>>382.6</td><td>512</td><td>4.5</td><td>152</td><td>1.3</td><td><strong>113</strong></td><td><strong>1.0</strong></td><td>120</td><td>1.1</td><td>814</td><td>72.1</td></tr><tr><td>ssn-N20000-s20001</td><td>+∞</td><td>>355.0</td><td>503</td><td>4.1</td><td><strong>122</strong></td><td><strong>1.0</strong></td><td>588</td><td>4.8</td><td>128</td><td>1.1</td><td>167</td><td>1.4</td></tr><tr><td>ssn-N20000-s20002</td><td>+∞</td><td>>356.6</td><td>450</td><td>3.7</td><td>160</td><td>1.3</td><td><strong>121</strong></td><td><strong>1.0</strong></td><td>1624</td><td>13.4</td><td>154</td><td>1.3</td></tr><tr><td>storm-N1000-s1000</td><td>23</td><td>3.6</td><td>10</td><td>1.6</td><td>19</td><td>3.0</td><td>8</td><td>1.3</td><td><strong>6</strong></td><td><strong>1.0</strong></td><td>8</td><td>1.3</td></tr><tr><td>storm-N1000-s1001</td><td>24</td><td>3.7</td><td>11</td><td>1.6</td><td>23</td><td>3.5</td><td>8</td><td>1.3</td><td><strong>7</strong></td><td><strong>1.0</strong></td><td>8</td><td>1.3</td></tr><tr><td>storm-N1000-s1002</td><td>24</td><td>3.8</td><td>11</td><td>1.7</td><td>21</td><td>3.3</td><td>8</td><td>1.3</td><td><strong>6</strong></td><td><strong>1.0</strong></td><td>8</td><td>1.3</td></tr><tr><td>storm-N5000-s5000</td><td>110</td><td>2.0</td><td>100</td><td>1.8</td><td>159</td><td>2.9</td><td>58</td><td>1.1</td><td><strong>54</strong></td><td><strong>1.0</strong></td><td>65</td><td>1.2</td></tr><tr><td>storm-N5000-s5001</td><td>117</td><td>2.2</td><td>118</td><td>2.2</td><td>184</td><td>3.4</td><td>59</td><td>1.1</td><td><strong>54</strong></td><td><strong>1.0</strong></td><td>65</td><td>1.2</td></tr><tr><td>storm-N5000-s5002</td><td>116</td><td>2.1</td><td>99</td><td>1.8</td><td>181</td><td>3.3</td><td>63</td><td>1.1</td><td><strong>55</strong></td><td><strong>1.0</strong></td><td>65</td><td>1.2</td></tr><tr><td>storm-N10000-s10000</td><td>215</td><td>1.4</td><td>468</td><td>3.8</td><td>508</td><td>3.2</td><td>162</td><td>1.0</td><td><strong>159</strong></td><td><strong>1.0</strong></td><td>191</td><td>1.2</td></tr><tr><td>storm-N10000-s10001</td><td>225</td><td>1.5</td><td>479</td><td>3.1</td><td>494</td><td>3.2</td><td><strong>154</strong></td><td><strong>1.0</strong></td><td>161</td><td>1.1</td><td>188</td><td>1.2</td></tr><tr><td>storm-N10000-s10002</td><td>233</td><td>1.5</td><td>542</td><td>3.5</td><td>474</td><td>3.1</td><td><strong>153</strong></td><td><strong>1.0</strong></td><td>157</td><td>1.0</td><td>189</td><td>1.2</td></tr><tr><td>storm-N20000-s20000</td><td><strong>465</strong></td><td><strong>1.0</strong></td><td>2240</td><td>4.8</td><td>1470</td><td>3.2</td><td>581</td><td>1.2</td><td>704</td><td>1.5</td><td>574</td><td>1.2</td></tr><tr><td>storm-N20000-s20001</td><td><strong>434</strong></td><td><strong>1.0</strong></td><td>2460</td><td>5.7</td><td>1300</td><td>3.0</td><td>585</td><td>1.3</td><td>669</td><td>1.5</td><td>603</td><td>1.4</td></tr><tr><td>storm-N20000-s20002</td><td><strong>476</strong></td><td><strong>1.0</strong></td><td>2410</td><td>5.1</td><td>1400</td><td>2.9</td><td>574</td><td>1.2</td><td>642</td><td>1.3</td><td>587</td><td>1.2</td></tr><tr><td>20term-N1000-s1000</td><td>544</td><td>13.5</td><td>749</td><td>18.6</td><td><strong>40</strong></td><td><strong>1.0</strong></td><td>82</td><td>2.0</td><td>46</td><td>1.1</td><td>74</td><td>1.8</td></tr><tr><td>20term-N1000-s1001</td><td>584</td><td>16.1</td><td>646</td><td>17.8</td><td><strong>36</strong></td><td><strong>1.0</strong></td><td>82</td><td>2.3</td><td>47</td><td>1.3</td><td>72</td><td>2.0</td></tr><tr><td>20term-N1000-s1002</td><td>604</td><td>16.0</td><td>877</td><td>23.2</td><td><strong>38</strong></td><td><strong>1.0</strong></td><td>82</td><td>2.2</td><td>53</td><td>1.4</td><td>76</td><td>2.0</td></tr><tr><td>20term-N5000-s5000</td><td>3095</td><td>4.7</td><td>29455</td><td>44.6</td><td><strong>660</strong></td><td><strong>1.0</strong></td><td>2059</td><td>3.1</td><td>1497</td><td>2.3</td><td>1951</td><td>3.0</td></tr><tr><td>20term-N5000-s5001</td><td>3699</td><td>5.4</td><td>22490</td><td>33.0</td><td><strong>681</strong></td><td><strong>1.0</strong></td><td>2066</td><td>3.0</td><td>1333</td><td>2.0</td><td>2302</td><td>3.4</td></tr><tr><td>20term-N5000-s5002</td><td>3725</td><td>6.6</td><td>21342</td><td>38.0</td><td><strong>561</strong></td><td><strong>1.0</strong></td><td>2178</td><td>3.9</td><td>1176</td><td>2.1</td><td>2486</td><td>4.4</td></tr><tr><td>20term-N10000-s10000</td><td>6803</td><td>3.1</td><td>+∞</td><td>>20.4</td><td><strong>2193</strong></td><td><strong>1.0</strong></td><td>9654</td><td>4.4</td><td>5526</td><td>2.5</td><td>11592</td><td>5.3</td></tr><tr><td>20term-N10000-s10001</td><td>6404</td><td>2.7</td><td>+∞</td><td>>19.5</td><td><strong>2330</strong></td><td><strong>1.0</strong></td><td>11062</td><td>4.7</td><td>7874</td><td>3.4</td><td>9436</td><td>4.1</td></tr><tr><td>20term-N10000-s10002</td><td>7494</td><td>3.3</td><td>+∞</td><td>>19.6</td><td><strong>2288</strong></td><td><strong>1.0</strong></td><td>11483</td><td>5.0</td><td>5196</td><td>2.3</td><td>10212</td><td>4.5</td></tr><tr><td>20term-N20000-s20000</td><td><strong>13429</strong></td><td><strong>1.0</strong></td><td>+∞</td><td>>5.7</td><td>+∞</td><td>>3.2</td><td>+∞</td><td>>3.2</td><td>+∞</td><td>>3.2</td><td>+∞</td><td>>3.2</td></tr><tr><td>20term-N20000-s20001</td><td>12763</td><td>1.4</td><td>+∞</td><td>>5.0</td><td><strong>9062</strong></td><td><strong>1.0</strong></td><td>+∞</td><td>>4.8</td><td>+∞</td><td>>4.8</td><td>+∞</td><td>>4.8</td></tr><tr><td>20term-N20000-s20002</td><td>14868</td><td>1.5</td><td>+∞</td><td>>8.1</td><td><strong>9613</strong></td><td><strong>1.0</strong></td><td>+∞</td><td>>4.5</td><td>+∞</td><td>>4.6</td><td>+∞</td><td>>4.6</td></tr><tr><td>Fleet20.3-N1000-s1000</td><td>513</td><td>9.4</td><td>224</td><td>4.1</td><td>143</td><td>2.6</td><td>105</td><td>1.9</td><td>102</td><td>1.9</td><td><strong>55</strong></td><td><strong>1.0</strong></td></tr><tr><td>Fleet20.3-N1000-s1001</td><td>539</td><td>10.1</td><td>228</td><td>4.3</td><td>139</td><td>2.6</td><td>110</td><td>2.1</td><td>100</td><td>1.9</td><td><strong>53</strong></td><td><strong>1.0</strong></td></tr><tr><td>Fleet20.3-N1000-s1002</td><td>546</td><td>7.7</td><td>224</td><td>3.2</td><td>154</td><td>2.2</td><td><strong>70</strong></td><td><strong>1.0</strong></td><td>103</td><td>1.5</td><td>115</td><td>1.6</td></tr><tr><td>Fleet20.3-N5000-s5000</td><td>2780</td><td>1.5</td><td>5530</td><td>2.9</td><td>2380</td><td>1.3</td><td>2050</td><td>1.1</td><td><strong>1880</strong></td><td><strong>1.0</strong></td><td>2110</td><td>1.1</td></tr><tr><td>Fleet20.3-N5000-s5001</td><td>2760</td><td>1.5</td><td>5090</td><td>2.8</td><td>2260</td><td>1.2</td><td><strong>1850</strong></td><td><strong>1.0</strong></td><td>1870</td><td>1.0</td><td>2070</td><td>1.1</td></tr><tr><td>Fleet20.3-N5000-s5002</td><td>2730</td><td>1.5</td><td>5370</td><td>2.9</td><td>2610</td><td>1.4</td><td>1950</td><td>1.0</td><td><strong>1870</strong></td><td><strong>1.0</strong></td><td>2110</td><td>1.1</td></tr><tr><td>Fleet20.3-N10000-s10000</td><td><strong>5860</strong></td><td><strong>1.0</strong></td><td>29600</td><td>5.1</td><td>10400</td><td>1.8</td><td>+∞</td><td>>7.4</td><td>8780</td><td>1.5</td><td>11000</td><td>1.9</td></tr><tr><td>Fleet20.3-N10000-s10001</td><td><strong>5480</strong></td><td><strong>1.0</strong></td><td>28200</td><td>5.1</td><td>8310</td><td>1.5</td><td>8350</td><td>1.5</td><td>8560</td><td>1.6</td><td>9950</td><td>1.8</td></tr><tr><td>Fleet20.3-N10000-s10002</td><td><strong>5790</strong></td><td><strong>1.0</strong></td><td>29000</td><td>5.0</td><td>11000</td><td>1.9</td><td>8190</td><td>1.4</td><td>8270</td><td>1.4</td><td>+∞</td><td>>7.5</td></tr><tr><td>Fleet20.3-N20000-s20000</td><td><strong>11400</strong></td><td><strong>1.0</strong></td><td>+∞</td><td>>4.0</td><td>+∞</td><td>>3.8</td><td>+∞</td><td>>3.8</td><td>+∞</td><td>>3.8</td><td>+∞</td><td>>3.9</td></tr><tr><td>Fleet20.3-N20000-s20001</td><td><strong>11500</strong></td><td><strong>1.0</strong></td><td>+∞</td><td>>3.8</td><td>18200</td><td>1.6</td><td>+∞</td><td>>3.8</td><td>+∞</td><td>>3.8</td><td>+∞</td><td>>3.8</td></tr><tr><td>Fleet20.3-N20000-s20002</td><td><strong>11000</strong></td><td><strong>1.0</strong></td><td>+∞</td><td>>4.6</td><td>+∞</td><td>>3.9</td><td>+∞</td><td>>3.9</td><td>+∞</td><td>>3.9</td><td>+∞</td><td>>4.0</td></tr><tr><td>product-N1000-s1000</td><td>1920</td><td>17.9</td><td>184</td><td>1.7</td><td>259</td><td>2.4</td><td>123</td><td>1.1</td><td>109</td><td>1.0</td><td><strong>107</strong></td><td><strong>1.0</strong></td></tr><tr><td>product-N1000-s1001</td><td>2070</td><td>19.9</td><td>197</td><td>1.9</td><td>302</td><td>2.9</td><td>125</td><td>1.2</td><td>109</td><td>1.0</td><td><strong>104</strong></td><td><strong>1.0</strong></td></tr><tr><td>product-N1000-s1002</td><td>1850</td><td>19.1</td><td>178</td><td>1.8</td><td>249</td><td>2.6</td><td>120</td><td>1.2</td><td><strong>97</strong></td><td><strong>1.0</strong></td><td><strong>97</strong></td><td><strong>1.0</strong></td></tr><tr><td>product-N5000-s5000</td><td>10500</td><td>8.0</td><td>3220</td><td>2.5</td><td>3630</td><td>2.8</td><td>1830</td><td>1.4</td><td>1390</td><td>1.1</td><td><strong>1310</strong></td><td><strong>1.0</strong></td></tr><tr><td>product-N5000-s5001</td><td>10100</td><td>7.4</td><td>3440</td><td>2.5</td><td>3830</td><td>2.8</td><td>1700</td><td>1.2</td><td>1480</td><td>1.1</td><td><strong>1360</strong></td><td><strong>1.0</strong></td></tr><tr><td>product-N5000-s5002</td><td>10800</td><td>7.4</td><td>3830</td><td>2.6</td><td>3730</td><td>2.6</td><td>2090</td><td>1.4</td><td>1580</td><td>1.1</td><td><strong>1460</strong></td><td><strong>1.0</strong></td></tr><tr><td>product-N10000-s10000</td><td>20200</td><td>3.6</td><td>15300</td><td>2.7</td><td>14000</td><td>2.5</td><td>7330</td><td>1.3</td><td>5820</td><td>1.0</td><td><strong>5580</strong></td><td><strong>1.0</strong></td></tr><tr><td>product-N10000-s10001</td><td>19100</td><td>3.7</td><td>13300</td><td>2.5</td><td>11800</td><td>2.3</td><td>6580</td><td>1.3</td><td>5560</td><td>1.1</td><td><strong>5230</strong></td><td><strong>1.0</strong></td></tr><tr><td>product-N10000-s10002</td><td>21300</td><td>4.0</td><td>17000</td><td>3.2</td><td>14100</td><td>2.6</td><td>6770</td><td>1.3</td><td><strong>5370</strong></td><td><strong>1.0</strong></td><td>5380</td><td>1.0</td></tr><tr><td>product-N20000-s20000</td><td>+∞</td><td>>1.7</td><td>+∞</td><td>>2.0</td><td>+∞</td><td>>1.0</td><td>32700</td><td>1.3</td><td>26000</td><td>1.0</td><td><strong>25200</strong></td><td><strong>1.0</strong></td></tr><tr><td>product-N20000-s20001</td><td>42600</td><td>2.1</td><td>+∞</td><td>>2.2</td><td>+∞</td><td>>2.2</td><td>26600</td><td>1.3</td><td>24100</td><td>1.2</td><td><strong>20000</strong></td><td><strong>1.0</strong></td></tr><tr><td>product-N20000-s20002</td><td>+∞</td><td>>1.8</td><td>+∞</td><td>>1.8</td><td>+∞</td><td>>1.8</td><td>29800</td><td>1.2</td><td>24100</td><td>1.0</td><td><strong>24000</strong></td><td><strong>1.0</strong></td></tr></tbody></table>
<table><caption>Table 8: Results for the Benders by batch algorithm with aggregation, with batch sizes from 1% to 20% of the total number of subproblems.</caption><thead><tr><th rowspan="2">instance</th><th colspan="2">Classic monocut</th><th colspan="2">Classic 1% CutAggr</th><th colspan="2">Classic 5% CutAggr</th><th colspan="2">BbB 1% CutAggr</th><th colspan="2">BbB 5% CutAggr</th><th colspan="2">BbB 10% CutAggr</th><th colspan="2">BbB 20% CutAggr</th></tr><tr><th>time</th><th>ratio</th><th>time</th><th>ratio</th><th>time</th><th>ratio</th><th>time</th><th>ratio</th><th>time</th><th>ratio</th><th>time</th><th>ratio</th><th>time</th><th>ratio</th></tr></thead><tbody><tr><td>LandS-N1000-s1000</td><td>2</td><td>2.6</td><td>0.94</td><td>1.2</td><td>1</td><td>1.6</td><td>2</td><td>2.2</td><td>0.89</td><td>1.2</td><td><strong>0.77</strong></td><td><strong>1.0</strong></td><td>0.86</td><td>1.1</td></tr><tr><td>LandS-N1000-s1001</td><td>2</td><td>2.7</td><td>1.00</td><td>1.3</td><td>1</td><td>1.8</td><td>2</td><td>2.1</td><td>0.75</td><td>1.0</td><td><strong>0.75</strong></td><td><strong>1.0</strong></td><td>0.90</td><td>1.2</td></tr><tr><td>LandS-N1000-s1002</td><td>2</td><td>2.3</td><td>1</td><td>1.3</td><td>1</td><td>1.7</td><td>2</td><td>2.0</td><td>0.99</td><td>1.2</td><td><strong>0.84</strong></td><td><strong>1.0</strong></td><td>0.91</td><td>1.1</td></tr><tr><td>LandS-N5000-s5000</td><td>11</td><td>2.7</td><td>7</td><td>1.8</td><td>8</td><td>2.0</td><td>10</td><td>2.6</td><td>5</td><td>1.2</td><td><strong>4</strong></td><td><strong>1.0</strong></td><td>4</td><td>1.1</td></tr><tr><td>LandS-N5000-s5001</td><td>10</td><td>2.3</td><td>7</td><td>1.6</td><td>9</td><td>2.0</td><td>9</td><td>2.1</td><td>5</td><td>1.2</td><td><strong>4</strong></td><td><strong>1.0</strong></td><td>4</td><td>1.0</td></tr><tr><td>LandS-N5000-s5002</td><td>11</td><td>2.9</td><td>7</td><td>1.9</td><td>8</td><td>2.1</td><td>8</td><td>2.2</td><td><strong>4</strong></td><td><strong>1.0</strong></td><td>4</td><td>1.0</td><td>4</td><td>1.1</td></tr><tr><td>LandS-N10000-s10000</td><td>22</td><td>2.7</td><td>16</td><td>1.9</td><td>18</td><td>2.2</td><td>17</td><td>2.0</td><td><strong>8</strong></td><td><strong>1.0</strong></td><td>9</td><td>1.1</td><td>9</td><td>1.1</td></tr><tr><td>LandS-N10000-s10001</td><td>22</td><td>2.8</td><td>16</td><td>2.0</td><td>20</td><td>2.5</td><td>14</td><td>1.8</td><td>8</td><td>1.0</td><td><strong>8</strong></td><td><strong>1.0</strong></td><td>9</td><td>1.2</td></tr><tr><td>LandS-N10000-s10002</td><td>20</td><td>2.6</td><td>16</td><td>2.0</td><td>18</td><td>2.2</td><td>17</td><td>2.1</td><td>8</td><td>1.0</td><td><strong>8</strong></td><td><strong>1.0</strong></td><td>9</td><td>1.2</td></tr><tr><td>LandS-N20000-s20000</td><td>49</td><td>3.0</td><td>34</td><td>2.0</td><td>39</td><td>2.3</td><td>45</td><td>2.7</td><td><strong>17</strong></td><td><strong>1.0</strong></td><td>18</td><td>1.1</td><td>19</td><td>1.2</td></tr><tr><td>LandS-N20000-s20001</td><td>43</td><td>2.4</td><td>35</td><td>1.9</td><td>39</td><td>2.2</td><td>42</td><td>2.4</td><td><strong>18</strong></td><td><strong>1.0</strong></td><td>18</td><td>1.0</td><td>21</td><td>1.2</td></tr><tr><td>LandS-N20000-s20002</td><td>44</td><td>2.6</td><td>32</td><td>1.9</td><td>40</td><td>2.3</td><td>45</td><td>2.6</td><td>18</td><td>1.0</td><td><strong>17</strong></td><td><strong>1.0</strong></td><td>19</td><td>1.1</td></tr><tr><td>gbd-N1000-s1000</td><td>2</td><td>3.5</td><td>1</td><td>2.4</td><td>2</td><td>3.1</td><td>2</td><td>2.9</td><td><strong>0.53</strong></td><td><strong>1.0</strong></td><td>0.68</td><td>1.3</td><td>0.89</td><td>1.7</td></tr><tr><td>gbd-N1000-s1001</td><td>2</td><td>3.6</td><td>1</td><td>1.6</td><td>2</td><td>2.5</td><td>2</td><td>2.4</td><td><strong>0.67</strong></td><td><strong>1.0</strong></td><td>0.99</td><td>1.5</td><td>1</td><td>1.5</td></tr><tr><td>gbd-N1000-s1002</td><td>2</td><td>3.6</td><td>1</td><td>1.9</td><td>2</td><td>2.5</td><td>2</td><td>3.0</td><td><strong>0.61</strong></td><td><strong>1.0</strong></td><td>0.68</td><td>1.1</td><td>0.88</td><td>1.4</td></tr><tr><td>gbd-N5000-s5000</td><td>13</td><td>3.8</td><td>8</td><td>2.4</td><td>11</td><td>3.2</td><td>10</td><td>3.0</td><td><strong>3</strong></td><td><strong>1.0</strong></td><td>4</td><td>1.1</td><td>4</td><td>1.3</td></tr><tr><td>gbd-N5000-s5001</td><td>11</td><td>3.6</td><td>9</td><td>2.8</td><td>10</td><td>3.2</td><td>8</td><td>2.5</td><td><strong>3</strong></td><td><strong>1.0</strong></td><td>4</td><td>1.1</td><td>4</td><td>1.4</td></tr><tr><td>gbd-N5000-s5002</td><td>12</td><td>3.4</td><td>9</td><td>2.6</td><td>9</td><td>2.7</td><td>9</td><td>2.6</td><td><strong>3</strong></td><td><strong>1.0</strong></td><td>4</td><td>1.1</td><td>5</td><td>1.3</td></tr><tr><td>gbd-N10000-s10000</td><td>24</td><td>3.4</td><td>18</td><td>2.5</td><td>21</td><td>2.9</td><td>18</td><td>2.5</td><td><strong>7</strong></td><td><strong>1.0</strong></td><td>8</td><td>1.1</td><td>9</td><td>1.2</td></tr><tr><td>gbd-N10000-s10001</td><td>24</td><td>4.0</td><td>19</td><td>3.3</td><td>19</td><td>3.2</td><td>13</td><td>2.1</td><td><strong>6</strong></td><td><strong>1.0</strong></td><td>8</td><td>1.4</td><td>9</td><td>1.5</td></tr><tr><td>gbd-N10000-s10002</td><td>23</td><td>3.8</td><td>20</td><td>3.4</td><td>23</td><td>3.9</td><td>14</td><td>2.3</td><td><strong>6</strong></td><td><strong>1.0</strong></td><td>8</td><td>1.4</td><td>11</td><td>1.8</td></tr><tr><td>gbd-N20000-s20000</td><td>48</td><td>3.8</td><td>39</td><td>3.2</td><td>47</td><td>3.7</td><td>50</td><td>4.0</td><td><strong>12</strong></td><td><strong>1.0</strong></td><td>16</td><td>1.3</td><td>20</td><td>1.6</td></tr><tr><td>gbd-N20000-s20001</td><td>51</td><td>3.6</td><td>42</td><td>3.0</td><td>45</td><td>3.2</td><td>31</td><td>2.2</td><td><strong>15</strong></td><td><strong>1.1</strong></td><td><strong>14</strong></td><td><strong>1.0</strong></td><td>19</td><td>1.4</td></tr><tr><td>gbd-N20000-s20002</td><td>47</td><td>3.4</td><td>41</td><td>3.0</td><td>45</td><td>3.3</td><td>43</td><td>3.2</td><td><strong>14</strong></td><td><strong>1.0</strong></td><td>14</td><td>1.0</td><td>19</td><td>1.4</td></tr><tr><td>ssn-N1000-s1000</td><td>2279</td><td>168.5</td><td>25</td><td>1.9</td><td>146</td><td>10.8</td><td><strong>14</strong></td><td><strong>1.0</strong></td><td>63</td><td>4.6</td><td>129</td><td>9.5</td><td>235</td><td>17.4</td></tr><tr><td>ssn-N1000-s1001</td><td>2720</td><td>185.6</td><td>24</td><td>1.7</td><td>135</td><td>9.2</td><td><strong>15</strong></td><td><strong>1.0</strong></td><td>63</td><td>4.3</td><td>130</td><td>8.8</td><td>253</td><td>17.3</td></tr><tr><td>ssn-N1000-s1002</td><td>2226</td><td>173.3</td><td>23</td><td>1.8</td><td>146</td><td>11.4</td><td><strong>13</strong></td><td><strong>1.0</strong></td><td>59</td><td>4.6</td><td>144</td><td>11.2</td><td>238</td><td>18.5</td></tr><tr><td>ssn-N5000-s5000</td><td>13425</td><td>152.4</td><td>371</td><td>4.2</td><td>1685</td><td>19.1</td><td><strong>88</strong></td><td><strong>1.0</strong></td><td>337</td><td>3.8</td><td>630</td><td>7.2</td><td>1342</td><td>15.2</td></tr><tr><td>ssn-N5000-s5001</td><td>14260</td><td>158.7</td><td>411</td><td>4.6</td><td>1536</td><td>17.1</td><td><strong>90</strong></td><td><strong>1.0</strong></td><td>322</td><td>3.6</td><td>672</td><td>7.5</td><td>1343</td><td>15.0</td></tr><tr><td>ssn-N5000-s5002</td><td>12695</td><td>140.6</td><td>416</td><td>4.6</td><td>1524</td><td>16.9</td><td><strong>90</strong></td><td><strong>1.0</strong></td><td>308</td><td>3.4</td><td>674</td><td>7.5</td><td>1280</td><td>14.2</td></tr><tr><td>ssn-N10000-s10000</td><td>26559</td><td>151.5</td><td>1212</td><td>6.9</td><td>3343</td><td>19.1</td><td><strong>175</strong></td><td><strong>1.0</strong></td><td>672</td><td>3.8</td><td>1396</td><td>8.0</td><td>2771</td><td>15.8</td></tr><tr><td>ssn-N10000-s10001</td><td>26228</td><td>140.6</td><td>1378</td><td>7.4</td><td>6126</td><td>32.8</td><td><strong>187</strong></td><td><strong>1.0</strong></td><td>760</td><td>4.1</td><td>1477</td><td>7.9</td><td>3143</td><td>16.8</td></tr><tr><td>ssn-N10000-s10002</td><td>24916</td><td>129.1</td><td>1147</td><td>5.9</td><td>5105</td><td>26.4</td><td><strong>193</strong></td><td><strong>1.0</strong></td><td>690</td><td>3.6</td><td>1397</td><td>7.2</td><td>2827</td><td>14.6</td></tr><tr><td>ssn-N20000-s20000</td><td>+∞</td><td>>94.6</td><td>7066</td><td>15.5</td><td>18068</td><td>39.6</td><td><strong>457</strong></td><td><strong>1.0</strong></td><td>1651</td><td>3.6</td><td>3463</td><td>7.6</td><td>6588</td><td>14.4</td></tr><tr><td>ssn-N20000-s20001</td><td>+∞</td><td>>94.3</td><td>5558</td><td>12.1</td><td>40319</td><td>88.0</td><td><strong>458</strong></td><td><strong>1.0</strong></td><td>1651</td><td>3.6</td><td>3065</td><td>6.7</td><td>6749</td><td>14.7</td></tr><tr><td>ssn-N20000-s20002</td><td>+∞</td><td>>106.2</td><td>13186</td><td>32.4</td><td>19979</td><td>49.1</td><td><strong>407</strong></td><td><strong>1.0</strong></td><td>1543</td><td>3.8</td><td>3630</td><td>8.9</td><td>6934</td><td>17.0</td></tr><tr><td>storm-N1000-s1000</td><td>23</td><td>3.7</td><td>12</td><td>2.0</td><td>15</td><td>2.4</td><td>12</td><td>1.9</td><td><strong>6</strong></td><td><strong>1.0</strong></td><td>7</td><td>1.1</td><td>10</td><td>1.6</td></tr><tr><td>storm-N1000-s1001</td><td>24</td><td>3.8</td><td>12</td><td>1.9</td><td>16</td><td>2.5</td><td>12</td><td>1.9</td><td><strong>6</strong></td><td><strong>1.0</strong></td><td>7</td><td>1.1</td><td>9</td><td>1.4</td></tr><tr><td>storm-N1000-s1002</td><td>24</td><td>3.7</td><td>13</td><td>2.0</td><td>15</td><td>2.3</td><td>13</td><td>2.0</td><td><strong>6</strong></td><td><strong>1.0</strong></td><td>7</td><td>1.1</td><td>9</td><td>1.4</td></tr><tr><td>storm-N5000-s5000</td><td>110</td><td>3.3</td><td>73</td><td>2.2</td><td>92</td><td>2.8</td><td>44</td><td>1.3</td><td><strong>33</strong></td><td><strong>1.0</strong></td><td>35</td><td>1.1</td><td>54</td><td>1.6</td></tr><tr><td>storm-N5000-s5001</td><td>117</td><td>3.6</td><td>72</td><td>2.2</td><td>97</td><td>3.0</td><td>54</td><td>1.6</td><td><strong>33</strong></td><td><strong>1.0</strong></td><td>36</td><td>1.1</td><td>56</td><td>1.7</td></tr><tr><td>storm-N5000-s5002</td><td>116</td><td>3.2</td><td>72</td><td>2.0</td><td>93</td><td>2.6</td><td>58</td><td>1.6</td><td><strong>37</strong></td><td><strong>1.0</strong></td><td><strong>36</strong></td><td><strong>1.0</strong></td><td>55</td><td>1.5</td></tr><tr><td>storm-N10000-s10000</td><td>215</td><td>3.0</td><td>157</td><td>2.2</td><td>202</td><td>2.8</td><td>121</td><td>1.7</td><td><strong>73</strong></td><td><strong>1.0</strong></td><td>82</td><td>1.1</td><td>105</td><td>1.4</td></tr><tr><td>storm-N10000-s10001</td><td>225</td><td>3.0</td><td>169</td><td>2.2</td><td>198</td><td>2.6</td><td>90</td><td>1.2</td><td><strong>76</strong></td><td><strong>1.0</strong></td><td>83</td><td>1.1</td><td>101</td><td>1.3</td></tr><tr><td>storm-N10000-s10002</td><td>233</td><td>3.2</td><td>166</td><td>2.3</td><td>194</td><td>2.7</td><td>118</td><td>1.6</td><td><strong>73</strong></td><td><strong>1.0</strong></td><td>80</td><td>1.1</td><td>107</td><td>1.5</td></tr><tr><td>storm-N20000-s20000</td><td>465</td><td>2.9</td><td>370</td><td>2.3</td><td>434</td><td>2.7</td><td>216</td><td>1.3</td><td>167</td><td>1.0</td><td><strong>161</strong></td><td><strong>1.0</strong></td><td>232</td><td>1.4</td></tr><tr><td>storm-N20000-s20001</td><td>434</td><td>2.7</td><td>380</td><td>2.4</td><td>413</td><td>2.6</td><td>245</td><td>1.5</td><td><strong>161</strong></td><td><strong>1.0</strong></td><td>179</td><td>1.1</td><td>246</td><td>1.5</td></tr><tr><td>storm-N20000-s20002</td><td>476</td><td>3.0</td><td>356</td><td>2.2</td><td>422</td><td>2.6</td><td>218</td><td>1.4</td><td><strong>160</strong></td><td><strong>1.0</strong></td><td>167</td><td>1.0</td><td>236</td><td>1.5</td></tr><tr><td>20term-N1000-s1000</td><td>544</td><td>36.7</td><td>272</td><td>18.4</td><td>310</td><td>20.9</td><td><strong>15</strong></td><td><strong>1.0</strong></td><td>36</td><td>2.5</td><td>71</td><td>4.8</td><td>140</td><td>9.5</td></tr><tr><td>20term-N1000-s1001</td><td>584</td><td>40.0</td><td>239</td><td>16.4</td><td>266</td><td>18.2</td><td><strong>15</strong></td><td><strong>1.0</strong></td><td>37</td><td>2.5</td><td>67</td><td>4.6</td><td>135</td><td>9.3</td></tr><tr><td>20term-N1000-s1002</td><td>604</td><td>41.4</td><td>305</td><td>20.9</td><td>364</td><td>25.0</td><td><strong>15</strong></td><td><strong>1.0</strong></td><td>37</td><td>2.5</td><td>65</td><td>4.5</td><td>148</td><td>10.2</td></tr><tr><td>20term-N5000-s5000</td><td>3095</td><td>46.0</td><td>1627</td><td>24.2</td><td>2026</td><td>30.1</td><td><strong>67</strong></td><td><strong>1.0</strong></td><td>199</td><td>3.0</td><td>401</td><td>6.0</td><td>830</td><td>12.4</td></tr><tr><td>20term-N5000-s5001</td><td>3699</td><td>47.2</td><td>1453</td><td>18.5</td><td>1911</td><td>24.4</td><td><strong>78</strong></td><td><strong>1.0</strong></td><td>197</td><td>2.5</td><td>381</td><td>4.9</td><td>794</td><td>10.1</td></tr><tr><td>20term-N5000-s5002</td><td>3725</td><td>57.8</td><td>1733</td><td>26.9</td><td>1898</td><td>29.5</td><td><strong>64</strong></td><td><strong>1.0</strong></td><td>182</td><td>2.8</td><td>404</td><td>6.3</td><td>893</td><td>13.9</td></tr><tr><td>20term-N10000-s10000</td><td>6803</td><td>52.5</td><td>3885</td><td>30.0</td><td>4741</td><td>36.6</td><td><strong>129</strong></td><td><strong>1.0</strong></td><td>411</td><td>3.2</td><td>892</td><td>6.9</td><td>1874</td><td>14.5</td></tr><tr><td>20term-N10000-s10001</td><td>6404</td><td>52.5</td><td>3193</td><td>26.2</td><td>4915</td><td>40.3</td><td><strong>122</strong></td><td><strong>1.0</strong></td><td>409</td><td>3.3</td><td>914</td><td>7.5</td><td>1970</td><td>16.1</td></tr><tr><td>20term-N10000-s10002</td><td>7494</td><td>54.5</td><td>3015</td><td>21.9</td><td>4864</td><td>35.4</td><td><strong>137</strong></td><td><strong>1.0</strong></td><td>388</td><td>2.8</td><td>886</td><td>6.4</td><td>2089</td><td>15.2</td></tr><tr><td>20term-N20000-s20000</td><td>13429</td><td>51.5</td><td>7375</td><td>28.3</td><td>10772</td><td>41.3</td><td><strong>261</strong></td><td><strong>1.0</strong></td><td>860</td><td>3.3</td><td>1913</td><td>7.3</td><td>7032</td><td>27.0</td></tr><tr><td>20term-N20000-s20001</td><td>12763</td><td>43.2</td><td>7433</td><td>25.1</td><td>26284</td><td>88.9</td><td><strong>296</strong></td><td><strong>1.0</strong></td><td>985</td><td>3.3</td><td>2139</td><td>7.2</td><td>4704</td><td>15.9</td></tr><tr><td>20term-N20000-s20002</td><td>14868</td><td>52.5</td><td>6287</td><td>22.2</td><td>11803</td><td>41.7</td><td><strong>283</strong></td><td><strong>1.0</strong></td><td>897</td><td>3.2</td><td>2101</td><td>7.4</td><td>+∞</td><td>>152.6</td></tr><tr><td>Fleet20.3-N1000-s1000</td><td>513</td><td>18.6</td><td>123</td><td>4.5</td><td>221</td><td>8.0</td><td><strong>28</strong></td><td><strong>1.0</strong></td><td>42</td><td>1.5</td><td>71</td><td>2.6</td><td>127</td><td>4.6</td></tr><tr><td>Fleet20.3-N1000-s1001</td><td>539</td><td>20.0</td><td>126</td><td>4.7</td><td>219</td><td>8.1</td><td><strong>27</strong></td><td><strong>1.0</strong></td><td>40</td><td>1.5</td><td>73</td><td>2.7</td><td>131</td><td>4.9</td></tr><tr><td>Fleet20.3-N1000-s1002</td><td>546</td><td>18.2</td><td>126</td><td>4.2</td><td>225</td><td>7.5</td><td><strong>30</strong></td><td><strong>1.0</strong></td><td>43</td><td>1.4</td><td>77</td><td>2.6</td><td>135</td><td>4.5</td></tr><tr><td>Fleet20.3-N5000-s5000</td><td>2780</td><td>25.7</td><td>905</td><td>8.4</td><td>1570</td><td>14.5</td><td><strong>108</strong></td><td><strong>1.0</strong></td><td>218</td><td>2.0</td><td>354</td><td>3.3</td><td>675</td><td>6.2</td></tr><tr><td>Fleet20.3-N5000-s5001</td><td>2760</td><td>26.5</td><td>930</td><td>8.9</td><td>1500</td><td>14.4</td><td><strong>104</strong></td><td><strong>1.0</strong></td><td>209</td><td>2.0</td><td>363</td><td>3.5</td><td>645</td><td>6.2</td></tr><tr><td>Fleet20.3-N5000-s5002</td><td>2730</td><td>24.8</td><td>873</td><td>7.9</td><td>1520</td><td>13.8</td><td><strong>110</strong></td><td><strong>1.0</strong></td><td>205</td><td>1.9</td><td>356</td><td>3.2</td><td>628</td><td>5.7</td></tr><tr><td>Fleet20.3-N10000-s10000</td><td>5860</td><td>27.4</td><td>2030</td><td>9.5</td><td>3430</td><td>16.0</td><td><strong>214</strong></td><td><strong>1.0</strong></td><td>426</td><td>2.0</td><td>725</td><td>3.4</td><td>1290</td><td>6.0</td></tr><tr><td>Fleet20.3-N10000-s10001</td><td>5480</td><td>26.2</td><td>1960</td><td>9.4</td><td>3520</td><td>16.8</td><td><strong>209</strong></td><td><strong>1.0</strong></td><td>467</td><td>2.2</td><td>721</td><td>3.4</td><td>1290</td><td>6.2</td></tr><tr><td>Fleet20.3-N10000-s10002</td><td>5790</td><td>27.2</td><td>2010</td><td>9.4</td><td>3430</td><td>16.1</td><td><strong>213</strong></td><td><strong>1.0</strong></td><td>426</td><td>2.0</td><td>716</td><td>3.4</td><td>1350</td><td>6.3</td></tr><tr><td>Fleet20.3-N20000-s20000</td><td>11400</td><td>28.4</td><td>5200</td><td>12.9</td><td>8040</td><td>20.0</td><td><strong>402</strong></td><td><strong>1.0</strong></td><td>886</td><td>2.2</td><td>1510</td><td>3.8</td><td>2810</td><td>7.0</td></tr><tr><td>Fleet20.3-N20000-s20001</td><td>11500</td><td>26.8</td><td>4820</td><td>11.2</td><td>7690</td><td>17.9</td><td><strong>429</strong></td><td><strong>1.0</strong></td><td>856</td><td>2.0</td><td>1490</td><td>3.5</td><td>2750</td><td>6.4</td></tr><tr><td>Fleet20.3-N20000-s20002</td><td>11000</td><td>25.9</td><td>5140</td><td>12.1</td><td>7850</td><td>18.5</td><td><strong>425</strong></td><td><strong>1.0</strong></td><td>885</td><td>2.1</td><td>1560</td><td>3.7</td><td>2770</td><td>6.5</td></tr><tr><td>product-N1000-s1000</td><td>1920</td><td>18.5</td><td>191</td><td>1.8</td><td>415</td><td>4.0</td><td><strong>104</strong></td><td><strong>1.0</strong></td><td>140</td><td>1.3</td><td>246</td><td>2.4</td><td>471</td><td>4.5</td></tr><tr><td>product-N1000-s1001</td><td>2070</td><td>21.3</td><td>197</td><td>2.0</td><td>452</td><td>4.7</td><td><strong>97</strong></td><td><strong>1.0</strong></td><td>149</td><td>1.5</td><td>266</td><td>2.7</td><td>528</td><td>5.4</td></tr><tr><td>product-N1000-s1002</td><td>1850</td><td>20.2</td><td>182</td><td>2.0</td><td>425</td><td>4.6</td><td><strong>91</strong></td><td><strong>1.0</strong></td><td>135</td><td>1.5</td><td>247</td><td>2.7</td><td>515</td><td>5.6</td></tr><tr><td>product-N5000-s5000</td><td>10500</td><td>29.8</td><td>1530</td><td>4.3</td><td>3290</td><td>9.3</td><td><strong>352</strong></td><td><strong>1.0</strong></td><td>734</td><td>2.1</td><td>1550</td><td>4.4</td><td>3180</td><td>9.0</td></tr><tr><td>product-N5000-s5001</td><td>10100</td><td>29.3</td><td>1460</td><td>4.2</td><td>3250</td><td>9.4</td><td><strong>345</strong></td><td><strong>1.0</strong></td><td>787</td><td>2.3</td><td>1420</td><td>4.1</td><td>2580</td><td>7.5</td></tr><tr><td>product-N5000-s5002</td><td>10800</td><td>27.7</td><td>1580</td><td>4.1</td><td>3430</td><td>8.8</td><td><strong>390</strong></td><td><strong>1.0</strong></td><td>797</td><td>2.0</td><td>1730</td><td>4.4</td><td>2860</td><td>7.3</td></tr><tr><td>product-N10000-s10000</td><td>20200</td><td>28.7</td><td>3830</td><td>5.4</td><td>8170</td><td>11.6</td><td><strong>704</strong></td><td><strong>1.0</strong></td><td>1620</td><td>2.3</td><td>2980</td><td>4.2</td><td>5670</td><td>8.1</td></tr><tr><td>product-N10000-s10001</td><td>19100</td><td>25.3</td><td>3910</td><td>5.2</td><td>7480</td><td>9.9</td><td><strong>756</strong></td><td><strong>1.0</strong></td><td>1400</td><td>1.9</td><td>2980</td><td>3.9</td><td>5140</td><td>6.8</td></tr><tr><td>product-N10000-s10002</td><td>21300</td><td>21.1</td><td>3740</td><td>3.7</td><td>7620</td><td>7.5</td><td><strong>1010</strong></td><td><strong>1.0</strong></td><td>1550</td><td>1.5</td><td>3200</td><td>3.2</td><td>5780</td><td>5.7</td></tr><tr><td>product-N20000-s20000</td><td>+∞</td><td>>24.1</td><td>9820</td><td>5.5</td><td>19300</td><td>10.8</td><td><strong>1790</strong></td><td><strong>1.0</strong></td><td>3330</td><td>1.9</td><td>6740</td><td>3.8</td><td>13500</td><td>7.5</td></tr><tr><td>product-N20000-s20001</td><td>42600</td><td>23.3</td><td>9670</td><td>5.3</td><td>19200</td><td>10.5</td><td><strong>1830</strong></td><td><strong>1.0</strong></td><td>3230</td><td>1.8</td><td>5950</td><td>3.3</td><td>11500</td><td>6.3</td></tr><tr><td>product-N20000-s20002</td><td>+∞</td><td>>29.6</td><td>10400</td><td>7.1</td><td>19600</td><td>13.4</td><td><strong>1460</strong></td><td><strong>1.0</strong></td><td>3540</td><td>2.4</td><td>6270</td><td>4.3</td><td>12500</td><td>8.6</td></tr></tbody></table>