# A two-phase Branch&Cut scheme for Integer Programs with polyhedral symmetries

Pascale Bendotti, Alexandre Heintzmann, Cécile Rottner

► To cite this version:

Pascale Bendotti, Alexandre Heintzmann, Cécile Rottner. A two-phase Branch&Cut scheme for Integer Programs with polyhedral symmetries. 2026. hal-05514821v2

HAL Id: hal-05514821

https://edf.hal.science/hal-05514821v2

Preprint submitted on 18 Feb 2026

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

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

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

Distributed under a Creative Commons CC BY 4.0 - Attribution - International License
A two-phase Branch&Cut scheme for Integer Programs with
polyhedral symmetries

Pascale Bendotti¹

Alexandre Heintzmann*

Cécile Rottner¹

¹ EDF Lab Paris-Saclay, 7 Boulevard Gaspard Monge, 91120 Palaiseau, France

February 17, 2026

Abstract

In this paper, we consider polyhedral symmetries, defined as permutations of variables that preserve feasibility independently of the objective function. Unlike classical symmetry-handling techniques, we develop a Branch&Cut framework with a separation in two-phases that leverages these symmetries to structure families of valid inequalities and enhance their separation. The first phase generates representative valid inequalities based solely on the constraint set, while the second phase separates their symmetry orbits during the Branch-and-Cut process. For column-wise symmetric polyhedral symmetry groups, we show that the orbit-separation problem reduces to a maximum matching problem which can be solved in polynomial time. We apply the proposed framework to the Symmetric-weight Chain Precedence Knapsack problem, a knapsack variant arising in Hydro Unit Commitment problems at EDF. Computational results show that exploiting polyhedral symmetries significantly strengthens the separation process and improves overall solution performance.

# 1 Introduction

We consider an integer linear program (P) $\min\{cx \mid x \in \mathcal{X}\}$, where the feasible solution set $\mathcal{X}$ is defined by linear inequalities and integrality requirements. The polytope $\mathcal{P}$ associated to problem (P) is the convex hull of solutions of (P): $\mathcal{P} = \text{conv}\{x \in \mathcal{X}\}$.

Symmetries are well known to severely affect the performance of Branch&Bound and Branch&Cut algorithms, by creating large sets of equivalent solutions. Classical approaches to handle symmetries in integer programming focus on *objective-preserving symmetries*, i.e., permutations of variables that map feasible solutions to feasible solutions with identical objective value. These symmetries induce orbits of solutions with identical objective value, and symmetry-handling techniques typically aim at selecting a representative solution in each orbit, for instance through lexicographic constraints or orbitopes (Friedman 2007, Kaibel et al. 2007, Margot 2009, Bendotti et al. 2020, 2021).

In this paper, our approach does not aim at reducing the feasible region by selecting representatives, but at enlarging the cutting plane power by exploiting orbits of valid inequalities. We then adopt a different perspective than classical literature on symmetries and focus on a broader notion of symmetry, which we call *polyhedral symmetries*. A polyhedral symmetry is defined as a permutation of the variables that preserves the feasible set $\mathcal{X}$, independently of the objective function. This notion strictly generalizes classical symmetries and naturally arises in many integer programs with interchangeable components, identical resources, or repeated structures. Despite their prevalence, polyhedral symmetries have received little attention comparatively to objective-preserving symmetries. For the specific case of the knapsack polytope with a few symmetric weights, Hojny and Roy (2024) define equivalence classes of lifted cover inequalities and take advantage of such symmetric structure to develop an efficient separation algorithm for these inequalities.

<footnote>*This research was carried during A. Heintzmann’s PhD, funded by EDF.</footnote>
Then, rather than breaking symmetries among feasible solutions with identical objective values, our approach exploits polyhedral symmetries to strengthen cutting-plane algorithms. The key observation is that polyhedral symmetries induce *orbits of valid inequalities*: if an inequality is valid (or facet-defining) for *P*, then all its images under polyhedral symmetries are valid (or facet-defining) as well. This structure can be leveraged to enhance separation procedures by searching, within an entire orbit of inequalities, for the most violated representative at a given fractional point. As polyhedral symmetries generalize classical objective-preserving symmetries, such approach can be applied to larger classes of problems featuring strong polyhedral symmetries but not necessarily objective-preserving symmetries.

Based on this idea, we propose a generic *two-phase Branch&Cut framework*, where valid inequality separation acts in two distinct phases. The first phase takes place before root node solving while the second phase corresponds to a polyhedral-symmetry-exploiting separation of fractional points during the B&C scheme. In the first phase, carried out independently of the objective function, a pool of representative valid inequalities is generated using purely structural properties of the constraint set. In a second phase, during the Branch&Cut process, the orbits of these inequalities are separated dynamically by solving an *orbit-separation problem*. This strategy contrasts with classical symmetry-breaking techniques: instead of discarding symmetric objects, we exploit them to strenghten the cutting-plane procedures during B&C. Moreover, the first phase does not depend on the objective coefficients. Therefore, for problems solved repeatedly (eg, in a decomposition framework), this two-phase approach is particularly relevant as the first phase can be solved just once to benefit to the solution scheme of all problems featuring the same constraint set.

For a broad and practically relevant class of polyhedral symmetry groups, namely *column-wise symmetric groups*, we show that the orbit-separation problem can be solved in polynomial time. More precisely, we prove that finding the most violated inequality within an orbit can be reduced to a maximum-weight matching problem on a bipartite graph. This result makes the proposed framework computationally tractable and suitable for large-scale applications.

We illustrate the proposed approach on the *Symmetric-weight Chain Precedence Knapsack problem* (SCPK), defined as a knapsack problem where groups of objects are subject to chain-precedence constraints. Polyhedral symmetries arise due to symmetric weights between objects of different groups. The (SCPK) captures the core polyhedral structure of Hydro Unit Commitment problems solved daily at EDF (Hechme-Doukopoulos et al. (2010), Artigues et al. (2025)). Building on recent polyhedral results for the (SCPK) (Bendotti et al. (2025)), we demonstrate how polyhedral symmetries can be exploited to strengthen the separation of strong valid inequalities within a 2-phase Branch&Cut algorithm. Computational experiments show that the proposed two-phase approach significantly improves the separation power and overall solution performance.

The paper is structured as follows. Section 2 introduces the notion of polyhedral symmetries and formalizes the proposed two-phase Branch-and-Cut framework. We show how polyhedral symmetries induce orbits of valid inequalities and formulate the associated orbit-separation problem. For column-wise symmetric polyhedral symmetry groups, we prove that this separation problem can be solved in polynomial time via a maximum-weight matching formulation. Section 3 is devoted to the Symmetric-weight Chain Precedence Knapsack problem (SCPK). We describe its polyhedral structure, review the most relevant classes of valid inequalities, and recall recent results on pattern inequalities that will be exploited in the sequel. In Section 4, we use those polyhedral results to specify first-phase algorithms for the (SCPK). We introduce a graph-based model that allows us to compute the rank of a pattern and to verify necessary conditions for generating strong pattern inequalities. On this base we describe the first phase of the proposed two-phase Branch-and-Cut approach applied to the (SCPK), namely the generation of representative patterns based solely on the constraint structure and facet-defining conditions. Section 5 reports computational experiments on (SCPK) instances to demonstrate the effectiveness of the proposed 2-phase B&C scheme to strengthen the separation process and improve overall solution performance. Note that this paper is an extended version of Heintzmann et al. (2024).
# 2 Two-phase Branch&Cut algorithm

First we introduce a few definitions and results regarding polyhedral symmetries. On this basis, we give the scheme of the proposed two-phase B&C approach. Finally, we show that for specially structured polyhedral symmetry groups, the problem of finding the most violated inequality among an inequality orbit can be solved in polynomial time.

## 2.1 Polyhedral symmetries

We define *polyhedral symmetries* of problem (P) as symmetries relative to polytope $\mathcal{P}$, regardless of the objective function.

**Definition 1.** For problem (P), a polyhedral symmetry is a permutation $\pi$ of the variables such that for any feasible solution $x \in \mathcal{X}$, $\pi(x)$ is also a feasible solution, i.e. $\pi(x) \in \mathcal{X}$.

We denote by $\mathcal{G}_{\mathcal{P}}$ the polyhedral symmetry group of (P), i.e. the group of all polyhedral symmetries of (P). This is a generalization of the classical concept of symmetry in integer linear programming, which also restricts the objective values of two symmetric solutions to be equal. Classical methods to handle symmetries may not apply to polyhedral symmetries. In particular, the idea is not to find a representative solution and discard other symmetric solutions, but rather to capture all polyhedral symmetric solutions in a special structure that can be exploited when generating valid inequalities.

**Definition 2.** For a given inequality $ax \le b$ and a given variable permutation $\pi$, the image of inequality $ax \le b$ through $\pi$ is defined as: $\pi(ax \le b) = \pi(a)x \le b$

The following simple results show that polyhedral symmetries directly extends to valid inequalities and facet defining inequalities.

**Property 1.** For any valid inequality $ax \le b$ for $\mathcal{P}$, inequality $\pi(ax \le b)$ is also valid, for any polyhedral symmetry $\pi \in \mathcal{G}_{\mathcal{P}}$

*Proof.* Let $\pi \in \mathcal{G}_{\mathcal{P}}$. For any $x$, $ax \le b$ is valid therefore $a\pi(x) \le b$. By scalar product properties, it yields $\pi(a)x \le b$ for any $x$. $\square$

**Property 2.** For any facet-defining inequality $ax \le b$ of $\mathcal{P}$, inequality $\pi(ax \le b)$ is also facet-defining, for any polyhedral symmetry $\pi \in \mathcal{G}_{\mathcal{P}}$.

*Proof.* Let $\pi \in \mathcal{G}_{\mathcal{P}}$ and let $d$ be the dimension of polytope $\mathcal{P}$. If an inequality $ax \le b$ is facet-defining for (P), there are $d+1$ affinely independent valid solutions verifying this inequality to equality. Let $x_0$ be such a solution satisfying $ax_0 = b$. Then by scalar product properties, we also have $\pi(a)\pi(x_0) = b$. Thus there are $d+1$ affinely independent points satisfying $\pi(ax \le b)$ to equality, therefore it is also facet-defining. $\square$

Based on these properties, we can define orbits of inequalities and work with inequality-representatives.

**Definition 3 (Inequality orbit).** For a given inequality $ax \le b$, the orbit $\mathcal{O}(ax \le b)$ of $ax \le b$ under group $\mathcal{G}_{\mathcal{P}}$ is the set of all inequalities obtained by applying polyhedral symmetries to $ax \le b$:

$$ \mathcal{O}(ax \le b) = \{ \pi(a)x \le b \mid \pi \in \mathcal{G}_{\mathcal{P}} \} $$

As the classical symmetry-breaking approaches, we can define an arbitrary representative for each inequality orbit.

**Definition 4 (Orbit-separation problem).** For a given inequality $ax \le b$ and a given point $\tilde{x}$, the orbit-separation problem consists in finding the most violated inequality at point $\tilde{x}$ in $\mathcal{O}(ax \le b)$.

The proposed two-phase Branch&Cut will rely on these concepts and properties to propose a separation framework exploiting polyhedral symmetries.
## 2.2 Two-phase Branch&Cut scheme

The proposed scheme works in two phases:

### First phase: inequality representatives generation before root node

* Based on structural properties (necessary facet-defining conditions for (P), ...), generate a pool $V$ of valid inequality representatives.

### Second phase: separation exploiting polyehedral symmetries

* For a given fractional point $\tilde{x}$ to separate :

* For each inequality-representative $ax \le b$ of the pool $V$

* Solve the orbit-separation problem for inequality $ax \le b$ at point $\tilde{x}$.

As it will be detailed in Section 2.3, when the polyhedral symmetry group has a special structure, the orbit-separation problem can be solved efficiently in polynomial time.

Note that the first phase does not depend on the objective coefficients. Therefore, for problems solved repeatedly (for example, in a decomposition framework), this two-phase approach is particularly relevant as the first phase can be solved just once to benefit to the solution scheme of all problem featuring the same constraint set.

## 2.3 The orbit separation problem

For a given fractional point $\tilde{x}$ and a given inequality $ax \le b$, finding the most violated inequality in the orbit of $ax \le b$ corresponds to finding the permutation $\pi \in G_P$ yielding the largest violation $\pi(a)\tilde{x} - b \ge 0$. For polyhedral symmetry groups with a particular structure, we provide an algorithm to find the most violated inequality within $O(ax \le b)$ in polynomial time.

Suppose variables $x$ can be arranged in a matrix with $I \ge 1$ columns and $J \ge 1$ rows. We denote by $x_{ij}$ the element at column $i$ and row $j$. We denote by $S_p$ the symmetric group (i.e. the set of all permutations) acting on $p$ columns of such a matrix.

**Definition 5 (Column-wise symmetric group).** Group $G$ is a column-wise symmetric group if it is a cartesian product of symmetric group acting on the columns of $x$: $G = S_{I_1} \times \dots \times S_{I_p}$, where $I_1, \dots, I_p$ are positive integers such that $\sum_{i=1}^p I_i = I$.

In the rest of the paper, integer program featuring polyhedral symmetry groups with such structure are called column-wise symmetric problems. The following examples show that such structure is quite common.

**Example 1 (Knapsack problem with a few different weights).** Consider a Binary Knapsack Problem with $I$ items and capacity $C$, where items can be partitioned into $p \ge 1$ groups such that all items within a same group share the same weight. Let $I_1, \dots, I_p$ denote the sizes of these groups, with $\sum_{\ell=1}^p I_\ell = I$. The problem can be written as

$$ \max \sum_{i=1}^{I} v_i x_i \quad \text{s.t.} \quad \sum_{i=1}^{I} w_{\ell(i)} x_i \le C, \quad x_i \in \{0, 1\}, $$

where $\ell(i)$ denotes the group index of item $i$. Any permutation of variables within a same weight group preserves the feasible region of the problem, independently of the objective coefficients.

Therefore, the polyhedral symmetry group of the knapsack polytope is a column-wise symmetric group: $G_P = S_{I_1} \times \dots \times S_{I_p}$. However, note that as the objective function differs for each item, these are not objective-preserving symmetries, therefore they cannot be exploited with classical symmetry-breaking methods. $\square$

<figure><img src="image_2.png" /></figure>
**Example 2 (Unit Commitment problem).** Consider a Unit Commitment (UC) problem over a time horizon *T*, involving a set of thermal or hydro units with identical technical characteristics. Let $x_{i,t}$ be a binary variable indicating whether unit *i* is on at time period *t*. Typical UC constraints include coupling constraints, such as demand constraints, and units' individual constraints, such as production limits, minimum up- and down-times and ramp constraints. When several units share identical constraints and parameters, any permutation of these units preserves feasibility, regardless of the objective function. By arranging the decision variables in a matrix with units as columns and time periods as rows, the polyhedral symmetry group of the UC polytope is a column-wise symmetric group $G_P = S_{I_1} \times \cdots \times S_{I_p}$, where each symmetric group $S_{I_l}$ acts on the set of identical units within a given class. □

In the following, we show that for column-wise symmetric problems, finding the most violated inequality among an inequality orbit can be done by solving a Maximum Matching Problem (MM).

**Definition 6 (Maximum Matching Problem).** Let $\mathcal{H}$ be a weighted bipartite graph. The (MM) is to find the set of edges $E$, such that at most one edge of $E$ is incident to each vertex of $\mathcal{H}$, while maximizing the sum of the weight of $E$.

**Property 3.** Consider a column-wise symmetric integer program. For a given inequality $ax \le b$ and a given fractional point $\tilde{x}$, a permutation $\pi$ maximizing the violation of inequality $\pi(a)x \le b$ at point $\tilde{x}$ can be obtained by solving an instance of the (MM).

*Proof.* Note that in this proof, we use the terms image and preimage of a function in their usual set-theoretic sense. The aim is to find the permutation $\pi$ maximizing $\sum_{i=1}^I \sum_{j=1}^J a_{\pi(i)j} \tilde{x}_{ij}$. To do so, we can build a bipartite graph $\mathcal{H} = (\mathcal{H}_1, \mathcal{H}_2, E)$. Set $\mathcal{H}_1 = \{1, \dots, I\}$ corresponds to the preimage of any column permutation $\pi$ and set $\mathcal{H}_2 = \{1, \dots, I\}$ corresponds to the image of $\pi$. In the set of edges $E$ there is an edge $(i, i')$ for each $i \in \mathcal{H}_1$, $i' \in \mathcal{H}_2$ such that $i$ and $i'$ are in the same orbit. Edge $(i, i')$ has a weight equal to $\sum_{j=1}^J a_{\pi(i)j} \tilde{x}_{ij}$. Solving this (MM) to optimality yields a matching maximizing the weight of the considered edges. One can deduce a permutation from this matching: $\pi(i) = i'$ if edge $(i, i')$ is in the matching. As the (MM) is solved to optimality, permutation $\pi$ is such that $\sum_{i=1}^I \sum_{j \in S_i(\mathcal{P})} \tilde{x}_{\pi(i)j}$ is maximized. □

As the (MM) is a problem that can be solved in polynomial time so is the orbit-separation problem under a column-symmetric polyhedral symmetry group. The (MM) can be solved with the Hungarian algorithm Kuhn (1955), of complexity $O(|\mathcal{H}_1| + |\mathcal{H}_2|)^4$. A more recent version Edmonds and Karp (1972) is of complexity $O(|\mathcal{H}_1| + |\mathcal{H}_2|)^3$.

## 2-phase Branch&Cut for column-wise symmetric problems

The first phase of the proposed 2-phase B&C scheme aims at generating representative for equivalence classes of valid inequalities. Therefore, the underlying algorithms are based on the considered problem polyhedral structure (non domination properties, facet defining conditions...). On the opposite, the second phase exploits the representatives generated during the first phase in a generic manner for any column-wise symmetric problem. In the following, we apply the 2-phase B&C scheme to the (SCPK), therefore we specify dedicated first-phase algorithms in Section 4. Note that the second phase algorithms are completely generic and need not be detailed for the (SCPK) specifically.

## 3 The Symmetric-weight Chain Precedence Knapsack problem

Consider *I* groups of *J* elements, where *I* and *J* are positive integers. Let item (i, j) be element *j* of group *i*. Item (i, j) has weight $w_{ij} \ge 0$ and value $v_{ij}$. Within each group, order constraints are such that any item (i, j) can be selected provided item (i, j - 1) is selected, thus inducing chain precedence constraints. Let *C* be the maximum capacity. The Chain Precedence Knapsack problem (CPK) is to maximize the total value of the selected items, while the chain precedence constraints are verified, and the total weight of the selected items is less than or equal to *C*. The Symmetric-weight Chain Precedence Knapsack problem (SCPK) (Bendotti et al. (2025)) is a (CPK) where item (i, j) has weight
$w_{ij} = w_j$, i.e., the weight of item $(i, j)$ does not depend on the group index $i$. It means that items $(i, j)$ and $(i', j)$ have the same weight, thus the knapsack is symmetrically weighted with respect to the groups. We define $(I, J, w, v, C)$ an instance of the (SCPK).

The motivation for studying the (SCPK) is that it is the core structure of the Hydro Unit Commitment (HUC) problem (Hechme-Doukopoulos et al. (2010), Artigues et al. (2025)), which is a production scheduling problem relative to hydroelectric plants.

The Knapsack Problem (KP) polytope and its variants have been widely studied (Hojny et al. (2020)). From a theoretical standpoint, the (SCPK) exhibits an interesting position within the family of knapsack problems. It is a special case of both the (PK) (Boyd (1993)) and (DK) (Salem et al. (2018)), yet it is neither a generalization nor a special case of the (BK) (Balas (1975)). Furthermore, the (SCPK) is not a Multiple Knapsack Problem (MK) (Ferreira et al. (1996)) despite the presence of multiple groups. Indeed, a capacity constraint is applied on all groups simultaneously in the (SCPK), whereas it is applied for each group individually in the (MK).

## 3.1 The Symmetric-weight Chain Precedence Knapsack polytope

Let $x_{ij}$ be a binary variable such that $x_{ij} = 1$ if item $(i, j)$ is selected in the solution. We denote $\mathcal{V}$ the set of variables $x_{ij}$ for the (SCPK). The total number of variables is $n = I \times J$. The (SCPK) can be formulated as follows.

$$ (F_{\text{SCPK}}) \qquad \max_{x_{ij} \in \{0,1\}} \sum_{i=1}^{I} \sum_{j=1}^{J} v_{ij}x_{ij} \\ \text{s.t.} \qquad \sum_{i=1}^{I} \sum_{j=1}^{J} w_{j}x_{ij} \leq C, \\ x_{ij} \leq x_{ij-1} \qquad \forall x_{ij} \in \mathcal{V}, j \geq 2 $$

The objective function is to maximize the total value of the selected items. The first set of inequalities corresponds to the capacity constraints, and the second set of inequalities corresponds to the chain precedence constraints. We define polytope $P_{(SCPK)}$ as the convex hull of (SCPK) solutions:

$$ P_{(SCPK)} = \text{conv}\{x \in \{0,1\}^n : x \text{ satisfies } (1)-(2)\}. $$

Note that the (SCPK) is column-wise symmetric, as any permutation of the groups in a feasible solution leads to another feasible solution. However the objective function differs from a group to another, thus these are not objective-preserving symmetries.

## 3.2 State-of-the-art: Minimum induced cover inequalities

As shown in Bendotti et al. (2025), valid inequalities from the literature that are the most relevant for the (SCPK) are relative to the (PK), and are called *minimum induced cover* (MIC) inequalities. Therefore, in this section we propose a brief state-of-the-art focused on MIC inequalities and their liftings. Let $(V, \leq)$ be a partially ordered set of items. Item $j$ covers item $i$ if there is no $k$ such that $j \prec k \prec i$. The (PK) can be formulated:

$$ \max_{x_j \in \{0,1\}} \left\{ \sum_{j \in V} v_j x_j \quad \text{s.t.} \quad \sum_{j \in V} w_j x_j \leq C, \quad x_j \leq x_i \quad \text{if } j \text{ covers } i \right\}. $$

In the classical case of the (BK), covers, minimal covers and minimal cover are defined by Balas (1975). A cover $U \subseteq V$ is a set of items such that $\sum_{j \in U} w_j > C$. A minimal cover $U \subseteq V$ is a cover such that no proper subset of $U$ is also a cover, $\sum_{j \in U \setminus \{i\}} w_j \leq C$, for each $i \in U$.

Minimal cover inequalities can be adapted to the (PK). Let $A$ be the arcs of the precedence graph. Set $A$ is modified such that if $(i, j) \in A$ and $(j, k) \in A$ then $(i, k) \in A$. Let $U$ be a variable set. We define $U_p$ the set of predecessors of $U$. More precisely, $U_p$ contains all $i \notin U$ such that $(i, j) \in A$ and $j \in U$. An induced cover is a set $U \subseteq V$, such that there is no arc between a pair of items in $U$ and $\sum_{j \in U} w_j + \sum_{k \in U_p} w_k \geq C$. A Minimal Induced Cover (MIC) is an induced cover $U$ such that $\sum_{j \in U \setminus \{i\}} w_j + \sum_{k \in U_p} w_k \leq C$, for each $i \in U$. With $U$ a MIC, the MIC inequality is: $\sum_{j \in U} x_j \leq |U|-1$. These MIC inequalities have been enhanced with a lifting procedure (Park and Park (1997)). From a MIC $U$, the procedure described uses items that have at least two successors of the precedence graph in $U$. A sequential lifting procedure has also been developed (van de Leensel et al. (1999)). Consider $U$ a MIC and $U_p$ the predecessors of $U$, we define $U_r = V \setminus (U \cup U_p)$. The sequential lifting procedure computes the coefficients $\alpha_j$ (resp. $\beta_j$), for each $j \in U_p$ (resp. $j \in U_r$), leading to a lifted inequality:
$\sum_{j \in U} x_j + \sum_{j \in U_p} \alpha_j(1 - x_j) + \sum_{j \in U_r} \beta_j x_j \le |U| - 1$. Computing the optimal values of coefficients $\alpha_j$, defined as *downlifting*, can be done in polynomial time. However computing the optimal values of coefficients $\beta_j$, defined as *uplifting*, is proven to be NP-hard.

Espinoza et al. (2015) defines a separation procedure, which computes bounds $\alpha_j$ and $\beta_j$ in a reduced precedence graph. The results show that computing bounds $\beta_j$ takes large computational times, even if the problem is relaxed.

### 3.3 Extension of the MIC inequalities to the (SCPK) chain precedence constraints.

From the inequalities of the (PK) previously described, downlifted and uplifted MIC inequalities dominate minimal cover inequalities and MIC inequalities.

Let $U$ a MIC for the (SCPK), $U_p$ the set of predecessors of $U$ and $U_r$ the set of all items that are not in $U \cup U_p$. Downlifted and uplifted MIC inequalities can be adapted to the (SCPK), by introducing $\alpha_{ij}$ and $\beta_{ij}$. In this case, they have the following form: $\sum_{(i,j) \in U} x_{ij} + \sum_{(i,j) \in U_p} \alpha_{ij}(1 - x_{ij}) + \sum_{(i,j) \in U_r} \beta_{ij}x_{ij} \le |U| - 1$. First, we have the following property.

**Property 4.** For all $(i, j) \in U_p$, the downlifting procedure yields $\alpha_{ij} = 0$ for the (SCPK).

The proof and an illustration are given in 7.1. This property means that there is no need to downlift an inequality for the (SCPK), as it can only yield coefficient 0. However, there is no similar proof for coefficients $\beta_{ij}$, i.e., for the uplifting. Hence, we introduce the Uplifted MIC (UMIC) inequalities for the (SCPK), with the following form.

**Definition 7 (UMIC inequalities for the (SCPK)).** The UMIC inequalities applied to the (SCPK) have the following form: $\sum_{(i,j) \in U} x_{ij} + \sum_{(i,j) \in U_r} \beta_{ij}x_{ij} \le |U| - 1$.

Valid UMIC inequalities can be obtained using the procedure of Espinoza et al. (2015), and are experimentally compared to the inequalities introduced this paper in **Section 5**.

### 3.4 Pattern inequalities

In this section we recall polyhedral results for the (SCPK) from Bendotti et al. (2025) that we will use for the numerical experiments. Without loss of generality, we suppose in the following that $P_{(SCPK)}$ is full-dimensional. A pattern $\mathcal{P}$ is a collection of $I$ sets $S_i(\mathcal{P}) \subseteq \{1, \dots, J\}, i \le I$. A set $S_i(\mathcal{P})$ contains the indices $j$ of the items in a same group. The sets of a pattern are not ordered, meaning that a pattern represents any group permutation of the (SCPK). The aim is to use such patterns as representatives for orbits of valid inequalities. For this purpose, for a given permutation $\pi$ of $\{1, \dots, I\}$, the item set $\mathcal{X}$ associated with pattern $\mathcal{P}$ and permutation $\pi$ is such that $(i, j) \in \mathcal{X}$ for each $j \in S_{\pi(i)}(\mathcal{P})$. We denote $\Omega(\mathcal{P})$ the set of all item sets associated with $\mathcal{P}$. We also denote $\mathcal{X}(\mathcal{P})$ the variable set associated to $\mathcal{P}$ and the identity permutation $\pi_{id}$. The idea is that $\mathcal{X}(\mathcal{P})$ will act as a representative for $\Omega(\mathcal{P})$ in the properties. We define the cardinality of a pattern $\mathcal{P}$ as $\text{card}(\mathcal{P}) = |\mathcal{X}(\mathcal{P})|$. The rank of a pattern $\mathcal{P}$ is the tightest valid upper bound for the sum of variables in $\mathcal{X}(\mathcal{P})$: $\text{rank}(\mathcal{P}) = \{\max \sum_{(i,j) \in \mathcal{X}(\mathcal{P})} x_{ij} : \text{satisfying } (1) - (2)\}$. The rank of a pattern can be computed with a shortest path algorithm (see Section 4.2).

**Definition 8 (Pattern inequalities).** The pattern inequality $(\pi(\mathcal{X}))$ associated with a pattern $\mathcal{P}$ and an item set $\mathcal{X} \in \Omega(\mathcal{P})$ is $\sum_{(i,j) \in \mathcal{X}} x_{ij} \le \text{rank}(\mathcal{P})$.

By definition of the rank, pattern inequalities are valid for $P_{(SCPK)}$. A pattern $\mathcal{P}$ is facet-defining if for any $\mathcal{X} \in \Omega(\mathcal{P})$, inequality $(\pi(\mathcal{X}))$ is facet-defining for the (SCPK). We provide three necessary conditions for a pattern to be facet-defining. Note that $\mathcal{P}$ is facet-defining if and only if inequality $(\pi(\mathcal{X}(\mathcal{P})))$ is facet-defining. Therefore, all conditions are stated for $\mathcal{X}(\mathcal{P})$ but by symmetry, all polyhedral results proven for $\mathcal{X}(\mathcal{P})$ also hold for any $\mathcal{X} \in \Omega(\mathcal{P})$.

Two of these conditions rely on the following definitions of set weights $s$ and $k$-intersections. For $\mathcal{X} \in \Omega(\mathcal{P})$, and for all $i \le I, j \le J$, the set weights are
$$
s_{ij}(\mathcal{X}) = \begin{cases} 0 & \text{if } (i,j) \notin \mathcal{X}, \\ \sum_{k=j'+1}^{j} w_k & \text{if } (i,j) \in \mathcal{X} \text{ with } j' = \max\{j'|(i,j') \in \mathcal{X}, j' < j\}, \\ \sum_{k=1}^{j} w_k & \text{if } (i,j) \in \mathcal{X} \text{ and } (i,j') \notin \mathcal{X}, \forall j' < j. \end{cases}
$$

The coefficient $s_{ij}(\mathcal{X})$ embeds the chain precedence constraints. Indeed, if $x_{ij} = 1$, $(i,j) \in \mathcal{X}$, then all $x_{ij'} = 1$, $j' \le j$, even for $(i,j') \notin \mathcal{X}$. Thus, if $x_{ij} = 1$ then the weights of all item $(i,j') \notin \mathcal{X}$ should be accounted for, which is the purpose of coefficients $s_{ij}(\mathcal{X})$.

**Definition 9 (k-intersection).** Let $\mathcal{X}, \mathcal{Y}$ be item sets. Item set $\mathcal{Y}$ is a k-intersection of $\mathcal{X}$ if the three following conditions hold: 1) $|\mathcal{Y} \cap \mathcal{X}| = k$, 2) for each item $(i,j) \in \mathcal{Y}$ if $(i,j') \in \mathcal{X}$ with $j' \le j$, then $(i,j') \in \mathcal{Y}, 3) \sum_{(i,j) \in \mathcal{Y}} s_{ij}(\mathcal{Y}) \le C$.

Thus, a k-intersection of $\mathcal{X}$ defines a set of $k$ items of $\mathcal{X}$ that can all be selected simultaneously in a feasible solution of the (SCPK). Consequently, if there exists a k-intersection of $\mathcal{X}$, then there is a feasible solution where $k$ items of $\mathcal{X}$ are selected.

**Property 5 (Facet-defining conditions).** If pattern $\mathcal{P}$ is facet-defining, then it verifies conditions

(i) For every set $S_i(\mathcal{P}) \in \mathcal{P}$ : $|S_i(\mathcal{P})| \ge 1$

(ii) For each $i \le I$, there is $\mathcal{Y}$ a k-intersection of $\mathcal{X}(\mathcal{P})$ with $(i, J) \in \mathcal{Y}$

(iii) For each $(i,j) \in \mathcal{X}(\mathcal{P})$, there is $\mathcal{Y}$ a k-intersection of $\mathcal{X}(\mathcal{P})$ with $(i,j-1) \in \mathcal{Y}$ and $(i,j') \notin \mathcal{Y}, \forall j' \ge j$.

For a given pattern $\mathcal{P}$, condition (i) can clearly be verified in linear time. Also, conditions (ii) and (iii) can be verified in polynomial time, by solving a shortest path algorithm at most once for each variable (see Section 4.3). A pattern is *flexible* if it verifies conditions (i), (ii) and (iii). Such conditions are necessary but not sufficient for $\mathcal{P}$ to be facet-defining. However, a minimum dimension can be guaranteed for the faces defined by flexible patterns inequalities.

**Theorem 1 (n-card($\mathcal{P}$) linearly independent points).** Let $\mathcal{P}$ be a flexible pattern and $\mathcal{X} \in \Omega(\mathcal{P})$. There are at least $n-\text{card}(\mathcal{P})$ linearly independent points that verify ($\text{pi}(\mathcal{X})$) to equality.

This result will be used in the first-phase separation to generate strong pattern-inequalities.

# 4 First-phase algorithms for the (SCPK)

The shortest path problem and many of its variants are known to be easy to solve (Bellman (1958), Dijkstra (1959)) when there are no negative cost cycles. In the case of the (SCPK), for a given pattern $\mathcal{P}$, it is possible to define a graph associated with $\mathcal{P}$, for which solving a variant of the shortest path problem provides information on the considered pattern (see Section 4.1). More specifically, algorithms on this graph will be used to compute the rank of pattern $\mathcal{P}$ in Section 4.2 and to verify conditions (ii) and (iii) for $\mathcal{P}$ in Section 4.3. These two algorithms will be used to generate strong representative pattern inequalities in the first phase of the proposed 2-phase B&C scheme, as described in Section 4.4

## 4.1 Graph model for the (SCPK)

Consider a pattern $\mathcal{P}$ and an item set $\mathcal{X} \in \Omega(\mathcal{P})$. Let $G = (W, A)$ be the graph defined as follows. Item set $\mathcal{X}$ is associated with vertex set $W$, a source vertex $p$ and a sink vertex $q$ are added to $W$. For convenience purposes, each vertex in $W$ is denoted by the corresponding variable in $\mathcal{X}$ and the vertices associated with $x_{ij} \in \mathcal{X}$ are renumbered with the same order as in a compact sequence in $\mathcal{X}$. More precisely consider the following renumbering, denoted by parentheses on the indices: For any $x_{ij} \in \mathcal{X}$, we consider $x_{(i)(j)} = x_{ij}$ with $(i) = i$ and $(j)$ the number of variables $x_{ij'} \in \mathcal{X}$ with $j' \le j$. To each couple $(x_{(i)(j)}, x_{(i)(j+1)}) \in \mathcal{X}^2$ corresponds an arc in $A$. To each $x_{(i)(j)} \in \mathcal{X}$ corresponds an arc in $A$ from $x_{(i)(j)}$ to $x_{(i')'(1)}, i' > i$. To each $x_{(i)(1)} \in \mathcal{X}$ corresponds an arc from source vertex $p$ to $x_{(i)(1)}$ in $A$. Similarly, for each vertex $x_{(i)(j)}$, it corresponds an arc from $x_{(i)(j)}$ to sink vertex $q$. Finally the weight of any arc heading to $x_{(i)(j)}$ is $s_{ij}(\mathcal{X})$ as defined in **Section 3.4** and to sink vertex $q$ is 0. Note that graph $G$ is a DAG with non-negative weights, meaning that shortest path problems on $G$ are easy to solve.
**Example 3 (Graph model).** Let $(3, 3, [3, 2, 2], v, C)$ be an instance of the (SCPK). For item set $\mathcal{X} = \{(1,1), (1,2), (2,1), (2,2), (2,3), (3,1), (3,3)\}$, the vertex set is $W = \{p, q, x_{(1)(1)}, x_{(1)(2)}, x_{(2)(1)}, x_{(2)(2)}, x_{(2)(3)}, x_{(3)(1)}, x_{(3)(2)}\}$. **Figure 1** illustrates graph $G$ associated with $\mathcal{X}$.

<figure><img src="image_3.png" /><figcaption>Figure 1: Graph $G$ for **Example 3**</figcaption></figure>

With graph $G$ defined for $\mathcal{X}$, the following property links a path in $G$ to an item set $\mathcal{Y} \subseteq \mathcal{X}$.

**Property 6.** Finding a shortest path in graph $G$ featuring exactly $k+1$ arcs is equivalent to finding $\mathcal{Y} \subset \mathcal{X}$, with $\mathcal{Y}$ featuring the following properties: 1) $|\mathcal{Y}| = k$, 2) for every $(i, j) \in \mathcal{Y}$ for each $(i, j') \in \mathcal{X}$ with $j' < j$, $(i, j') \in \mathcal{Y}$ 3) $\mathcal{Y}$ minimizes its set weights $s_{ij}(\mathcal{Y})$.

The proof is given in Appendix 7.2.

## 4.2 Computing the rank

Clearly, if the sum of the set weights of $\mathcal{Y}$ is smaller than or equal to $C$, then $\mathcal{Y}$ is a $k$-intersection of $\mathcal{X}$. By definition, if a $k$-intersection of $\mathcal{X}$ exists, then there is a feasible solution with $k$ variables of $\mathcal{X}$ to 1. Hence, the idea to compute the rank of a pattern $\mathcal{P}$ is to find a maximum cardinality path in $G$ associated with $\mathcal{X} \in \Omega(\mathcal{P})$, with its total weight being smaller than or equal to $C$. From **Property 6**, if the maximum cardinality path found is with $k+1$ arcs, then the rank of $\mathcal{P}$ is $k$. Such a rank computing algorithm is described in **Algorithm 1**.

The procedure `COMPUTERANK(\mathcal{P})` in **Algorithm 1** returns the rank of $\mathcal{P}$. **Algorithm 1** is a variant of the Bellman-Ford algorithm Bellman (1958) to compute the maximum cardinality path with a total weight less or equal $C$. The cardinality of such a path is then translated into the rank of $\mathcal{P}$. Differences with the Bellman-Ford algorithm are detailed in Appendix 7.3.

**Example 4 (Rank computation example).** Let $(3, 3, [3, 2, 2], v, 6)$ be an instance of the (SCPK). Let $\mathcal{X} = \{(1,1), (1,2), (2,1), (2,2), (2,3), (3,1), (3,3)\}$ be the item set as in **Example 3**, with its graph depicted in **Figure 1**. The table of values computed with **Algorithm 1** for this instance is depicted in **Table 1**, where the value of nbArcs and dist[w] for each $w \in W$ is shown for the initialization (first row), and at the end of each iteration of the while loop (second to fifth row). The algorithm stops when nbArcs = 4 as all values are greater than $C = 6$. Hence the maximum cardinality path is with nbArcs - 1 = 3 arcs, going through nbArcs - 2 vertices besides p and q. Consequently, the rank obtained in this example is 2.
<table><caption>Table 1: Values of Algorithm 1 relative to Example 4.</caption><thead><tr><th>nbArcs</th><th>p</th><th>x<sub>(1)</sub>(1)</th><th>x<sub>(1)</sub>(2)</th><th>x<sub>(2)</sub>(1)</th><th>x<sub>(2)</sub>(2)</th><th>x<sub>(2)</sub>(3)</th><th>x<sub>(3)</sub>(1)</th><th>x<sub>(3)</sub>(3)</th><th>q</th></tr></thead><tbody><tr><td>0</td><td>0</td><td>&infin;</td><td>&infin;</td><td>&infin;</td><td>&infin;</td><td>&infin;</td><td>&infin;</td><td>&infin;</td><td>&infin;</td></tr><tr><td>1</td><td>&infin;</td><td>3</td><td>&infin;</td><td>3</td><td>&infin;</td><td>&infin;</td><td>3</td><td>&infin;</td><td>&infin;</td></tr><tr><td>2</td><td>&infin;</td><td>&infin;</td><td>5</td><td>6</td><td>5</td><td>&infin;</td><td>6</td><td>7</td><td>3</td></tr><tr><td>3</td><td>&infin;</td><td>&infin;</td><td>&infin;</td><td>8</td><td>8</td><td>7</td><td>8</td><td>10</td><td>5</td></tr><tr><td>4</td><td>&infin;</td><td>&infin;</td><td>&infin;</td><td>&infin;</td><td>10</td><td>10</td><td>10</td><td>12</td><td>7</td></tr></tbody></table>

**Algorithm 1** Computing the rank of a pattern

**procedure** `COMPUTERANK`(*pattern* *P*):

build *G* = (*W*, *A*) associated with *X* ∈ Ω(*P*) for permutation π<sub>id</sub>

dist[*p*] ← 0 ; dist[*w*] ← +∞, ∀*w* ∈ *W* \ {*p*} ; nbArcs ← 0

while min(dist) ≤ C do

nDist[*w*] ← ∞, ∀*w* ∈ *W*

for *a* ∈ *A* do

nDist[*a head*] ← min(nDist[*a head*], dist[*a tail*] + *a weight*)

end for

dist ← nDist ; nbArcs ← nbArcs + 1

end while

*k* ← nbArcs − 2

return *k*

end procedure

## 4.3 Verifying conditions (ii) and (iii)

Let $\mathcal{P}$ be a pattern of rank $k$ and $\mathcal{X} \in \Omega(\mathcal{P})$ be the item set associated with $\mathcal{P}$ and with identity permutation $\pi_{id}$. To verify if condition (ii) holds for a group $i$, one needs to find a set $\mathcal{Y}$ being a $k$-intersection of $\mathcal{X}$ with $x_{iJ} \in \mathcal{Y}$. To verify if condition (iii) holds for $x_{ij}$, one needs to find a set $\mathcal{Y}$ being a $k$-intersection of $\mathcal{X}$ with $x_{ij-1} \in \mathcal{Y}$ and $x_{ij} \notin \mathcal{Y}$. Let $u$ be the number of variables $x_{ij'} \in \mathcal{X}$, with $j' \le J$ for condition (ii), and with $j' < j$ for condition (iii). Finding such $k$-intersection is to find a shortest path of length $k - u + 1$ in $G$, without any variable of group $i$. The procedure `VERIFYCONDITION` in Algorithm 2 returns a boolean, equals to True if (ii) is verified for $x_{ij}$, $j < J$, or (iii) is verified for $x_{iJ}$. To do so, we use another variant of the Bellman-Ford algorithm, to compute the path with minimal weight and cardinality $k - u + 1$. Details about the proposed algorithm are described in Appendix 7.4 along with the proof of the following result.

**Property 7.** `VERIFYCONDITION`(*P*, *i*, *j*) returns true only if (ii) is verified for *i*, in the case $j = J+1$, and returns true if (iii) is verified for *i* and *j*, in the case $j \in S_i(P)$.

**Remark 1.** Both algorithms described run in polynomial time with respect to $|W|$, with $|W| = \text{card}(\mathcal{P}) + 2$ in Alg. 1, and $|W| = \text{card}(\mathcal{P}) + 2 - |S_i(\mathcal{P})|$ in Alg. 2. In the case of Alg. 1, the **while** loop can occur $|W|$ times, and in the case of Alg. 2, the **while** loop can occur $\text{rank}(\mathcal{P}) \le |W|$ times. In both cases, in the **while** loop we iterate over the arcs of $A$, meaning $|A| \le |W|^2$ operations. Hence, both algorithms have a worst case time complexity of $O(|W|^3)$. It is worth mentioning that because of the structure of $G$, $|A|$ is usually much smaller than $|W|^2$ as proven in **Property 8**. Hence, these algorithms usually require much less than $|W|^3$ operations.

In the following, we use the standard Landau notation $\Theta(\cdot)$ to denote asymptotically tight bounds.

**Property 8.** Let $\mathcal{P}$ be a pattern and $V$ be the cardinality of the smallest set $S_i(\mathcal{P})$. Let $\mathcal{X} \in \Omega(\mathcal{P})$ be an item set and $G = (W, A)$ be the graph associated with $\mathcal{X}$, then $\frac{|W|^2}{|A|} = \Theta(V)$.

**Theorem 2.** Conditions (i), (ii) and (iii) for a given pattern $\mathcal{P}$ can be verified in polynomial time.

The proofs of these two results are provided respectively in **Appendices 7.5** and 7.6.

## 4.4 First-phase pattern generation algorithm for the (SCPK)

In this section, we describe the algorithm used to generate flexible patterns in the first phase of the proposed Branch&Cut scheme. It is based on the two algorithms defined in **Sections 4.2 and 4.3**,
<caption>**Algorithm 2** Verifying conditions (ii) and (iii)</caption>

**procedure** VERIFYCONDITION pattern $\mathcal{P}$, $i \in \{1, \dots, I\}$, $j \in \{1, \dots, J+1\}$):
  $\triangleright j \le J$ for condition (ii), $j = J+1$ for condition (iii)
  $u \leftarrow |\{j' \in S_i(\mathcal{P}) : j' < j\}|$ ; $\mathcal{X}$ ← set in $\Omega(\mathcal{P})$ for permutation $\pi_{id}$ ; $\mathcal{X}'$ ← $\mathcal{X} \setminus \{x_{ij'} : j' \in S_i(\mathcal{P})\}$
  build $G = (W, A)$ associated with $\mathcal{X}'$
  $dist[p] \leftarrow 0$ ; $dist[w] \leftarrow +\infty$, $\forall w \in W \setminus \{p\}$ ; $nbArcs \leftarrow 0$
  **while** nbArcs $\le$ rank($\mathcal{P}$) $- u$ **do**
    $nDist[w] \leftarrow \infty$, $\forall w \in W$
    **for** $a \in A$ **do**
      $nDist[a head] \leftarrow \min(nDist[a head], dist[a tail] + a$.weight)
    **end for**
    $dist \leftarrow nDist$ ; $nbArcs \leftarrow nbArcs + 1$
  **end while**
  **return** $dist[q] + \sum_{j'=1}^{j-1} w_{j'} \le C$
**end procedure**

as the pattern generation procedure heavily relies on conditions (ii) and (iii) and also on the rank.
The complete procedure is described in Algorithm 3, using Algorithm 1 and Algorithm 2.

<caption>**Algorithm 3** Generating a flexible pattern</caption>

1: **procedure** GENERATEPATTERN( instance $(I, J, w, v, C)$ of the (SCPK))
2: &nbsp;&nbsp;&nbsp;&nbsp;lowerBound $\leftarrow [C/\sum_{j=1}^J w_j]$ ; $k \leftarrow$ random integer in $[lowerBound; n]$ ; $\mathcal{P} \leftarrow I$ sets $\{J\}$
3: &nbsp;&nbsp;&nbsp;&nbsp;**while** $card(\mathcal{P}) \le k$ **do**
4: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$i \leftarrow$ random integer in $[1; I]$ such that $|S_i(\mathcal{P})| < J$ ; $j \leftarrow S_i(\mathcal{P})(1)$ ; $S_i(\mathcal{P}) \leftarrow S_i(\mathcal{P}) \cup \{j-1\}$
5: &nbsp;&nbsp;&nbsp;&nbsp;**end while**
6: &nbsp;&nbsp;&nbsp;&nbsp;**while** (ii) and (iii) not verified for $\mathcal{P}$ **do**
7: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$\mathcal{X}$ ← set in $\Omega(\mathcal{P})$ for permutation $\pi_{id}$
8: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$x_{ij} \notin \mathcal{X}$ ← variable chosen randomly s.t. $x_{ij+1} \in \mathcal{X}$ or $j = J$
9: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**if** no such $x_{ij}$ remains **then** go to line 17
10: &nbsp;&nbsp;&nbsp;&nbsp;**end if**
11: &nbsp;&nbsp;&nbsp;&nbsp;**if** $j = J$ and $!\text{VERIFYCONDITION}(\mathcal{P}, i, j)$ **then** $S_i(\mathcal{P}) = S_i(\mathcal{P}) \cup \{J\}$ &nbsp;&nbsp;&nbsp;&nbsp;$\triangleright$ (see Algorithm 2)
12: &nbsp;&nbsp;&nbsp;&nbsp;**end if**
13: &nbsp;&nbsp;&nbsp;&nbsp;**if** $j < J$ and $!\text{VERIFYCONDITION}(\mathcal{P}, i, j)$ **then** $S_i(\mathcal{P}) = S_i(\mathcal{P}) \cup \{j\} \setminus \{j+1\}$ &nbsp;&nbsp;&nbsp;&nbsp;$\triangleright$ (see Algorithm 2)
14: &nbsp;&nbsp;&nbsp;&nbsp;**end if**
15: &nbsp;&nbsp;&nbsp;&nbsp;**end while**
16: &nbsp;&nbsp;&nbsp;&nbsp;**if** $\text{COMPUTERANK}(\mathcal{P})=k$ **then** return $\mathcal{P}$ &nbsp;&nbsp;&nbsp;&nbsp;$\triangleright$ (see Algorithm 1)
17: &nbsp;&nbsp;&nbsp;&nbsp;**else** pattern discarded
18: &nbsp;&nbsp;&nbsp;&nbsp;**end if**
19: &nbsp;&nbsp;&nbsp;&nbsp;**end procedure**

In Algorithm 3, the lower bound on $k$ ensures that the rank is high enough to create a flexible pattern. Indeed, because of condition (i), too small of a rank will lead to patterns that cannot be flexible patterns. The algorithm starts by initializing a pattern $\mathcal{P}$ containing $I$ times the set $\{J\}$. By construction, $\mathcal{P}$ has at least one index per set, hence condition (i) is verified. In order for the pattern inequalities of $\mathcal{P}$ not to be trivial, it requires $card(\mathcal{P}) > rank(\mathcal{P})$. As the $\mathcal{P}$ is initialized with cardinality $I$, in the case $rank(\mathcal{P}) \ge I$ one needs to add elements to $\mathcal{P}$. For the purpose of this algorithm, we start with elements of higher indices. To do so, we select a random $i$ and add $j-1$ to $S_i(\mathcal{P})$, with $j = S_i(\mathcal{P})(1)$ the smallest index in $S_i(\mathcal{P})$. The sets are randomly selected in order to make it possible to generate different patterns for a same $k$. The core of the procedure is to modify $\mathcal{P}$ so that it verifies condition (ii) and (iii). We randomly select $i$ and $j$ such that $j \notin S_i(\mathcal{P})$ and $j+1 \in S_i(\mathcal{P})$ or $j = J$ and call the procedure `VERIFYCONDITION($\mathcal{P}, i, j$)`. If `VERIFYCONDITION($\mathcal{P}, i, j$)` returns false, then in the case $j < J$ we replace $j+1$ by $j$ in $S_i(\mathcal{P})$, and in the case $j = J$ we add $J$ to $S_i(\mathcal{P})$. The elements are also chosen randomly, so that two same patterns for the same rank $k$ can yield two different flexible patterns through this procedure. Finally, because of the modifications of $\mathcal{P}$, it is possible for it to have $rank(\mathcal{P}) > k$, hence we need to compute it. If the rank is different than $k$, then $\mathcal{P}$ may not be a flexible pattern, as verifying the conditions (ii) and (iii) depends on the rank $k$. One
would need to restart the whole procedure to verify if (ii) and (iii) indeed hold for $\mathcal{P}$. We chose to discard $\mathcal{P}$ in this case, in order to avoid too long computational time for each call to the procedure `GENERATEPATTERN((I, J, w, v, C))`. Note that this procedure always ends. Indeed, the modifications made to the pattern $\mathcal{P}$ are either adding $J$ to $S_i(\mathcal{P})$ if $J \notin S_i(\mathcal{P})$ (line 17), or replacing $j$ in $S_i(\mathcal{P})$ by $j-1$ if $j-1 \notin S_i(\mathcal{P})$. Hence, the worst case is when all groups of $\mathcal{P}$ are filled with all indices, in which case the algorithm stops as there will not be any $x_{ij} \notin \mathcal{X}$.

**Property 9.** `GENERATEPATTERN((I, J, w, v, C))` only returns a pattern if it is a flexible pattern.

The proof is provided in Appendix 7.7.

As these conditions are only necessary for a pattern to be facet-defining, the returned pattern is not necessarily facet-defining. However, it is flexible thus it ensures the associated inequality to have a known lower bound on the dimension of the associated face as proven in **Theorem 1**, thus leading to relatively strong inequalities.

Note that `GENERATEPATTERN((I, J, w, v, C))` returns at most a single pattern, which may not be enough to make a large difference in a B&C framework. Consequently, we call this procedure multiple times as the first phase of the two phase scheme, in order to generate various patterns. Each call is independent from the previous ones, meaning that multiple calls can be done in parallel on different threads. The set of patterns obtained with this procedure is then used within the second phase of the 2-phase B&C scheme.

# 5 Experimental results

Results are computed on a single thread of an Intel Core i7-9850H CPU @ 2.60GHz processor, with 12 CPUs of 12 cores, with Linux as operating system. All algorithms are developed with C++. Version 12.8 of CPLEX is used to solve model $F_{SCPK}$. Recall that UMIC inequalities, introduced in **Section 3.2**, have been adapted to the (SCPK) in **Section 3.3**. Hence, in this section we compare to the classical B&C scheme different variants of the two-phase B&C algorithm, using three sets of inequalities: pattern inequalities, inequalities added internally by CPLEX and UMIC inequalities. Sixty (SCPK) instances have been generated for the experimental comparisons, organized in three instances sets depending on instance's size: set 1 (instances 1 to 20) with $I = 20$, $J = 5$; set 2 (instances 21 to 40) with $I = 30$, $J = 5$; and set 3 (instances 41 to 60) with $I = 20$, $J = 10$. The resulting instance set is available online $^1$. Details about instance generation are provided in Appendix 7.8.

## 5.1 Pattern generation (first phase)

To generate a set of patterns, we repeatedly generate patterns one by one via the pattern generation process depicted in **Algorithm 3**. This process is random-based, hence it can produce multiple times the same pattern. In this case, we only consider one copy of each pattern. Although the process is random-based, we only generate a single set of patterns for each instance. Indeed, preliminary results have shown that for a given instance, solving with different sets of generated patterns yields very similar results, both in terms of generated patterns, and B&C results to solve the (SCPK). Even if the pattern generation procedure could be parallelized, we use a single thread.

Details on pattern generation for each instance is provided in Appendix 7.9.

## 5.2 Separation of inequalities (second phase)

**Separation of the UMIC inequalities** In order to compare to the state-of-the-art exact method for the (SCPK), the separation of UMIC inequalities is done using classical B&C ideas (without any first phase). Thus, for UMIC inequalities, we used the state-of-the-art uplifting algorithm and we implemented the separation process as described in Espinoza et al. (2015). This algorithm first generates a smaller instance, with a *contracted graph*, based on the fractional solution. On the smaller

<footnote n="1">¹https://github.com/Eegann/SCPKinstances, accessed 2025-06-01</footnote>
instance, a MIC is found for each variable. For each MIC, computing coefficients $\beta_{ij}$ for a given $(i, j) \in U_r$ to optimality is NP-hard. Hence, the linear relaxation is considered instead. For a given $(i, j) \in U_r$, if $\beta_{ij}$ is fractional, then it is rounded up to enforce the inequality. This process yields UMIC inequalities for the instance relative to the contracted graph, which is then translated back to the original instance. The algorithm returns only the three most violated UMIC inequalities.

We implemented the separation with the following features as described in Espinoza et al. (2015). In particular, the separation is only enabled for the root node. As long as a violated inequality is found, the LP relaxation is recomputed and the separation process is repeated. The separation procedure is disabled once the number of UMIC inequalities added reaches ten times the number of inequalities of the model.

**Separation of the pattern inequalities** Preliminary results have shown that separation of pattern inequalities is less efficient using a classical B&C scheme, because each separation heuristic tested was quite long to run at each node and often failed to produce violated inequalities. Therefore, separation of pattern inequalities is done only through the two-phase B&C scheme, within a user cut callback from CPLEX. For a given pattern set, it reduces to solve an (MM) for each of its patterns (see **Section 2.3**), hence creating one inequality per pattern, and retain the most violated inequality. Preliminary results show that this strategy is, on average, more efficient than retaining the first violated inequality, or all the violated inequalities.

This process is repeated at each node, as long as a violated inequality is found. This means that the separation of the pattern inequalities is made at least once per node. Recall that an (MM) is solved for each pattern, and from **Table 6** (in Appendix) the number of patterns can reach hundreds. Preliminary results show that using the separation of the pattern inequalities at each node takes up to 90% of the total computational time, and the larger the tree, the fewer the cuts. Besides, preliminary results also show that few patterns yield the majority of the added cuts. Hence, we propose the following scheme, which takes advantage of the fact that we have a set of patterns. For each pattern, we compute the average violation of the added cuts, which is 0.0 when no cut has been added. The set of patterns is kept sorted by decreasing value of this average violation. The idea is to divide the size of the set by two at some nodes, keeping only the first half of the set, such that the set is empty at 10,000 nodes. More precisely, the number of times the set must be divided is $\log_2$ of the number of patterns. Hence, one can divide 10,000 by this number to know at which number of nodes of the B&C the set is divided. Besides, we also limit the number of added cuts to 100. The separation of the patterns is disabled once either the set of patterns is empty, or the number of added cuts has reached 100. Note that the violation of a cut does not have an upper bound of 1 despite variables being binary, as illustrated by Example 5.

**Example 5** (Violation values of pattern inequalities). Let (2,2,[10,5],v,25) be an instance of the (SCPK). One can obtain the fractional solution $\tilde{x}_{11} = 1, \tilde{x}_{12} = 1, \tilde{x}_{21} = 0.66, \tilde{x}_{22} = 0.66$. For this instance, inequality $\tilde{x}_{12} + \tilde{x}_{21} + \tilde{x}_{22} \le 1$ is valid and has a violation value of 1.32 when cutting the fractional solution.

**Separation of UMIC and pattern inequalities.** When both UMIC and pattern inequalities are considered, we first generate pattern inequalities at the root node. Once no more pattern inequalities are violated at the root node, we then generate UMIC inequalities as previously defined. When no more UMIC inequalities are violated, we resume the B&C algorithm and separate the pattern inequalities as described earlier.

## 5.3 Numerical results of the two-phase B&C for the (SCPK)

The B&C framework is limited to a single thread, and a maximum of 3600 seconds of computational time. For the following, we define default CPLEX (namely CPLEX with all default options enabled), and no-cut CPLEX, which is default CPLEX with cuts disabled. Four experimental variants of the two-phase B&C are compared to three classical B&C schemes:

* 1-C: default CPLEX (classical B&C)
• 1-U: no-cut CPLEX with UMIC inequalities (classical B&C)

• 1-C+U: default Cplex with UMIC inequalities (classical B&C)

• 2-P: no-cut CPLEX with pattern inequalities (two-phase B&C)

• 2-C+P: default CPLEX with pattern inequalities (two-phase B&C)

• 2-P: umic: no-cut CPLEX with pattern inequalities and UMIC inequalities (two-phase B&C)

• 2-all: default CPLEX with pattern inequalities and UMIC inequalities (two-phase B&C)

Recall that preliminary results have shown that separating pattern inequalities through a classical B&C scheme was clearly less efficient compared to a 2-phase B&C, therefore do not present results for pattern inequalities with classical B&C.

**General results** Figure 2 represents the number of instances solved for each variant with respect to the computational time. Note that the scale is linear between 0 and 500 seconds, and becomes logarithmic between 500 and 3600, for readability purposes. **Figure 3** is similar but with respect to the number of nodes. For this figure, the scale is linear between 0 and 2 million nodes, and then becomes linear between 2 million and 60 million nodes.

We first notice that on **Figure 2**, variant **2-P** outperforms **1-U** and **1-C**. Besides, variants **2-C+P** and **2-all** are the most efficient below 100 seconds. Above 100 seconds, variant **2-P+U** is the most effective, closely followed by variant **2-P**. These results show that apart from **2-P** being an interesting variant on its own, it can be used alongside other valid inequalities to produce the most efficient variant. Indeed, for any computational time, the variant solving the most instances always features a 2-phase B&C for pattern inequalities. When it comes to **Figure 3**, similar conclusions can be drawn for the most efficient variants. Indeed, variants and **2-all** are the most efficient variants for instances with less than 10 million nodes, and then **2-P+U** becomes the most efficient. Hence, using **2-P** reduces the number of nodes explored.

**More detailed results** (about computational time, gap at the root node, mean violation values of pattern inequalities...) are provided in Tables 7, 8 and 9 from Appendix 7.10. For space's sake, the details are given only for the first 10 instances of the 3 instance sets, but the behaviors are similar for the other instances. First, from Tables 7, 8 and 9, the 2-phase B&C scheme clearly reduces the computational time, for example on the following instances, where we emphasize in bold when only a variant with the 2-phase scheme can solve the (SCPK) at the root node: 1, 2, 3, 8, 21, 27, 29, 46, 49. In general, there are then more than 10% of the instances that are solved at the root node only by a variant featuring the 2-phase scheme. Note also that these improvement are sometimes due to very few inequalities, for example, less than 7 inequalities are added in instance 3 and less than 14 in instance 27. Note however that there are instances where **2-P** is outperformed by **1-C** or **1-U**. For example, **1-U** outperforms **2-P** for instance 5. This suggests that the cuts added from each of these variants are not the same. This also explains why in **Figure 3** and **Figure 2**, variants combining the 2-phase scheme for pattern inequalities with either Umic inequalities or Cplex's inequalities outperform the other variants. We also note that the gaps at the root node are sometimes the highest for variant **2-P** (for example in instance 7). As **2-P** is nevertheless one of the most efficient variant, this suggests that very few cuts are added at the root node, and **2-P** requires some branching in order to produce efficient cuts.

One limitation of pattern inequalities that stands out from **Table 8** is that sometimes, no pattern inequality is violated. This is due to the limited set of patterns. Besides, when no pattern inequality is found, there are also very few UMIC inequalities. See for example instances 24, 25 or 43 where about ten UMIC inequalities were added, even if the maximal number of UMIC inequalities is much larger. This suggests that for these instances, another set of inequality, such as inequalities with integer coefficients, may be the most relevant. Note also that the instances where no pattern inequalities were found tend to be large instances. Indeed, one instance with $I = 20$ and $J = 5$, two with $I = 30$ and $J = 5$ and five with $I = 20$ and $J = 10$ are in this case. This can be due to the first phase time limit being the exact same, independently of the size of the instance.
<figure><img src="image_4.png" /><figcaption>Figure 2: Number of instances solved with respect to the computational time</figcaption></figure>

<figure><img src="image_5.png" /><figcaption>Figure 3: Number of instances solved with respect to the number of nodes</figcaption></figure>
**Variants ranking** In order to further compare the variants, we define the three following metrics:

* **\#best**: the number of instances where a variant features the smallest computational time, or the smallest gap if no variant solves the instance to optimality.

* **\#solved**: the number of instances solved by a variant

* **avg-time**: the average time for instances solved by a variant

Note that sometimes, the computational time of two variants are very similar for a given instance. In such a case, distinguishing a single best variant may not be accurate, hence we will consider multiple best variants when their computational times are close. For a given instance, let *time*\* be the computational time of the quickest variant. Any variant is considered the best if their computational time is below $1.1 \cdot time\*$ or $time\* + 1$. For instances which are not solved, consider *gap*\* the smallest gap. As for the time, any variant is the best variant if its gap is below $1.1 \cdot gap\*$ or $gap\* + 0.1$.

Based on these metrics, we define two rankings. Ranking $R_1$ is solely based on metric \#best. Note that two variants can have the same ranking for $R_1$. Ranking $R_2$ is based on \#solved, and on avg-time to break a tie. **Table 2 to 4** show respectively for each set of instance, the value of each metric and the ranking for $R_1$ and $R_2$ of each variant.

<table><caption>Table 2: Metrics for instances with $I = 20$ and $J = 5$</caption><thead><tr><th>variant</th><th>#best</th><th>#solved</th><th>avg-time-solved</th><th>R<sub>1</sub></th><th>R<sub>2</sub></th></tr></thead><tbody><tr><td>Cplx</td><td>2</td><td>18</td><td>499.10</td><td>6</td><td>7</td></tr><tr><td>Umic</td><td>5</td><td>19</td><td>426.63</td><td>5</td><td>5</td></tr><tr><td>Psep</td><td>6</td><td>19</td><td>185.23</td><td>2</td><td>2</td></tr><tr><td>Cplx+Umic</td><td>1</td><td>19</td><td>578.63</td><td>7</td><td>6</td></tr><tr><td>Cplx+Psep</td><td>6</td><td>19</td><td>322.06</td><td>2</td><td>4</td></tr><tr><td>Psep+Umic</td><td>9</td><td>19</td><td>170.03</td><td>1</td><td>1</td></tr><tr><td>All</td><td>6</td><td>19</td><td>295.96</td><td>2</td><td>3</td></tr></tbody></table>

<table><caption>Table 3: Metrics for instances with $I = 30$ and $J = 5$</caption><thead><tr><th>variant</th><th>#best</th><th>#solved</th><th>avg-time-solved</th><th>R<sub>1</sub></th><th>R<sub>2</sub></th></tr></thead><tbody><tr><td>Cplx</td><td>6</td><td>14</td><td>446.34</td><td>3</td><td>7</td></tr><tr><td>Umic</td><td>5</td><td>19</td><td>725.79</td><td>5</td><td>1</td></tr><tr><td>Psep</td><td>3</td><td>18</td><td>513.20</td><td>6</td><td>3</td></tr><tr><td>Cplx+Umic</td><td>7</td><td>15</td><td>571.03</td><td>6</td><td>6</td></tr><tr><td>Cplx+Psep</td><td>7</td><td>16</td><td>310.85</td><td>2</td><td>5</td></tr><tr><td>Psep+Umic</td><td>5</td><td>18</td><td>374.13</td><td>4</td><td>2</td></tr><tr><td>All</td><td>8</td><td>17</td><td>460.43</td><td>1</td><td>4</td></tr></tbody></table>

<table><caption>Table 4: Metrics for instances with $I = 20$ and $J = 10$</caption><thead><tr><th>variant</th><th>#best</th><th>#solved</th><th>avg-time</th><th>R<sub>1</sub></th><th>R<sub>2</sub></th></tr></thead><tbody><tr><td>Cplx</td><td>1</td><td>18</td><td>630.96</td><td>6</td><td>7</td></tr><tr><td>Umic</td><td>8</td><td>20</td><td>361.62</td><td>2</td><td>3</td></tr><tr><td>Psep</td><td>7</td><td>20</td><td>348.45</td><td>3</td><td>2</td></tr><tr><td>Cplx+Umic</td><td>1</td><td>18</td><td>628.51</td><td>6</td><td>6</td></tr><tr><td>Cplx+Psep</td><td>4</td><td>18</td><td>505.75</td><td>4</td><td>5</td></tr><tr><td>Psep+Umic</td><td>11</td><td>20</td><td>328.75</td><td>1</td><td>1</td></tr><tr><td>All</td><td>4</td><td>19</td><td>631.17</td><td>4</td><td>4</td></tr></tbody></table>

These tables emphasize the improvement of the resolution of the (SCPK) when using 2-phase B&C scheme for pattern inequalities. Indeed, all four variants featuring the 2-phase scheme (2-P, 2-C+P, 2-P+U, 2-all) always contain the best variant for both rankings. The only exception 1-U being the best variant with respect to $R_2$ in **Table 3**. Besides, variant 1-C always occupies a worst position than 1-C+2-P with respect to both $R_1$ and $R_2$, and 1-U always occupy a worst position than 2-P+U for $R_1$, and for two out of the three tables for $R_2$.

**Tables 2 to 4** also show that increasing the number of groups $I$ makes the instances drastically harder, while increasing the number of items $J$ makes the instances slightly harder. Indeed, the number of instances solved \#solved which is significantly lower in **Table 3** than in the two other tables. Despite \#solved being similar in **Table 2** and **4**, the average computational time is clearly higher in **Table 4**. Hence, even if instances with $I = 30$ and $J = 5$ have fewer variables than instances with $I = 20$ and $J = 10$, the former are more difficult than the latter. This could be explained by the fact that with higher number of groups $I$, the polyhedral symmetries as defined in **Definition 1** are further increased, which is not necessarily the case when increasing the number of items $J$.
# 6 Conclusion

In this paper, we introduced the concept of polyhedral symmetries and propose a two-phase Branch&Cut framework exploiting this structure to efficiently separate valid inequalities. We show that when the polyhedral symmetry group has special structure, the orbit-separation problem can be solved in polynomial time.

The application considered is the (SCPK), a variant of the knapsack problem and a special case of the (PK), featuring polyhedral symmetries. We adapt uplifted minimal induced cover inequalities defined for the (PK) to the case of the (SCPK). Building on previous polyhedral studies for the (SCPK) which introduce pattern inequalities as a new class of valid inequalities and necessary facet-defining conditions, we apply the two-phase Branch&Cut framework developed in this paper to the SCPK. To this aim, we proposed efficient algorithms to compute the rank of a pattern, and to check the necessary facet-defining conditions. Moreover, another algorithm is presented to generate a set of patterns verifying such conditions as pre-processing for the first phase of the scheme.

Experimental results demonstrate the efficiency of the two-phase B&C with the pattern inequalities against classical B&C schemes featuring CPLEX's inequalities and uplifted minimal induced cover inequalities. Results show that our two-phase B&C algorithm outperform a B&C algorithm featuring any of these two sets of inequalities. Besides, when combining multiple sets of inequalities, combinations featuring pattern inequalities yield the best results.

An extension of this work would be to include other valid inequalities for the (SCPK) within the two-phase scheme, for example UMIC inequalities. The proposed framework can also be extended to other problems, such as the use case of the Hydro Unit Commitment problem whose core structure corresponds to the (SCPK). Another promising perspective would be to apply the two phase B&C scheme to other problems facing polyhedral symmetries, and develop a generic first phase algorithm based on facet-defining conditions.

# References

Artigues, C., Bendotti, P., Heintzmann, A., Ngueveu, S. U., and Rottner, C. (2025). Borwin: Exact algorithm based on a bi-objective relaxation for window-constrained problems. https://edf.hal.science/hal-05269754/document.

Balas, E. (1975). Facets of the knapsack polytope. Mathematical programming, 8(1):146–164.

Bellman, R. (1958). On a routing problem. Quarterly of applied mathematics, 16(1):87–90.

Bendotti, P., Fouilhoux, P., and Rottner, C. (2020). Symmetry-breaking inequalities for ilp with structured sub-symmetry. Mathematical Programming, 183:61–103.

Bendotti, P., Fouilhoux, P., and Rottner, C. (2021). Orbitopal fixing for the full (sub-) orbitope and application to the unit commitment problem. Mathematical Programming, 186(1):337–372.

Bendotti, P., Heintzmann, A., and Rottner, C. (2025). The symmetric-weight chain-precedence knapsack polytope.

Boyd, E. (1993). Polyhedral results for the precedence-constrained knapsack problem. Discrete Applied Mathematics, 41(3):185–201.

Dijkstra, E. W. (1959). A note on two problems in connexion with graphs. Numerische mathematik, 1(1):269–271.

Edmonds, J. and Karp, R. M. (1972). Theoretical improvements in algorithmic efficiency for network flow problems. Journal of the ACM (JACM), 19(2):248–264.

Espinoza, D., Goycoolea, M., and Moreno, E. (2015). The precedence constrained knapsack problem: Separating maximally violated inequalities. Discrete Applied Mathematics, 194:65–80.

Ferreira, C. E., Martin, A., and Weismantel, R. (1996). Solving multiple knapsack problems by cutting planes. SIAM Journal on Optimization, 6(3):858–877.

Friedman, E. J. (2007). Fundamental Domains for Integer Programs with Symmetries, pages 146–153. Springer Berlin Heidelberg, Berlin, Heidelberg.

Hechme-Doukopoulos, G., Brignol-Charousset, S., Malick, J., and Lemaréchal, C. (2010). The short-term electricity production management problem at EDF. Optima Newsletter, 84:2–6.
Heintzmann, A., Bendotti, P., and Rottner, C. (2024). Handling polyhedral symmetries with a dedicated branch&cut: application to a knapsack variant. *Refereed paper of INFORMS Optimization Society Conference*. https://sites.google.com/view/ios2024refereed?usp=sharing.

Hojny, C., Gally, T., Habeck, O., Lüthen, H., Matter, F., Pfetsch, M. E., and Schmitt, A. (2020). Knapsack polytopes: a survey. *Annals of Operations Research*, 292(1):469–517.

Hojny, C. and Roy, C. (2024). Computational aspects of lifted cover inequalities for knapsacks with few different weights. *arXiv preprint arXiv:2412.14919*.

Kaibel, V., Peinhardt, M., and Pfetsch, M. E. (2007). Orbitopal fixing. In *IPCO*, pages 74–88. Springer.

Kuhn, H. W. (1955). The hungarian method for the assignment problem. *Naval research logistics quarterly*, 2(1-2):83–97.

Margot, F. (2009). Symmetry in integer linear programming. *50 Years of Integer Programming 1958-2008: From the Early Years to the State-of-the-Art*, pages 647–686.

Park, K. and Park, S. (1997). Lifting cover inequalities for the precedence-constrained knapsack problem. *Discrete Applied Mathematics*, 72(3):219–241.

Pisinger, D. (2005). Where are the hard knapsack problems? *Computers & Operations Research*, 32(9):2271–2284.

Salem, M. B., Taktak, R., Mahjoub, A. R., and Ben-Abdallah, H. (2018). Optimization algorithms for the disjunctively constrained knapsack problem. *Soft Computing*, 22(6):2025–2043.

van de Leensel, R. L., Van Hoesel, C., and Van de Klundert, J. (1999). Lifting valid inequalities for the precedence constrained knapsack problem. *Mathematical programming*, 86(1):161–185.
# 7 Appendix

## 7.1 Proof of Property 4

We first recall the downlifting described in van de Leensel et al. (1999), before showing that for the (SCPK), it can only yield coefficients $\alpha_{ij} = 0$. To do so, we introduce further definitions. Let $U$ be a MIC. We define $\pi$ a pfrs-order (precedence first, remaining second), an order for items $(i, j) \in U_p \cup U_r$, such that $\pi_{ij} < \pi_{i'j'}$ if one of the following stands:

* $(i, j) \in U_p$ and $(i', j') \in U_r$

* $(i, j) \in U_p$, $(i', j') \in U_p$, $i = i'$ and $j > j'$ (reversed topological order)

* $(i, j) \in U_r$, $(i', j') \in U_r$, $i = i'$ and $j < j'$ (topological order)

We denote $s^\pi(ij)$ (resp. $p^\pi(ij)$) the set of all items $(i', j')$ such that $\pi_{ij} < \pi_{i'j'}$ (resp. $\pi_{ij} > \pi_{i'j'}$). For a given $(i, j) \in U$, coefficient $\alpha_{ij}$ is computed as follows:

$$ 
\begin{array}{l}
\alpha_{ij} = |U| - 1 - \max \sum_{(i', j') \in U} x_{i'j'} + \sum_{(i', j') \in U_p \cap p^\pi(ij)} \alpha_{i'j'} (1 - x_{i'j'}) \\
\text{s.t.} \quad \sum_{i'=1}^{I} \sum_{j'=1}^{J} w_{j'} x_{i'j'} \le C \\
\qquad x_{i'j'} \le x_{i'j'-1} \quad \forall x_{i'j'} \in \mathcal{V}, j' \ge 2 \\
\qquad x_{i'j'} = 0 \quad \forall (i', j') \in U_r, \\
\qquad x_{i'j'} = 1 \quad \forall (i', j') \in U_p \cap s^\pi(ij), \\
\qquad x_{ij} = 0 \\
\qquad x_{i'j'} \in \{0, 1\} \quad \forall x_{i'j'} \in \mathcal{V}.
\end{array}
$$

*Proof.* Consider $x_{ij}$ such that $\pi_{ij} = 1$. Clearly, $p^\pi(ij) = \emptyset$, hence one maximizes $\sum_{(i', j') \in U} x_{i'j'}$. By definition of a MIC, for each pair of items in $U$, they must be incomparable, i.e., there cannot be two items of the same group. Also, by definition of the pfrs-order, $(i, j+1) \in U$. Hence, as $x_{ij} = 0$, then $x_{ij+1} = 0$, but for all items $(i', j') \in U_p$, then $x_{i'j'} = 1$. By definition of a MIC, there is a feasible solution with all variables of $U \cup U_p \setminus \{x_{ij+1}\}$ to 1. Consequently, the optimal solution of the problem to compute value $\alpha_{ij}$ has value $|U| - 1$, and coefficient $\alpha_{ij} = 0$. One can repeat the same reasoning for all variables in $U_p$. $\square$

## 7.2 Proof of Property 6

*Proof.* First, suppose that we found the shortest path in $G$ with exactly $k+1$ arcs. 1) The path between $p$ and $q$ with exactly $k+1$ arcs is a path with $k+2$ vertices. Note that such a path necessarily exists with $k \in \{1, \dots, \text{card}(P)\}$. Indeed, by construction of $G$, there is a path going through all nodes $x_{(i)(j)}$ and there is an arc from any $x_{(i)(j)}$ to $q$. Also any arc $(x_{(i)(j)}, x_{(i')(j')})$ is with $(i') \ge i$ or $(j') > (j)$, thus there are no cycles in $G$. Hence, the $k+2$ vertices are necessarily different. As $p$ and $q$ do not correspond to any variables of $\mathcal{X}$, a path with exactly $k+1$ arcs represents a set $\mathcal{Y}$ with exactly $k$ variables of $\mathcal{X}$.

2) By construction of $G$, the only arc towards $x_{(i)(j)}$ is from $x_{(i)(j-1)}$ with $(j) > 1$. Consequently, for each $(i, j) \in \mathcal{Y}$ such that $x_{ij'} \in \mathcal{X}$ and $j' < j$, then $x_{ij'} \in \mathcal{Y}$.

3) By construction of $G$, for each $(i, j) \in \mathcal{X}$, every arc towards $x_{ij}$ has a weight $s_{ij}(\mathcal{X})$. As such, a path with a set $\mathcal{Y} \subseteq \mathcal{X}$ of variables has a weight equal to $\sum_{x_{ij} \in \mathcal{Y}} s_{ij}(\mathcal{X})$. Hence, set $\mathcal{Y}$ corresponds to a shortest path minimizing the sum of its set weights.

Now, suppose that we have $\mathcal{Y} \subseteq \mathcal{X}$ satisfying 1), 2) and 3). By construction of $G$, for each item in $\mathcal{Y}$ there is a corresponding vertex in $G$. Besides, as $\mathcal{Y}$ satisfies 2), then there exists a path from $p$ to $q$ by sorting the items $(i, j) \in \mathcal{Y}$ by decreasing $i$ and $j$. As $|\mathcal{Y}| = k$, the associated path has $k+1$ arcs. Finally, as $\mathcal{Y}$ verifies 3), then there are no other path in $G$ with exactly $k+1$ arcs with a lower value. $\square$
## 7.3 Rank computation

**Difference between Algorithm 1 and Bellman-Ford algorithm** The first difference with the Bellman-Ford algorithm is that the vector *dist* contains, at the end of the *n*th iteration of the while loop, the distance between source *p* and any other node *w* ∈ *W* in exactly *n* arcs. Hence, at each iteration of the while loop, *nDist* is initialized with value ∞, and for all *w* ∈ *W*, *nDist*[*w*] is replaced only if there is a path from *p* to *w* in *n* arcs. More precisely, the value *nDist*[*w*] is replaced only if during the *n*th iteration of the while loop there is a path from *p* to *w'* ∈ *W* in *n* − 1 arcs, i.e., *dist*[*n*] < ∞ and an arc from *w'* to *w*. The second difference is the stopping condition, which is when all paths have a distance greater than *C*. As all weights are positive, as soon as all path have weight greater than *C*, there cannot be a path with even more arcs of total weight less or equal *C*. When the algorithm stops, there is no path with *nbArcs* with total weight less or equal *C*. Hence, the maximum cardinality path found is with *nbArcs* − 1 arcs, containing *nbArcs* − 2 vertices different than *p* and *q*. Consequently, the rank of *P* is *k* = *nbArcs* − 2 as *p* and *q* do not represent any variable.

## 7.4 Verifying conditions (ii) and (iii)

**Algorithm 2** shares various similarities with **Algorithm 1** for managing vector *dist* and *nDist* in order to only keep, at the *n*th iteration of the while loop, the shortest path between *p* and *w* ∈ *W* with cardinality exactly *n*. The first difference with **Algorithm 1** lies in the initialization phase of **Algorithm 2**, where a second set $\mathcal{X}' = \mathcal{X} \setminus x_{ij'}$ for each $j' \in S_i(\mathcal{P})$. The second difference is the stopping condition. In **Algorithm 1**, we looked for the path with the largest cardinality, hence we stop when no path has a total weight less than or equal to *C*. In the case of **Algorithm 2** we do the opposite; we look for the path with minimum weight, for a given cardinality. Hence, we iterate until *dist* contains the distances of the minimum weight paths between *p* and all *w* ∈ *W* with cardinality *k* − *u* + 1, meaning with *k* − *u* vertices different from *p* and *q*.

### 7.4.1 Proof of Property 7

*Proof.* Indeed, this algorithm searches for the path with minimum weight, and exactly $k-u+1$ arcs, between *p* and *q*. By construction of $\mathcal{X}'$, this path is without any variables of group *i*. Consequently if the total weight of the generated shortest path plus $\sum_{j'=1}^{j-1} w_{j'}$ is smaller than or equal to *C*, then there is a *k*-intersection of $\mathcal{X}'$ as follows. The *k*-intersection contains all $k-u$ variables in the generated shortest path besides *p* and *q* and the variables $x_{ij'} \in \mathcal{V}$, $j' < j$. In the case $j \le J$, the resulting *k*-intersection contains the variable $x_{ij-1}$ but not $x_{ij}$, which corresponds to condition (iii). In the case $j = J+1$, the resulting *k*-intersection contains $x_{iJ}$, which corresponds to condition (ii). □

## 7.5 Proof of Property 8

*Proof.* First, we consider $\mathcal{P}$ with all sets $S_i(\mathcal{P})$ of cardinality $V$. We recall that $W = |\mathcal{X}| + 2$ by construction of $G$. For each vertex $x_{(i)(1)}$, there is an arc $(p, x_{(i)(1)})$. For each vertex $x_{(i)(j)}$ with $j > 1$, there is an arc $(x_{(i)(j-1)}, x_{(i)(j)})$. This sums up to a total of $|\mathcal{X}|$ arcs. For each vertex $x_{(i)(j)}$, there is an arc $(x_{(i)(j)}, q)$. Accounting for the previously enumerated arcs, there are $2|\mathcal{X}|$ arcs.

For each $x_{(i)(j)}$, there is an arc $(x_{(i)(j)}, x_{(i')}(1))$, for every $i' > 1$. Consequently, for every $i \le I$, there are $|S_i(\mathcal{P})| \cdot (I - i) = V \cdot (I - i)$ arcs. This yields a total of $\sum_{i=1}^I V \cdot (I - i) = \sum_{i=0}^{I-1} V \cdot i$ which is equal to $V \cdot \frac{(I-1)I}{2}$.

In total, the number of arcs $|A|$ is equal to $2 \cdot V \cdot I + \frac{1}{2} \cdot V \cdot (I^2 - I)$ which can be approximated by $V \cdot I^2$ when $V$ and $I$ are large. Also, we can compute $|W|^2 = (I \cdot V + 2)^2 = I^2 \cdot V^2 + 4 \cdot V \cdot I + 4 > I^2 \cdot J^2 + 4 \cdot V \cdot I$, which can be approximated by $V^2 \cdot I^2$ when $V$ and $I$ are large, meaning that $\frac{|W|^2}{|A|} = \Theta(V)$.

Consider now that we add one vertex $x_{(i)(j)}$ to $G$. This adds arc $(x_{(i)(j-1)}, x_{(i)(j)})$, $(x_{(i)(j)}, q)$ and at most $I-1$ arcs $(x_{(i)(j)}, x_{(i'),(1)})$, with $i' > i$. This results to a total of $I+1$ arcs, which is smaller than $|W|$, hence by adding one vertex, the factor $V$ between $|W|^2$ and $|A|$ holds. The same result applies by adding more than one vertex. Consequently, for any pattern $\mathcal{P}$, approximation $\frac{|W|^2}{|A|} = \Theta(V)$ still holds. □
## 7.6 Proof of Theorem 2

*Proof.* Condition (i) requires to verify if each set is non-empty, which is linear w.r.t. the number of sets $I$. Condition (ii) requires to run **Algorithm 2** for each $x_{ij}$, $i \le I$, which is an algorithm of complexity $O(|W|^3)$, $|W| \le n$ a total of $I \le n$ times. Condition (ii) can be verified in $O(n^4)$ time. Condition (iii) requires to run **Algorithm 2** for each $x_{ij} \in \mathcal{X}$, which is an algorithm of complexity $O(|W|^3)$, $|W| \le n$ a total of $|\mathcal{X}| \le n$ times. Condition (iii) can be verified in $O(n^4)$ time. $\square$

**Remark 2.** It is worth mentioning that the time complexity $O(n^4)$ is rarely reached. Indeed, only one pattern has a cardinality equal to $n$: the one containing $I$ times the set $\{1, \dots, J\}$. All other patterns have a smaller cardinality, which reduces the required time to verify (ii) and (iii) in two ways. The first one is that **Algorithm 2** is needed $card(\mathcal{P})$ times for (iii), and $I \le card(\mathcal{P})$ times for (ii). The second one is that the complexity of **Algorithm 2** depends on $|W|$, which is $card(\mathcal{P}) + 2 - |S_i(\mathcal{P})|$ as mentioned in **Remark 1**. Then likewise **Algorithm 2** usually requires much less than $|W|^3$ operations.

## 7.7 Proof of Property 9

*Proof.* As $\mathcal{P}$ is discarded if $rank(\mathcal{P}) \neq k$, it ensures the rank of $\mathcal{P}$ to be exactly $k$. Similarly, pattern $\mathcal{P}$ verifies conditions (ii) and (iii). Indeed, condition (ii) is verified for every $i \in \{1, \dots, I\}$ and (iii) is verified for every $i \in \{1, \dots, I\}$ and $j \in S_i(\mathcal{P})$. Also, if a condition (ii) is verified for a given $i$, it is still verified if $\mathcal{P}$ is modified during the core of procedure `GENERATEPATTERN((I, J, w, v, C))`. Similarly, if condition (iii) is verified for a given $i$ and $j \in S_i(\mathcal{P})$, it is still verified if $\mathcal{P}$ is modified during the core of procedure `GENERATEPATTERN((I, J, w, v, C))`. Indeed, as either one element is added, or an index $j'$ is replaced by $j' - 1$ in a set $S_i'(\mathcal{P})$, then the same $k$-intersection satisfying (ii) or (iii) can be found, or a $k$-intersection with lighter total set weights. As $\mathcal{P}$ is initialized with one element per set, and the size of a set cannot decrease (when an index $i$ is removed, it is replaced by $i - 1$), condition (i) is verified. Therefore, the procedure `GENERATEPATTERN((I, J, w, v, C))` returns the pattern only if it verifies (i), (ii) and (iii). $\square$

## 7.8 Instance description

One of the main result when comparing the solving time of various knapsack problem instances Pisinger (2005) is that a stronger correlation between weight and value tends to induce a large increase of the computational times. Instance generators for variants of the knapsack problem are at disposal <fnref n="2" /> with various characteristics. However, none of them produce instances for the particular case of the (SCPK), i.e., with $I$ groups of $J$ elements, chain precedence constraints and symmetric weights $w_j$, $j \le J$. Hence, we generate our own random instances by keeping a strong enough correlation between weights and values. From a pool of hundred generated instances, sixty are retained. The selection criteria is for these instances to take at least 60 seconds to be solved by CPLEX, with all the default options of CPLEX enabled but the cuts. As such, there is enough room in terms of computational time and number of explored B&C nodes to see the impact of each of the family of cuts considered. The 60 retained instances are as follows, instances 1 to 20 with $I = 20$ $J = 5$; instances 21 to 40 with $I = 30$ $J = 5$; instances 41 to 60 with $I = 20$ $J = 10$. Note that these instances are in the case $I \ge J$, for which the (SCPK) is proven to be NP-hard.

To see how a correlation similar to that proposed in Pisinger (2005) can extend to the generated (SCPK) instances, **Table 5** gives the correlation between the weights and values, as well as the correlation between the cumulated weights and cumulated values.

For the (SCPK), a set of hundred instances are generated, with weights and values constructed as follows: For all $j \le J$, we generate a random value $R_j \in [0, 1]$. The value of item $(i, j)$ is $R_j \cdot 350$ plus a random value in $[-35; 35]$. The weight of items $(i, j)$ for every $i \le I$ is $R_j \cdot 3$ plus a random value in $[-1.5; 1.5]$. The capacity $C$ is selected randomly between 0 and the sum of the weights of all items. The idea is to use $R_j$ to create some correlation between the weight, but adding a random value in order to allow for a large enough set of instances. From this set of hundred instances 15 are retained:

<footnote n="2">²http://hjemmesider.diku.dk/~pisinger/codes.html, accessed 2023-06-20</footnote>
**Correlation values** When considering instances from the difficult classes in Pisinger (2005) the correlation coefficient is above 0.98. In the case of the (SCPK), item $(i, j)$ can only be selected if $(i, j - 1)$ has been selected, due to chain precedence constraints. Hence, one can compute the correlation coefficients between the weights and values, but also the correlation coefficient between the cumulated weights and cumulated value, i.e., $\sum_{j=1}^{J} w_j$ and $\sum_{j=1}^{J} v_{ij}$ instead of $w_j$ and $v_{ij}$.

**Table 5** gives the correlation between the weights and values (*cor*), as well as the correlation between the cumulated weights and cumulated values (*cor*<sub>C</sub>). The considered linear Bravais-Pearson correlation formula is as follows: $cor = \frac{cov(w,v)}{\sigma_w \cdot \sigma_v}$, with $cov(w, v)$ the covariance, and $\sigma_w$ (resp. $\sigma_v$) the standard deviation of the weights (resp. values).

Interestingly, for the (SCPK) instances, metric *cor* often takes a low or even negative value, whereas metric *cor*<sub>C</sub> is always over 0.70. This indicates that *cor*<sub>C</sub> is a better metric to evaluate the hardness of (SCPK) instances. It also appears that metric *cor* has a higher value for instances 41 to 60 have higher. As these instances are with *J* = 10 items per group, it could mean that for instances with high *J*, the value of *cor* and *cor*<sub>C</sub> become correlated. Note that this remark do not apply for the number of groups *I*, as there is no noticeable difference between instances 1 to 20 and 21 to 40. Note that values in **Table 5** are rounded and value 1.00 does not necessarily mean a perfect correlation.

<table><caption>**Table 5:** Correlation coefficients between the value and weight for all instances</caption><thead><tr><th>inst</th><th>cor</th><th>cor<sub>C</sub></th><th>inst</th><th>cor</th><th>cor<sub>C</sub></th><th>inst</th><th>cor</th><th>cor<sub>C</sub></th></tr></thead><tbody><tr><td>1</td><td>0.82</td><td>0.85</td><td>21</td><td>-0.3</td><td>0.97</td><td>41</td><td>0.57</td><td>1.0</td></tr><tr><td>2</td><td>-0.67</td><td>0.94</td><td>22</td><td>0.29</td><td>0.98</td><td>42</td><td>0.56</td><td>0.98</td></tr><tr><td>3</td><td>0.36</td><td>0.98</td><td>23</td><td>0.18</td><td>0.99</td><td>43</td><td>0.68</td><td>0.99</td></tr><tr><td>4</td><td>0.51</td><td>0.99</td><td>24</td><td>0.69</td><td>0.99</td><td>44</td><td>0.59</td><td>0.99</td></tr><tr><td>5</td><td>0.7</td><td>1.0</td><td>25</td><td>0.42</td><td>0.99</td><td>45</td><td>0.67</td><td>0.98</td></tr><tr><td>6</td><td>0.03</td><td>0.96</td><td>26</td><td>0.65</td><td>0.99</td><td>46</td><td>0.37</td><td>0.99</td></tr><tr><td>7</td><td>0.72</td><td>0.99</td><td>27</td><td>0.73</td><td>0.98</td><td>47</td><td>0.35</td><td>0.99</td></tr><tr><td>8</td><td>0.81</td><td>0.97</td><td>28</td><td>0.87</td><td>1.0</td><td>48</td><td>0.36</td><td>0.99</td></tr><tr><td>9</td><td>0.33</td><td>0.99</td><td>29</td><td>0.32</td><td>1.0</td><td>49</td><td>0.52</td><td>0.99</td></tr><tr><td>10</td><td>0.65</td><td>1.0</td><td>30</td><td>-0.26</td><td>0.99</td><td>50</td><td>0.14</td><td>0.99</td></tr><tr><td>11</td><td>0.59</td><td>0.99</td><td>31</td><td>-0.8</td><td>0.99</td><td>51</td><td>0.61</td><td>0.99</td></tr><tr><td>12</td><td>0.97</td><td>0.99</td><td>32</td><td>0.69</td><td>0.99</td><td>52</td><td>0.48</td><td>0.99</td></tr><tr><td>13</td><td>0.0</td><td>0.99</td><td>33</td><td>0.44</td><td>0.98</td><td>53</td><td>0.2</td><td>0.99</td></tr><tr><td>14</td><td>0.49</td><td>0.97</td><td>34</td><td>0.48</td><td>0.92</td><td>54</td><td>0.44</td><td>1.0</td></tr><tr><td>15</td><td>0.61</td><td>0.97</td><td>35</td><td>-0.06</td><td>0.94</td><td>55</td><td>0.2</td><td>0.99</td></tr><tr><td>16</td><td>0.89</td><td>1.0</td><td>36</td><td>0.45</td><td>0.85</td><td>56</td><td>0.2</td><td>0.98</td></tr><tr><td>17</td><td>0.74</td><td>0.99</td><td>37</td><td>0.54</td><td>0.71</td><td>57</td><td>0.87</td><td>0.98</td></tr><tr><td>18</td><td>-0.03</td><td>0.99</td><td>38</td><td>0.03</td><td>0.98</td><td>58</td><td>0.54</td><td>1.0</td></tr><tr><td>19</td><td>0.82</td><td>0.99</td><td>39</td><td>0.58</td><td>0.98</td><td>59</td><td>0.9</td><td>0.98</td></tr><tr><td>20</td><td>-0.44</td><td>0.99</td><td>40</td><td>0.23</td><td>0.98</td><td>60</td><td>0.51</td><td>0.77</td></tr></tbody></table>

## 7.9 Pattern generation metrics

The following metrics are used in **Table 6** to compare the pattern generations for each instance:

* \#iter: number of iterations of the generation process

* \#find: number of iterations where a flexible pattern is found

* \#patt: number of different flexible patterns found

* %facet: proportion of patterns guaranteed to be pattern-facet, i.e., with a set of cardinality 1

Firstly, one can see that the generation becomes slower on larger instances, thus with the same time limit, fewer iterations can be performed. More precisely, there are thousands of iterations for instances 1 to 20, around a thousand for instances 21 to 40, and hundreds for instances 41 to 60. Consequently, fewer patterns are found for larger instances. Note that there are many instances for which most iterations of the pattern generation procedure fail to produce a flexible pattern in a majority of cases. Indeed, there are instances for which the procedure produces a flexible pattern during less than 10% of the iterations, see for example instances 4, 15, 22, 36, 44, 50. Generally speaking, the larger the instances, the higher the proportion of failed iterations.

Moreover, when \#find is large, most of the flexible patterns are generated multiple times. Indeed, generally speaking, the ratio between \#patt and \#find is smaller when \#find is large. This is due to
the procedure being random-based, hence when #find is large, there is a higher chance to generate duplicates.

<table><caption>Table 6: Patterns generations</caption><thead><tr><th>inst</th><th>#iter</th><th>#find</th><th>#patt</th><th>%facet</th><th>inst</th><th>#iter</th><th>#find</th><th>#patt</th><th>%facet</th><th>inst</th><th>#iter</th><th>#find</th><th>#patt</th><th>%facet</th></tr></thead><tbody><tr><td>1</td><td>5011</td><td>3245</td><td>244</td><td>4.9</td><td>21</td><td>1123</td><td>517</td><td>106</td><td>3.8</td><td>41</td><td>371</td><td>31</td><td>18</td><td>16.7</td></tr><tr><td>2</td><td>7428</td><td>3870</td><td>45</td><td>15.6</td><td>22</td><td>977</td><td>21</td><td>9</td><td>88.9</td><td>42</td><td>346</td><td>17</td><td>11</td><td>36.4</td></tr><tr><td>3</td><td>7432</td><td>6594</td><td>53</td><td>9.4</td><td>23</td><td>1290</td><td>947</td><td>186</td><td>2.7</td><td>43</td><td>338</td><td>31</td><td>18</td><td>16.7</td></tr><tr><td>4</td><td>4070</td><td>385</td><td>78</td><td>19.2</td><td>24</td><td>851</td><td>69</td><td>34</td><td>14.7</td><td>44</td><td>339</td><td>10</td><td>9</td><td>44.4</td></tr><tr><td>5</td><td>4112</td><td>1125</td><td>207</td><td>3.9</td><td>25</td><td>815</td><td>93</td><td>50</td><td>20.0</td><td>45</td><td>299</td><td>12</td><td>8</td><td>37.5</td></tr><tr><td>6</td><td>3935</td><td>274</td><td>61</td><td>29.5</td><td>26</td><td>1001</td><td>332</td><td>140</td><td>9.3</td><td>46</td><td>484</td><td>97</td><td>53</td><td>7.5</td></tr><tr><td>7</td><td>4421</td><td>1428</td><td>199</td><td>5.5</td><td>27</td><td>990</td><td>200</td><td>43</td><td>11.6</td><td>47</td><td>470</td><td>126</td><td>82</td><td>4.9</td></tr><tr><td>8</td><td>3414</td><td>210</td><td>26</td><td>23.1</td><td>28</td><td>773</td><td>68</td><td>32</td><td>12.5</td><td>48</td><td>650</td><td>326</td><td>205</td><td>1.5</td></tr><tr><td>9</td><td>3603</td><td>281</td><td>50</td><td>26.0</td><td>29</td><td>859</td><td>305</td><td>144</td><td>5.6</td><td>49</td><td>864</td><td>616</td><td>182</td><td>1.1</td></tr><tr><td>10</td><td>3935</td><td>395</td><td>74</td><td>17.6</td><td>30</td><td>870</td><td>38</td><td>20</td><td>40.0</td><td>50</td><td>375</td><td>5</td><td>2</td><td>100.0</td></tr><tr><td>11</td><td>4059</td><td>1078</td><td>195</td><td>7.2</td><td>31</td><td>859</td><td>172</td><td>72</td><td>12.5</td><td>51</td><td>354</td><td>50</td><td>40</td><td>7.5</td></tr><tr><td>12</td><td>4649</td><td>2008</td><td>296</td><td>3.4</td><td>32</td><td>855</td><td>34</td><td>11</td><td>72.7</td><td>52</td><td>336</td><td>38</td><td>22</td><td>18.2</td></tr><tr><td>13</td><td>4444</td><td>644</td><td>125</td><td>14.4</td><td>33</td><td>1208</td><td>36</td><td>8</td><td>100.0</td><td>53</td><td>374</td><td>6</td><td>4</td><td>50.0</td></tr><tr><td>14</td><td>5937</td><td>2484</td><td>96</td><td>4.2</td><td>34</td><td>795</td><td>98</td><td>44</td><td>22.7</td><td>54</td><td>727</td><td>344</td><td>200</td><td>1.0</td></tr><tr><td>15</td><td>3501</td><td>250</td><td>40</td><td>20.0</td><td>35</td><td>790</td><td>82</td><td>38</td><td>23.7</td><td>55</td><td>385</td><td>80</td><td>55</td><td>5.5</td></tr><tr><td>16</td><td>9023</td><td>308</td><td>11</td><td>100.0</td><td>36</td><td>880</td><td>25</td><td>8</td><td>62.5</td><td>56</td><td>863</td><td>587</td><td>187</td><td>1.1</td></tr><tr><td>17</td><td>4112</td><td>1393</td><td>166</td><td>4.2</td><td>37</td><td>960</td><td>169</td><td>52</td><td>11.5</td><td>57</td><td>297</td><td>2</td><td>2</td><td>0.0</td></tr><tr><td>18</td><td>4294</td><td>192</td><td>33</td><td>45.5</td><td>38</td><td>1027</td><td>22</td><td>7</td><td>57.1</td><td>58</td><td>363</td><td>6</td><td>6</td><td>50.0</td></tr><tr><td>19</td><td>5125</td><td>1787</td><td>152</td><td>7.9</td><td>39</td><td>812</td><td>177</td><td>94</td><td>4.3</td><td>59</td><td>366</td><td>43</td><td>34</td><td>5.9</td></tr><tr><td>20</td><td>3869</td><td>287</td><td>57</td><td>28.1</td><td>40</td><td>804</td><td>29</td><td>20</td><td>50.0</td><td>60</td><td>517</td><td>102</td><td>46</td><td>4.3</td></tr></tbody></table>

## 7.10 Detailed experimental results for each instance set

In Tables 7, 8 and 9, we present the following metrics :

* inst: the instance number.

* variant: experimental variant of the B&C considered.

* C cuts (resp. U cuts): number of added CPLEX cuts (resp. number of added UMIC cuts)

* P cuts: number of added pattern cuts.

* P cuts vio: average violation value of the added pattern cuts.

* r-value: linear relaxation value at the root node.

* r-gap: gap between the linear relaxation value at the root node and the optimal solution, if optimality is proven by at least one variant.

* user-time: proportion of the time dedicated to the separation of pattern and UMIC inequalities.

* #nodes: number of nodes explored.

* time/gap: total computational time in seconds when the instance is solved; gap between the upper and lower bound provided by CPLEX at the time limit when the instance is not solved.
<table><caption>Table 7: Detailed results for (SCPK) instance set 1 ($I = 20, J = 5$)</caption><thead><tr><th>inst</th><th>variant</th><th>C cuts</th><th>U cuts</th><th>P cuts</th><th>P cuts vio</th><th>r value</th><th>r-gap</th><th>user time</th><th>#nodes</th><th>time/gap</th></tr></thead><tbody><tr><td rowspan="10">1</td><td>1-C</td><td>345</td><td>-</td><td>-</td><td>-</td><td>8125.38</td><td>2.66%</td><td>-</td><td>3625008</td><td>353.2</td></tr><tr><td>1-U</td><td>-</td><td>94</td><td>-</td><td>-</td><td>8205.39</td><td>3.67%</td><td>1.0%</td><td>80545158</td><td>2874.6</td></tr><tr><td>2-P</td><td>-</td><td>-</td><td>100</td><td>0.48</td><td>8087.65</td><td>2.18%</td><td>38.4%</td><td>21483</td><td>1.9</td></tr><tr><td>1-C+U</td><td>238</td><td>15</td><td>-</td><td>-</td><td>8125.38</td><td>2.66%</td><td>0.6%</td><td>13783767</td><td>1144.2</td></tr><tr><td>2-C+P</td><td>74</td><td>-</td><td>100</td><td>0.6</td><td>8067.12</td><td>1.92%</td><td>72.6%</td><td>3672</td><td>1.2</td></tr><tr><td>2-P+U</td><td>-</td><td>18</td><td>100</td><td>0.44</td><td>8087.65</td><td>2.18%</td><td>63.3%</td><td>29865</td><td>3.9</td></tr><tr><td>2-all</td><td>74</td><td>0</td><td>100</td><td>0.6</td><td>8067.12</td><td>1.92%</td><td>75.4%</td><td>3672</td><td>1.2</td></tr><tr><td>1-C</td><td>305</td><td>-</td><td>-</td><td>-</td><td>-</td><td>8498.94</td><td>3.34%</td><td>-</td><td>1048228</td><td>135.3</td></tr><tr><td>1-U</td><td>-</td><td>312</td><td>-</td><td>-</td><td>8501.42</td><td>3.37%</td><td>6.5%</td><td>1056401</td><td>67.6</td></tr><tr><td>2-P</td><td>-</td><td>-</td><td>100</td><td>0.34</td><td>8427.76</td><td>2.47%</td><td>1.2%</td><td>270933</td><td>19.1</td></tr><tr><td rowspan="4">2</td><td>1-C+U</td><td>235</td><td>24</td><td>-</td><td>-</td><td>8496.87</td><td>3.31%</td><td>0.6%</td><td>1027977</td><td>102.7</td></tr><tr><td>2-C+P</td><td>143</td><td>-</td><td>100</td><td>0.32</td><td>8426.69</td><td>2.46%</td><td>1.1%</td><td>208598</td><td>19.9</td></tr><tr><td>2-P+U</td><td>-</td><td>0</td><td>100</td><td>0.34</td><td>8427.76</td><td>2.47%</td><td>1.4%</td><td>270933</td><td>18.5</td></tr><tr><td>2-all</td><td>143</td><td>0</td><td>100</td><td>0.32</td><td>8426.69</td><td>2.46%</td><td>1.3%</td><td>208598</td><td>18.4</td></tr><tr><td rowspan="10">3</td><td>1-C</td><td>405</td><td>-</td><td>-</td><td>-</td><td>5234.55</td><td>9.41%</td><td>-</td><td>1849854</td><td>173.0</td></tr><tr><td>1-U</td><td>-</td><td>426</td><td>-</td><td>-</td><td>5214.77</td><td>8.99%</td><td>8.3%</td><td>2095765</td><td>160.9</td></tr><tr><td>2-P</td><td>-</td><td>-</td><td>7</td><td>0.9</td><td>4829.68</td><td>0.95%</td><td>35.5%</td><td>0</td><td>0.0</td></tr><tr><td>1-C+U</td><td>58</td><td>315</td><td>-</td><td>-</td><td>5200.3</td><td>8.69%</td><td>6.7%</td><td>2088692</td><td>164.9</td></tr><tr><td>2-C+P</td><td>5</td><td>-</td><td>3</td><td>0.76</td><td>4795.72</td><td>0.24%</td><td>17.9%</td><td>0</td><td>0.0</td></tr><tr><td>2-P+U</td><td>-</td><td>0</td><td>7</td><td>0.9</td><td>4829.68</td><td>0.95%</td><td>33.1%</td><td>0</td><td>0.0</td></tr><tr><td>2-all</td><td>5</td><td>0</td><td>3</td><td>0.76</td><td>4795.72</td><td>0.24%</td><td>15.9%</td><td>0</td><td>0.0</td></tr><tr><td>1-C</td><td>405</td><td>-</td><td>-</td><td>-</td><td>6575.88</td><td>0.90%</td><td>-</td><td>5442220</td><td>1351.5</td></tr><tr><td>1-U</td><td>-</td><td>39</td><td>-</td><td>-</td><td>6575.69</td><td>0.90%</td><td>0.8%</td><td>5885435</td><td>318.2</td></tr><tr><td>2-P</td><td>-</td><td>-</td><td>100</td><td>0.26</td><td>6575.87</td><td>0.90%</td><td>0.7%</td><td>4735131</td><td>377.6</td></tr><tr><td rowspan="4">4</td><td>1-C+U</td><td>227</td><td>40</td><td>-</td><td>-</td><td>6575.2</td><td>0.89%</td><td>0.4%</td><td>5738509</td><td>882.8</td></tr><tr><td>2-C+P</td><td>143</td><td>-</td><td>100</td><td>0.43</td><td>6569.79</td><td>0.81%</td><td>0.4%</td><td>3649391</td><td>542.1</td></tr><tr><td>2-P+U</td><td>-</td><td>6</td><td>100</td><td>0.36</td><td>6575.62</td><td>0.90%</td><td>0.8%</td><td>4970221</td><td>357.5</td></tr><tr><td>2-all</td><td>142</td><td>2</td><td>100</td><td>0.38</td><td>6569.75</td><td>0.81%</td><td>0.4%</td><td>3571861</td><td>492.4</td></tr><tr><td rowspan="5">5</td><td>1-C</td><td>405</td><td>-</td><td>-</td><td>-</td><td>14288.9</td><td>1.10%</td><td>-</td><td>1816805</td><td>280.6</td></tr><tr><td>1-U</td><td>-</td><td>27</td><td>-</td><td>-</td><td>14302.5</td><td>1.20%</td><td>1.1%</td><td>1180341</td><td>56.5</td></tr><tr><td>2-P</td><td>-</td><td>-</td><td>100</td><td>0.11</td><td>14291.1</td><td>1.12%</td><td>2.7%</td><td>1226118</td><td>93.2</td></tr><tr><td>1-C+U</td><td>231</td><td>33</td><td>-</td><td>-</td><td>14283.4</td><td>1.06%</td><td>0.7%</td><td>1066178</td><td>142.9</td></tr><tr><td>2-C+P</td><td>143</td><td>-</td><td>100</td><td>0.11</td><td>14291.0</td><td>1.12%</td><td>1.4%</td><td>988415</td><td>146.4</td></tr><tr><td rowspan="4">6</td><td>2-P+U</td><td>-</td><td>7</td><td>100</td><td>0.11</td><td>14290.5</td><td>1.12%</td><td>3.5%</td><td>1144164</td><td>79.9</td></tr><tr><td>2-all</td><td>139</td><td>6</td><td>100</td><td>0.12</td><td>14290.5</td><td>1.12%</td><td>1.6%</td><td>1062315</td><td>139.9</td></tr><tr><td>1-C</td><td>400</td><td>-</td><td>-</td><td>-</td><td>19711.6</td><td>0.95%</td><td>-</td><td>242702</td><td>53.4</td></tr><tr><td>1-U</td><td>-</td><td>38</td><td>-</td><td>-</td><td>19896.3</td><td>1.89%</td><td>2.1%</td><td>1355505</td><td>65.8</td></tr><tr><td rowspan="5">7</td><td>2-P</td><td>-</td><td>-</td><td>59</td><td>0.19</td><td>19921.7</td><td>2.02%</td><td>7.1%</td><td>1334199</td><td>82.7</td></tr><tr><td>1-C+U</td><td>237</td><td>18</td><td>-</td><td>-</td><td>19706.9</td><td>0.92%</td><td>1.0%</td><td>250298</td><td>42.0</td></tr><tr><td>2-C+P</td><td>143</td><td>-</td><td>100</td><td>0.08</td><td>19711.6</td><td>0.95%</td><td>9.0%</td><td>213517</td><td>36.7</td></tr><tr><td>2-P+U</td><td>-</td><td>38</td><td>75</td><td>0.19</td><td>19896.3</td><td>1.89%</td><td>7.6%</td><td>1308569</td><td>84.4</td></tr><tr><td>2-all</td><td>144</td><td>15</td><td>100</td><td>0.12</td><td>19706.9</td><td>0.92%</td><td>11.6%</td><td>248436</td><td>39.2</td></tr><tr><td rowspan="10">8</td><td>1-C</td><td>405</td><td>-</td><td>-</td><td>-</td><td>13801.3</td><td>1.78%</td><td>-</td><td>8463734</td><td>1690.0</td></tr><tr><td>1-U</td><td>-</td><td>345</td><td>-</td><td>-</td><td>13874.4</td><td>2.32%</td><td>2.2%</td><td>6975709</td><td>473.7</td></tr><tr><td>2-P</td><td>-</td><td>-</td><td>100</td><td>0.39</td><td>13821.2</td><td>1.92%</td><td>0.6%</td><td>6770252</td><td>541.6</td></tr><tr><td>1-C+U</td><td>206</td><td>81</td><td>-</td><td>-</td><td>13794.3</td><td>1.73%</td><td>0.4%</td><td>8454711</td><td>1067.6</td></tr><tr><td>2-C+P</td><td>143</td><td>-</td><td>100</td><td>0.5</td><td>13783.6</td><td>1.65%</td><td>0.4%</td><td>7102323</td><td>921.0</td></tr><tr><td>2-P+U</td><td>-</td><td>0</td><td>100</td><td>0.39</td><td>13821.2</td><td>1.92%</td><td>0.7%</td><td>6770252</td><td>487.4</td></tr><tr><td>2-all</td><td>143</td><td>0</td><td>100</td><td>0.5</td><td>13783.6</td><td>1.65%</td><td>0.4%</td><td>7102323</td><td>858.4</td></tr><tr><td>1-C</td><td>305</td><td>-</td><td>-</td><td>-</td><td>19621.1</td><td>2.02%</td><td>-</td><td>22632994</td><td>0.45%</td></tr><tr><td>1-U</td><td>-</td><td>438</td><td>-</td><td>-</td><td>19674.1</td><td>2.29%</td><td>0.9%</td><td>19907454</td><td>1697.2</td></tr><tr><td>2-P</td><td>-</td><td>-</td><td>100</td><td>0.29</td><td>19544.5</td><td>1.62%</td><td>0.5%</td><td>1638025</td><td>136.2</td></tr><tr><td rowspan="4">9</td><td>1-C+U</td><td>178</td><td>15</td><td>-</td><td>-</td><td>19618.0</td><td>2.00%</td><td>0.6%</td><td>31306241</td><td>2831.5</td></tr><tr><td>2-C+P</td><td>3</td><td>-</td><td>2</td><td>0.74</td><td>19232.8</td><td>0.00%</td><td>17.8%</td><td>0</td><td>0.0</td></tr><tr><td>2-P+U</td><td>-</td><td>0</td><td>100</td><td>0.29</td><td>19544.5</td><td>1.62%</td><td>0.7%</td><td>1638025</td><td>121.4</td></tr><tr><td>2-all</td><td>3</td><td>0</td><td>2</td><td>0.74</td><td>19232.8</td><td>0.00%</td><td>15.4%</td><td>0</td><td>0.0</td></tr><tr><td rowspan="10">10</td><td>1-C</td><td>305</td><td>-</td><td>-</td><td>-</td><td>21935.5</td><td>0.54%</td><td>-</td><td>1759737</td><td>248.0</td></tr><tr><td>1-U</td><td>-</td><td>26</td><td>-</td><td>-</td><td>21940.7</td><td>0.57%</td><td>1.3%</td><td>2189901</td><td>100.9</td></tr><tr><td>2-P</td><td>-</td><td>-</td><td>100</td><td>0.08</td><td>21946.3</td><td>0.59%</td><td>3.0%</td><td>2115733</td><td>185.2</td></tr><tr><td>1-C+U</td><td>239</td><td>12</td><td>-</td><td>-</td><td>21931.8</td><td>0.53%</td><td>0.4%</td><td>1844651</td><td>241.3</td></tr><tr><td>2-C+P</td><td>164</td><td>-</td><td>100</td><td>0.03</td><td>21935.5</td><td>0.54%</td><td>2.0%</td><td>1879557</td><td>274.9</td></tr><tr><td>2-P+U</td><td>-</td><td>26</td><td>100</td><td>0.06</td><td>21940.7</td><td>0.57%</td><td>3.7%</td><td>2175143</td><td>175.8</td></tr><tr><td>2-all</td><td>143</td><td>9</td><td>100</td><td>0.06</td><td>21931.8</td><td>0.53%</td><td>2.2%</td><td>1876011</td><td>246.9</td></tr><tr><td>1-C</td><td>405</td><td>-</td><td>-</td><td>-</td><td>22807.8</td><td>0.73%</td><td>-</td><td>1415897</td><td>299.3</td></tr><tr><td>1-U</td><td>-</td><td>243</td><td>-</td><td>-</td><td>22806.8</td><td>0.73%</td><td>2.3%</td><td>1531487</td><td>119.2</td></tr><tr><td>2-P</td><td>-</td><td>-</td><td>100</td><td>0.24</td><td>22796.6</td><td>0.68%</td><td>0.6%</td><td>1108389</td><td>111.4</td></tr><tr><td>1-C+U</td><td>228</td><td>30</td><td>-</td><td>-</td><td>22803.6</td><td>0.71%</td><td>0.3%</td><td>1294867</td><td>204.4</td></tr><tr><td>2-C+P</td><td>143</td><td>-</td><td>100</td><td>0.35</td><td>22796.5</td><td>0.68%</td><td>0.4%</td><td>1190879</td><td>185.3</td></tr><tr><td>2-P+U</td><td>-</td><td>0</td><td>100</td><td>0.24</td><td>22796.6</td><td>0.68%</td><td>0.7%</td><td>1108389</td><td>102.1</td></tr><tr><td>2-all</td><td>143</td><td>0</td><td>100</td><td>0.35</td><td>22796.5</td><td>0.68%</td><td>0.5%</td><td>1190879</td><td>169.0</td></tr></tbody></table>
<table><caption>Table 8: Detailed results for (SCPK) instance set 2 ($I = 30, J = 5$)</caption><thead><tr><th>inst</th><th>variant</th><th>C cuts</th><th>U cuts</th><th>P cuts</th><th>P cuts vio</th><th>r value</th><th>r-gap</th><th>user time</th><th>#nodes</th><th>time/gap</th></tr></thead><tbody><tr><td rowspan="10">21</td><td>1-C</td><td>605</td><td>-</td><td>-</td><td>-</td><td>6672.83</td><td>1.14%</td><td>-</td><td>10830484</td><td>0.08%</td></tr><tr><td>1-U</td><td>-</td><td>482</td><td>-</td><td>-</td><td>6675.75</td><td>1.18%</td><td>1.2%</td><td>18347628</td><td>1387.1</td></tr><tr><td>2-P</td><td>-</td><td>-</td><td>100</td><td>0.21</td><td>6643.91</td><td>0.70%</td><td>57.6%</td><td>1381</td><td>1.0</td></tr><tr><td>1-C+U</td><td>354</td><td>25</td><td>-</td><td>-</td><td>6672.14</td><td>1.13%</td><td>0.4%</td><td>17067043</td><td>2390.8</td></tr><tr><td>2-C+P</td><td>4</td><td>-</td><td>2</td><td>0.48</td><td>6597.65</td><td>0.00%</td><td>43.2%</td><td>0</td><td>0.0</td></tr><tr><td>2-P+U</td><td>-</td><td>0</td><td>100</td><td>0.21</td><td>6643.91</td><td>0.70%</td><td>71.2%</td><td>1381</td><td>1.2</td></tr><tr><td>2-all</td><td>4</td><td>0</td><td>2</td><td>0.48</td><td>6597.65</td><td>0.00%</td><td>41.9%</td><td>0</td><td>0.0</td></tr><tr><td>1-C</td><td>605</td><td>-</td><td>-</td><td>-</td><td>42275.2</td><td>0.35%</td><td>-</td><td>1791840</td><td>871.6</td></tr><tr><td>1-U</td><td>-</td><td>306</td><td>-</td><td>-</td><td>42290.1</td><td>0.39%</td><td>2.5%</td><td>1722333</td><td>172.2</td></tr><tr><td>2-P</td><td>-</td><td>-</td><td>100</td><td>0.33</td><td>42301.2</td><td>0.41%</td><td>0.6%</td><td>1133096</td><td>116.0</td></tr><tr><td rowspan="4">22</td><td>1-C+U</td><td>342</td><td>61</td><td>-</td><td>-</td><td>42271.1</td><td>0.34%</td><td>0.2%</td><td>1974608</td><td>678.0</td></tr><tr><td>2-C+P</td><td>263</td><td>-</td><td>100</td><td>0.06</td><td>42273.2</td><td>0.35%</td><td>0.2%</td><td>1052428</td><td>339.6</td></tr><tr><td>2-P+U</td><td>-</td><td>0</td><td>100</td><td>0.33</td><td>42301.2</td><td>0.41%</td><td>0.7%</td><td>1133096</td><td>104.2</td></tr><tr><td>2-all</td><td>262</td><td>3</td><td>100</td><td>0.07</td><td>42271.0</td><td>0.34%</td><td>0.3%</td><td>1097905</td><td>331.4</td></tr><tr><td rowspan="10">23</td><td>1-C</td><td>227</td><td>-</td><td>-</td><td>-</td><td>7961.65</td><td>1.33%</td><td>-</td><td>31200</td><td>4.4</td></tr><tr><td>1-U</td><td>-</td><td>291</td><td>-</td><td>-</td><td>7962.61</td><td>1.35%</td><td>1.8%</td><td>6100604</td><td>479.0</td></tr><tr><td>2-P</td><td>-</td><td>-</td><td>100</td><td>0.21</td><td>8051.68</td><td>2.48%</td><td>0.5%</td><td>25484185</td><td>2344.5</td></tr><tr><td>1-C+U</td><td>360</td><td>9</td><td>-</td><td>-</td><td>7961.65</td><td>1.33%</td><td>0.2%</td><td>3351591</td><td>652.8</td></tr><tr><td>2-C+P</td><td>263</td><td>-</td><td>100</td><td>0.26</td><td>7957.28</td><td>1.28%</td><td>0.4%</td><td>3523210</td><td>665.0</td></tr><tr><td>2-P+U</td><td>-</td><td>291</td><td>100</td><td>0.21</td><td>7962.61</td><td>1.35%</td><td>1.5%</td><td>5231512</td><td>571.1</td></tr><tr><td>2-all</td><td>261</td><td>6</td><td>100</td><td>0.24</td><td>7961.65</td><td>1.33%</td><td>0.5%</td><td>3531747</td><td>596.7</td></tr><tr><td>1-C</td><td>218</td><td>-</td><td>-</td><td>-</td><td>28987.0</td><td>0.25%</td><td>-</td><td>67547</td><td>9.8</td></tr><tr><td>1-U</td><td>-</td><td>9</td><td>-</td><td>-</td><td>29027.2</td><td>0.39%</td><td>0.9%</td><td>4945832</td><td>235.2</td></tr><tr><td>2-P</td><td>-</td><td>-</td><td>0</td><td>nan</td><td>29030.7</td><td>0.40%</td><td>4.9%</td><td>4911185</td><td>245.0</td></tr><tr><td rowspan="4">24</td><td>1-C+U</td><td>358</td><td>12</td><td>-</td><td>-</td><td>28987.0</td><td>0.25%</td><td>0.3%</td><td>1960764</td><td>408.0</td></tr><tr><td>2-C+P</td><td>363</td><td>-</td><td>0</td><td>nan</td><td>28987.0</td><td>0.25%</td><td>2.5%</td><td>2256372</td><td>463.9</td></tr><tr><td>2-P+U</td><td>-</td><td>9</td><td>0</td><td>nan</td><td>29027.2</td><td>0.39%</td><td>5.6%</td><td>4945832</td><td>220.2</td></tr><tr><td>2-all</td><td>360</td><td>9</td><td>0</td><td>nan</td><td>28987.4</td><td>0.25%</td><td>2.7%</td><td>2494889</td><td>465.7</td></tr><tr><td rowspan="10">25</td><td>1-C</td><td>605</td><td>-</td><td>-</td><td>-</td><td>28438.1</td><td>0.66%</td><td>-</td><td>12354812</td><td>0.16%</td></tr><tr><td>1-U</td><td>-</td><td>6</td><td>-</td><td>-</td><td>28455.7</td><td>0.72%</td><td>0.9%</td><td>28764074</td><td>1537.8</td></tr><tr><td>2-P</td><td>-</td><td>-</td><td>0</td><td>nan</td><td>28456.6</td><td>0.73%</td><td>1.8%</td><td>28518001</td><td>1509.9</td></tr><tr><td>1-C+U</td><td>360</td><td>9</td><td>-</td><td>-</td><td>28438.1</td><td>0.66%</td><td>0.2%</td><td>14436657</td><td>0.2%</td></tr><tr><td>2-C+P</td><td>363</td><td>-</td><td>0</td><td>nan</td><td>28438.1</td><td>0.66%</td><td>0.6%</td><td>14007958</td><td>0.2%</td></tr><tr><td>2-P+U</td><td>-</td><td>6</td><td>0</td><td>nan</td><td>28455.7</td><td>0.72%</td><td>2.1%</td><td>28764074</td><td>1412.8</td></tr><tr><td>2-all</td><td>361</td><td>6</td><td>0</td><td>nan</td><td>28438.1</td><td>0.66%</td><td>0.7%</td><td>14962100</td><td>0.19%</td></tr><tr><td>1-C</td><td>5</td><td>-</td><td>-</td><td>-</td><td>13369.2</td><td>0.29%</td><td>-</td><td>1507</td><td>0.2</td></tr><tr><td>1-U</td><td>-</td><td>368</td><td>-</td><td>-</td><td>13377.6</td><td>0.35%</td><td>75.8%</td><td>24847</td><td>11.6</td></tr><tr><td>2-P</td><td>-</td><td>-</td><td>1</td><td>0.98</td><td>13385.3</td><td>0.41%</td><td>92.3%</td><td>23136</td><td>18.7</td></tr><tr><td rowspan="4">26</td><td>1-C+U</td><td>194</td><td>102</td><td>-</td><td>-</td><td>13363.2</td><td>0.24%</td><td>59.7%</td><td>4324</td><td>1.7</td></tr><tr><td>2-C+P</td><td>237</td><td>-</td><td>10</td><td>0.1</td><td>13369.2</td><td>0.29%</td><td>94.0%</td><td>5115</td><td>16.4</td></tr><tr><td>2-P+U</td><td>-</td><td>66</td><td>1</td><td>0.98</td><td>13377.4</td><td>0.35%</td><td>92.6%</td><td>23300</td><td>20.6</td></tr><tr><td>2-all</td><td>176</td><td>123</td><td>10</td><td>0.12</td><td>13363.2</td><td>0.24%</td><td>96.1%</td><td>4771</td><td>18.7</td></tr><tr><td rowspan="10">27</td><td>1-C</td><td>605</td><td>-</td><td>-</td><td>-</td><td>8548.64</td><td>1.17%</td><td>-</td><td>2834093</td><td>778.5</td></tr><tr><td>1-U</td><td>-</td><td>390</td><td>-</td><td>-</td><td>8544.39</td><td>1.12%</td><td>2.0%</td><td>6337030</td><td>618.0</td></tr><tr><td>2-P</td><td>-</td><td>-</td><td>14</td><td>0.43</td><td>8453.1</td><td>0.04%</td><td>59.8%</td><td>3</td><td>0.1</td></tr><tr><td>1-C+U</td><td>228</td><td>218</td><td>-</td><td>-</td><td>8544.35</td><td>1.12%</td><td>0.8%</td><td>4590923</td><td>820.1</td></tr><tr><td>2-C+P</td><td>2</td><td>-</td><td>5</td><td>0.41</td><td>8454.58</td><td>0.06%</td><td>34.3%</td><td>0</td><td>0.0</td></tr><tr><td>2-P+U</td><td>-</td><td>0</td><td>14</td><td>0.43</td><td>8453.1</td><td>0.04%</td><td>89.6%</td><td>3</td><td>0.2</td></tr><tr><td>2-all</td><td>2</td><td>0</td><td>5</td><td>0.41</td><td>8454.58</td><td>0.06%</td><td>34.6%</td><td>0</td><td>0.0</td></tr><tr><td>1-C</td><td>605</td><td>-</td><td>-</td><td>-</td><td>9552.2</td><td>0.38%</td><td>-</td><td>5278948</td><td>2040.7</td></tr><tr><td>1-U</td><td>-</td><td>9</td><td>-</td><td>-</td><td>9577.34</td><td>0.65%</td><td>1.0%</td><td>4911215</td><td>260.5</td></tr><tr><td>2-P</td><td>-</td><td>-</td><td>30</td><td>0.91</td><td>9562.54</td><td>0.49%</td><td>2.7%</td><td>5299676</td><td>450.9</td></tr><tr><td rowspan="4">28</td><td>1-C+U</td><td>356</td><td>18</td><td>-</td><td>-</td><td>9551.93</td><td>0.38%</td><td>0.2%</td><td>4876800</td><td>1175.8</td></tr><tr><td>2-C+P</td><td>268</td><td>-</td><td>95</td><td>0.18</td><td>9549.92</td><td>0.36%</td><td>2.5%</td><td>1573932</td><td>430.4</td></tr><tr><td>2-P+U</td><td>-</td><td>3</td><td>37</td><td>0.63</td><td>9562.5</td><td>0.49%</td><td>3.3%</td><td>4748985</td><td>377.5</td></tr><tr><td>2-all</td><td>259</td><td>12</td><td>100</td><td>0.27</td><td>9549.69</td><td>0.36%</td><td>2.0%</td><td>2078450</td><td>507.8</td></tr><tr><td rowspan="10">29</td><td>1-C</td><td>605</td><td>-</td><td>-</td><td>-</td><td>12865.2</td><td>1.07%</td><td>-</td><td>9946516</td><td>0.28%</td></tr><tr><td>1-U</td><td>-</td><td>696</td><td>-</td><td>-</td><td>12914.1</td><td>1.46%</td><td>1.1%</td><td>26036123</td><td>0.47%</td></tr><tr><td>2-P</td><td>-</td><td>-</td><td>100</td><td>0.37</td><td>12870.7</td><td>1.11%</td><td>0.4%</td><td>14287036</td><td>1691.6</td></tr><tr><td>1-C+U</td><td>335</td><td>72</td><td>-</td><td>-</td><td>12860.9</td><td>1.04%</td><td>0.3%</td><td>18331800</td><td>0.41%</td></tr><tr><td>2-C+P</td><td>263</td><td>-</td><td>100</td><td>0.29</td><td>12825.7</td><td>0.76%</td><td>0.2%</td><td>8591393</td><td>1876.6</td></tr><tr><td>2-P+U</td><td>-</td><td>0</td><td>100</td><td>0.37</td><td>12870.7</td><td>1.11%</td><td>0.4%</td><td>14287036</td><td>1542.3</td></tr><tr><td>2-all</td><td>259</td><td>12</td><td>100</td><td>0.29</td><td>12825.2</td><td>0.76%</td><td>0.3%</td><td>7896841</td><td>1656.6</td></tr><tr><td>1-C</td><td>5</td><td>-</td><td>-</td><td>-</td><td>36394.2</td><td>0.25%</td><td>-</td><td>6657</td><td>0.6</td></tr><tr><td>1-U</td><td>-</td><td>462</td><td>-</td><td>-</td><td>36424.9</td><td>0.33%</td><td>13.0%</td><td>507285</td><td>61.2</td></tr><tr><td>2-P</td><td>-</td><td>-</td><td>1</td><td>0.3</td><td>36444.2</td><td>0.39%</td><td>16.2%</td><td>626080</td><td>36.9</td></tr><tr><td rowspan="4">30</td><td>1-C+U</td><td>350</td><td>39</td><td>-</td><td>-</td><td>36392.1</td><td>0.24%</td><td>0.8%</td><td>121340</td><td>38.1</td></tr><tr><td>2-C+P</td><td>362</td><td>-</td><td>1</td><td>0.3</td><td>36394.2</td><td>0.25%</td><td>14.2%</td><td>117803</td><td>42.4</td></tr><tr><td>2-P+U</td><td>-</td><td>231</td><td>1</td><td>0.3</td><td>36426.7</td><td>0.34%</td><td>28.5%</td><td>435076</td><td>44.4</td></tr><tr><td>2-all</td><td>346</td><td>48</td><td>1</td><td>0.3</td><td>36392.1</td><td>0.24%</td><td>15.5%</td><td>123822</td><td>42.0</td></tr></tbody></table>
<table><caption>Table 9: Detailed results for (SCPK) instance set 3 ($I = 20, J = 10$)</caption><thead><tr><th>inst</th><th>variant</th><th>C cuts</th><th>U cuts</th><th>P cuts</th><th>P cuts vio</th><th>r value</th><th>r-gap</th><th>user time</th><th>#nodes</th><th>time/gap</th></tr></thead><tbody><tr><td rowspan="8">41</td><td>1-C</td><td>905</td><td>-</td><td>-</td><td>-</td><td>39387.8</td><td>0.56%</td><td>-</td><td>1147464</td><td>805.1</td></tr><tr><td>1-U</td><td>-</td><td>108</td><td>-</td><td>-</td><td>39392.1</td><td>0.57%</td><td>1.2%</td><td>988599</td><td>92.3</td></tr><tr><td>2-P</td><td>-</td><td>-</td><td>100</td><td>0.18</td><td>39395.3</td><td>0.58%</td><td>0.5%</td><td>1073907</td><td>138.9</td></tr><tr><td>1-C+U</td><td>536</td><td>21</td><td>-</td><td>-</td><td>39376.9</td><td>0.53%</td><td>0.1%</td><td>1007053</td><td>619.0</td></tr><tr><td>2-C+P</td><td>443</td><td>-</td><td>100</td><td>0.17</td><td>39268.5</td><td>0.25%</td><td>1.3%</td><td>31038</td><td>16.6</td></tr><tr><td>2-P+U</td><td>-</td><td>18</td><td>100</td><td>0.29</td><td>39381.2</td><td>0.54%</td><td>0.9%</td><td>1006298</td><td>118.7</td></tr><tr><td>2-all</td><td>432</td><td>24</td><td>100</td><td>0.19</td><td>39267.1</td><td>0.25%</td><td>2.6%</td><td>30758</td><td>15.2</td></tr><tr><td>1-C</td><td>770</td><td>-</td><td>-</td><td>-</td><td>-</td><td>43984.0</td><td>0.61%</td><td>-</td><td>3693204</td><td>2452.6</td></tr><tr><td>1-U</td><td>-</td><td>101</td><td>-</td><td>-</td><td>-</td><td>43984.2</td><td>0.61%</td><td>1.2%</td><td>3358215</td><td>250.5</td></tr><tr><td>2-P</td><td>-</td><td>-</td><td>15</td><td>0.08</td><td>-</td><td>44062.4</td><td>0.79%</td><td>2.0%</td><td>4544901</td><td>292.8</td></tr><tr><td rowspan="5">42</td><td>1-C+U</td><td>534</td><td>18</td><td>-</td><td>-</td><td>43973.6</td><td>0.58%</td><td>0.1%</td><td>3203088</td><td>1441.7</td></tr><tr><td>2-C+P</td><td>443</td><td>-</td><td>100</td><td>0.07</td><td>43984.0</td><td>0.61%</td><td>0.3%</td><td>3185171</td><td>1208.5</td></tr><tr><td>2-P+U</td><td>-</td><td>101</td><td>7</td><td>0.08</td><td>43984.2</td><td>0.61%</td><td>2.7%</td><td>3833602</td><td>263.0</td></tr><tr><td>2-all</td><td>437</td><td>15</td><td>100</td><td>0.07</td><td>43973.6</td><td>0.58%</td><td>0.3%</td><td>3001514</td><td>1101.1</td></tr><tr><td>1-C</td><td>605</td><td>-</td><td>-</td><td>-</td><td>-</td><td>35842.2</td><td>0.30%</td><td>-</td><td>2358605</td><td>725.3</td></tr><tr><td rowspan="8">43</td><td>1-U</td><td>-</td><td>9</td><td>-</td><td>-</td><td>35855.1</td><td>0.34%</td><td>0.6%</td><td>2289708</td><td>164.6</td></tr><tr><td>2-P</td><td>-</td><td>-</td><td>0</td><td>nan</td><td>35856.8</td><td>0.34%</td><td>3.8%</td><td>2173793</td><td>152.1</td></tr><tr><td>1-C+U</td><td>360</td><td>9</td><td>-</td><td>-</td><td>35841.5</td><td>0.30%</td><td>0.2%</td><td>2062250</td><td>613.7</td></tr><tr><td>2-C+P</td><td>363</td><td>-</td><td>0</td><td>nan</td><td>35842.2</td><td>0.30%</td><td>1.0%</td><td>2086498</td><td>606.1</td></tr><tr><td>2-P+U</td><td>-</td><td>9</td><td>0</td><td>nan</td><td>35856.1</td><td>0.34%</td><td>4.0%</td><td>2287786</td><td>143.7</td></tr><tr><td>2-all</td><td>361</td><td>6</td><td>0</td><td>nan</td><td>35841.5</td><td>0.30%</td><td>1.2%</td><td>1983926</td><td>547.7</td></tr><tr><td>1-C</td><td>560</td><td>-</td><td>-</td><td>-</td><td>-</td><td>27403.7</td><td>0.49%</td><td>-</td><td>11954214</td><td>0.09%</td></tr><tr><td>1-U</td><td>-</td><td>12</td><td>-</td><td>-</td><td>-</td><td>27409.7</td><td>0.51%</td><td>0.8%</td><td>15852557</td><td>935.6</td></tr><tr><td rowspan="5">44</td><td>2-P</td><td>-</td><td>-</td><td>100</td><td>0.19</td><td>-</td><td>27411.0</td><td>0.51%</td><td>0.7%</td><td>15539237</td><td>1120.6</td></tr><tr><td>1-C+U</td><td>362</td><td>21</td><td>-</td><td>-</td><td>-</td><td>27403.7</td><td>0.49%</td><td>0.2%</td><td>15865687</td><td>0.07%</td></tr><tr><td>2-C+P</td><td>263</td><td>-</td><td>100</td><td>0.14</td><td>-</td><td>27403.7</td><td>0.49%</td><td>0.2%</td><td>17989260</td><td>0.05%</td></tr><tr><td>2-P+U</td><td>-</td><td>12</td><td>100</td><td>0.17</td><td>-</td><td>27409.8</td><td>0.51%</td><td>0.8%</td><td>16270349</td><td>1049.5</td></tr><tr><td>2-all</td><td>259</td><td>12</td><td>100</td><td>0.11</td><td>-</td><td>27403.7</td><td>0.49%</td><td>0.3%</td><td>19431792</td><td>3546.4</td></tr><tr><td rowspan="8">45</td><td>1-C</td><td>519</td><td>-</td><td>-</td><td>-</td><td>-</td><td>41001.8</td><td>0.56%</td><td>-</td><td>760888</td><td>279.2</td></tr><tr><td>1-U</td><td>-</td><td>26</td><td>-</td><td>-</td><td>-</td><td>41001.5</td><td>0.56%</td><td>0.8%</td><td>877880</td><td>59.3</td></tr><tr><td>2-P</td><td>-</td><td>-</td><td>100</td><td>0.11</td><td>-</td><td>41002.8</td><td>0.56%</td><td>0.6%</td><td>973276</td><td>83.9</td></tr><tr><td>1-C+U</td><td>538</td><td>12</td><td>-</td><td>-</td><td>-</td><td>41001.1</td><td>0.56%</td><td>0.1%</td><td>855127</td><td>497.3</td></tr><tr><td>2-C+P</td><td>443</td><td>-</td><td>100</td><td>0.13</td><td>-</td><td>41001.8</td><td>0.56%</td><td>0.1%</td><td>914876</td><td>452.1</td></tr><tr><td>2-P+U</td><td>-</td><td>21</td><td>100</td><td>0.08</td><td>-</td><td>41001.5</td><td>0.56%</td><td>0.7%</td><td>939816</td><td>75.3</td></tr><tr><td>2-all</td><td>442</td><td>3</td><td>100</td><td>0.06</td><td>-</td><td>41001.1</td><td>0.56%</td><td>0.1%</td><td>902994</td><td>404.4</td></tr><tr><td>1-C</td><td>705</td><td>-</td><td>-</td><td>-</td><td>-</td><td>19874.4</td><td>0.82%</td><td>-</td><td>1633243</td><td>528.2</td></tr><tr><td>1-U</td><td>-</td><td>335</td><td>-</td><td>-</td><td>-</td><td>19837.3</td><td>0.63%</td><td>19.4%</td><td>1395433</td><td>171.9</td></tr><tr><td rowspan="5">46</td><td>2-P</td><td>-</td><td>-</td><td>14</td><td>0.22</td><td>-</td><td>19841.7</td><td>0.65%</td><td>8.5%</td><td>917318</td><td>74.2</td></tr><tr><td>1-C+U</td><td>320</td><td>267</td><td>-</td><td>-</td><td>-</td><td>19840.8</td><td>0.65%</td><td>6.1%</td><td>1650862</td><td>425.1</td></tr><tr><td>2-C+P</td><td>7</td><td>-</td><td>2</td><td>1.29</td><td>-</td><td>19730.3</td><td>0.09%</td><td>14.4%</td><td>0</td><td>0.0</td></tr><tr><td>2-P+U</td><td>-</td><td>6</td><td>9</td><td>0.3</td><td>-</td><td>19840.8</td><td>0.65%</td><td>9.4%</td><td>934128</td><td>70.0</td></tr><tr><td>2-all</td><td>7</td><td>3</td><td>1</td><td>1.57</td><td>-</td><td>19730.3</td><td>0.09%</td><td>88.3%</td><td>0</td><td>0.1</td></tr><tr><td rowspan="8">47</td><td>1-C</td><td>745</td><td>-</td><td>-</td><td>-</td><td>-</td><td>19858.7</td><td>0.76%</td><td>-</td><td>1042047</td><td>299.5</td></tr><tr><td>1-U</td><td>-</td><td>36</td><td>-</td><td>-</td><td>-</td><td>19867.0</td><td>0.80%</td><td>1.6%</td><td>1686472</td><td>102.6</td></tr><tr><td>2-P</td><td>-</td><td>-</td><td>0</td><td>nan</td><td>-</td><td>19870.6</td><td>0.82%</td><td>9.5%</td><td>1690735</td><td>105.8</td></tr><tr><td>1-C+U</td><td>535</td><td>21</td><td>-</td><td>-</td><td>-</td><td>19853.2</td><td>0.73%</td><td>0.4%</td><td>1609470</td><td>383.8</td></tr><tr><td>2-C+P</td><td>543</td><td>-</td><td>0</td><td>nan</td><td>-</td><td>19858.7</td><td>0.76%</td><td>2.6%</td><td>1651034</td><td>412.1</td></tr><tr><td>2-P+U</td><td>-</td><td>36</td><td>0</td><td>nan</td><td>-</td><td>19867.0</td><td>0.80%</td><td>10.9%</td><td>1689543</td><td>101.2</td></tr><tr><td>2-all</td><td>535</td><td>18</td><td>1</td><td>0.38</td><td>-</td><td>19853.2</td><td>0.73%</td><td>3.3%</td><td>1693933</td><td>371.2</td></tr><tr><td>1-C</td><td>475</td><td>-</td><td>-</td><td>-</td><td>-</td><td>2311.63</td><td>2.08%</td><td>-</td><td>13556897</td><td>2597.2</td></tr><tr><td>1-U</td><td>-</td><td>183</td><td>-</td><td>-</td><td>-</td><td>2322.33</td><td>2.55%</td><td>0.9%</td><td>13346766</td><td>867.4</td></tr><tr><td rowspan="5">48</td><td>2-P</td><td>-</td><td>-</td><td>39</td><td>0.23</td><td>-</td><td>2323.39</td><td>2.60%</td><td>3.0%</td><td>12000229</td><td>738.3</td></tr><tr><td>1-C+U</td><td>293</td><td>16</td><td>-</td><td>-</td><td>-</td><td>2311.63</td><td>2.08%</td><td>0.3%</td><td>12412538</td><td>2026.0</td></tr><tr><td>2-C+P</td><td>200</td><td>-</td><td>100</td><td>0.16</td><td>-</td><td>2311.63</td><td>2.08%</td><td>0.9%</td><td>12719732</td><td>1789.5</td></tr><tr><td>2-P+U</td><td>-</td><td>183</td><td>100</td><td>0.22</td><td>-</td><td>2322.68</td><td>2.57%</td><td>2.2%</td><td>12753438</td><td>1004.9</td></tr><tr><td>2-all</td><td>194</td><td>13</td><td>100</td><td>0.17</td><td>-</td><td>2311.63</td><td>2.08%</td><td>0.7%</td><td>12334318</td><td>1638.7</td></tr><tr><td rowspan="8">49</td><td>1-C</td><td>905</td><td>-</td><td>-</td><td>-</td><td>-</td><td>2274.55</td><td>3.33%</td><td>-</td><td>840705</td><td>359.1</td></tr><tr><td>1-U</td><td>-</td><td>1044</td><td>-</td><td>-</td><td>-</td><td>2272.52</td><td>3.23%</td><td>31.6%</td><td>828917</td><td>201.3</td></tr><tr><td>2-P</td><td>-</td><td>-</td><td>100</td><td>0.47</td><td>-</td><td>2220.74</td><td>0.88%</td><td>79.8%</td><td>45</td><td>0.6</td></tr><tr><td>1-C+U</td><td>140</td><td>633</td><td>-</td><td>-</td><td>-</td><td>2270.72</td><td>3.15%</td><td>16.1%</td><td>882489</td><td>217.6</td></tr><tr><td>2-C+P</td><td>1</td><td>-</td><td>100</td><td>0.36</td><td>-</td><td>2220.28</td><td>0.86%</td><td>76.8%</td><td>125</td><td>0.8</td></tr><tr><td>2-P+U</td><td>-</td><td>0</td><td>100</td><td>0.47</td><td>-</td><td>2220.74</td><td>0.88%</td><td>83.9%</td><td>45</td><td>0.6</td></tr><tr><td>2-all</td><td>1</td><td>0</td><td>100</td><td>0.36</td><td>-</td><td>2220.28</td><td>0.86%</td><td>81.0%</td><td>125</td><td>0.8</td></tr><tr><td>1-C</td><td>630</td><td>-</td><td>-</td><td>-</td><td>-</td><td>34994.5</td><td>0.54%</td><td>-</td><td>10303438</td><td>0.23%</td></tr><tr><td>1-U</td><td>-</td><td>12</td><td>-</td><td>-</td><td>-</td><td>35039.6</td><td>0.67%</td><td>0.8%</td><td>41293662</td><td>2296.7</td></tr><tr><td rowspan="5">50</td><td>2-P</td><td>-</td><td>-</td><td>0</td><td>nan</td><td>-</td><td>35041.0</td><td>0.67%</td><td>0.9%</td><td>42987493</td><td>2514.4</td></tr><tr><td>1-C+U</td><td>374</td><td>12</td><td>-</td><td>-</td><td>-</td><td>34993.7</td><td>0.54%</td><td>0.2%</td><td>14044700</td><td>0.21%</td></tr><tr><td>2-C+P</td><td>378</td><td>-</td><td>0</td><td>nan</td><td>-</td><td>34994.5</td><td>0.54%</td><td>0.3%</td><td>13951413</td><td>0.2%</td></tr><tr><td>2-P+U</td><td>-</td><td>12</td><td>0</td><td>nan</td><td>-</td><td>35039.6</td><td>0.67%</td><td>1.1%</td><td>35768862</td><td>1778.2</td></tr><tr><td>2-all</td><td>375</td><td>9</td><td>0</td><td>nan</td><td>-</td><td>34993.7</td><td>0.54%</td><td>0.3%</td><td>14563900</td><td>0.2%</td></tr></tbody></table>