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

HAL
open science

# Improving Dantzig-Wolfe relaxation through crosswise decomposition

Pascale Bendotti, Pierre Fouilhoux, Cécile Rottner, Thibault Vignon

► To cite this version:

Pascale Bendotti, Pierre Fouilhoux, Cécile Rottner, Thibault Vignon. Improving Dantzig-Wolfe relaxation through crosswise decomposition. 2025. hal-05315705

HAL Id: hal-05315705

https://edf.hal.science/hal-05315705v1

Preprint submitted on 15 Oct 2025

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_2.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
Improving Dantzig-Wolfe relaxation through crosswise decomposition

Pascale Bendotti

EDF R&D, 7 Boulevard Gaspard Monge, 91120 Palaiseau, France
Sorbonne Université, CNRS, LIP6 UMR 7606, 4 place Jussieu, 75005 Paris, France
pascale.bendotti@edf.fr

Pierre Fouilhoux

LIPN CNRS, Université Sorbonne Paris Nord, 99, avenue Jean-Baptiste Clément 93430 Villetaneuse, France
pierre.fouilhoux@lipn.fr

Cécile Rottner

EDF R&D, 7 Boulevard Gaspard Monge, 91120 Palaiseau, France
cecile.rottner@edf.fr

Thibault Vignon

LIPN CNRS, Université Sorbonne Paris Nord, 99, avenue Jean-Baptiste Clément 93430 Villetaneuse, France
thibault.vignon.2019@polytechnique.org

**Abstract**

Reformulation of mixed integer programs based on decomposition is a common approach to obtain stronger linear relaxation and thus better bounds in a branch-and-bound type algorithm. We introduce the so-called crosswise decomposition technique as a framework performing double Dantzig-Wolfe decomposition across two orthogonal structures simultaneously. It relies on variable splitting, a technique better known in Lagrangian relaxation. Our theoretical contributions include a dynamic lower bound valid throughout the course of column generation, and two convergence acceleration techniques specific to the double decomposition framework. We illustrate through computational experiments the potential of this framework on a pared-down form of the Unit Commitment Problem which captures the core of its combinatorial complexity.

**Keywords** Mixed-Integer Programming, Decomposition, Variable splitting, Dantzig-Wolfe, Double Convexification, Lagrangian Relaxation, Unit Commitment.

**Acknowledgments** The authors are grateful to the Gaspard Monge Program for Optimization, Operations Research and their Interactions with Data Science (PGMO) for funding this research.

# 1 Introduction

State-of-the-art mixed integer programming solvers are regularly improving and are in many cases very effective to solve (mixed) integer programs. Some variants of difficult problems still remain hard to solve. These solvers typically use branch-and-cut techniques to both induce improved convex or linear programming bounds and carry out implicit enumeration of the solutions. However these systems do not fully account for the problem structure.

An alternative formulation is commonly proposed to better capture the structure of the problem or even to eliminate symmetries. This leads to the so-called reformulations that rely on a *decomposition* of the problem. The aim of such an approach is to bring out underlying structures of the problem. The principle is to extract subproblems which are easier to solve and then to combine their corresponding solutions. Decomposition can take various shapes, like Dantzig-Wolfe, Benders or Lagrangian relaxation (see for example [22] or [40]).

Among the wide variety of methods used to obtain a stronger bound than linear relaxation, *partial convexification* is arguably the most prevalent. Partial convexification can be implemented through either Lagrangian relaxation [10] or Dantzig-Wolfe decomposition [8], which is the technique we will focus on. Dantzig-Wolfe decomposition expresses every feasible solution as a convex combination of extreme points. In general, there may be exponentially many extreme points, but in practice the optimal solution almost always requires only a reduced number of them. This leads us to employ column generation, which iteratively generates the variables likely to improve the current solution. The use of column generation in a Branch & Bound scheme is called Branch & Price [4].

© Pascale Bendotti & Pierre Fouilhoux & Cécile Rottner & Thibault Vignon;
licensed under Creative Commons License Attribution 4.0 International

<figure><img src="image_3.png" /></figure>
To further improve the relaxation value compared to the aforementioned partial convexification, one can want to simultaneously convexify two sets of constraints. This can be very useful when each set of constraints is easy to tackle, but their combination is hard, e.g., if the matrices associated with the sets of constraints are both block-diagonal for different block structures. In order to simultaneously convexify the feasible sets for both sets of constraints, two copies of the decision variables are used. This duplication of variables is known in the literature as *variable splitting*. This technique was first proposed by Monique Guignard in 1987, in the Lagrangian relaxation framework, and given the name *Lagrangian decomposition*. In a similar fashion as the simple convexification case, we can reformulate this relaxation using Dantzig-Wolfe decomposition. We obtain a *double decomposition* with two or more independent pricing subproblems, and can benefit from a larger improvement in relaxation value than we would have from convexification of either set of constraints on its own.

In practice this means that each subproblem may contain very few variables and constraints, and can then be solved using efficient methods, like pseudo-polynomial dynamic programming algorithms. Pricing by dynamic programming brings not only a reduced solving time, but also and perhaps more importantly, the ability to deal with non-linear constraints or objective functions. However, double decomposition generally resulted in poor convergence properties for column generation (e.g. [19]). Indeed, such a decomposition brings several quirks to column generation which impair its convergence: our theoretical contributions exploit these particularities in order to improve the efficiency of column generation for double decomposition.

The choice of the structures on which to decompose is crucial to the usefulness and efficiency of a double decomposition. Structures of particular interest for double decomposition appear when there are two competing orthogonal structures in the variables and constraints, amounting in both sides of the decomposition to breaking up into small independent subproblems. We call decomposing simultaneously on both orthogonal structures *crosswise decomposition*. The considered application on the Unit Commitment Problem will feature such a structural property and in this case, crosswise decomposition will show promising results.

Our first contribution is a lower bound which can be computed at each iteration of column generation with no extra effort and may be equal or very close to the relaxation value. Depending on the dynamic behavior of column generation, it can provide in many cases a strong valid bound without having to wait for termination of the procedure.

Our other theoretical contributions concern the improvement of column generation convergence in double decomposition. We describe and analyze two convergence acceleration techniques we developed specifically for this framework: primal cost splitting and variable balancing with an inequality. These two adaptations are at first glance incompatible in many cases; we propose an algorithm to efficiently combine them through dynamic adjustment of the pricing subproblems objective function.

We apply this framework to a stripped-down version of the Unit Commitment Problem (UCP), which captures the combinatorial difficulty of the industrial problem while abstracting the technical specificities of production units. This allows us to analyze the impact of (1) the crosswise decomposition framework compared to standard methods, and (2) the aforementioned convergence acceleration techniques.

In Section 2, we introduce more precisely our setting and notations, and provide a brief state of the art. Section 3 presents the dynamic lower bound, and Section 4 the convergence acceleration techniques. Finally, Section 5 details the application to the UCP and discusses the experimental results we obtained.

## 2 Double convexification and Dantzig-Wolfe decomposition

In this article, the MIP considered has the following form:

$$ (P): \left\{ \begin{array}{ll} \min_{x \in X} & cx \\ \text{s.t.} & x \in A \\ & x \in B \end{array} \right. $$

where variables $x$ must satisfy the global constraint set $X \subset \mathbb{R}^n$ including some integrity constraints over some variables and the two constraint sets $A$ and $B$, while maximizing a cost vector $c$. To produce optimal or provably good solutions, the goal is to approach the optimal value, denoted $value(P)$, by relaxing some constraints or using decomposition methods. Constraints sets $A$ and $B$ are supposed to have a particular (distinct) structure whose convexification leads to strong relaxation bounds. Such structures can be block-diagonal inequality matrices, or the structure of a well solved NP-hard problem, e.g., knapsack problem, or non-linear constraints.
<figure><img src="image_4.png" /><figcaption>Figure 1 Interpretation of double convexification</figcaption></figure>

Convexifying a set of constraints $M$ is to consider the convex hull of vectors satisfying both $X$ and $M$, i.e., $conv^M = conv\{x \in X \cap M\}$ and the associated pricing problem that is to find extreme points of this convex set. It is often the case that simultaneously convexifying both constraint sets $A$ and $B$, i.e., $conv^{A \cap B}$, drives to a hard to solve pricing subproblem, whereas the two pricing subproblems associated with $conv^A$ and $conv^B$ are easier to solve. In that case, the classical convexification is to consider either convexification $C^A$ or $C^B$ as follows.

$$ (C^A): \left\{ \begin{array}{ll} \min & cx \\ \text{s.t.} & x \in conv^A \\ & x \in B \end{array} \right. $$

$$ (C^B): \left\{ \begin{array}{ll} \min & cx \\ \text{s.t.} & x \in A \\ & x \in conv^B \end{array} \right. $$

In this article, we consider the following decomposition (DC) called double convexification (or overlapping convexification) as the two convexified spaces partially overlap.

$$ (DC): \left\{ \begin{array}{ll} \min & cx \\ \text{s.t.} & x \in conv^A \cap conv^B \end{array} \right. $$

Figure 1 illustrates the relaxation standpoint between (P), $C^A$, $C^B$ and DC. Figure 1 proposes in (a) the general case when constraints $A$ and $B$ are non-linear constraints, while in (b), $A$ and $B$ are inequalities. In both cases, point $x_P$ (resp. $x_A$, $x_B$ and $x_{DC}$) corresponds to the solution obtained by solving the continuous relaxation (P) (resp. $C^A$, $C^B$ and DC) through the diverse convexifications. The hope is that, as represented in this illustration, the relaxation value provided by (DC) is more interesting than the other lower bounds. ▷ Property 1 ([13]). The optimal value of (DC) is greater than or equal to the optimal value of $(C^A)$ (resp. $(C^B)$).

## Variable splitting

To implement this double convexification, a classical method, called variable splitting, is to create two copies of the decision variables as follows.

$$ (P') : \left\{ \begin{array}{ll} \min_{x, \tilde{x} \in X} & cx \\ \text{s.t.} & x \in A \\ & \tilde{x} \in B \\ & x = \tilde{x} \end{array} \right. $$

This MILP ($P'$) is equivalent to our initial program as $value(P') = value(P)$. In the Lagrangian context, Guignard and Kim [13] introduced variable splitting in 1987, thus obtaining the Lagrangian decomposition framework presented in this section. Variable splitting is also common in stochastic programming based on scenarios, where variables are duplicated into one copy for each scenario (e.g., [18] or [37]). Note that the term variable splitting is sometimes used for other approaches: for example, Niu et al. [26] use it to describe a symmetry-breaking approach which adds aggregated variables to their formulation and then apply Lagrangian relaxation.

In order to decompose the formulation into two pricing problems with distinct structures, the two classical approaches are Lagrangian and Dantzig-Wolfe decomposition.
## Lagrangian decomposition

The Lagrangian decomposition obtained by relaxing constraint $x = \tilde{x}$ in program ($P'$) drives to program ($LD$) and the associated Lagrangian dual ($LDD$).

$$ (LD(\lambda)) : \left\{ \begin{array}{ll} \min_{x, \tilde{x} \in X} & cx + \lambda(x - \tilde{x}) \\ \text{s.t.} & x \in A \\ & \tilde{x} \in B \end{array} \right. \qquad (LDD) : \left\{ \begin{array}{ll} \max_{\lambda \in \mathbb{R}^n} & value(LD(\lambda)) \end{array} \right. $$

From classical Lagrangian properties, $value(DC) = value(LDD)$. Moreover, from the variable splitting techniques, the ($LD$) program splits into two independent MIPs, leading to the name *Lagrangian decomposition* given to the technique introduced by Guignard and Kim in 1987 [13]. Variable splitting has since then been applied successfully to many MILP and MINLP problems, for example by Ghaddar et al. to the pump scheduling problem in water networks [11].

Guignard and Kim [13] show that the lower bound provided by Lagrangian decomposition is at least as strong as both of the bounds from the Lagrangian relaxations of either set of constraints. To obtain a strictly better bound in Lagrangian decomposition, each convexified set must be such that its convexification provides a tighter envelope than the convex hull of its original description. Otherwise, the bound provided by Lagrangian decomposition is equal to the best of the two Lagrangian relaxation values.

## Double Dantzig-Wolfe decomposition

The double Dantzig-Wolfe decomposition is obtained by considering both sets $\mathcal{P}^A$ and $\mathcal{P}^B$ of extreme points of $conv^A$ and $conv^B$. Every feasible solution of ($P'$) can be expressed according to the points in $\mathcal{P}^A$ and $\mathcal{P}^B$:

$$ x = \sum_{\pi \in \mathcal{P}^A} \lambda_{\pi} \pi \quad \text{with} \quad \sum_{\pi \in \mathcal{P}^A} \lambda_{\pi} = 1 \text{ and } \lambda_{\pi} \ge 0 \quad \forall \pi \in \mathcal{P}^A $$

$$ \tilde{x} = \sum_{\mu \in \mathcal{P}^B} \rho_{\mu} \mu \quad \text{with} \quad \sum_{\mu \in \mathcal{P}^B} \rho_{\mu} = 1 \text{ and } \rho_{\mu} \ge 0 \quad \forall \mu \in \mathcal{P}^B $$

The resulting master problem ($MP'$) equivalent to ($P'$) is solved iteratively using column generation. At each iteration $k$, a restricted master problem ($RMP_k$) is induced from two subsets $\mathcal{P}_k^A$ and $\mathcal{P}_k^B$ of extreme points as follows. When it is clear from the context, the subscript $k$ will be omitted for the variables and subproblems.

$$ (RMP_k) : \left\{ \begin{array}{ll} \min & \sum_{\pi \in \mathcal{P}_k^A} c\pi\lambda_{\pi} \\ \text{s.t.} & \sum_{\pi \in \mathcal{P}_k^A} \lambda_{\pi}\pi = \sum_{\mu \in \mathcal{P}_k^B} \rho_{\mu}\mu \quad [\gamma] \\ & \sum_{\pi \in \mathcal{P}_k^A} \lambda_{\pi} = 1 \quad [\sigma_1] \\ & \sum_{\mu \in \mathcal{P}_k^B} \rho_{\mu} = 1 \quad [\sigma_2] \\ & \lambda_{\pi} \ge 0, \rho_{\mu} \ge 0 \quad \forall \pi \in \mathcal{P}_k^A, \forall \mu \in \mathcal{P}_k^B \end{array} \right. $$

Note that ($RMP_k$) is then a linear program and the dual values associated with its constraints are indicated in brackets. The first constraint is exactly variable splitting constraint $x = \tilde{x}$ from problem ($P'$).

This decomposition is theoretically equivalent to the Lagrangian decomposition, and we also obtain two distinct pricing problems:

$$ (PP_k^A) : \left\{ \begin{array}{ll} \min_{x \in X} & -\sigma_1 + (c - \gamma)x \\ \text{s.t.} & x \in A \end{array} \right. \qquad (PP_k^B) : \left\{ \begin{array}{ll} \min_{\tilde{x} \in X} & -\sigma_2 + \gamma\tilde{x} \\ \text{s.t.} & \tilde{x} \in B \end{array} \right. $$

Applying variable splitting in Dantzig-Wolfe decomposition results in double Dantzig-Wolfe decomposition and was first studied by Vanderbeck [39, 40, 9]. There have since been attempts to apply it to real-world problems, but not nearly as many as for Lagrangian decomposition.
Létocart et al. apply double Dantzig-Wolfe decomposition to the generalized assignment problem [19], and Pimentel et al. on multi-item capacitated lot sizing [27], but both report poor convergence properties for the resulting column generation. One exception is the work of Zhao et al. on the fixed charge transportation problem [43], which reports a lower integrality gap using this technique compared to previous best methods. They mention that they balance primal costs between their two main subproblems, without going into detail on this idea, which motivated our work in Section 4.1. In a network optimization context where pricing problems relate to path computation, Martin et al. [23] propose a framework called Atomic Column Generation, making use of variable splitting in Dantzig-Wolfe decomposition. The idea is to combine the advantages of various existing pricing algorithms (here more than ten), each taking into account a slightly different set of constraints.

Note that variable splitting is not always necessary to reach a formulation with properties similar to double decomposition. Indeed, Kim et al. [17] design a formulation on the unsplittable flow problem that enables double column generation with many independent pricing subproblems, but no duplicated copies of any variable. Instead, they maintain their two original types of variables, linked in the master problem by an inequality. This situation inspired our work in Section 4.2.

### Crosswise decomposition

Crosswise decomposition corresponds to the double Dantzig-Wolfe decomposition in the special case of problems with the crosswise property. More precisely, an MIP formulation features the crosswise property if (1) its decision variables are double indexed, i.e., $x_{ij}$ for $i \in I, j \in J$, and (2) if there are two types of constraints corresponding to these two indexes, i.e., constraints $A_i \subset A$ involving variables $x_{i\bullet}$ for all $i \in I$, and constraints $B_j \subset B$ involving variables $x_{\bullet j}$ for all $j \in J$. In this case, much can be gained from the decomposition according to these two categories of constraints. Indeed, by convexifying constraints $A$ we obtain $|I|$ independent subproblems instead of a single larger one; by convexifying constraints $B$ we obtain $|J|$ independent subproblems. If we apply double decomposition to an MILP formulation featuring such a structure, we obtain $|I|$ independent subproblems on one side and $|J|$ independent subproblems on the other, with the two sides linked by variable splitting. Considering the vector of decision variables $x_{ij}$ as a matrix, this decomposition scheme equates to the execution of double convexification with variable splitting on the lines of this matrix on the one hand and on the columns of the matrix on the other hand: this is why we call this method crosswise decomposition. Note that the methods proposed in Sections 3 and 4 are more general and do not rely on this crosswise structure. However, the application considered in Section 5 features such a structural property and shows promising practical results.

## 3 Dynamic lower bound in crosswise decomposition

As exhibited in the state of the art, crosswise decomposition can lead to an improved relaxation value compared to more common single decomposition techniques. We now consider the dynamic nature of the column generation which provides this bound. The dynamic behavior of column generation is very important, as its iterative analysis can sometimes provide a bound equal or very close to the relaxation value without having to wait for convergence of the procedure. This bound is what we will examine in this section.

The relaxation value is the optimal value of the complete master problem, i.e., the restricted master problem after convergence. However, before convergence we can compute with no extra effort a bound whose value can increase or decrease at each iteration but which is always valid for the complete master problem (and thus lower than the relaxation value).

The following consists in the adaptation of the bound given by Vanderbeck [40] for simple decomposition to the case of crosswise decomposition, with variable splitting.

**Theorem 1.** At a given iteration $k$, we note $(\gamma^k, \sigma_1^k, \sigma_2^k)$ an optimal dual solution for $RMP_k$. Then $\text{value}(P) \ge \text{value}(PP_k^A) + \sigma_1^k + \text{value}(PP_k^B) + \sigma_2^k$.

**Proof.** The dual of the restricted master problem $RMP_k$ at iteration $k$ is expressed as:

$$ \max \quad \sigma_1 + \sigma_2 $$

$$ \text{s.t.} \quad \gamma\pi + \sigma_1 \le c\pi \quad \forall \pi \in P_k^A $$

$$ \sigma_2 \le \gamma\mu \quad \forall \mu \in P_k^B $$

$$ \gamma, \sigma_1, \sigma_2 \in \mathbb{R} $$
Note $\xi_1^k = \text{value}(PP_k^A) + \sigma_1^k$ and $\xi_2^k = \text{value}(PP_k^B) + \sigma_2^k$. Then $(\gamma^k, \xi_1^k, \xi_2^k)$ forms a feasible solution for the dual of complete master problem $MP$: indeed, $\xi_1^k$ and $\xi_2^k$ satisfy the constraints of the dual problem when they are expressed over every point of $conv^A$ and $conv^B$ respectively, not only those considered at iteration $t$ of column generation. Therefore $\xi_1^k + \xi_2^k$ is lower than the optimal value of the dual of the complete master problem, which by weak duality is lower than the optimal value of the complete master problem and then of problem $P$.

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

# 4 Accelerating column generation convergence in crosswise decomposition

Beyond the bound it provides, the second major concern with any column generation scheme is the quality of its convergence. The aim is to reduce as much as possible the number of pricing iterations and the number of columns required for convergence.

To this end, several classes of established techniques exist, of which one particularly important group is stabilisation techniques. One can refer to [9] for an extended presentation of classical stabilisation techniques for column generation.

Here, we are more precisely interested in techniques which are specific to double decomposition, brought about by the two copies of each variable (variable splitting). These techniques were touched upon in the literature, we propose an in-depth analysis of such techniques and their combination.

## 4.1 Primal cost balancing

One idea aiming to accelerate column generation convergence is to balance the primal costs between the two classes of pricing subproblems. This originates from the work of Zhao et al. on the fixed charge transportation problem [43], which mentions the idea without going into any detail.

Because the problem remains equivalent, we can transform its objective function in this manner:

$$ (P'_{\alpha}): \left\{ \begin{array}{ll} \min_{x, \tilde{x} \in X} & (1-\alpha)cx + \alpha c \tilde{x} \\ \text{s.t.} & x \in A \\ & \tilde{x} \in B \\ & x = \tilde{x} \end{array} \right. $$

where $\alpha$ is the cost-balancing parameter, between 0 and 1. Note that with $\alpha = 0$, i.e., no cost balancing, $(P'_{\alpha}) = (P')$.

The pricing subproblems become:

$$ (PP_{\alpha}^{A}): \left\{ \begin{array}{ll} \min_{x \in X} & -\sigma_1 + ((1-\alpha)c - \gamma)x \\ \text{s.t.} & x \in A \end{array} \right. $$

$$ (PP_{\alpha}^{B}): \left\{ \begin{array}{ll} \min_{\tilde{x} \in X} & -\sigma_2 + (\alpha c + \gamma)\tilde{x} \\ \text{s.t.} & \tilde{x} \in B \end{array} \right. $$

### ▷ Theorem 2. $(P'_{\alpha})$ has objective value identical to the initial problem $(P')$.

**Proof.** Because of the variable splitting equality $x = x'$, we always have $(1-\alpha)cx + \alpha cx' = cx$.

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

This reformulation preserves the match between the constraints of the dual of the master problem and the cost functions of the two pricing subproblems, which ensures that the dynamic lower bound given in Section 3 remains valid. However, it affects the iterative behaviour of the column generation, and with it the behaviour of this bound.

The rationale for this balancing is that it is beneficial to 'guide' both subproblems towards generating columns with a lower primal cost. In order for this to happen, both subproblems need to account for these primal costs, rather than them being entirely placed on a single one. Though this justification does not constitute a proof per se, cost balancing has proven to be very useful experimentally.
## 4.2 Variable splitting inequality

Under certain conditions which we shall specify, when applying variable splitting we can reformulate the problem using a splitting inequality rather than an equality to link the two copies of each variable. This leads to two possible formulations depending on which copy of the variables bears the cost.

$$ (P'_{in}): \min_{(x,\tilde{x}) \in \mathcal{X}} cx \quad \text{or} \quad (\tilde{P}'_{in}): \min_{(x,\tilde{x}) \in \mathcal{X}} c\tilde{x} $$

where the feasible set $\mathcal{X}$ is defined as:

$$ \mathcal{X} = \begin{cases} x, \tilde{x} \in X \\ x \in A \\ \tilde{x} \in B \\ x \ge \tilde{x} \end{cases} $$

Let us now consider the conditions under which such relaxations preserve the optimal value.

▷ Definition 1. Constraint set $B$ is said to be $\mathcal{X}$-dominant if:

$$ (x, \tilde{x}) \in \mathcal{X} \implies x \in B $$

Symmetrically, we can define the concept of antidominance in $\mathcal{X}$.

▷ Definition 2. Constraint set $A$ is said to be $\mathcal{X}$-antidominant if:

$$ (x, \tilde{x}) \in \mathcal{X} \implies \tilde{x} \in A $$

▷ Remark 1. Note that when $B$ is dominant (i.e., for any $x \in B$, if $x' \ge x$ then $x' \in B$), then $B$ is also $\mathcal{X}$-dominant. Similarly, when $A$ is antidominant (i.e., for any $x' \in A$, if $x' \ge x$ then $x \in A$), then $A$ is also $\mathcal{X}$-antidominant.

In particular, if $A$ (resp. $B$) is a set of knapsack (resp. covering) constraints, it is antidominant (resp. dominant).

▷ Theorem 3. If $B$ is $\mathcal{X}$-dominant, $(P'_{in})$ has the same optimal value as $(P)$ for any objective vector $c$.

**Proof.** Formulation $(P'_{in})$ is a relaxation of $(P)$. Therefore it suffices to show that any solution of $(P'_{in})$ can be transformed into a same value solution of $(P)$ to prove the result. Suppose $B$ is $\mathcal{X}$-dominant. Then, for any $(x, \tilde{x})$ feasible for $(P'_{in})$, $x$ is feasible for $(P)$ and has the same objective value. ◀

▷ Corollary 1. When constraints $B$ are linear constraints, i.e., $Bx \le b$, $(P'_{in})$ has the same optimal value as $(P)$ for any objective vector $c$ if and only if $B$ is $\mathcal{X}$-dominant.

**Proof.** The first implication follows directly from Theorem 3. Conversely, suppose that there exists $(x, \tilde{x})$ feasible for $(P'_{in})$ such that $B_jx > b_j$ for some row $j$ of matrix $B$. Then, choosing the objective vector $c = -B_j$, we have that $(x, \tilde{x})$ has objective value strictly less than $-b_j$, whereas the optimal value of $(P)$ cannot be smaller than $-b_j$ because every feasible solution for $(P)$ satisfies $B_jx \le b_j$. ◀

We can prove similarly results for $(\tilde{P}'_{in})$.

▷ Theorem 4. If $A$ is $\mathcal{X}$-antidominant, $(\tilde{P}'_{in})$ has the same optimal value as $(P)$ for any objective vector $c$.

▷ Corollary 2. When constraints $A$ are linear constraints, i.e., $Ax \le a$, $(\tilde{P}'_{in})$ has the same optimal value as $(P)$ for any objective vector $c$ if and only if $A$ is $\mathcal{X}$-antidominant.

The proof can be done similarly as for Corollary 1.

Reformulations $(P'_{in})$ and $(\tilde{P}'_{in})$ partially relax the constraints of the restricted master problem $(P)$, which has two objectives:

- make the search for feasible integer solutions easier: indeed, the solutions provided by the two pricing subproblems are no longer required to coincide exactly, which considerably eases the finding of integer solutions. These integer feasible solutions are very important in Branch & Price as they provide an upper bound on the optimal value of the problem.
- accelerate the convergence of column generation by shrinking the dual feasible space. To understand this, consider that column generation in the primal is equivalent to adding cuts in the dual. The dual search space being as reduced as possible can lead to more useful cuts, and therefore fewer iterations.

Outside the frame of variable splitting, the benefits of inequalities compared to equalities in a column generation scheme has already been noted. For example, several works in Branch & Price on set partitioning problems, such as graph coloring, highlight the positive impact of inequalities ([39], [24]). In these cases, the replacement of an equality by an inequality comes from the relaxation of a partitioning problem to a covering problem.

Now suppose we are in the case where $B$ is $\mathcal{X}$-dominant. With the splitting inequality, the master problem considered in column generation becomes:

$$ (MP_{in}): \left\{ \begin{array}{ll} \min & \sum_{\pi \in \mathcal{P}^A} (c\pi)\lambda_{\pi} \\ \text{s.t.} & \sum_{\pi \in \mathcal{P}^A} \lambda_{\pi} \pi \ge \sum_{\mu \in \mathcal{P}^B} \rho_{\mu} \mu \\ & \sum_{\pi \in \mathcal{P}^A} \lambda_{\pi} = 1 \\ & \sum_{\mu \in \mathcal{P}^B} \rho_{\mu} = 1 \\ & \lambda_{\pi} \ge 0, \rho_{\mu} \ge 0 \quad \forall \pi \in \mathcal{P}^A, \forall \mu \in \mathcal{P}^B \end{array} \right. $$

This does not affect the expression of the two pricing problems.

It also has no impact on the validity or the computation of the dynamic lower bound (3). However, like primal cost balancing presented in Section 4.1, it affects the iterative behaviour of column generation and thus of the lower bound.

## 4.3 Combining cost balancing and splitting inequality

In this section, we consider formulation ($P'_{in}$) and we suppose it satisfies the condition of Theorem 3, i.e., it is such that $B$ is $\mathcal{X}$-dominant. By Theorem 3, optimality is preserved in ($P'_{in}$). We now study the optimality of the reformulation obtained by combining cost balancing and splitting inequalities, i.e., by balancing costs in ($P'_{in}$).

### Validity of the combination

Cost balancing can take different forms depending on the structure of the problem, but it is always possible to implement it in some way. We examined previously the conditions under which the variable splitting inequality can be applied, and showed that they are not extremely restrictive. However, in many cases where the variable splitting inequality can be implemented, it is incompatible with cost balancing. In order to see this, let us examine the combined formulation ($P''$):

$$ (P'') : \left\{ \begin{array}{ll} \min_{x, \tilde{x} \in X} & (1 - \alpha)cx + \alpha c\tilde{x} \\ \text{s.t.} & x \in A \\ & \tilde{x} \in B \\ & x \ge \tilde{x} \end{array} \right. $$

where $\alpha$ is the cost-balancing parameter, logically (but not necessarily) between 0 and 1.

In general, when $B$ is $\mathcal{X}$-dominant, ($P''$) is a relaxation of ($P'_{in}$).

▷ Property 2. If $B$ is $\mathcal{X}$-dominant, the optimal value of ($P''$) is less than or equal to that of ($P'_{in}$).

**Proof.** Consider $(x, \tilde{x})$ an optimal solution of ($P'_{in}$) with value $cx$. As set $B$ is $\mathcal{X}$-dominant, $x \in B$ and solution $(x, x)$ is valid for ($P''$) and has cost $cx$. ▼
Note that the optimal value of ($P''$) may be strictly lower than that of ($P'_{in}$), as constraint set $A$ is arbitrary. In particular, if an optimal solution $(x, \tilde{x})$ of ($P''$) is such that $cx > c\tilde{x}$, it may not be possible to obtain the same optimal value for ($P'_{in}$) as it may be that $\tilde{x} \notin A$.

To ensure that such a formulation is always valid, i.e., of optimal value no lower than the initial formulation, it is necessary that for every feasible solution $(x, \tilde{x})$ of ($P''$), the constraints $x \in B$ and $\tilde{x} \in A$ hold.

Indeed, what has changed compared to the case where we do not balance primal costs is that we impose costs on the variable $\tilde{x}$. Therefore $\tilde{x}$ must verify the constraints corresponding to matrix $A$; whereas a variable which bears no cost can take any values as long as the variables bearing the costs match a feasible solution.

**$\triangleright$ Property 3.** If $A$ is $\mathcal{X}$-antidominant and $B$ is $\mathcal{X}$-dominant, then formulation ($P''$) has same optimal value as ($P'_{in}$).

**Proof.** Property 2 shows that ($P''$) has an optimal value less than or equal to that of ($P'_{in}$). We thus show the reverse. Consider an optimal solution $(x, \tilde{x})$ of ($P''$). Set $A$ is $\mathcal{X}$-antidominant, thus $\tilde{x} \in A$. Suppose that $c\tilde{x} > cx$. Then solution $(x, x)$ is feasible for ($P''$) and would have higher value than $(x, \tilde{x})$, which is a contradiction. Therefore $c\tilde{x} \le cx$. Solution $(\tilde{x}, \tilde{x})$ is feasible for ($P'_{in}$) and has value $c\tilde{x} \le (1-\alpha)cx + \alpha c\tilde{x}$. $\quad \blacksquare$

As stated in Remark 1, condition of Property 3 holds in particularly structured problems, for example when $A$ contains knapsack constraints and $B$ covering constraints. In many other cases, including the applications presented in this article, such a condition will not hold, preventing us from directly using the combined formulation ($P''$) for the master problem.

## A solution: guidance by dynamic cost balancing (DCB)

We can nevertheless make use of both techniques thanks to the observation that cost balancing serves only to orient the pricing subproblems, whereas the splitting inequality intervenes only in the master problem. This leads us to want to formulate the master problem with the splitting inequality but no cost balancing, while still applying this cost balancing in the pricing subproblems.

However, in column generation, we can guarantee convergence only if the primal costs of the master problem and the pricing subproblems coincide.

Consequently, the proposed guidance approach will use the splitting inequality in the master problem and start column generation with pricing subproblems featuring cost balancing. Then it will terminate column generation with no cost balancing so that the cost seen in the pricing subproblems match exactly those in the master problem. This allows us to benefit from the acceleration of convergence provided by cost balancing, while guaranteeing proper termination of the column generation.

At each iteration $k$ of the column generation procedure, we thus consider a restricted master problem of the following form:

$$ (P_k'') : \left\{ \begin{array}{ll} \min & (1 - \alpha_k)cx + \alpha_k c\tilde{x} \\ \text{s.t.} & x \in A_k \\ & \tilde{x} \in B_k \\ & x \ge \tilde{x} \end{array} \right. $$

where $\alpha_k$ is an iteration-dependent cost-balancing parameter, and $A_k, B_k$ are the convex hulls of columns previously generated respectively from sets $A$ and $B$. Associated subproblems are ($PP_{\alpha_k}^A$) and ($PP_{\alpha_k}^B$). The idea of dynamic cost balancing (DCB) is to choose a relevant sequence of $(\alpha_k)$ to accelerate convergence, while the optimal value obtained at convergence remains equal to that of ($P'$). To ensure such a behavior, sequence $(\alpha_k)$ must be decreasing, and the classical stopping criterion used for the column generation procedure should be slightly adapted.

The DCB stopping criterion for the column generation procedure can be stated as follows.

**$\triangleright$ Definition 3 (DCB stopping criterion).** Column generation stops at iteration $k$ if the reduced cost is non-negative and if $\alpha_k = 0$.

**$\triangleright$ Definition 4 (Admissible DCB parameter).** A sequence of cost-balancing parameters $(\alpha_k)$ is said to be *admissible* if it satisfies the following conditions:

- It reaches 0 in a finite number of iterations.

- Once it reaches 0, it remains at 0.
▷ Property 4. The column generation algorithm with restricted master ($P_k''$) converges to the optimal value of ($DC$) if the DCB stopping criterion is used and if sequence ($\alpha_k$) is admissible.

**Proof.** While $\alpha_k \neq 0$, the procedure does not stop. Once sequence ($\alpha_k$) reaches 0 (which it does by definition), it remains at 0. Thus at this point the procedure corresponds to a classical column generation on master problem ($DC$), thus converging to ($DC$) optimal value. ◀

Algorithm 1 provides a pseudo-code description of the corresponding procedure.

In practice, we choose a sequence of parameters ($\alpha_k$) decreasing according to different profiles (exponential, piecewise linear, ...). Also, if at iteration $k$, the reduced cost is non-negative with a nonzero $\alpha_k$, then $\alpha_{k+1} = 0$ at the next iteration. We will provide further detail on this technique in the experimental section (Section 5).

<table><caption>**Algorithm 1:** Column generation in double decomposition with guidance by cost-balancing</caption><thead><tr><th></th><th></th></tr></thead><tbody><tr><td>Inputs</td><td>: Initial restricted master problem RMP, pricing problems PP<sup>A</sup> and PP<sup>B</sup></td></tr><tr><td>Outputs</td><td>: Relaxation value</td></tr><tr><td>1</td><td>initialize restricted master problem with the splitting inequality</td></tr><tr><td>2</td><td>α &larr; 0.5</td></tr><tr><td>3</td><td>red.cost<sup>A</sup> &larr; 0</td><td>//reduced costs associated with each pricing problem</td></tr><tr><td>4</td><td>red.cost<sup>B</sup> &larr; 0</td><td></td></tr><tr><td></td><td><b>First phase</b> : Column generation guided by cost balancing</td></tr><tr><td>5</td><td>while α &gt; 0 do</td></tr><tr><td>6</td><td>solve restricted master RMP, then solve pricing problems PP<sup>A</sup> and PP<sup>B</sup></td></tr><tr><td>7</td><td>extract optimal solutions and assign their values to red.cost<sup>A</sup> and red.cost<sup>B</sup></td></tr><tr><td>8</td><td><b>if</b> red.cost<sup>A</sup> &lt; 0 <b>then</b></td></tr><tr><td>9</td><td>&nbsp;&nbsp;&nbsp;&nbsp;calculate reduced cost of the solution without cost balancing red.cost<sup>A</sup><sub>α=0</sub></td></tr><tr><td>10</td><td>&nbsp;&nbsp;&nbsp;&nbsp;<b>if</b> red.cost<sup>A</sup><sub>α=0</sub> &lt; 0 <b>then</b></td></tr><tr><td>11</td><td>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;add the solution as a new column to RMP</td></tr><tr><td>12</td><td>&nbsp;&nbsp;&nbsp;&nbsp;<b>else</b></td></tr><tr><td>13</td><td>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<b>//prevent generating new columns not truly of strictly negative reduced cost</b></td></tr><tr><td>14</td><td>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;α &larr; 0</td></tr><tr><td>15</td><td><b>end</b></td></tr><tr><td>16</td><td><b>end</b></td></tr><tr><td>17</td><td>repeat the above procedure (lines 9-16) for pricing problem B</td></tr><tr><td>18</td><td><b>if</b> red.cost<sup>A</sup> + red.cost<sup>B</sup> &lt; 0 <b>then</b></td></tr><tr><td>19</td><td>&nbsp;&nbsp;&nbsp;&nbsp;decrease α slightly according to the chosen profile</td></tr><tr><td>20</td><td><b>else</b></td></tr><tr><td>21</td><td>&nbsp;&nbsp;&nbsp;&nbsp;<b>//failed to generate new columns with cost balancing, so move to second phase</b></td></tr><tr><td>22</td><td><b>end</b></td></tr><tr><td>23</td><td><b>end</b></td></tr><tr><td></td><td><b>Second phase</b>: Column generation with splitting inequality only: we have reached α = 0, so we no longer have any cost balancing, and column generation proceeds in classical fashion</td></tr><tr><td>24</td><td><b>while</b> red.cost<sup>A</sup> + red.cost<sup>B</sup> &lt; 0 <b>do</b></td></tr><tr><td>25</td><td>&nbsp;&nbsp;&nbsp;&nbsp;solve restricted master RMP, then solve pricing problems PP<sup>A</sup> and PP<sup>B</sup></td></tr><tr><td>26</td><td>&nbsp;&nbsp;&nbsp;&nbsp;extract optimal solutions and assign their values to red.cost<sup>A</sup> and red.cost<sup>B</sup></td></tr><tr><td>27</td><td><b>end</b></td></tr><tr><td>28</td><td><b>return</b> optimal value of RMP</td></tr></tbody></table>

# 5 Application to the Unit Commitment Problem

The Unit Commitment Problem is an optimization problem relative to electricity production planning.
## 5.1 Problem description

In this problem, we consider a discrete time horizon $\mathcal{H} = \{1, ..., H\}$, with at each time step $t$ a given electrical power demand $D_t$ to be satisfied. There are $n$ available electrical production units, and the decision to be made consists in determining how much each unit must produce at each time step.

On top of these demand constraints, the production units must satisfy technical and operational constraints, which are very numerous in practice and include:

- Minimum consecutive time steps powered on and shut down (i.e., we cannot produce using a unit that was only just shut down, and conversely cannot shut down a unit that has only just been turned on). These constraints are usually known as min-up and min-down constraints. We denote for each unit $i$, $L^i$ the minimum up-time $\ell^i$ the minimum down-time $d$;

- Restrictions on the power produced by each unit: the power can be either restricted to a continuous span of possible power outputs when the unit is up, or to a finite number of values;

- Constraints specific to the nature of the unit (nuclear, hydraulic, thermal, etc.), some of which are non-linear. For the UCP, solution cost can be broken down into three components, for each unit $i$:

- a production cost proportional to power output, $c_p^i$;

- a fixed production cost $c_f^i$ (which applies as long as the power output is non-zero)

- a startup cost $c_0^i$, which is often non-linear (for example, for thermal and nuclear units, it is an increasing function on the time since last shutdown).

The non-linear constraints and costs in the UCP make it currently impossible to solve realistic instance size by a generic solver. However, utility companies such as EDF have developed dynamic programming algorithms which efficiently tackle these non-linearities for a single production unit. The current industrial solution method is based on a Lagrangian decomposition which creates an independent subproblem for each production unit [29], allowing the use of the aforementioned dynamic programming algorithms. Due to variable splitting, this Lagrangian decomposition also has a subproblem for each time step, in this case a pure linear relaxation. This method has two main limitations: maximizing the Lagrangian induces convergence issues, and the structure of the time step subproblems is not used to improve the relaxation value. Given these observations, here we seek to decompose the UCP using column generation and exploit the time step subproblems in order to obtain stronger bounds.

In order to provide a proof-of-concept for the UCP, we study a simplified problem which contains the combinatorial core of the UCP, known as the Min-up/min-down Unit Commitment Problem, or MUCP [31]. The MUCP is already itself strongly NP-hard [6]. It retains only demand constraints, production limits and min-up/min-down constraints. Its decision variables are, for each unit $i$ and each time step $t$:

- $x_{i,t}$, binary variable equal to 1 if unit $i$ is on (i.e., producing non-zero power) at time step $t$;

- $u_{i,t}$, binary variable equal to 1 if we turn on unit $i$ at time step $t$ (i.e., it was off at the previous time step);

- $p_{i,t}$, variable equal to the power output of unit $i$ at time step $t$.

We can now write the corresponding MILP:

(MUCP):

$$ \min \sum_{i \in \mathcal{N}} \sum_{t \in \mathcal{H}} c_i^f x_{i,t} + c_i^p p_{i,t} + c_i^0 u_{i,t} \quad (1) $$

$$ \text{s.t.} \quad \sum_{t'=t-L^i+1}^{t} u_{i,t'} \le x_{i,t} \quad \forall i \in \mathcal{N}, \forall t \in \{L^i, ..., H\} \quad (2) $$

$$ \sum_{t'=t-\ell^i+1}^{t} u_{i,t'} \le 1 - x_{i,t-\ell^i} \quad \forall i \in \mathcal{N}, \forall t \in \{\ell^i+1, ..., H\} \quad (3) $$

$$ u_{i,t} \ge x_{i,t} - x_{i,t-1} \quad \forall i \in \mathcal{N}, \forall t \in \mathcal{H} \quad (4) $$

$$ P_i^{\min} x_{i,t} \le p_{i,t} \le P_i^{\max} x_{i,t} \quad \forall i \in \mathcal{N}, \forall t \in \mathcal{H} \quad (5) $$

$$ \sum_{i \in \mathcal{N}} p_{i,t} \ge D_t \quad \forall t \in \mathcal{H} \quad (6) $$

$$ x_{i,t}, u_{i,t} \in \{0,1\}, p_{i,t} \in \mathcal{P} \quad \forall i \in \mathcal{N}, \forall t \in \mathcal{H} \quad (7) $$
<figure><img src="image_7.png" /><figcaption>Figure 2 Relationship between decompositions on the UCP</figcaption></figure>

Constraint (2) and (3) are the min-up and min-down constraints. Constraint (4) is the startup constraint ensuring proper link between u and x variables, while constraint (5) ensures the link between x and p variables. Finally, (6) is the demand constraints.

Notably, the MUCP does not incorporate any of the non-linearities from the UCP, which makes it adapted to a theoretical study, with the possibility to extend the proof-of-concept to the “full” UCP at a later stage.

## 5.2 Crosswise decomposition

The key idea is to decompose simultaneously along each unit (with subproblems containing the min-up/min-down constraints) and along each time step (with subproblems containing the demand constraints and power output restrictions). Decomposition along each unit is in any case necessary. Indeed due to the large size of a UCP instance and the variety of its constraints, in particular the non-linear ones, no method is currently able to solve the industrial UCP without such a decomposition. Also decomposing along time steps is likely to improve relaxation value. Indeed, the subproblems induced by each time step will in general not have the integrity property. This is best understood by considering that demand constraints are essentially knapsack constraints. Figure 2 depicts the relationships between the different possible decompositions for the industrial UCP. The set of points satisfying demand constraints (resp. unit constraints) is denoted by $T$ (resp. $U$). The convex hull of integral points in $T$ (resp. $U$) is denoted by $conv^T$ (resp. $conv^U$). Point $x_C$ corresponds to the continuous non-linear relaxation, $x_U$ to the unit decomposition, and $x_{CD}$ to the proposed crosswise decomposition. Note that $x_T$ corresponds to the solution of the time step decomposition, where the master problem would be non-linear due to unit constraints, thus making it very difficult to solve.

In our crosswise decomposition, the splitting happens on the $x$ variables (which encode whether a unit is up or down), and we denote $\tilde{x}$ their copy in the time step subproblems. There is no splitting on $u$ or $p$ variables, because they appear only in the constraints of one of the subproblems, namely the unit or the time step subproblem. The resulting formulation is as follows:

Master problem:

$$ (MP): \left\{ \begin{array}{ll} \min & \sum_{i \in \mathcal{N}} \sum_{t \in \mathcal{H}} c_i^0 u_{it} + (1 - \alpha) c_i^f x_{it} + \sum_{t \in \mathcal{H}} \sum_{i \in \mathcal{N}} c_i^p p_{it} + \alpha c_i^f \tilde{x}_{it} \rho^\mu \\ \text{s.t.} & x_{it} = \tilde{x}_{it} \\ & (x_{i\bullet}, u_{i\bullet}) \in \text{conv}_i, (\tilde{x}_{\bullet t}, p_{\bullet t}) \in \text{conv}_t \end{array} \right. \quad \begin{array}{l} \forall (i,t) \in \mathcal{N} \times \mathcal{H} \quad (\gamma_{i,t}) \\ \forall i \in \mathcal{N}, \forall t \in \mathcal{H} \end{array} $$

where $conv_i$ and $conv_t$ denote the convex hulls of the points iteratively generated by the following two classes of pricing subproblems:

Production unit pricing subproblem:
$$ (PP_i): \left\{ \begin{array}{ll} \min & -\sigma_i + \sum_{t \in \mathcal{H}} ((1-\alpha)c_i^f - \gamma_{i,t})x_{it} + c_i^0 u_{it}) \\ \text{s.t.} & \sum_{t'=t-L^i+1}^{t} u_{it'} \le x_{it} & \forall t \in \{L^i, \dots, H\} \\ & \sum_{t'=t-\ell^i+1}^{t} u_{it'} \le 1 - x_{i,t-\ell^i} & \forall t \in \{\ell^i+1, \dots, H\} \\ & u_{it} \ge x_{it} - x_{i,t-1} & \forall t \in \mathcal{H} \\ & x_{it}, u_{it} \in \{0,1\} & \forall t \in \mathcal{H} \end{array} \right. $$

Time step pricing subproblem:

$$ (PP_t): \left\{ \begin{array}{ll} \min & -\sigma_t + \sum_{i \in \mathcal{N}} (\gamma_{i,t}\tilde{x}_{it} + \alpha c_i^f \tilde{x}_{it} + c_i^p p_{it}) \\ \text{s.t.} & \sum_{i \in \mathcal{N}} p_i \ge D_t \\ & P_i^{min} \tilde{x}_{it} \le p_{it} \le P_i^{max} \tilde{x}_{it} & \forall i \in \mathcal{N} \\ & \tilde{x}_{it} \in \{0,1\}, \quad p_{it} \in \mathcal{P} & \forall i \in \mathcal{N} \end{array} \right. $$

where $\alpha$ is a parameter which allows the implementation of the cost balancing technique described in Section 4.1.

Examining the time step subproblems leads to the idea of replacing the variable splitting equality $x = \tilde{x}$ in (MP) by inequality $x \ge \tilde{x}$, as explained in Section 4.2. Indeed, turning on additional units could only increase total power production, and therefore demand constraints remain verified : the condition to apply Corollary 1 is satisfied. However, when combining this with the cost balancing there is a catch, as described in Section 4.3. For the relaxation value not to decrease, turning on additional units needs to incur no extra primal cost in the time step subproblems, i.e., $\alpha c_i^f + c_i^p P_i^{min} \le 0$. Otherwise, during dips in demand solution $x$ (from the unit subproblems) could have units maintained up, while solution $\tilde{x}$ (from the time step subproblems) could have the latter units down. In the first case, it would prevent an extra cost to restart the units, while in the second, it would prevent a part of the production costs associated with the units up. It is possible to set a value $\alpha < 0$ such that the aforementioned inequality is satisfied, but this means not balancing the costs between subproblems.

We will therefore apply Algorithm 1 to combine the two elements, namely splitting inequality in the master problem and cost balancing between the two classes of subproblems. In this way, it is possible to both guarantee proper column generation termination and preserve the relaxation value.

## 5.3 Experimental setup and instances

To evaluate in terms of performance the crosswise decomposition and the techniques presented in Section 4, we applied the crosswise decomposition with column generation to the MUCP with the formulations defined in Section 5.2. For the implementation we used the SCIP framework. Within the SCIP framework, to solve the restricted master problem at each iteration we employed CPLEX, a widely used commercial solver for linear programs. No classical stabilization techniques were used other than those implemented by the default configuration of SCIP. We solve the pricing subproblems for each time step and unit by dynamic programming. We also used CPLEX in its mixed-integer programming mode to provide a state-of-the-art compact MILP benchmark to which we compared the relaxation values obtained by our decompositions. The versions used are SCIP 8.0.0 and CPLEX 12.8. All experiments were conducted on a PC equipped with an Intel Core i7 3.4 GHz processor, with 16 GB of RAM.

The experiments were conducted on MUCP instances with discrete power output levels from the work of Bendotti, Fouilhoux and Rottner [5]. We present column generation results on two sizes of instances : 20 production units and 48 time steps (i.e., 960 $x$ variables), and 20 production units and 96 time steps (i.e., 1920 $x$ variables). Note that the latter corresponds to a realistic size for an industrial application on a daily basis.

## 5.4 Experimental results

Table 1 compares the relaxation values obtained by four methods:
<table><caption>Table 1 Average lower bounds obtained by different methods</caption><thead><tr><th>Instance size</th><th>Method</th><th>Dual bound</th><th>CPU.</th></tr></thead><tbody><tr><td rowspan="4">20 units<br>48 time steps</td><td>Unit</td><td>608902.72</td><td>0.15</td></tr><tr><td>SCIP</td><td>609123.00</td><td>1.01</td></tr><tr><td>CPLEX</td><td>620196.39</td><td>1.47</td></tr><tr><td>CD</td><td>621105.88</td><td>60.70</td></tr><tr><td rowspan="4">20 units<br>96 time steps</td><td>Unit</td><td>3652917.95</td><td>0.52</td></tr><tr><td>SCIP</td><td>3654827.10</td><td>4.31</td></tr><tr><td>CPLEX</td><td>3738546.80</td><td>5.04</td></tr><tr><td>CD</td><td>3747280.15</td><td>387.09</td></tr></tbody></table>

- Unit: Dantzig-Wolfe decomposition along production units, which is one of the most classical solution methods for the UCP;

- SCIP: compact formulation (1) solved with default SCIP solver at the root (which automatically generates cuts using open-source methods), equipped with CPLEX as continuous linear program solver;

- CPLEX: compact formulation (1) solved with the default CPLEX solver at the root (which automatically generates cuts using proprietary methods);

- CD: vanilla crosswise decomposition (the most basic version without convergence acceleration).

In addition, we list the CPU times in seconds necessary to obtain these four relaxation values. Note that all values presented in this section are averages over 20 instances for each size, see Section 6 for detailed individual results by instance.

We observe that unit decomposition provides the weakest of the three relaxations, while crosswise decomposition provides the strongest. Lower bound value comes at a cost in computation time, with an order of magnitude between each method. Recall that the non-linearities present in the industrial UCP make a compact MIP approach impractical.

In order to benefit from the good dual bounds of crosswise decomposition with less computational effort, we now assess the effectiveness of the acceleration techniques presented in Section 4. To this aim, we combine crosswise decomposition with different acceleration techniques, leading to six solution methods detailed hereafter. Here CD will denote the vanilla crosswise decomposition, i.e., without cost balancing and with a splitting equality. We add cost balancing in $CD_\alpha$ and the splitting inequality in $CD^\leq$. Finally, we combine these two techniques using Algorithm 1, and test three possible ways to have the balancing parameter $\alpha$ change over iterations: $CD^\leq_{\alpha,step}$ maintains full cost balancing in the pricing (i.e., $\alpha = 1$) until this no longer results in columns of negative reduced cost; in $CD^\leq_{\alpha,exp}$, parameter $\alpha$ decreases exponentially; and in $CD^\leq_{\alpha,p,l}$ it follows a piecewise-linear function (full cost balancing for some iterations, then a linear decrease until zero cost balancing is reached). The rate of decay for the cost balancing parameter was fixed by preliminary experiments. To give a numerical idea of the chosen rate, the parameter reaches half of its starting value after $2\sqrt{nT}$ iterations in both $CD^\leq_{\alpha,exp}$ and $CD^\leq_{\alpha,p,l}$.

In order to analyze the dynamic behaviour of column generation, it is interesting to track the evolution of two values, as we do in Figure 3:

- the current dual value of the restricted master problem, in orange in Figure 3, which, after convergence, provides the relaxation value;

- the dynamic lower bound presented in Section 3, in blue in Figure 3, which is a valid lower bound at any iteration. Note that when we combine cost balancing and splitting inequality, the dynamic lower bound is not defined, which explains why the value is zero as long as the cost balancing parameter is non-zero.

For readability purposes, the plots in Figure 3 are for a single representative instance with 20 production units and 48 time steps. However, all instances in our test set follow the same overall pattern in behavior.

In Figure 3a, for the vanilla crosswise decomposition, we observe a rather stable convergence in the sense that the lower bound is monotone non-decreasing, which is desirable in column generation. The current value of the restricted master problem decreases continuously after a plateau at the start, leveling out as we approach convergence. In Figure 3b we can see a very interesting phenomenon of “double convergence” : the dual value levels off a first time, then decreases more noticeably again before converging. The inflection point corresponds to the moment when cost balancing stops. This observation motivated the use of the $CD^\leq_{\alpha,exp}$ and $CD^\leq_{\alpha,p,l}$ methods, in order to decrease balancing more gradually. We can observe in Figure 3c and Figure 3d that these
<figure><img src="image_8.png" /><figcaption>Figure 3 Visualization of column generation convergence when using different methods</figcaption></figure>

techniques indeed successfully get rid of the “double convergence” phenomenon. The $CD_{\alpha,exp}^{<}$ method displays excellent convergence properties. However, as the cost balancing parameter never reaches exactly zero due to its exponential decrease, the dynamic lower bound is not defined until the very end of column generation. The $CD_{\alpha,p,l.}^{<}$ method, with the piecewise-linear decrease of the cost balancing parameter, is therefore more effective when using the dynamic lower bound.

Table 2 presents the average performance of these six methods. For each method, entries from left to right are as follows: $n_{cvg}^{inst}$ the number of instances for which column generation converged within the one hour time limit versus the set with 20 instances, Iter the number of iterations necessary, Cols U the number of columns generated in unit subproblems, Cols T the number of columns generated in time step subproblems, PrimalB the primal bound (i.e., the value of the best integer solution found), Gap the integrality gap (expressed as a proportion of the lower bound), CPU<sub>RMP</sub> computation time dedicated to solving the restricted master problem (in seconds), and CPU the total computation time (in seconds). Note that by Property 3 and Property 4, the relaxation value (lower bound) obtained by these six methods is always identical.

We observe that the vast majority of computation time is spent solving the restricted master problem, which illustrates how fast pricing becomes for the small independent subproblems created by crosswise decomposition. Moreover, possibly the most important driver of computation time is the number of columns generated, even more than the number of iterations. We see that cost balancing significantly reduces the number of generated columns. The splitting inequality brings a less noticeable improvement on this front, but greatly improves the primal bound and with it the integrality gap. $CD_{\alpha,step}^{<}$ and $CD_{\alpha,exp}^{<}$ perform well on most instances, but with high variability which leads to $CD_{\alpha,exp}^{<}$ not reaching convergence within one hour on one instance. $CD_{\alpha,p,l.}^{<}$ appears to implement the idea more reliably. It is the method with the lowest number of columns generated and computation time for both sets of instances, while retaining the strong primal bound enabled by the splitting inequality.
<table><caption>Table 2 Average performance of different crosswise decomposition methods</caption><thead><tr><th>Instance size</th><th>Method</th><th>n<sub>cvg</sub><sup>inst</sup>/20</th><th>Iter</th><th>Colts U</th><th>Colts T</th><th>PrimalB</th><th>Gap</th><th>CPU<sub>RMP</sub></th><th>CPU</th></tr></thead><tbody><tr><td rowspan="3">20 units</td><td>CD</td><td>20/20</td><td>207</td><td>2740</td><td>5574</td><td>1331374</td><td>1.15</td><td>59</td><td>60</td></tr><tr><td>CD<sub>α</sub></td><td>20/20</td><td>192</td><td>1951</td><td>4833</td><td>1331374</td><td>1.15</td><td>36</td><td>36</td></tr><tr><td>CD<sup>≤</sup></td><td>20/20</td><td>263</td><td>2481</td><td>4842</td><td>724871</td><td>0.17</td><td>44</td><td>45</td></tr><tr><td rowspan="3">48 time steps</td><td>CD<sup>≤</sup><sub>α,step</sub></td><td>20/20</td><td>864</td><td>2125</td><td>4499</td><td>699005</td><td>0.12</td><td>55</td><td>58</td></tr><tr><td>CD<sup>≤</sup><sub>α,exp</sub></td><td>20/20</td><td>391</td><td>1815</td><td>3515</td><td>702056</td><td>0.13</td><td>26</td><td>28</td></tr><tr><td>CD<sup>≤</sup><sub>α,p-l</sub></td><td>20/20</td><td>483</td><td>1924</td><td>3464</td><td>691541</td><td>0.11</td><td>31</td><td>33</td></tr><tr><td rowspan="3">20 units</td><td>CD</td><td>20/20</td><td>566</td><td>3683</td><td>13271</td><td>9275340</td><td>1.48</td><td>375</td><td>387</td></tr><tr><td>CD<sub>α</sub></td><td>20/20</td><td>325</td><td>2765</td><td>11418</td><td>9275340</td><td>1.48</td><td>194</td><td>201</td></tr><tr><td>CD<sup>≤</sup></td><td>20/20</td><td>830</td><td>3828</td><td>12301</td><td>5168414</td><td>0.37</td><td>365</td><td>382</td></tr><tr><td rowspan="3">96 time steps</td><td>CD<sup>≤</sup><sub>α,step</sub></td><td>20/20</td><td>2777</td><td>3265</td><td>11681</td><td>4842886</td><td>0.28</td><td>618</td><td>676</td></tr><tr><td>CD<sup>≤</sup><sub>α,exp</sub></td><td>19/20</td><td>2203</td><td>2706</td><td>9871</td><td>5371701</td><td>0.41</td><td>415</td><td>462</td></tr><tr><td>CD<sup>≤</sup><sub>α,p-l</sub></td><td>20/20</td><td>808</td><td>2705</td><td>7178</td><td>5106732</td><td>0.35</td><td>171</td><td>189</td></tr></tbody></table>

# 6 Conclusion

This work proposed an in-depth study of the method we call crosswise decomposition. We detailed the conditions conducive to its application and confirmed experimentally the gain in relaxation value it can bring. We presented several techniques relative to efficient implementation of crosswise decomposition. These aim to accelerate the convergence of the corresponding column generation while preserving the quality of the dual bound and improving the quality of the primal bound. We were able to prove the practical impact of these methods on computation time.

A promising perspective would be to improve the rate of convergence of the crosswise decomposition at non-root nodes. Indeed, we fine-tuned the balancing of costs between subproblems for column generation at the root node, but observed that this parameterization was not the most effective lower in the tree. This observation could warrant the use of larger-scale experiments incorporating statistical analysis in order to find the ideal meta-parameters for column generation at non-root nodes. This would allow us to benefit from the improved bounds within a Branch&Price framework.

We cited several applications on which column generation with variable splitting has been attempted before with moderate success; it would be interesting to revisit them in light of the new set of tools introduced in this work. Another promising perspective is to apply the crosswise decomposition framework to other problems with complex structures which classical column generation methods struggle to solve.

# References

1. Badr Afify, Sujoy Ray, Andrei Soeanu, Anjali Awasthi, Mourad Debbabi, and Mohamad Allouche. Evolutionary learning algorithm for reliable facility location under disruption. *Expert Systems With Applications*, 2019.

2. Yu An, Bo Zeng, Yu Zhang, and Long Zhao. Reliable p-median facility location problem: two-stage robust models and algorithms. *Transportation Research Part B*, 2014.

3. Nezir Aydin and Alper Murat. A swarm intelligence based sample average approximation algorithm for the capacitated reliable facility location problem. *Int. J. Production Economics*, 2013.

4. Cynthia Barnhart, Ellis L. Johnson, George L. Nemhauser, Martin W. P. Savelsbergh, and Pamela H. Vance. Branch-and-price: Column generation for solving huge integer programs. *Operations Research*, pages 316–329, 1998.

5. Pascale Bendotti, Pierre Fouilhoux, and Cécile Rottner. The min-up/min-down unit commitment polytope. *Journal of Combinatorial Optimization*, 36:1024–1058, 2018.

6. Pascale Bendotti, Pierre Fouilhoux, and Cécile Rottner. On the complexity of the Unit Commitment Problem. *Annals of Operations Research*, 274(1-2):119–130, March 2019.

7. Martin Bergner, Alberto Caprara, Alberto Ceselli, Fabio Furini, Marco E. Lübbecke, Enrico Malaguti, and Emiliano Traversi. Automatic dantzig-wolfe reformulation of mixed integer programs. *Mathematical Programming*, 149(1-2):391–424, 2014.

8. G. B. Dantzig and Philip Wolfe. Decomposition principle for linear programs. *Operations Research*, 8(1):101–111, 1960.
9

Guy Desaulniers, Marius M. Solomon, Jacques Desrosiers, and Francois Vanderbeck. Column generation. 2003.

10

Arthur M. Geoffrion. Lagrangian relaxation for integer programming. In *50 Years of Integer Programming 1958-2008* - *From the Early Years to the State-of-the-Art*, pages 243–281. Springer, 2010.

11

Bissan Ghaddar, Joe Naoum-Sawaya, Akihiro Kishimoto, Nicole Taheri, and Bradley Eck. A lagrangian decomposition approach for the pump scheduling problem in water networks. *European Journal of Operational Research*, 241(2):490–501, 2015.

12

Gianfranco Guastaroba and Maria Grazia Speranza. A heuristic for bilp problems: The single source capacitated facility location problem. *European Journal of Operational Research*, 238(2):438–450, 2014.

13

Monique Guignard and Siwhan Kim. Lagrangean decomposition for integer programming: theory and applications. *RAIRO-Operations Research*, 21(4):307–323, 1987.

14

Dorit S. Hochbaum. Heuristics for the fixed cost median problem. *Mathematical Programming*, 22:148–162, 1982.

15

Kurt Jornsten and Mikael Nasberg. A new lagrangian relaxation approach to the generalized assignment problem. *European Journal of Operational Research*, 27(3):313–323, 1986.

16

Taghi Khaniyev, Samir Elhedhli, and Fatih Safa Erenay. Structure detection in mixed-integer programs. *INFORMS Journal on Computing*, 30(3):570–587, 2018.

17

Deokseong Kim, Kyungsik Lee, Kyungchul Park, and Sungsoo Park. An integer programming approach to the path selection problems. *International Network Planning Symposium*, 2003.

18

Yu-Ching Lee, Yu-Shih Chen, and Albert Y. Chen. Lagrangian dual decomposition for the ambulance relocation and routing considering stochastic demand with the truncated poisson. *Transportation Research Part B: Methodological*, 157:1–23, 2022.

19

Lucas Létocart, Anass Nagih, and Nora Touati Moungla. Dantzig-wolfe and lagrangian decompositions in integer linear programming. *Int. J. Math. Oper. Res.*, 4(3):247–262, 2012.

20

Xiaohan Lu and Chun Cheng. Locating facilities with resiliency to capacity failures and correlated demand uncertainty. *Transportation Research Part E*, 2021.

21

Pat Malkin. Minimum runtime and stoptime polyhedra. In *Private Communication*, pages 1.5, 1.2.5. 2003.

22

Jakub Marecek. Exploiting structure in integer programs, 2011.

23

Sebastien Martin, Pierre Bauguion, Youcef Magnouche, and Jérémie Leguay. Atomic column generation for consensus between algorithms: Application to path computation. *Networks*.

24

Anuj Mehrotra and Michael A. Trick. A column generation approach for graph coloring. *INFORMS J. Comput.*, 8:344–354, 1996.

25

Guignard Monique. Lagrangean relaxation. *TOP*, 11(3):151–200, December 2003.

26

Huimin Niu, Xuesong Zhou, and Xiaopeng Tian. Coordinating assignment and routing decisions in transit vehicle schedules: A variable-splitting lagrangian decomposition approach for solution symmetry breaking. *Transportation Research Part B: Methodological*, 107:70–101, 2018.

27

Carina Maria Oliveira Pimentel, Filipe Pereira Alvelos, and José Manuel Valério de Carvalho. Comparing dantzig-wolfe decompositions and branch-and-price algorithms for the multi-item capacitated lot sizing problem. *Optim. Methods Softw.*, 25(2):299–319, 2010.

28

Deepak Rajan and Samer Takriti. Minimum up/down polytopes of the unit commitment problem with start-up costs. *IBM Research Report*, 2005.

29

Arnaud Renaud. Daily generation management at electricite de france: from planning towards real time. *IEEE Transactions on Automatic Control*, 38(7):1080–1093, 1993.

30

Mohammad Rohaninejada, Rashed Sahraeiana, and Reza Tavakkoli-Moghaddam. An accelerated benders decomposition algorithm for reliable facility location problems in multi-echelon networks. *Computers & Industrial Engineering*, 2018.

31

Cécile Rottner. Combinatorial aspects of the unit commitment problem, 2018. PhD thesis.

32

David. M. Ryan and Byron. A. Foster. An integer programming approach to scheduling. In *Computer scheduling of public transport : Urban passenger vehicle and crew scheduling*, pages 269–280. A. Wren (ed.), North Holland Publishing Company, 1981.

33

Jaehyeon Ryu and Sungsoo Park. A branch-and-price algorithm for the robust single-source capacitated facility location problem under demand uncertainty. *EURO Journal on Transportation and Logistics*, 2022.

34

Ahmed Saif and Erick Delage. Data-driven distributionally robust capacitated facility location problem. *European Journal of Operational Research*, 2021.

35

Jose A. Santivanez and Hector J. Carlo. Reliable capacitated facility location problem with service levels. *EURO Journal on Transportation and Logistics*, 2018.

36

Karmel S. Shehadeh and Ece Sanci. Distributionally robust facility location with bimodal random demand. *Computers Operations Research*, 2021.

37

Kavinesh J. Singh, Andy B. Philpott, and R. Kevin Wood. Dantzig-wolfe decomposition for solving multistage stochastic capacity-planning problems. *Operations Research*, 57(5):1271–1286, 2009.

38

Wim van Ackooij, Claudia D'Ambrosio, Dimitri Thomopulos, and Renan Spencer Trindade. Decomposition and
shortest path problem formulation for solving the hydro unit commitment and scheduling in a hydro valley. *European Journal of Operational Research*, 291(3):935-943, 2021.

39 François Vanderbeck. Decomposition and column generation for integer programs, 1994, PhD thesis.

40 François Vanderbeck and Laurence A Wolsey. Reformulation and decomposition of integer programs. In *50 Years of Integer Programming 1958-2008*, pages 431-502. Springer, 2010.

41 A. Volgenant. A note on splitting of variables in integer programming models. *European Journal of Operational Research*, 122(1):166-172, 2000.

42 Guodong Yua, William B.Haskell, and Yang Liu. Resilient facility location against the risk of disruptions. *Transportation Research Part B*, 2017.

43 Yixin Zhao, Torbjörn Larsson, Elina Rönnberg, and Panos M. Pardalos. The fixed charge transportation problem: a strong formulation based on lagrangian decomposition and column generation. *J. Glob. Optim.*, 72(3):517-538, 2018.
# Appendix

In Table 3 to Table 6 entries from left to right are as follows:

- Method: specific variant of crosswise decomposition used;

- id: instance identifier;

- Iter: number of iterations necessary;

- Var: total number of columns generated;

- cols U: number of columns generated in unit subproblems;

- cols T: number of columns generated in time step subproblems;

- CPU: total computation time (in seconds);

- CPU<sub>RMP</sub>: the computation time dedicated to solving the restricted master problem;

- Gap: integrality gap;

- DualB: dual bound;

- PrimalB: primal bound;

- LR: value of the linear relaxation;

- CPU<sub>LR</sub>: computation time for the linear relaxation;

- R0<sub>Cpx</sub>: root node relaxation value found by CPLEX;

- CPU<sub>R0<sub>Cpx</sub></sub>: root node computation time.
<table><caption>Table 3 Performance of different crosswise decomposition methods on instances with 20 production units and 48 time steps, instances 1 to 10</caption><thead><tr><th>Method</th><th>id</th><th>Iter</th><th>Var</th><th>cols U</th><th>cols T</th><th>CPU</th><th>CPU<sub>RMP</sub></th><th>Gap</th><th>DualB</th><th>PrimalB</th><th>LR</th><th>CPU<sub>LR</sub></th><th>R0<sub>Cpx</sub></th><th>CPU<sub>R0Cpx</sub></th></tr></thead><tbody><tr><td>CD</td><td>1</td><td>182</td><td>8226</td><td>2849</td><td>5309</td><td>61.16964</td><td>60.26397</td><td>1.087019</td><td>670940.8</td><td>1400266</td><td>656370.1</td><td>0.040789</td><td>670139.9</td><td>1.821062</td></tr><tr><td>CD<sub>α</sub></td><td>1</td><td>126</td><td>6446</td><td>1930</td><td>4448</td><td>30.36366</td><td>29.72613</td><td>1.087019</td><td>670940.8</td><td>1400266</td><td>656370.1</td><td>0.040665</td><td>670139.9</td><td>1.855682</td></tr><tr><td>CD<sup>≤</sup></td><td>1</td><td>189</td><td>7106</td><td>2459</td><td>4579</td><td>44.98589</td><td>44.08695</td><td>0.1510564</td><td>670940.8</td><td>772290.7</td><td>656370.1</td><td>0.040169</td><td>670139.9</td><td>1.856148</td></tr><tr><td>CD<sup>≤</sup><sub>α,step</sub></td><td>1</td><td>421</td><td>5685</td><td>2151</td><td>3466</td><td>38.85115</td><td>37.06632</td><td>0.1415388</td><td>670940.8</td><td>765905</td><td>656370.1</td><td>0.060094</td><td>670139.9</td><td>1.837339</td></tr><tr><td>CD<sup>≤</sup><sub>α,exp</sub></td><td>1</td><td>130</td><td>4922</td><td>1817</td><td>3037</td><td>17.67167</td><td>16.92618</td><td>0.1630822</td><td>670940.8</td><td>780359.4</td><td>656370.1</td><td>0.040551</td><td>670139.9</td><td>1.862503</td></tr><tr><td>CD<sup>≤</sup><sub>α,p.l.</sub></td><td>1</td><td>121</td><td>4997</td><td>1952</td><td>2977</td><td>19.01114</td><td>18.34559</td><td>0.1500082</td><td>670940.8</td><td>771587.5</td><td>656370.1</td><td>0.040701</td><td>670139.9</td><td>1.853505</td></tr><tr><td>CD</td><td>2</td><td>213</td><td>7967</td><td>2659</td><td>5240</td><td>60.27075</td><td>59.2263</td><td>1.057808</td><td>668217.4</td><td>1375063</td><td>656409.3</td><td>0.047693</td><td>666389.8</td><td>1.526157</td></tr><tr><td>CD<sub>α</sub></td><td>2</td><td>161</td><td>6367</td><td>1832</td><td>4467</td><td>33.49951</td><td>32.70748</td><td>1.057808</td><td>668217.4</td><td>1375063</td><td>656409.3</td><td>0.05268</td><td>666389.8</td><td>1.582556</td></tr><tr><td>CD<sup>≤</sup></td><td>2</td><td>187</td><td>7139</td><td>2408</td><td>4663</td><td>45.55288</td><td>44.60941</td><td>0.2247927</td><td>668217.4</td><td>818427.7</td><td>656409.3</td><td>0.049064</td><td>666389.8</td><td>1.577305</td></tr><tr><td>CD<sup>≤</sup><sub>α,step</sub></td><td>2</td><td>176</td><td>5584</td><td>2064</td><td>3452</td><td>24.5882</td><td>23.6984</td><td>0.1426169</td><td>668217.4</td><td>763516.5</td><td>656409.3</td><td>0.049631</td><td>666389.8</td><td>1.503111</td></tr><tr><td>CD<sup>≤</sup><sub>α,exp</sub></td><td>2</td><td>119</td><td>4958</td><td>1764</td><td>3126</td><td>17.26378</td><td>16.5829</td><td>0.1470994</td><td>668217.4</td><td>766511.7</td><td>656409.3</td><td>0.049574</td><td>666389.8</td><td>1.525624</td></tr><tr><td>CD<sup>≤</sup><sub>α,p.l.</sub></td><td>2</td><td>132</td><td>5037</td><td>1916</td><td>3053</td><td>18.65587</td><td>17.9421</td><td>0.1769984</td><td>668217.4</td><td>786490.8</td><td>656409.3</td><td>0.051504</td><td>666389.8</td><td>1.520562</td></tr><tr><td>CD</td><td>3</td><td>263</td><td>8580</td><td>2722</td><td>5790</td><td>61.23508</td><td>59.85221</td><td>1.281777</td><td>516953.5</td><td>1179573</td><td>503744.9</td><td>0.048351</td><td>516554.8</td><td>1.031519</td></tr><tr><td>CD<sub>α</sub></td><td>3</td><td>231</td><td>7246</td><td>2000</td><td>5178</td><td>42.66601</td><td>41.52706</td><td>1.281777</td><td>516953.5</td><td>1179573</td><td>503744.9</td><td>0.047658</td><td>516554.8</td><td>1.037444</td></tr><tr><td>CD<sup>≤</sup></td><td>3</td><td>285</td><td>7424</td><td>2439</td><td>4917</td><td>39.59243</td><td>38.23882</td><td>0.09183916</td><td>516953.5</td><td>564430.1</td><td>503744.9</td><td>0.044843</td><td>516554.8</td><td>1.041939</td></tr><tr><td>CD<sup>≤</sup><sub>α,step</sub></td><td>3</td><td>218</td><td>5582</td><td>2016</td><td>3498</td><td>21.4494</td><td>20.34266</td><td>0.1094228</td><td>516953.5</td><td>573520</td><td>503744.9</td><td>0.054853</td><td>516554.8</td><td>1.082314</td></tr><tr><td>CD<sup>≤</sup><sub>α,exp</sub></td><td>3</td><td>414</td><td>5431</td><td>1827</td><td>3536</td><td>27.60127</td><td>25.52078</td><td>0.09209723</td><td>516953.5</td><td>564563.5</td><td>503744.9</td><td>0.045747</td><td>516554.8</td><td>1.043446</td></tr><tr><td>CD<sup>≤</sup><sub>α,p.l.</sub></td><td>3</td><td>392</td><td>5155</td><td>1863</td><td>3224</td><td>25.34369</td><td>23.47584</td><td>0.08806485</td><td>516953.5</td><td>562478.9</td><td>503744.9</td><td>0.045972</td><td>516554.8</td><td>1.073906</td></tr><tr><td>CD</td><td>4</td><td>153</td><td>8051</td><td>2621</td><td>5362</td><td>58.5CD<sub>α</sub></td><td>57.69478</td><td>1.104844</td><td>665131.6</td><td>1399998</td><td>652443.2</td><td>0.04735</td><td>664105.4</td><td>1.697668</td></tr><tr><td>CD<sub>α</sub></td><td>4</td><td>118</td><td>6531</td><td>1863</td><td>4600</td><td>31.2234</td><td>30.57977</td><td>1.104844</td><td>665131.6</td><td>1399998</td><td>652443.2</td><td>0.048514</td><td>664105.4</td><td>1.728164</td></tr><tr><td>CD<sup>≤</sup></td><td>4</td><td>139</td><td>7066</td><td>2424</td><td>4574</td><td>40.5292</td><td>39.7757</td><td>0.1393816</td><td>665131.6</td><td>757838.7</td><td>652443.2</td><td>0.046266</td><td>664105.4</td><td>1.695781</td></tr><tr><td>CD<sup>≤</sup><sub>α,step</sub></td><td>4</td><td>135</td><td>5580</td><td>2075</td><td>3437</td><td>23.38146</td><td>22.64981</td><td>0.1081813</td><td>665131.6</td><td>737086.3</td><td>652443.2</td><td>0.049582</td><td>664105.4</td><td>1.683441</td></tr><tr><td>CD<sup>≤</sup><sub>α,exp</sub></td><td>4</td><td>265</td><td>5292</td><td>1800</td><td>3424</td><td>26.3069</td><td>24.99763</td><td>0.1446087</td><td>665131.6</td><td>761315.3</td><td>652443.2</td><td>0.047088</td><td>664105.4</td><td>1.663407</td></tr><tr><td>CD<sup>≤</sup><sub>α,p.l.</sub></td><td>4</td><td>135</td><td>5246</td><td>1915</td><td>3263</td><td>21.64004</td><td>20.90305</td><td>0.08041977</td><td>665131.6</td><td>718621.3</td><td>652443.2</td><td>0.046909</td><td>664105.4</td><td>1.663296</td></tr><tr><td>CD</td><td>5</td><td>190</td><td>8392</td><td>2827</td><td>5497</td><td>63.06996</td><td>62.1793</td><td>0.99781</td><td>698809.5</td><td>1396089</td><td>687042.8</td><td>0.040024</td><td>697769.1</td><td>1.5202</td></tr><tr><td>CD<sub>α</sub></td><td>5</td><td>151</td><td>7013</td><td>2077</td><td>4868</td><td>37.02546</td><td>36.30423</td><td>0.99781</td><td>698809.5</td><td>1396089</td><td>687042.8</td><td>0.040879</td><td>697769.1</td><td>1.491195</td></tr><tr><td>CD<sup>≤</sup></td><td>5</td><td>309</td><td>7779</td><td>2606</td><td>5105</td><td>52.78635</td><td>51.48658</td><td>0.1148053</td><td>698809.5</td><td>779036.5</td><td>687042.8</td><td>0.041503</td><td>697769.1</td><td>1.500389</td></tr><tr><td>CD<sup>≤</sup><sub>α,step</sub></td><td>5</td><td>402</td><td>6497</td><td>2442</td><td>3987</td><td>40.98545</td><td>39.3169</td><td>0.2041044</td><td>698809.5</td><td>841439.6</td><td>687042.8</td><td>0.040745</td><td>697769.1</td><td>1.511006</td></tr><tr><td>CD<sup>≤</sup><sub>α,exp</sub></td><td>5</td><td>474</td><td>5690</td><td>1889</td><td>3733</td><td>36.97531</td><td>34.79811</td><td>0.05348942</td><td>698809.5</td><td>736188.4</td><td>687042.8</td><td>0.041362</td><td>697769.1</td><td>1.521053</td></tr><tr><td>CD<sup>≤</sup><sub>α,p.l.</sub></td><td>5</td><td>168</td><td>5532</td><td>2108</td><td>3356</td><td>22.79806</td><td>21.98354</td><td>0.080009</td><td>698809.5</td><td>754720.5</td><td>687042.8</td><td>0.042261</td><td>697769.1</td><td>1.5243</td></tr><tr><td>CD</td><td>6</td><td>176</td><td>8352</td><td>2651</td><td>5633</td><td>56.80365</td><td>55.80342</td><td>1.342833</td><td>553409.6</td><td>1296546</td><td>542302.5</td><td>0.051208</td><td>552549</td><td>1.259398</td></tr><tr><td>CD<sub>α</sub></td><td>6</td><td>177</td><td>6898</td><td>1862</td><td>4968</td><td>35.20201</td><td>34.22323</td><td>1.342833</td><td>553409.6</td><td>1296546</td><td>542302.5</td><td>0.073557</td><td>552549</td><td>1.260585</td></tr><tr><td>CD<sup>≤</sup></td><td>6</td><td>350</td><td>7353</td><td>2417</td><td>4868</td><td>48.21</td><td>46.49611</td><td>0.1166258</td><td>553409.6</td><td>617951.4</td><td>542302.5</td><td>0.050869</td><td>552549</td><td>1.269614</td></tr><tr><td>CD<sup>≤</sup><sub>α,step</sub></td><td>6</td><td>379</td><td>6148</td><td>2087</td><td>3993</td><td>28.44318</td><td>26.60194</td><td>0.08721039</td><td>553409.6</td><td>601672.6</td><td>542302.5</td><td>0.054774</td><td>552549</td><td>1.274318</td></tr><tr><td>CD<sup>≤</sup><sub>α,exp</sub></td><td>6</td><td>132</td><td>4897</td><td>1754</td><td>3075</td><td>13.70195</td><td>12.88667</td><td>0.1082244</td><td>553409.6</td><td>613302</td><td>542302.5</td><td>0.051183</td><td>552549</td><td>1.273243</td></tr><tr><td>CD<sup>≤</sup><sub>α,p.l.</sub></td><td>6</td><td>137</td><td>4874</td><td>1805</td><td>CD<sub>α</sub></td><td>14.32397</td><td>13.46512</td><td>0.1210535</td><td>553409.6</td><td>620401.7</td><td>542302.5</td><td>0.050805</td><td>552549</td><td>1.292591</td></tr><tr><td>CD</td><td>7</td><td>166</td><td>8010</td><td>2594</td><td>5348</td><td>52.97672</td><td>52.12459</td><td>1.027257</td><td>642197.1</td><td>1301898</td><td>632669.9</td><td>0.045856</td><td>641325.6</td><td>1.431231</td></tr><tr><td>CD<sub>α</sub></td><td>7</td><td>135</td><td>6534</td><td>1865</td><td>4601</td><td>31.6087</td><td>30.92135</td><td>1.027257</td><td>642197.1</td><td>1301898</td><td>632669.9</td><td>0.044993</td><td>641325.6</td><td>1.458143</td></tr><tr><td>CD<sup>≤</sup></td><td>7</td><td>150</td><td>7109</td><td>2443</td><td>4598</td><td>40.95955</td><td>40.18537</td><td>0.1332492</td><td>642197.1</td><td>727769.3</td><td>632669.9</td><td>0.046436</td><td>641325.6</td><td>1.45833</td></tr><tr><td>CD<sup>≤</sup><sub>α,step</sub></td><td>7</td><td>450</td><td>5970</td><td>2062</td><td>3840</td><td>39.18898</td><td>36.91173</td><td>0.1132831</td><td>642197.1</td><td>714947.1</td><td>632669.9</td><td>0.047661</td><td>641325.6</td><td>1.466183</td></tr><tr><td>CD<sup>≤</sup><sub>α,exp</sub></td><td>7</td><td>145</td><td>5147</td><td>1804</td><td>3275</td><td>18.82922</td><td>17.87826</td><td>0.1477565</td><td>642197.1</td><td>737085.9</td><td>632669.9</td><td>0.051289</td><td>641325.6</td><td>1.509463</td></tr><tr><td>CD<sup>≤</sup><sub>α,p.l.</sub></td><td>7</td><td>216</td><td>5182</td><td>1868</td><td>3246</td><td>24.41903</td><td>23.35052</td><td>0.1030589</td><td>642197.1</td><td>708381.2</td><td>632669.9</td><td>0.046823</td><td>641325.6</td><td>1.454287</td></tr><tr><td>CD</td><td>8</td><td>223</td><td>8971</td><td>2995</td><td>5908</td><td>66.27022</td><td>65.12333</td><td>1.192775</td><td>642386.8</td><td>1408609</td><td>629820.6</td><td>0.044619</td><td>641501.5</td><td>1.390416</td></tr><tr><td>CD<sub>α</sub></td><td>8</td><td>176</td><td>7217</td><td>2132</td><td>5017</td><td>37.79095</td><td>36.88573</td><td>1.192775</td><td>642386.8</td><td>1408609</td><td>629820.6</td><td>0.044312</td><td>641501.5</td><td>1.387249</td></tr><tr><td>CD<sup>≤</sup></td><td>8</td><td>370</td><td>7843</td><td>2636</td><td>5139</td><td>51.53898</td><td>49.82307</td><td>0.1381031</td><td>642386.8</td><td>731102.4</td><td>629820.6</td><td>0.044796</td><td>641501.5</td><td>1.378679</td></tr><tr><td>CD<sup>≤</sup><sub>α,step</sub></td><td>8</td><td>1238</td><td>6991</td><td>2287</td><td>4636</td><td>73.62954</td><td>68.43135</td><td>0.1649393</td><td>642386.8</td><td>748341.6</td><td>629820.6</td><td>0.04406</td><td>641501.5</td><td>1.391546</td></tr><tr><td>CD<sup>≤</sup><sub>α,exp</sub></td><td>8</td><td>141</td><td>5145</td><td>1843</td><td>3234</td><td>15.95466</td><td>15.12739</td><td>0.1069338</td><td>642386.8</td><td>711079.6</td><td>629820.6</td><td>0.04512</td><td>641501.5</td><td>1.398871</td></tr><tr><td>CD<sup>≤</sup><sub>α,p.l.</sub></td><td>8</td><td>168</td><td>5475</td><td>2094</td><td>3313</td><td>19.59417</td><td>18.68543</td><td>0.05902485</td><td>642386.8</td><td>680303.5</td><td>629820.6</td><td>0.045642</td><td>641501.5</td><td>1.368331</td></tr><tr><td>CD</td><td>9</td><td>191</td><td>8440</td><td>2852</td><td>5520</td><td>62.80591</td><td>61.86399</td><td>1.055205</td><td>658045.9</td><td>1352419</td><td>646706.9</td><td>0.039313</td><td>657193.6</td><td>1.289417</td></tr><tr><td>CD<sub>α</sub></td><td>9</td><td>203</td><td>6922</td><td>2020</td><td>4834</td><td>38.22051</td><td>37.30707</td><td>1.055205</td><td>658045.9</td><td>1352419</td><td>646706.9</td><td>0.037841</td><td>657193.6</td><td>1.290841</td></tr><tr><td>CD<sup>≤</sup></td><td>9</td><td>241</td><td>7654</td><td>2608</td><td>4978</td><td>47.32071</td><td>46.24155</td><td>0.07214954</td><td>658045.9</td><td>705523.6</td><td>646706.9</td><td>0.037064</td><td>657193.6</td><td>1.294835</td></tr><tr><td>CD<sup>≤</sup><sub>α,step</sub></td><td>9</td><td>1067</td><td>6724</td><td>2202</td><td>4454</td><td>67.07043</td><td>63.05745</td><td>0.1112945</td><td>658045.9</td><td>731282.8</td><td>646706.9</td><td>0.038052</td><td>657193.6</td><td>1.301297</td></tr><tr><td>CD<sup>≤</sup><sub>α,exp</sub></td><td>9</td><td>197</td><td>5373</td><td>1917</td><td>3388</td><td>21.35941</td><td>20.33913</td><td>0.05697048</td><td>658045.9</td><td>695535.1</td><td>646706.9</td><td>0.05045</td><td>657193.6</td><td>1.336049</td></tr><tr><td>CD<sup>≤</sup><sub>α,p.l.</sub></td><td>9</td><td>164</td><td>5507</td><td>2056</td><td>3383</td><td>22.43628</td><td>21.54064</td><td>0.06473854</td><td>658045.9</td><td>700646.9</td><td>646706.9</td><td>0.045545</td><td>657193.6</td><td>1.334407</td></tr><tr><td>CD</td><td>10</td><td>198</td><td>8878</td><td>2948</td><td>5862</td><td>63.38261</td><td>62.39569</td><td>1.28151</td><td>560099.7</td><td>1277873</td><td>547678.8</td><td>0.039041</td><td>560339.5</td><td>1.175416</td></tr><tr><td>CD<sub>α</sub></td><td>10</td><td>144</td><td>7215</td><td>2109</td><td>5038</td><td>39.59412</td><td>38.86638</td><td>1.28151</td><td>560099.7</td><td>1277873</td><td>547678.8</td><td>0.038498</td><td>560339.5</td><td>1.175586</td></tr><tr><td>CD<sup>≤</sup></td><td>10</td><td>200</td><td>7869</td><td>2738</td><td>5063</td><td>42.15482</td><td>41.20609</td><td>0.1723956</td><td>560099.7</td><td>656658.4</td><td>547678.8</td><td>0.054639</td><td>560339.5</td><td>1.180771</td></tr><tr><td>CD<sup>≤</sup><sub>α,step</sub></td><td>10</td><td>936</td><td>7389</td><td>2178</td><td>5143</td><td>50.6577</td><td>47.07771</td><td>0.09521624</td><td>560099.7</td><td>613430.2</td><td>547678.8</td><td>0.038588</td><td>560339.5</td><td>1.183256</td></tr><tr><td>CD<sup>≤</sup><sub>α,exp</sub></td><td>10</td><td>148</td><td>5581</td><td>2007</td><td>3506</td><td>19.32473</td><td>18.52145</td><td>0.1228275</td><td>560099.7</td><td>628895.3</td><td>547678.8</td><td>0.039499</td><td>560339.5</td><td>1.180448</td></tr><tr><td>CD<sup>≤</sup><sub>α,p.l.</sub></td><td>10</td><td>148</td><td>5481</td><td>2034</td><td>3379</td><td>18.13506</td><td>17.35879</td><td>0.08518942</td><td>560099.7</td><td>607814.2</td><td>547678.8</td><td>0.039198</td><td>560339.5</td><td>1.19696</td></tr></tbody></table>
<table><caption>Table 4 Performance of different crosswise decomposition methods on instances with 20 production units and 48 time steps, instances 11 to 20</caption><thead><tr><th>Method</th><th>id</th><th>Iter</th><th>Var</th><th>cols U</th><th>cols T</th><th>CPU</th><th>CPU<sub>RMP</sub></th><th>Gap</th><th>DualB</th><th>PrimalB</th><th>LR</th><th>CPU<sub>LR</sub></th><th>R0<sub>Cpx</sub></th><th>CPU<sub>R0Cpx</sub></th></tr></thead><tbody><tr><td>CD</td><td>11</td><td>196</td><td>8578</td><td>2809</td><td>5701</td><td>63.07698</td><td>62.08391</td><td>1.175761</td><td>613075.7</td><td>1333906</td><td>599624.7</td><td>0.03816</td><td>611784.4</td><td>1.818828</td></tr><tr><td>CD<sub>α</sub></td><td>11</td><td>242</td><td>7138</td><td>2052</td><td>5018</td><td>41.57501</td><td>40.56669</td><td>1.175761</td><td>613075.7</td><td>1333906</td><td>599624.7</td><td>0.037641</td><td>611784.4</td><td>1.818135</td></tr><tr><td>CD<sup>≤</sup></td><td>11</td><td>200</td><td>7439</td><td>2558</td><td>4813</td><td>42.9282</td><td>42.05633</td><td>0.1053474</td><td>613075.7</td><td>677661.6</td><td>599624.7</td><td>0.039247</td><td>611784.4</td><td>1.828654</td></tr><tr><td>CD<sub>α,step</sub></td><td>11</td><td>281</td><td>6101</td><td>2233</td><td>3800</td><td>29.32416</td><td>28.14732</td><td>0.08081888</td><td>613075.7</td><td>662623.8</td><td>599624.7</td><td>0.037919</td><td>611784.4</td><td>1.822781</td></tr><tr><td>CD<sub>α,exp</sub></td><td>11</td><td>126</td><td>5097</td><td>1866</td><td>3163</td><td>16.42016</td><td>15.75063</td><td>0.1969473</td><td>613075.7</td><td>733819.3</td><td>599624.7</td><td>0.038149</td><td>611784.4</td><td>1.822995</td></tr><tr><td>CD<sup>≤</sup><sub>α,p.l.</sub></td><td>11</td><td>302</td><td>5355</td><td>1949</td><td>3338</td><td>26.14902</td><td>24.92378</td><td>0.1016256</td><td>613075.7</td><td>675379.9</td><td>599624.7</td><td>0.037945</td><td>611784.4</td><td>1.822119</td></tr><tr><td>CD</td><td>12</td><td>205</td><td>8226</td><td>2665</td><td>5493</td><td>59.94914</td><td>58.90567</td><td>1.097545</td><td>622621.8</td><td>1305977</td><td>610673.5</td><td>0.046582</td><td>621225</td><td>1.465959</td></tr><tr><td>CD<sub>α</sub></td><td>12</td><td>178</td><td>6583</td><td>1919</td><td>4596</td><td>35.19724</td><td>34.32844</td><td>1.097545</td><td>622621.8</td><td>1305977</td><td>610673.5</td><td>0.047505</td><td>621225</td><td>1.464595</td></tr><tr><td>CD<sup>≤</sup></td><td>12</td><td>266</td><td>7330</td><td>2507</td><td>4755</td><td>44.76713</td><td>43.52342</td><td>0.1342657</td><td>622621.8</td><td>706218.5</td><td>610673.5</td><td>0.047017</td><td>621225</td><td>1.468884</td></tr><tr><td>CD<sub>α,step</sub></td><td>12</td><td>788</td><td>6481</td><td>2038</td><td>4375</td><td>56.64706</td><td>53.29932</td><td>0.1852689</td><td>622621.8</td><td>737974.2</td><td>610673.5</td><td>0.04796</td><td>621225</td><td>1.467706</td></tr><tr><td>CD<sub>α,exp</sub></td><td>12</td><td>205</td><td>5063</td><td>1775</td><td>3220</td><td>19.0924</td><td>18.01952</td><td>0.1677248</td><td>622621.8</td><td>727050.9</td><td>610673.5</td><td>0.047933</td><td>621225</td><td>1.472875</td></tr><tr><td>CD<sup>≤</sup><sub>α,p.l.</sub></td><td>12</td><td>234</td><td>4909</td><td>1832</td><td>3009</td><td>21.21358</td><td>20.07541</td><td>0.2071917</td><td>622621.8</td><td>751623.9</td><td>610673.5</td><td>0.047887</td><td>621225</td><td>1.471134</td></tr><tr><td>CD</td><td>13</td><td>203</td><td>8990</td><td>2864</td><td>6058</td><td>64.72174</td><td>63.75631</td><td>1.256037</td><td>546717</td><td>1233414</td><td>537263.7</td><td>0.040584</td><td>545750.6</td><td>1.353683</td></tr><tr><td>CD<sub>α</sub></td><td>13</td><td>239</td><td>7411</td><td>2109</td><td>5234</td><td>43.54413</td><td>42.5128</td><td>1.256037</td><td>546717</td><td>1233414</td><td>537263.7</td><td>0.039494</td><td>545750.6</td><td>1.348532</td></tr><tr><td>CD<sup>≤</sup></td><td>13</td><td>539</td><td>8418</td><td>2622</td><td>5728</td><td>66.36188</td><td>64.2064</td><td>0.07807767</td><td>546717</td><td>589403.4</td><td>537263.7</td><td>0.039171</td><td>545750.6</td><td>1.344479</td></tr><tr><td>CD<sub>α,step</sub></td><td>13</td><td>4265</td><td>13875</td><td>2244</td><td>11563</td><td>259.5151</td><td>243.721</td><td>0.050889</td><td>546717</td><td>574538.9</td><td>537263.7</td><td>0.036767</td><td>545750.6</td><td>1.347886</td></tr><tr><td>CD<sub>α,exp</sub></td><td>13</td><td>394</td><td>5693</td><td>1899</td><td>3726</td><td>28.10507</td><td>26.40268</td><td>0.1250141</td><td>546717</td><td>615064.3</td><td>537263.7</td><td>0.057484</td><td>545750.6</td><td>1.362244</td></tr><tr><td>CD<sup>≤</sup><sub>α,p.l.</sub></td><td>13</td><td>173</td><td>5361</td><td>1994</td><td>3299</td><td>19.57228</td><td>18.74354</td><td>0.06862355</td><td>546717</td><td>584234.7</td><td>537263.7</td><td>0.04081</td><td>545750.6</td><td>1.349445</td></tr><tr><td>CD</td><td>14</td><td>351</td><td>8527</td><td>2658</td><td>5801</td><td>70.2663</td><td>68.52755</td><td>1.356521</td><td>583771.9</td><td>1375671</td><td>568321.6</td><td>0.05002</td><td>582873.6</td><td>1.176992</td></tr><tr><td>CD<sub>α</sub></td><td>14</td><td>206</td><td>7013</td><td>1914</td><td>5031</td><td>36.08492</td><td>35.02628</td><td>1.356521</td><td>583771.9</td><td>1375671</td><td>568321.6</td><td>0.050095</td><td>582873.6</td><td>1.177834</td></tr><tr><td>CD<sup>≤</sup></td><td>14</td><td>466</td><td>7432</td><td>2366</td><td>4998</td><td>52.11272</td><td>49.93484</td><td>0.09449633</td><td>583771.9</td><td>638936.2</td><td>568321.6</td><td>0.050555</td><td>582873.6</td><td>1.174575</td></tr><tr><td>CD<sub>α,step</sub></td><td>14</td><td>4866</td><td>10936</td><td>1903</td><td>8965</td><td>261.0296</td><td>240.1427</td><td>0.1112106</td><td>583771.9</td><td>648693.6</td><td>568321.6</td><td>0.050365</td><td>582873.6</td><td>1.178171</td></tr><tr><td>CD<sub>α,exp</sub></td><td>14</td><td>4082</td><td>9757</td><td>1672</td><td>8017</td><td>190.2738</td><td>172.0268</td><td>0.09802933</td><td>583771.9</td><td>640998.7</td><td>568321.6</td><td>0.051563</td><td>582873.6</td><td>1.196629</td></tr><tr><td>CD<sup>≤</sup><sub>α,p.l.</sub></td><td>14</td><td>6150</td><td>10841</td><td>1795</td><td>8978</td><td>281.8742</td><td>255.5635</td><td>0.1026432</td><td>583771.9</td><td>643692.1</td><td>568321.6</td><td>0.050783</td><td>582873.6</td><td>1.172857</td></tr><tr><td>CD</td><td>15</td><td>245</td><td>8387</td><td>2715</td><td>5604</td><td>63.42361</td><td>62.005</td><td>1.126388</td><td>653944.2</td><td>1390539</td><td>641549.5</td><td>0.05402</td><td>653062.1</td><td>1.450822</td></tr><tr><td>CD<sub>α</sub></td><td>15</td><td>178</td><td>6699</td><td>1877</td><td>4754</td><td>35.95637</td><td>34.92651</td><td>1.126388</td><td>653944.2</td><td>1390539</td><td>641549.5</td><td>0.053622</td><td>653062.1</td><td>1.437355</td></tr><tr><td>CD<sup>≤</sup></td><td>15</td><td>163</td><td>7138</td><td>2355</td><td>4715</td><td>37.54917</td><td>36.59217</td><td>0.1198247</td><td>653944.2</td><td>732302.8</td><td>641549.5</td><td>0.052906</td><td>653062.1</td><td>1.417562</td></tr><tr><td>CD<sub>α,step</sub></td><td>15</td><td>344</td><td>5972</td><td>2055</td><td>3849</td><td>31.07018</td><td>29.25375</td><td>0.1427517</td><td>653944.2</td><td>747295.8</td><td>641549.5</td><td>0.056985</td><td>653062.1</td><td>1.458856</td></tr><tr><td>CD<sub>α,exp</sub></td><td>15</td><td>152</td><td>5118</td><td>1778</td><td>3272</td><td>17.65271</td><td>16.68646</td><td>0.2096449</td><td>653944.2</td><td>791040.3</td><td>641549.5</td><td>0.055567</td><td>653062.1</td><td>1.460613</td></tr><tr><td>CD<sup>≤</sup><sub>α,p.l.</sub></td><td>15</td><td>204</td><td>5339</td><td>1927</td><td>3344</td><td>21.89135</td><td>20.68859</td><td>0.1716901</td><td>653944.2</td><td>766219.9</td><td>641549.5</td><td>0.057146</td><td>653062.1</td><td>1.434457</td></tr><tr><td>CD</td><td>16</td><td>201</td><td>8425</td><td>2764</td><td>5593</td><td>60.4331</td><td>59.3135</td><td>1.108189</td><td>583990.5</td><td>1231163</td><td>571873.4</td><td>0.053905</td><td>582873.4</td><td>1.632707</td></tr><tr><td>CD<sub>α</sub></td><td>16</td><td>176</td><td>6943</td><td>1974</td><td>4901</td><td>36.40495</td><td>35.47055</td><td>1.108189</td><td>583990.5</td><td>1231163</td><td>571873.4</td><td>0.04855</td><td>582873.4</td><td>1.589451</td></tr><tr><td>CD<sup>≤</sup></td><td>16</td><td>410</td><td>7575</td><td>2482</td><td>5025</td><td>52.79361</td><td>50.91562</td><td>0.0991627</td><td>583990.5</td><td>641900.6</td><td>571873.4</td><td>0.055909</td><td>582873.4</td><td>1.620744</td></tr><tr><td>CD<sub>α,step</sub></td><td>16</td><td>195</td><td>5959</td><td>2147</td><td>3744</td><td>24.66732</td><td>23.63838</td><td>0.09679516</td><td>583990.5</td><td>640518</td><td>571873.4</td><td>0.048746</td><td>582873.4</td><td>1.568335</td></tr><tr><td>CD<sub>α,exp</sub></td><td>16</td><td>151</td><td>5150</td><td>1839</td><td>3243</td><td>16.48457</td><td>15.50051</td><td>0.2337974</td><td>583990.5</td><td>720526</td><td>571873.4</td><td>0.05026</td><td>582873.4</td><td>1.637963</td></tr><tr><td>CD<sup>≤</sup><sub>α,p.l.</sub></td><td>16</td><td>162</td><td>5034</td><td>1941</td><td>3025</td><td>18.04931</td><td>17.16173</td><td>0.1760834</td><td>583990.5</td><td>686821.5</td><td>571873.4</td><td>0.049197</td><td>582873.4</td><td>1.639375</td></tr><tr><td>CD</td><td>17</td><td>174</td><td>8172</td><td>2584</td><td>5520</td><td>58.59417</td><td>57.51595</td><td>1.19761</td><td>662654</td><td>1456255</td><td>649656.2</td><td>0.047872</td><td>661302.5</td><td>1.674374</td></tr><tr><td>CD<sub>α</sub></td><td>17</td><td>187</td><td>6434</td><td>1771</td><td>4595</td><td>33.83785</td><td>32.77499</td><td>1.19761</td><td>662654</td><td>1456255</td><td>649656.2</td><td>0.048367</td><td>661302.5</td><td>1.665526</td></tr><tr><td>CD<sup>≤</sup></td><td>17</td><td>188</td><td>7017</td><td>2321</td><td>4628</td><td>39.03267</td><td>37.92196</td><td>0.1113055</td><td>662654</td><td>736411.1</td><td>649656.2</td><td>0.048009</td><td>661302.5</td><td>1.633863</td></tr><tr><td>CD<sub>α,step</sub></td><td>17</td><td>498</td><td>5660</td><td>1965</td><td>3627</td><td>36.39755</td><td>33.96954</td><td>0.1041815</td><td>662654</td><td>731690.3</td><td>649656.2</td><td>0.048216</td><td>661302.5</td><td>1.646757</td></tr><tr><td>CD<sub>α,exp</sub></td><td>17</td><td>118</td><td>4759</td><td>1672</td><td>3019</td><td>14.83805</td><td>14.06699</td><td>0.08579225</td><td>662654</td><td>719504.6</td><td>649656.2</td><td>0.066367</td><td>661302.5</td><td>1.628986</td></tr><tr><td>CD<sup>≤</sup><sub>α,p.l.</sub></td><td>17</td><td>146</td><td>4803</td><td>1775</td><td>2960</td><td>16.40378</td><td>15.52649</td><td>0.09830734</td><td>662654</td><td>727797.8</td><td>649656.2</td><td>0.048727</td><td>661302.5</td><td>1.621659</td></tr><tr><td>CD</td><td>18</td><td>183</td><td>8537</td><td>2919</td><td>5550</td><td>61.48128</td><td>60.67954</td><td>1.175927</td><td>521579.5</td><td>1134919</td><td>510835</td><td>0.03782</td><td>521141.3</td><td>1.313914</td></tr><tr><td>CD<sub>α</sub></td><td>18</td><td>473</td><td>7474</td><td>2182</td><td>5224</td><td>53.25983</td><td>51.61144</td><td>1.175927</td><td>521579.5</td><td>1134919</td><td>510835</td><td>0.034954</td><td>521141.3</td><td>1.319779</td></tr><tr><td>CD<sup>≤</sup></td><td>18</td><td>169</td><td>7569</td><td>2669</td><td>4832</td><td>46.84739</td><td>46.11605</td><td>1.024866</td><td>521579.5</td><td>1056129</td><td>510835</td><td>0.033589</td><td>521141.3</td><td>1.292538</td></tr><tr><td>CD<sub>α,step</sub></td><td>18</td><td>232</td><td>6347</td><td>2538</td><td>3741</td><td>29.12886</td><td>28.18144</td><td>0.1209903</td><td>521579.5</td><td>584685.5</td><td>510835</td><td>0.034834</td><td>521141.3</td><td>1.306727</td></tr><tr><td>CD<sub>α,exp</sub></td><td>18</td><td>139</td><td>5282</td><td>1957</td><td>3257</td><td>19.27616</td><td>18.59717</td><td>0.1367949</td><td>521579.5</td><td>592928.9</td><td>510835</td><td>0.034337</td><td>521141.3</td><td>1.306143</td></tr><tr><td>CD<sup>≤</sup><sub>α,p.l.</sub></td><td>18</td><td>150</td><td>5559</td><td>2194</td><td>3297</td><td>21.64332</td><td>20.94134</td><td>0.08255064</td><td>521579.5</td><td>564636.2</td><td>510835</td><td>0.034635</td><td>521141.3</td><td>1.30956</td></tr><tr><td>CD</td><td>19</td><td>157</td><td>7543</td><td>2479</td><td>4996</td><td>48.54862</td><td>47.73065</td><td>0.90275</td><td>808833.7</td><td>1539008</td><td>796563.5</td><td>0.050682</td><td>807792.7</td><td>1.71454</td></tr><tr><td>CD<sub>α</sub></td><td>19</td><td>111</td><td>5980</td><td>1675</td><td>4237</td><td>29.48018</td><td>28.84512</td><td>0.90275</td><td>808833.7</td><td>1539008</td><td>796563.5</td><td>0.04981</td><td>807792.7</td><td>1.688006</td></tr><tr><td>CD<sup>≤</sup></td><td>19</td><td>133</td><td>6533</td><td>2224</td><td>4241</td><td>34.39392</td><td>33.688</td><td>0.1441945</td><td>808833.7</td><td>925463.1</td><td>796563.5</td><td>0.061879</td><td>807792.7</td><td>1.691419</td></tr><tr><td>CD<sub>α,step</sub></td><td>19</td><td>147</td><td>5038</td><td>1841</td><td>3129</td><td>20.15168</td><td>19.39996</td><td>0.1463138</td><td>808833.7</td><td>927177.2</td><td>796563.5</td><td>0.050855</td><td>807792.7</td><td>1.693416</td></tr><tr><td>CD<sub>α,exp</sub></td><td>19</td><td>112</td><td>4702</td><td>1659</td><td>2975</td><td>16.26179</td><td>15.56596</td><td>0.1155419</td><td>808833.7</td><td>902287.9</td><td>796563.5</td><td>0.050094</td><td>807792.7</td><td>1.702619</td></tr><tr><td>CD<sup>≤</sup><sub>α,p.l.</sub></td><td>19</td><td>117</td><td>4745</td><td>1736</td><td>2941</td><td>17.11226</td><td>16.43976</td><td>0.1302264</td><td>808833.7</td><td>914165.2</td><td>796563.5</td><td>0.070098</td><td>807792.7</td><td>1.72133</td></tr><tr><td>CD</td><td>20</td><td>286</td><td>8402</td><td>2628</td><td>5706</td><td>58.83814</td><td>57.35012</td><td>1.256633</td><td>548737.5</td><td>1238299</td><td>536504.4</td><td>0.051143</td><td>548344</td><td>1.516697</td></tr><tr><td>CD<sub>α</sub></td><td>20</td><td>235</td><td>6985</td><td>1865</td><td>5052</td><td>37.35365</td><td>36.13469</td><td>1.256633</td><td>548737.5</td><td>1238299</td><td>536504.4</td><td>0.048714</td><td>548344</td><td>1.499136</td></tr><tr><td>CD<sup>≤</sup></td><td>20</td><td>322</td><td>7047</td><td>2339</td><td>4640</td><td>41.5459</td><td>39.93737</td><td>0.2063737</td><td>548737.5</td><td>661982.5</td><td>536504.4</td><td>0.049423</td><td>548344</td><td>1.479639</td></tr><tr><td>CD<sub>α,step</sub></td><td>20</td><td>245</td><td>5344</td><td>1981</td><td>3295</td><td>19.76653</td><td>18.55353</td><td>0.1549491</td><td>548737.5</td><td>633763.9</td><td>536504.4</td><td>0.05007</td><td>548344</td><td>1.489017</td></tr><tr><td>CD<sub>α,exp</sub></td><td>20</td><td>194</td><td>4927</td><td>1778</td><td>3081</td><td>16.3912</td><td>15.29214</td><td>0.09900385</td><td>548737.5</td><td>603064.7</td><td>536504.4</td><td>0.059217</td><td>548344</td><td>1.521067</td></tr><tr><td>CD<sup>≤</sup><sub>α,p.l.</sub></td><td>20</td><td>259</td><td>4717</td><td>1738</td><td>2911</td><td>17.41168</td><td>16.09706</td><td>0.1021932</td><td>548737.5</td><td>604814.8</td><td>536504.4</td><td>0.050478</td><td>548344</td><td>1.542273</td></tr></tbody></table>
<table><caption>Table 5 Performance of different crosswise decomposition methods on instances with 20 production units and 96 time steps, instances 1 to 10</caption><thead><tr><th>Method</th><th>id</th><th>Iter</th><th>Var</th><th>cols U</th><th>cols T</th><th>CPU</th><th>CPU<sub>RMP</sub></th><th>Gap</th><th>DualB</th><th>PrimalB</th><th>LR</th><th>CPU<sub>LR</sub></th><th>R0<sub>Cpx</sub></th><th>CPU<sub>R0<sub>Cpx</sub></sub></th></tr></thead><tbody><tr><td>CD</td><td>1</td><td>287</td><td>16598</td><td>3584</td><td>12898</td><td>366.1391</td><td>356.4787</td><td>1.432244</td><td>4392100</td><td>1.068266e+07</td><td>4281066</td><td>0.176596</td><td>4382368</td><td>3.714251</td></tr><tr><td>CD<sub>α</sub></td><td>1</td><td>331</td><td>14080</td><td>2612</td><td>11352</td><td>184.6715</td><td>176.1953</td><td>1.432244</td><td>4392100</td><td>1.068266e+07</td><td>4281066</td><td>0.166289</td><td>4382368</td><td>3.474848</td></tr><tr><td>CD<sup>≤</sup></td><td>1</td><td>468</td><td>14832</td><td>3458</td><td>11258</td><td>255.3428</td><td>243.5121</td><td>0.237982</td><td>4392100</td><td>5437341</td><td>4281066</td><td>0.16566</td><td>4382368</td><td>3.493462</td></tr><tr><td>CD<sup>≤</sup><sub>α,step</sub></td><td>1</td><td>1895</td><td>14493</td><td>2848</td><td>11529</td><td>429.7435</td><td>383.3924</td><td>0.1348196</td><td>4392100</td><td>4984242</td><td>4281066</td><td>0.162775</td><td>4382368</td><td>3.413023</td></tr><tr><td>CD<sup>≤</sup><sub>α,exp</sub></td><td>1</td><td>3455</td><td>14623</td><td>2495</td><td>12012</td><td>671.9756</td><td>587.5854</td><td>0.1613316</td><td>4392100</td><td>5100685</td><td>4281066</td><td>0.165931</td><td>4382368</td><td>3.501722</td></tr><tr><td>CD<sup>≤</sup><sub>α,p.l.</sub></td><td>1</td><td>2671</td><td>12405</td><td>2848</td><td>9805</td><td>509.7531</td><td>444.64</td><td>0.2072615</td><td>4392100</td><td>5302413</td><td>4281066</td><td>0.165668</td><td>4382368</td><td>3.493617</td></tr><tr><td>CD</td><td>2</td><td>361</td><td>17463</td><td>3866</td><td>13481</td><td>327.0166</td><td>319.9255</td><td>1.481063</td><td>3716459</td><td>9220768</td><td>3623137</td><td>0.121096</td><td>3706254</td><td>3.199852</td></tr><tr><td>CD<sub>α</sub></td><td>2</td><td>281</td><td>15008</td><td>2984</td><td>11908</td><td>200.266</td><td>194.7183</td><td>1.481063</td><td>3716459</td><td>9220768</td><td>3623137</td><td>0.123165</td><td>3706254</td><td>3.201031</td></tr><tr><td>CD<sup>≤</sup></td><td>2</td><td>1304</td><td>18348</td><td>4315</td><td>13917</td><td>535.601</td><td>511.1061</td><td>0.1823322</td><td>3716459</td><td>4394089</td><td>3623137</td><td>0.122655</td><td>3706254</td><td>3.190915</td></tr><tr><td>CD<sup>≤</sup><sub>α,step</sub></td><td>2</td><td>2507</td><td>16219</td><td>3312</td><td>12791</td><td>623.9888</td><td>575.3372</td><td>0.3248449</td><td>3716459</td><td>4923732</td><td>3623137</td><td>0.119537</td><td>3706254</td><td>3.135558</td></tr><tr><td>CD<sup>≤</sup><sub>α,exp</sub></td><td>2</td><td>7093</td><td>23422</td><td>2843</td><td>20463</td><td>1590.225</td><td>1459.041</td><td>0.1738564</td><td>3716459</td><td>4362589</td><td>3623137</td><td>0.121848</td><td>3706254</td><td>3.196634</td></tr><tr><td>CD<sup>≤</sup><sub>α,p.l.</sub></td><td>2</td><td>2052</td><td>12161</td><td>2888</td><td>9157</td><td>443.6792</td><td>405.7054</td><td>0.2930523</td><td>3716459</td><td>4805576</td><td>3623137</td><td>0.121238</td><td>3706254</td><td>3.177985</td></tr><tr><td>CD</td><td>3</td><td>320</td><td>16805</td><td>3756</td><td>12933</td><td>318.9549</td><td>312.6325</td><td>1.452834</td><td>3806776</td><td>9337391</td><td>3702084</td><td>0.126759</td><td>3797849</td><td>4.275405</td></tr><tr><td>CD<sub>α</sub></td><td>3</td><td>208</td><td>14063</td><td>2899</td><td>11048</td><td>175.9392</td><td>171.7677</td><td>1.452834</td><td>3806776</td><td>9337391</td><td>3702084</td><td>0.124377</td><td>3797849</td><td>4.205191</td></tr><tr><td>CD<sup>≤</sup></td><td>3</td><td>239</td><td>15041</td><td>3743</td><td>11182</td><td>219.0921</td><td>214.2946</td><td>0.180563</td><td>3806776</td><td>4494139</td><td>3702084</td><td>0.125278</td><td>3797849</td><td>4.228908</td></tr><tr><td>CD<sup>≤</sup><sub>α,step</sub></td><td>3</td><td>258</td><td>10715</td><td>3167</td><td>7432</td><td>110.2962</td><td>105.0993</td><td>0.1081617</td><td>3806776</td><td>4218523</td><td>3702084</td><td>0.12754</td><td>3797849</td><td>4.279428</td></tr><tr><td>CD<sup>≤</sup><sub>α,exp</sub></td><td>3</td><td>181</td><td>9072</td><td>2622</td><td>6334</td><td>67.26346</td><td>63.37389</td><td>0.1659254</td><td>3806776</td><td>4438417</td><td>3702084</td><td>0.127777</td><td>3797849</td><td>4.267366</td></tr><tr><td>CD<sup>≤</sup><sub>α,p.l.</sub></td><td>3</td><td>182</td><td>9012</td><td>2661</td><td>6235</td><td>72.12295</td><td>68.30734</td><td>0.2114366</td><td>3806776</td><td>4611668</td><td>3702084</td><td>0.128258</td><td>3797849</td><td>4.265445</td></tr><tr><td>CD</td><td>4</td><td>252</td><td>16270</td><td>3573</td><td>12581</td><td>274.3275</td><td>268.3255</td><td>1.32232</td><td>4283832</td><td>9948428</td><td>4198193</td><td>0.156788</td><td>4270289</td><td>3.781571</td></tr><tr><td>CD<sub>α</sub></td><td>4</td><td>196</td><td>13293</td><td>2586</td><td>10591</td><td>156.378</td><td>151.7647</td><td>1.32232</td><td>4283832</td><td>9948428</td><td>4198193</td><td>0.157545</td><td>4270289</td><td>3.810679</td></tr><tr><td>CD<sup>≤</sup></td><td>4</td><td>431</td><td>15498</td><td>3764</td><td>11618</td><td>304.7017</td><td>294.8057</td><td>1.204754</td><td>4283832</td><td>9444797</td><td>4198193</td><td>0.156668</td><td>4270289</td><td>3.787535</td></tr><tr><td>CD<sup>≤</sup><sub>α,step</sub></td><td>4</td><td>3699</td><td>16302</td><td>3322</td><td>12864</td><td>1138.955</td><td>1057.691</td><td>0.6064565</td><td>4283832</td><td>6881790</td><td>4198193</td><td>0.158148</td><td>4270289</td><td>3.774781</td></tr><tr><td>CD<sup>≤</sup><sub>α,exp</sub></td><td>4</td><td>250</td><td>10166</td><td>2760</td><td>7290</td><td>96.48059</td><td>90.45146</td><td>1.113166</td><td>4283832</td><td>9052446</td><td>4198193</td><td>0.158084</td><td>4270289</td><td>3.778996</td></tr><tr><td>CD<sup>≤</sup><sub>α,p.l.</sub></td><td>4</td><td>1491</td><td>11726</td><td>2763</td><td>8847</td><td>420.0961</td><td>386.2796</td><td>0.6064565</td><td>4283832</td><td>6881790</td><td>4198193</td><td>0.157605</td><td>4270289</td><td>3.78065</td></tr><tr><td>CD</td><td>5</td><td>219</td><td>16113</td><td>3598</td><td>12399</td><td>276.6317</td><td>272.5275</td><td>1.387961</td><td>3971356</td><td>9483444</td><td>3894893</td><td>0.140375</td><td>3958748</td><td>4.433402</td></tr><tr><td>CD<sub>α</sub></td><td>5</td><td>170</td><td>13013</td><td>2604</td><td>10293</td><td>148.4034</td><td>145.1754</td><td>1.387961</td><td>3971356</td><td>9483444</td><td>3894893</td><td>0.138143</td><td>3958748</td><td>4.364679</td></tr><tr><td>CD<sup>≤</sup></td><td>5</td><td>234</td><td>15308</td><td>3779</td><td>11413</td><td>251.979</td><td>247.5886</td><td>0.2830509</td><td>3971356</td><td>5095451</td><td>3894893</td><td>0.136513</td><td>3958748</td><td>4.360728</td></tr><tr><td>CD<sup>≤</sup><sub>α,step</sub></td><td>5</td><td>395</td><td>11392</td><td>3348</td><td>7928</td><td>162.0914</td><td>154.9017</td><td>0.2024267</td><td>3971356</td><td>4775264</td><td>3894893</td><td>0.140888</td><td>3958748</td><td>4.431455</td></tr><tr><td>CD<sup>≤</sup><sub>α,exp</sub></td><td>5</td><td>173</td><td>9135</td><td>2566</td><td>6453</td><td>73.30808</td><td>69.85265</td><td>0.8074434</td><td>3971356</td><td>7178000</td><td>3894893</td><td>0.139654</td><td>3958748</td><td>4.361597</td></tr><tr><td>CD<sup>≤</sup><sub>α,p.l.</sub></td><td>5</td><td>183</td><td>9203</td><td>2773</td><td>6314</td><td>84.62596</td><td>81.03864</td><td>1.286845</td><td>3971356</td><td>9081875</td><td>3894893</td><td>0.139001</td><td>3958748</td><td>4.371008</td></tr><tr><td>CD</td><td>6</td><td>436</td><td>17656</td><td>3759</td><td>13781</td><td>352.481</td><td>342.8464</td><td>1.514054</td><td>4098199</td><td>1.030309e+07</td><td>4000395</td><td>0.133405</td><td>4091832</td><td>3.199381</td></tr><tr><td>CD<sub>α</sub></td><td>6</td><td>263</td><td>15029</td><td>2903</td><td>12010</td><td>206.0064</td><td>200.137</td><td>1.514054</td><td>4098199</td><td>1.030309e+07</td><td>4000395</td><td>0.132356</td><td>4091832</td><td>3.150872</td></tr><tr><td>CD<sup>≤</sup></td><td>6</td><td>245</td><td>15804</td><td>3849</td><td>11839</td><td>243.4721</td><td>237.2137</td><td>0.304611</td><td>4098199</td><td>5346555</td><td>4000395</td><td>0.131086</td><td>4091832</td><td>3.15415</td></tr><tr><td>CD<sup>≤</sup><sub>α,step</sub></td><td>6</td><td>242</td><td>11938</td><td>3334</td><td>8488</td><td>120.3215</td><td>114.7648</td><td>0.1557672</td><td>4098199</td><td>4736564</td><td>4000395</td><td>0.133013</td><td>4091832</td><td>3.175163</td></tr><tr><td>CD<sup>≤</sup><sub>α,exp</sub></td><td>6</td><td>244</td><td>10356</td><td>2869</td><td>7371</td><td>102.586</td><td>96.83373</td><td>0.3097289</td><td>4098199</td><td>5367530</td><td>4000395</td><td>0.132949</td><td>4091832</td><td>3.191945</td></tr><tr><td>CD<sup>≤</sup><sub>α,p.l.</sub></td><td>6</td><td>357</td><td>10110</td><td>2857</td><td>7137</td><td>112.4787</td><td>104.4654</td><td>0.1571922</td><td>4098199</td><td>4742404</td><td>4000395</td><td>0.132327</td><td>4091832</td><td>3.159532</td></tr><tr><td>CD</td><td>7</td><td>227</td><td>16410</td><td>3686</td><td>12608</td><td>281.2168</td><td>276.6124</td><td>1.350688</td><td>4136376</td><td>9723332</td><td>4053855</td><td>0.139192</td><td>4124782</td><td>4.669124</td></tr><tr><td>CD<sub>α</sub></td><td>7</td><td>175</td><td>13406</td><td>2653</td><td>10637</td><td>159.1975</td><td>155.608</td><td>1.350688</td><td>4136376</td><td>9723332</td><td>4053855</td><td>0.139423</td><td>4124782</td><td>4.61622</td></tr><tr><td>CD<sup>≤</sup></td><td>7</td><td>564</td><td>15500</td><td>3834</td><td>11550</td><td>345.2287</td><td>334.4088</td><td>0.2253316</td><td>4136376</td><td>5068433</td><td>4053855</td><td>0.137696</td><td>4124782</td><td>4.582473</td></tr><tr><td>CD<sup>≤</sup><sub>α,step</sub></td><td>7</td><td>905</td><td>12031</td><td>3364</td><td>8551</td><td>283.8326</td><td>266.6913</td><td>0.3151751</td><td>4136376</td><td>5440059</td><td>4053855</td><td>0.133159</td><td>4124782</td><td>4.596906</td></tr><tr><td>CD<sup>≤</sup><sub>α,exp</sub></td><td>7</td><td>331</td><td>9734</td><td>2672</td><td>6946</td><td>111.688</td><td>104.9955</td><td>0.2506379</td><td>4136376</td><td>5173109</td><td>4053855</td><td>0.139414</td><td>4124782</td><td>4.611712</td></tr><tr><td>CD<sup>≤</sup><sub>α,p.l.</sub></td><td>7</td><td>345</td><td>9559</td><td>2806</td><td>6637</td><td>115.9881</td><td>109.1442</td><td>0.5482436</td><td>4136376</td><td>6404118</td><td>4053855</td><td>0.139105</td><td>4124782</td><td>4.59132</td></tr><tr><td>CD</td><td>8</td><td>243</td><td>16900</td><td>3751</td><td>13033</td><td>286.48</td><td>281.6306</td><td>1.494322</td><td>3861105</td><td>9630838</td><td>3770435</td><td>0.112269</td><td>3848791</td><td>3.725969</td></tr><tr><td>CD<sub>α</sub></td><td>8</td><td>240</td><td>14294</td><td>2817</td><td>11361</td><td>184.0206</td><td>179.3171</td><td>1.494322</td><td>3861105</td><td>9630838</td><td>3770435</td><td>0.113585</td><td>3848791</td><td>3.709815</td></tr><tr><td>CD<sup>≤</sup></td><td>8</td><td>2168</td><td>17826</td><td>3889</td><td>13821</td><td>748.8172</td><td>709.0912</td><td>0.4111125</td><td>3861105</td><td>5448454</td><td>3770435</td><td>0.110931</td><td>3848791</td><td>3.715485</td></tr><tr><td>CD<sup>≤</sup><sub>α,step</sub></td><td>8</td><td>797</td><td>13706</td><td>3478</td><td>10112</td><td>255.3309</td><td>240.444</td><td>1.494322</td><td>3861105</td><td>9630838</td><td>3770435</td><td>0.113144</td><td>3848791</td><td>3.74773</td></tr><tr><td>CD<sup>≤</sup><sub>α,exp</sub></td><td>8</td><td>16062</td><td>25786</td><td>2719</td><td>22951</td><td>3600.111</td><td>3298.729</td><td>1e+20</td><td>-1e+20</td><td>8603550</td><td>3770435</td><td>0.112314</td><td>3848791</td><td>3.73545</td></tr><tr><td>CD<sup>≤</sup><sub>α,p.l.</sub></td><td>8</td><td>578</td><td>10230</td><td>2849</td><td>7265</td><td>158.6575</td><td>147.7141</td><td>0.1991977</td><td>3861105</td><td>4630229</td><td>3770435</td><td>0.11491</td><td>3848791</td><td>3.714808</td></tr><tr><td>CD</td><td>9</td><td>436</td><td>18358</td><td>3923</td><td>14319</td><td>369.1481</td><td>359.6947</td><td>1.619536</td><td>3491841</td><td>9147003</td><td>3397138</td><td>0.153837</td><td>3485827</td><td>3.686364</td></tr><tr><td>CD<sub>α</sub></td><td>9</td><td>323</td><td>15314</td><td>2884</td><td>12314</td><td>210.8025</td><td>203.7514</td><td>1.619536</td><td>3491841</td><td>9147003</td><td>3397138</td><td>0.153963</td><td>3485827</td><td>3.685012</td></tr><tr><td>CD<sup>≤</sup></td><td>9</td><td>3024</td><td>20091</td><td>3924</td><td>16051</td><td>873.6011</td><td>802.2545</td><td>0.1451043</td><td>3491841</td><td>3998522</td><td>3397138</td><td>0.15331</td><td>3485827</td><td>3.691447</td></tr><tr><td>CD<sup>≤</sup><sub>α,step</sub></td><td>9</td><td>11183</td><td>23913</td><td>3104</td><td>20693</td><td>2324.656</td><td>2091.927</td><td>0.1658318</td><td>3491841</td><td>4070899</td><td>3397138</td><td>0.149739</td><td>3485827</td><td>3.669084</td></tr><tr><td>CD<sup>≤</sup><sub>α,exp</sub></td><td>9</td><td>3573</td><td>13069</td><td>2610</td><td>10343</td><td>579.6664</td><td>505.5624</td><td>0.1016227</td><td>3491841</td><td>3846691</td><td>3397138</td><td>0.152163</td><td>3485827</td><td>3.650509</td></tr><tr><td>CD<sup>≤</sup><sub>α,p.l.</sub></td><td>9</td><td>431</td><td>9114</td><td>2587</td><td>6411</td><td>99.23626</td><td>89.87658</td><td>0.1213557</td><td>3491841</td><td>3915596</td><td>3397138</td><td>0.154795</td><td>3485827</td><td>3.672268</td></tr><tr><td>CD</td><td>10</td><td>288</td><td>16336</td><td>3502</td><td>12718</td><td>266.3938</td><td>259.3331</td><td>1.384342</td><td>3907690</td><td>9317269</td><td>3799292</td><td>0.155087</td><td>3898291</td><td>4.013987</td></tr><tr><td>CD<sub>α</sub></td><td>10</td><td>299</td><td>14106</td><td>2623</td><td>11367</td><td>176.7016</td><td>168.6203</td><td>1.384342</td><td>3907690</td><td>9317269</td><td>3799292</td><td>0.153996</td><td>3898291</td><td>4.019465</td></tr><tr><td>CD<sup>≤</sup></td><td>10</td><td>1087</td><td>15831</td><td>3647</td><td>12068</td><td>419.9235</td><td>393.9139</td><td>0.1527095</td><td>3907690</td><td>4504432</td><td>3799292</td><td>0.154624</td><td>3898291</td><td>4.025333</td></tr><tr><td>CD<sup>≤</sup><sub>α,step</sub></td><td>10</td><td>627</td><td>11382</td><td>2963</td><td>8303</td><td>162.074</td><td>147.1805</td><td>0.2260313</td><td>3907690</td><td>4790950</td><td>3799292</td><td>0.152717</td><td>3898291</td><td>4.006556</td></tr><tr><td>CD<sup>≤</sup><sub>α,exp</sub></td><td>10</td><td>710</td><td>10771</td><td>2579</td><td>8076</td><td>149.6016</td><td>132.3376</td><td>0.1359551</td><td>3907690</td><td>4438961</td><td>3799292</td><td>0.154668</td><td>3898291</td><td>4.00177</td></tr><tr><td>CD<sup>≤</sup><sub>α,p.l.</sub></td><td>10</td><td>551</td><td>9310</td><td>2572</td><td>6622</td><td>124.8666</td><td>111.6732</td><td>0.1554511</td><td>3907690</td><td>4515145</td><td>3799292</td><td>0.15447</td><td>3898291</td><td>3.993646</td></tr></tbody></table>
<table><caption>Table 6 Performance of different crosswise decomposition methods on instances with 20 production units and 96 time steps, instances 11 to 20</caption><thead><tr><th>Method</th><th>id</th><th>Iter</th><th>Var</th><th>cols U</th><th>cols T</th><th>CPU</th><th>CPU<sub>RMP</sub></th><th>Gap</th><th>DualB</th><th>PrimalB</th><th>LR</th><th>CPU<sub>RL</sub></th><th>R0<sub>Cpx</sub></th><th>CPU<sub>R0Cpx</sub></th></tr></thead><tbody><tr><td>CD</td><td>11</td><td>426</td><td>16895</td><td>3603</td><td>13176</td><td>340.1297</td><td>331.2325</td><td>1.539279</td><td>3757834</td><td>9542188</td><td>3666790</td><td>0.133597</td><td>3748256</td><td>3.947048</td></tr><tr><td>CD<sub>α</sub></td><td>11</td><td>215</td><td>14051</td><td>2739</td><td>11196</td><td>170.5674</td><td>165.9899</td><td>1.539279</td><td>3757834</td><td>9542188</td><td>3666790</td><td>0.134057</td><td>3748256</td><td>3.949107</td></tr><tr><td>CD<sup>≤</sup></td><td>11</td><td>1175</td><td>17498</td><td>3995</td><td>13387</td><td>513.9754</td><td>490.4074</td><td>0.1332168</td><td>3757834</td><td>4258441</td><td>3666790</td><td>0.133066</td><td>3748256</td><td>3.939897</td></tr><tr><td>CD<sup>≤</sup><sub>α,step</sub></td><td>11</td><td>3182</td><td>14603</td><td>3202</td><td>11285</td><td>832.1969</td><td>769.1725</td><td>0.1931396</td><td>3757834</td><td>4483621</td><td>3666790</td><td>0.133546</td><td>3748256</td><td>3.961786</td></tr><tr><td>CD<sup>≤</sup><sub>α,exp</sub></td><td>11</td><td>1233</td><td>10672</td><td>2677</td><td>7879</td><td>292.1017</td><td>266.849</td><td>0.1557731</td><td>3757834</td><td>4343203</td><td>3666790</td><td>0.133935</td><td>3748256</td><td>3.930886</td></tr><tr><td>CD<sup>≤</sup><sub>α,p.l.</sub></td><td>11</td><td>250</td><td>9568</td><td>2743</td><td>6709</td><td>84.28276</td><td>78.92575</td><td>0.2431877</td><td>3757834</td><td>4671693</td><td>3666790</td><td>0.134099</td><td>3748256</td><td>3.916706</td></tr><tr><td>CD</td><td>12</td><td>363</td><td>16928</td><td>3678</td><td>13134</td><td>312.5763</td><td>304.2799</td><td>1.495137</td><td>3047550</td><td>7604055</td><td>2962110</td><td>0.132848</td><td>3042028</td><td>3.335432</td></tr><tr><td>CD<sub>α</sub></td><td>12</td><td>323</td><td>14549</td><td>2820</td><td>11613</td><td>190.5187</td><td>182.8971</td><td>1.495137</td><td>3047550</td><td>7604055</td><td>2962110</td><td>0.135188</td><td>3042028</td><td>3.343131</td></tr><tr><td>CD<sup>≤</sup></td><td>12</td><td>715</td><td>15732</td><td>3804</td><td>11812</td><td>326.3393</td><td>310.3454</td><td>0.3195432</td><td>3047550</td><td>4021374</td><td>2962110</td><td>0.132242</td><td>3042028</td><td>3.319464</td></tr><tr><td>CD<sup>≤</sup><sub>α,step</sub></td><td>12</td><td>8307</td><td>22222</td><td>3447</td><td>18659</td><td>1905.94</td><td>1724.908</td><td>0.1160197</td><td>3047550</td><td>3401126</td><td>2962110</td><td>0.133194</td><td>3042028</td><td>3.334194</td></tr><tr><td>CD<sup>≤</sup><sub>α,exp</sub></td><td>12</td><td>4111</td><td>18874</td><td>2722</td><td>16036</td><td>829.6115</td><td>738.9376</td><td>0.0977077</td><td>3047550</td><td>3345319</td><td>2962110</td><td>0.132302</td><td>3042028</td><td>3.31063</td></tr><tr><td>CD<sup>≤</sup><sub>α,p.l.</sub></td><td>12</td><td>671</td><td>8790</td><td>2563</td><td>6111</td><td>137.2558</td><td>122.2336</td><td>0.1267238</td><td>3047550</td><td>3433747</td><td>2962110</td><td>0.134614</td><td>3042028</td><td>3.326248</td></tr><tr><td>CD</td><td>13</td><td>286</td><td>16106</td><td>3518</td><td>12472</td><td>269.806</td><td>262.4755</td><td>1.409641</td><td>3840036</td><td>9253107</td><td>3752724</td><td>0.158888</td><td>3832304</td><td>3.228276</td></tr><tr><td>CD<sub>α</sub></td><td>13</td><td>225</td><td>13233</td><td>2552</td><td>10565</td><td>154.7337</td><td>18.99995</td><td>1.409641</td><td>3840036</td><td>9253107</td><td>3752724</td><td>0.158978</td><td>3832304</td><td>3.244017</td></tr><tr><td>CD<sup>≤</sup></td><td>13</td><td>476</td><td>15420</td><td>3672</td><td>11632</td><td>294.3323</td><td>282.433</td><td>1.308967</td><td>3840036</td><td>8866518</td><td>3752724</td><td>0.161252</td><td>3832304</td><td>3.242829</td></tr><tr><td>CD<sup>≤</sup><sub>α,step</sub></td><td>13</td><td>626</td><td>12343</td><td>3118</td><td>9109</td><td>194.9562</td><td>179.4684</td><td>0.09443389</td><td>3840036</td><td>4202665</td><td>3752724</td><td>0.15891</td><td>3832304</td><td>3.205974</td></tr><tr><td>CD<sup>≤</sup><sub>α,exp</sub></td><td>13</td><td>422</td><td>10368</td><td>2663</td><td>7589</td><td>120.0277</td><td>109.2596</td><td>1.301357</td><td>3840036</td><td>8837293</td><td>3752724</td><td>0.160662</td><td>3832304</td><td>3.251802</td></tr><tr><td>CD<sup>≤</sup><sub>α,p.l.</sub></td><td>13</td><td>642</td><td>9628</td><td>2612</td><td>6900</td><td>155.8067</td><td>139.9279</td><td>0.292804</td><td>3840036</td><td>8804450</td><td>3752724</td><td>0.160005</td><td>3832304</td><td>3.225662</td></tr><tr><td>CD</td><td>14</td><td>279</td><td>16740</td><td>3630</td><td>12994</td><td>274.6817</td><td>268.2244</td><td>1.507848</td><td>3614938</td><td>9065717</td><td>3511970</td><td>0.140676</td><td>3610020</td><td>3.204638</td></tr><tr><td>CD<sub>α</sub></td><td>14</td><td>358</td><td>14794</td><td>2794</td><td>11884</td><td>213.6274</td><td>205.5091</td><td>1.507848</td><td>3614938</td><td>9065717</td><td>3511970</td><td>0.141913</td><td>3610020</td><td>3.202665</td></tr><tr><td>CD<sup>≤</sup></td><td>14</td><td>840</td><td>17077</td><td>3913</td><td>13048</td><td>369.2306</td><td>350.7269</td><td>1.38798</td><td>3614938</td><td>8632401</td><td>3511970</td><td>0.141361</td><td>3610020</td><td>3.233254</td></tr><tr><td>CD<sup>≤</sup><sub>α,step</sub></td><td>14</td><td>980</td><td>14633</td><td>3613</td><td>10904</td><td>268.0998</td><td>246.3182</td><td>0.1102256</td><td>3614938</td><td>4013397</td><td>3511970</td><td>0.140774</td><td>3610020</td><td>3.202138</td></tr><tr><td>CD<sup>≤</sup><sub>α,exp</sub></td><td>14</td><td>442</td><td>9847</td><td>2621</td><td>7110</td><td>108.46</td><td>98.29225</td><td>0.1465733</td><td>3614938</td><td>4144792</td><td>3511970</td><td>0.142091</td><td>3610020</td><td>3.210422</td></tr><tr><td>CD<sup>≤</sup><sub>α,p.l.</sub></td><td>14</td><td>1205</td><td>10091</td><td>2636</td><td>7339</td><td>213.7934</td><td>186.7961</td><td>0.1485015</td><td>3614938</td><td>4151762</td><td>3511970</td><td>0.143304</td><td>3610020</td><td>3.220228</td></tr><tr><td>CD</td><td>15</td><td>1301</td><td>18631</td><td>3980</td><td>14535</td><td>551.7299</td><td>526.9097</td><td>1.679305</td><td>2844976</td><td>7622557</td><td>2752658</td><td>0.116899</td><td>2840822</td><td>3.587681</td></tr><tr><td>CD<sub>α</sub></td><td>15</td><td>486</td><td>15535</td><td>3049</td><td>12370</td><td>230.1775</td><td>220.6781</td><td>1.679305</td><td>2844976</td><td>7622557</td><td>2752658</td><td>0.116534</td><td>2840822</td><td>3.540825</td></tr><tr><td>CD<sup>≤</sup></td><td>15</td><td>798</td><td>17196</td><td>4215</td><td>12865</td><td>355.9644</td><td>340.5914</td><td>0.1370307</td><td>2844976</td><td>3234825</td><td>2752658</td><td>0.117159</td><td>2840822</td><td>3.540479</td></tr><tr><td>CD<sup>≤</sup><sub>α,step</sub></td><td>15</td><td>11600</td><td>26483</td><td>3459</td><td>22908</td><td>2316.336</td><td>2099.025</td><td>0.07851553</td><td>2844976</td><td>3068351</td><td>2752658</td><td>0.117056</td><td>2840822</td><td>3.584847</td></tr><tr><td>CD<sup>≤</sup><sub>α,exp</sub></td><td>15</td><td>14100</td><td>24561</td><td>2906</td><td>21539</td><td>2446.068</td><td>2158.588</td><td>0.1362883</td><td>2844976</td><td>3232713</td><td>2752658</td><td>0.117075</td><td>2840822</td><td>3.565334</td></tr><tr><td>CD<sup>≤</sup><sub>α,p.l.</sub></td><td>15</td><td>250</td><td>8714</td><td>2736</td><td>5862</td><td>65.92924</td><td>60.76415</td><td>0.11592</td><td>2844976</td><td>3174765</td><td>2752658</td><td>0.118465</td><td>2840822</td><td>3.549913</td></tr><tr><td>CD</td><td>16</td><td>4501</td><td>20222</td><td>3539</td><td>16567</td><td>1603.601</td><td>1513.537</td><td>1.435062</td><td>3928043</td><td>9565026</td><td>3829119</td><td>0.166469</td><td>3920102</td><td>3.514194</td></tr><tr><td>CD<sub>α</sub></td><td>16</td><td>1369</td><td>14592</td><td>2665</td><td>11811</td><td>459.6575</td><td>431.8111</td><td>1.435062</td><td>3928043</td><td>9565026</td><td>3829119</td><td>0.168546</td><td>3920102</td><td>3.530934</td></tr><tr><td>CD<sup>≤</sup></td><td>16</td><td>676</td><td>15468</td><td>3682</td><td>11670</td><td>361.6828</td><td>347.7719</td><td>0.2179985</td><td>3928043</td><td>4784350</td><td>3829119</td><td>0.167975</td><td>3920102</td><td>3.5309</td></tr><tr><td>CD<sup>≤</sup><sub>α,step</sub></td><td>16</td><td>352</td><td>11882</td><td>3320</td><td>8446</td><td>147.3209</td><td>139.8077</td><td>0.7358641</td><td>3928043</td><td>6818548</td><td>3829119</td><td>0.169704</td><td>3920102</td><td>3.531758</td></tr><tr><td>CD<sup>≤</sup><sub>α,exp</sub></td><td>16</td><td>187</td><td>9480</td><td>2618</td><td>6746</td><td>75.3603</td><td>71.10676</td><td>0.127964</td><td>3928043</td><td>8358735</td><td>3829119</td><td>0.16987</td><td>3920102</td><td>3.531216</td></tr><tr><td>CD<sup>≤</sup><sub>α,p.l.</sub></td><td>16</td><td>187</td><td>9375</td><td>2680</td><td>6579</td><td>80.51134</td><td>76.27746</td><td>0.2259185</td><td>3928043</td><td>4815460</td><td>3829119</td><td>0.171412</td><td>3920102</td><td>3.534294</td></tr><tr><td>CD</td><td>17</td><td>257</td><td>18341</td><td>3939</td><td>14286</td><td>340.7951</td><td>335.8012</td><td>1.864536</td><td>2792710</td><td>7999818</td><td>2703091</td><td>0.11678</td><td>2786414</td><td>3.13343</td></tr><tr><td>CD<sub>α</sub></td><td>17</td><td>341</td><td>15850</td><td>3081</td><td>12653</td><td>225.1321</td><td>217.3822</td><td>1.864536</td><td>2792710</td><td>7999818</td><td>2703091</td><td>0.116921</td><td>2786414</td><td>3.131077</td></tr><tr><td>CD<sup>≤</sup></td><td>17</td><td>605</td><td>17508</td><td>4231</td><td>13161</td><td>325.0454</td><td>313.9805</td><td>0.1157397</td><td>2792710</td><td>3115937</td><td>2703091</td><td>0.117053</td><td>2786414</td><td>3.123491</td></tr><tr><td>CD<sup>≤</sup><sub>α,step</sub></td><td>17</td><td>1766</td><td>15898</td><td>3564</td><td>12218</td><td>374.6783</td><td>343.3451</td><td>0.1473254</td><td>2792710</td><td>3204147</td><td>2703091</td><td>0.116795</td><td>2786414</td><td>3.1248</td></tr><tr><td>CD<sup>≤</sup><sub>α,exp</sub></td><td>17</td><td>428</td><td>10637</td><td>2910</td><td>7611</td><td>108.0555</td><td>99.91148</td><td>0.1166937</td><td>2792710</td><td>3118601</td><td>2703091</td><td>0.11909</td><td>2786414</td><td>3.156957</td></tr><tr><td>CD<sup>≤</sup><sub>α,p.l.</sub></td><td>17</td><td>373</td><td>10593</td><td>2994</td><td>7483</td><td>111.187</td><td>104.1512</td><td>0.667523</td><td>2792710</td><td>4656907</td><td>2703091</td><td>0.118775</td><td>2786414</td><td>3.128587</td></tr><tr><td>CD</td><td>18</td><td>292</td><td>15879</td><td>3421</td><td>12342</td><td>254.1129</td><td>247.1444</td><td>1.32928</td><td>3995137</td><td>9305794</td><td>3901389</td><td>0.138112</td><td>3984164</td><td>2.84785</td></tr><tr><td>CD<sub>α</sub></td><td>18</td><td>260</td><td>13999</td><td>2578</td><td>11305</td><td>186.3094</td><td>180.4152</td><td>1.32928</td><td>3995137</td><td>9305794</td><td>3901389</td><td>0.137736</td><td>3984164</td><td>2.813004</td></tr><tr><td>CD<sup>≤</sup></td><td>18</td><td>745</td><td>14809</td><td>3487</td><td>11206</td><td>304.9595</td><td>288.8249</td><td>0.1803957</td><td>3995137</td><td>4715843</td><td>3901389</td><td>0.138658</td><td>3984164</td><td>2.836295</td></tr><tr><td>CD<sup>≤</sup><sub>α,step</sub></td><td>18</td><td>1754</td><td>14476</td><td>2963</td><td>11397</td><td>412.8411</td><td>375.2467</td><td>0.1507036</td><td>3995137</td><td>4597219</td><td>3901389</td><td>0.137465</td><td>3984164</td><td>2.837702</td></tr><tr><td>CD<sup>≤</sup><sub>α,exp</sub></td><td>18</td><td>1463</td><td>11999</td><td>2605</td><td>9278</td><td>295.9352</td><td>263.9823</td><td>0.1306179</td><td>3995137</td><td>4516974</td><td>3901389</td><td>0.137983</td><td>3984164</td><td>2.838323</td></tr><tr><td>CD<sup>≤</sup><sub>α,p.l.</sub></td><td>18</td><td>1869</td><td>11059</td><td>2567</td><td>8376</td><td>363.6869</td><td>323.5905</td><td>0.1566945</td><td>3995137</td><td>4621153</td><td>3901389</td><td>0.138291</td><td>3984164</td><td>2.827994</td></tr><tr><td>CD</td><td>19</td><td>262</td><td>16222</td><td>3636</td><td>12470</td><td>275.2622</td><td>269.0719</td><td>1.524055</td><td>3673307</td><td>9271627</td><td>3567235</td><td>0.13669</td><td>3667815</td><td>3.471493</td></tr><tr><td>CD<sub>α</sub></td><td>19</td><td>218</td><td>14004</td><td>2750</td><td>11138</td><td>174.8372</td><td>169.6978</td><td>1.524055</td><td>3673307</td><td>9271627</td><td>3567235</td><td>0.137304</td><td>3667815</td><td>3.46598</td></tr><tr><td>CD<sup>≤</sup></td><td>19</td><td>452</td><td>14978</td><td>3639</td><td>11223</td><td>258.1576</td><td>247.8717</td><td>0.150468</td><td>3673307</td><td>4226022</td><td>3567235</td><td>0.136529</td><td>3667815</td><td>3.474766</td></tr><tr><td>CD<sup>≤</sup><sub>α,step</sub></td><td>19</td><td>741</td><td>11471</td><td>3061</td><td>8294</td><td>187.0043</td><td>170.3391</td><td>0.1261294</td><td>3673307</td><td>4136619</td><td>3567235</td><td>0.135202</td><td>3667815</td><td>3.461251</td></tr><tr><td>CD<sup>≤</sup><sub>α,exp</sub></td><td>19</td><td>1586</td><td>12301</td><td>2652</td><td>9533</td><td>466.5733</td><td>419.8394</td><td>0.1167152</td><td>3673307</td><td>4102037</td><td>3567235</td><td>0.187875</td><td>3667815</td><td>4.748303</td></tr><tr><td>CD<sup>≤</sup><sub>α,p.l.</sub></td><td>19</td><td>1644</td><td>10005</td><td>2557</td><td>7332</td><td>318.4726</td><td>282.0285</td><td>0.2258534</td><td>3673307</td><td>4502936</td><td>3567235</td><td>0.139386</td><td>3667815</td><td>3.485296</td></tr><tr><td>CD</td><td>20</td><td>296</td><td>16545</td><td>3731</td><td>12698</td><td>412.4823</td><td>404.1546</td><td>1.505111</td><td>3785338</td><td>9482692</td><td>3690785</td><td>0.171325</td><td>3773980</td><td>5.089575</td></tr><tr><td>CD<sub>α</sub></td><td>20</td><td>236</td><td>13794</td><td>2722</td><td>10956</td><td>229.3587</td><td>222.8188</td><td>1.505111</td><td>3785338</td><td>9482692</td><td>3690785</td><td>0.17229</td><td>3773980</td><td>5.083105</td></tr><tr><td>CD<sup>≤</sup></td><td>20</td><td>363</td><td>15156</td><td>3734</td><td>11306</td><td>349.6746</td><td>339.7053</td><td>0.1307754</td><td>3785338</td><td>4280367</td><td>3690785</td><td>0.170213</td><td>3773980</td><td>5.09293</td></tr><tr><td>CD<sup>≤</sup><sub>α,step</sub></td><td>20</td><td>3740</td><td>15163</td><td>3328</td><td>11719</td><td>1286.835</td><td>1188.231</td><td>0.1832943</td><td>3785338</td><td>4479169</td><td>3690785</td><td>0.170728</td><td>3773980</td><td>5.095108</td></tr><tr><td>CD<sup>≤</sup><sub>α,exp</sub></td><td>20</td><td>1892</td><td>12097</td><td>3035</td><td>8946</td><td>608.4735</td><td>557.8983</td><td>1.405129</td><td>3785338</td><td>9104224</td><td>3690785</td><td>0.170987</td><td>3773980</td><td>5.090923</td></tr><tr><td>CD<sup>≤</sup><sub>α,p.l.</sub></td><td>20</td><td>241</td><td>9345</td><td>2785</td><td>6444</td><td>110.878</td><td>103.9692</td><td>0.1652763</td><td>3785338</td><td>4410964</td><td>3690785</td><td>0.173597</td><td>3773980</td><td>5.089338</td></tr></tbody></table>