# The Symmetric-weight Chain-Precedence Knapsack Polytope

Pascale Bendotti, Alexandre Heintzmann, Cécile Rottner

► To cite this version:

Pascale Bendotti, Alexandre Heintzmann, Cécile Rottner. The Symmetric-weight Chain-Precedence Knapsack Polytope. 2026. hal-05514630

HAL Id: hal-05514630

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

Preprint submitted on 17 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
# The Symmetric-weight Chain-Precedence Knapsack Polytope

Pascale Bendotti¹

Alexandre Heintzmann*

Cécile Rottner¹

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

February 17, 2026

## Abstract

We study the Symmetric-weight Chain Precedence Knapsack Problem (SCPK), a knapsack variant where items are partitioned into groups, and items in the same group are subject to chain-precedence constraints. The precedence chains and the item weights are identical across groups, inducing a rich set of polyhedral symmetries, defined as permutations of the variables that preserves the feasible set, independently of the objective function. The (SCPK) is motivated by hydro unit commitment problems, where operating points are activated cumulatively and associated water flows are identical across time periods. Rather than handling symmetry as a source of redundancy to be eliminated, we exploit the invariance of the (SCPK) polytope under permutations of the groups to guide its polyhedral description. We introduce the notion of *patterns*, symmetry-invariant objects that represent equivalence classes of valid inequalities. These are called *pattern inequalities* and generalize classical cover-type inequalities to this symmetric setting. We prove that pattern inequalities dominate existing binary inequalities derived from cover and induced cover approaches. Moreover, we show that all facet-defining inequalities of the (SCPK) with 0-1 coefficients are characterized by pattern inequalities. We provide necessary and, in a special case, sufficient conditions for a pattern inequality to be facet-defining. In a second paper, experimental results show the efficiency of pattern inequalities within a symmetry-aware Branch&Cut framework.

## 1 Introduction

The knapsack problem and its numerous variants play a central role in combinatorial optimization and integer programming, both from a theoretical and an applied perspective. Over the past decades, extensive polyhedral studies have led to strong formulations and cutting-plane methods for classical variants such as the Binary Knapsack Problem (BK), the Precedence Constrained Knapsack Problem (PK), and the Disjunctive Knapsack Problem (DK) (Hojny et al. (2020)). These advances have been instrumental in the design of efficient exact algorithms for large-scale industrial applications.

In this paper, we study a knapsack variant featuring polyhedral symmetries, defined as permutations of the variables that preserves the feasible set, independently of the objective function.

Symmetries play a fundamental role in the structure and complexity of many integer programming problems. Classically, symmetries are defined as *objective-preserving symmetries*, i.e., permutations of variables that map feasible solutions to feasible solutions with identical objective value. When present, such symmetries induce equivalence classes of feasible solutions with same objective value, and are typically handled by symmetry-breaking constraints or branching rules (Friedman 2007, Kaibel et al. 2007, Margot 2009, Bendotti et al. 2020, 2021), as they may otherwise lead to large amounts of redundant search in branch-and-bound algorithms.

Polyhedral symmetries are not objective-preserving symmetries, thus the aforementioned symmetry-breaking techniques cannot be used as such. However, polyhedral symmetries can be exploited to understand the geometry of the polytope and to derive entire families of facet-defining inequalities from a single representative. Despite their potential, polyhedral symmetries have received less attention

<footnote>*This research was carried during A. Heintzmann's PhD, funded by EDF.</footnote>
compared 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.

The knapsack variant considered in this paper is the Symmetric-weight Chain Precedence Knapsack Problem (SCPK), a knapsack problem where items are partitioned into groups, and items in the same group are subject to chain-precedence constraints. The precedence chains and the item weights are identical across groups, inducing a rich set of symmetries in the associated polytope: permuting the groups leaves the capacity structure unchanged and maps feasible solutions to feasible solutions without affecting their contribution to the knapsack constraint. More precisely, 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) 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. This symmetry in the weights induces polyhedral symmetries for the (SCPK) polytope, that are not present in general in classical knapsack variants. We define (*I*, *J*, *w*, *v*, *C*) an instance of the (SCPK). Figure 1 depicts a graphical representation of the (SCPK), where a square represents an item, and arrows stand for the chain precedence constraints.

<figure><img src="image_2.png" /><figcaption>Figure 1: Graphical representation of the (SCPK)</figcaption></figure>

The (SCPK) is primarily motivated by the Hydro Unit Commitment (HUC) problem (Hechme-Doukopoulos et al. (2010), Artigues et al. (2025)), a production scheduling problem relative to hydro-electric plants. More precisely, consider the single unit HUC (1-HUC) problem as follows. The time is discretized into *T* time periods. The hydro plant exclusively operates on *N* points. Operating point *i* ≤ *N* is a pair featuring the delivered water *D*ᵢ and the produced power *P*ᵢ sold at time-dependent price λᵢ, *t* ≤ *T*, denoted by (*D*ᵢ, *P*ᵢ · λᵢ). The operating points are activated in a cumulative fashion, i.e., operating point *i* at time period *t* activates all operating points *j* < *i* for the same time period. The main constraints are that the plant is located between two reservoirs with upper bounds and lower bounds on their volumes at each time period. The aim is to maximize the value of the 1-HUC problem, while verifying the volume constraints at each time period. The (SCPK) contains the main
constraints of the 1-HUC problem, as we show in the following. With $T = I$ time periods, $N = J$ operating points, to each item $(w_i, v_{it})$ corresponds an operating point $(D_i, P_i \cdot \lambda_t)$. By construction, operating points of the 1-HUC problem and items of the (SCPK) have the same chain precedence constraints. The main difference is that the HUC problem has $T$ upper and $T$ lower bounds on the volume of delivered water, while the (SCPK) has a unique upper bound on the total weight of the items. The $T$ upper bounds of the 1-HUC problem can be modeled with $T$ nested (SCPK), considering time periods $1$ to $t$ for each $t \le T$. As the $T$ (SCPK) are nested, they cannot be considered independently.

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)). In particular, the symmetric-weight assumption combined to the chain-precedence constraints fundamentally alters the polyhedral structure: an (SCPK) without precedence constraints would be with one item per group and reduce to a trivial (BK), where each item has the exact same weight. As a result, classical families of facet-defining inequalities, such as minimal cover inequalities or their lifted variants, are usually not facet-defining for the (SCPK) polytope. 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).

The contributions of this paper are summarized as follows. We formally define the Symmetric-weight Chain Precedence Knapsack Problem and prove that it is NP-hard. We introduce a compact integer linear formulation of the (SCPK) and study basic polyhedral properties of the associated polytope. In order to capture polyhedral symmetries of the (SCPK) polytope, we define the notion of patterns, which act as representatives for equivalence classes of symmetric valid inequalities. We show that the corresponding class of pattern inequalities are valid and dominate existing binary inequalities derived from cover and induced cover inequalities. We establish necessary conditions under which a pattern inequality is facet-defining and identify a special class of patterns for which these conditions are also sufficient. We show that all facet-defining inequalities of the (SCPK) with 0-1 coefficients are captured by pattern inequalities. A numerical comparison is provided in (Bendotti et al. (2025)) demonstrate the efficiency of such inequalities. It shows that pattern inequalities largely outperform CPLEX generated cuts, and can also outperform standard lifted minimal (induced) cover inequalities for variants of the KP.

The paper is organized as follows. In Section 2, we analyze the complexity of the (SCPK) and review relevant polyhedral results for related knapsack variants. Section 3 introduces pattern inequalities and presents the main polyhedral results. Necessary and sufficient facet-defining conditions are discussed in Section 4.

# 2 The Symmetric-weight Chain Precedence Knapsack problem

We first prove the NP-hardness of the (SCPK) in Section 2.1. A literature review of related problems is done in Section 2.2, and first polyhedral properties are provided in Section 2.3.

## 2.1 Complexity

Before stating the complexity of the (SCPK), we identify two straightforward special cases where the (SCPK) is easy to solve.

**Property 1.** Let $(I, J, w, v, C)$ be an instance of the (SCPK). If $I = 1$ or $J = 1$, the (SCPK) can be solved in polynomial time.

In the following, we only consider instances of the (SCPK) with $I \ge 2$ and $J \ge 2$. To state the complexity of the (SCPK), we recall the following two problems of the literature. The first problem is the Unbounded Integer Knapsack Problem (UIK), which is a knapsack problem where items can be selected an unlimited number of times. The second problem is the Subset Sum Problem (SSP),
where considering a set of positive integer $S$, and a target integer $W$, the aim is to find $S' \subseteq S$ such that the sum of all elements of $S'$ equals $W$. First a reduction from the (UIK) allows us to prove the NP-hardness of the (SCPK) when $I \ge \frac{C}{w_1}$. Then a reduction from the (SSP) enables us to prove the NP-hardness of the (SCPK) when $I \ge J$.

**Theorem 1.** The (SCPK) is NP-hard when $I \ge \frac{C}{w_1}$

**Theorem 2.** The (SCPK) is NP-hard when $I \ge J$

The proofs are provided respectively in **Appendices 6.1 and 6.2**. Note that the case of the (SCPK) where $I < \min(\frac{C}{w_1}, J)$ remains an open question. The (SCPK) and the (CPK) are generalizations of the Unbounded Integer Knapsack problem (UIK). Consequently the (CPK) is a generalization of both the (BK) and the (UIK). The Bounded Integer Knapsack problem (BIK) (Ceria et al. (1998)) is also a generalization of the (BK) and the (UIK). Indeed, the (BK) is a special case with upper bounds 1 on the number of repetition for each item, and the (UIK) is a special case with finite upper bound sufficiently large to not be restrictive. However, the (BIK) and the (SCPK) are not related. In fact, the (BIK) considers a maximum number of repetitions for each item, while the (SCPK) would be closer to an Integer Knapsack problem with a shared upper bound on the total number of items, repetition included. This shared upper bound is the number of groups $I$. As the chain precedence constraints are specific precedence constraints, the (CPK) is also a special case of the (PK). The chain precedence constraints can also be modeled as disjunctive constraints, hence the (CPK) is also a special case of the (DK). All connections between the knapsack problem variants are depicted in **Figure 2** with a graph in which each vertex represents a variant and each arc indicates that the variant at the tail is a generalization of the variant at the head.

<figure><img src="image_3.png" /><figcaption>Figure 2: Generalization orders of some variants of the knapsack problem</figcaption></figure>

## 2.2 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 with the Integer Linear Program (ILP) $F_{SCPK}$ as follows.

$$ \begin{array}{ll} \max_{x_{ij} \in \{0,1\}} & \sum_{i=1}^{I} \sum_{j=1}^{J} v_{ij}x_{ij} \\ \text{s.t.} & \sum_{i=1}^{I} \sum_{j=1}^{J} w_{ij}x_{ij} \le C, \\ & x_{ij} \le x_{ij-1}, \quad \forall x_{ij} \in \mathcal{V}, j \ge 2 \end{array} $$

In this formulation, the objective function is to maximize the total value of the selected items. Inequality (1) is the capacity constraint, inequalities (2) correspond to the chain precedence constraints. We define polytope $P_{(SCPK)}$ as the convex hull of the feasible solutions of the (SCPK):

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

The proposed formulation is the so-called *incremental formulation* (Markowitz and Manne (1957)). It is also possible to define a *multiple choice formulation*, featuring disjunctive constraints instead of chain precedence constraints (2). Both formulations yield the same LP relaxation (Croxton et al. (2003)), but we do not further detail the multiple choice formulation, as it is not necessary for the purpose of this paper.
We can remark that the (SCPK) features symmetries. Indeed, items have symmetric weights, the chain precedence constraints (2) are the same for each group, and the capacity constraint (1) applies to all groups. Hence, from a feasible solution, one can obtain another feasible solution by a permutation of the groups. However, the values of such solutions are not necessarily the same, as there are no symmetries in the values thus we fall into the case of polyhedral symmetries.

**Definition 1.** [(Bendotti et al. 2025)] A polyhedral symmetry is a permutation $\pi$ of the variables such that for any feasible solution $x$, $\pi(x)$ is also a feasible solution.

In other words, a polyhedral symmetry only concerns the constraints. This is a generalization of the classical symmetry which also restricts the objective values of symmetric solutions to be equal.

## 2.3 Related knapsack polytopes

The (SCPK) belongs to the broad family of knapsack problems and is closely related to several well-studied variants. In this section, we briefly review polyhedral results for knapsack problems that are structurally related to the (SCPK), with the objective of identifying which existing inequalities may extend to the (SCPK) and which limitations motivate the introduction of new classes of inequalities.

We focus on three main variants: the Binary Knapsack Problem (BK), the Disjunctive Knapsack Problem (DK), and the Precedence Constrained Knapsack Problem (PK). These problems encompass the (SCPK) in different ways and have been the subject of extensive polyhedral investigations.

### 2.3.1 Binary knapsack polytope

The Binary Knapsack Problem (BK) is defined on a set of items $V$, each with weight $w_j$ and value $v_j$, and a single capacity $C$ constraint. Its polyhedral structure has been widely studied. In particular, minimal cover inequalities, introduced by Balas (1975), constitute a fundamental class of facet-defining inequalities. A set $U \subseteq V$ is a cover if $\sum_{j \in U} w_j > C$, and a minimal cover if no proper subset of $U$ is a cover. The corresponding minimal cover inequality is $\sum_{j \in U} x_j \le |U| - 1$, and defines a facet of the binary knapsack polytope under mild conditions. A lifting for minimal cover inequalities is introduced in Letchford and Souli (2020) and several extensions have been proposed, including extended cover inequalities, (1, $k$)-configuration inequalities, and weight inequalities (see Del Pia et al. (2023) for a recent survey).

Although the (SCPK) is neither a special case nor a generalization of the (BK), cover-type inequalities play a central role in the development of polyhedral results for more complex knapsack variants. In particular, many polyhedral studies of the (PK) and (DK) rely on suitable generalizations of minimal cover inequalities. This observation motivates a careful examination of their relevance for the (SCPK).

### 2.3.2 Disjunctive knapsack polytope

The Disjunctive Knapsack Problem (DK) extends the (BK) by introducing conflicts between items, modeled through a disjunctive graph whose vertices correspond to items and whose edges represent pairs of items that cannot be selected simultaneously. A compact formulation includes both the capacity constraint and disjunctive constraints of the form $x_i + x_j \le 1$ for each edge $\{i, j\}$. Several families of facet-defining inequalities have been identified for the (DK), including clique inequalities, cover inequalities, odd-cycle inequalities, hypergraph inequalities, and their extensions Salem et al. (2018). These inequalities strongly exploit the structure of the underlying disjunctive graph.

In the (SCPK), chain precedence constraints can be reformulated as disjunctive constraints within each group. However, the resulting disjunctive graph has a very specific structure: conflicts only occur between items belonging to the same group, and no disjunctive edges exist across groups. As a consequence, the disjunctive graph of the SCPK decomposes into independent cliques, one per group. This very particular structure prevents the direct application of most (DK) inequalities. In particular, clique-based, odd-cycle, and hypergraph inequalities only yield trivial cuts for the SCPK. More generally, inequalities relying on interactions between different cliques in the disjunctive graph cannot capture the coupling induced by the single global capacity constraint of the SCPK.
### 2.3.3 Precedence constrained knapsack polytope

As stated previously, the (SCPK) is a special case of the (PK), defined as follows. 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$. A formulation of the (PK) is:

$$ \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, \ x_j \leq x_i \quad \text{if } j \text{ covers } i \right\}. $$

The minimal cover and related inequalities have been extended to the (PK) in Boyd (1993). To do so, lower-ideals are defined as sets $U \subset V$ such that if $i \in U$ and $j \prec i$, then $j \in U$. The minimal cover inequalities have been extended to the case of the (PK) with $U$ a minimal cover as well as a lower-ideal: $\sum_{j \in U} x_j \leq |U| - 1$. The minimal cover inequalities have been enhanced in the literature with various liftings. In Boyd (1993) a lifting procedure is described, starting from a facet of a lower-dimensional polyhedron. The lifting procedure provides valid inequalities that are not necessarily facet-defining for the (PK).

Minimal cover inequalities can also be adapted to the (PK) without the use of lower-ideals (Park and Park (1997), van de Leensel et al. (1999)). Let $A$ be the arcs of the precedence graph. The arc 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 any 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$. The MIC inequalities are as follows, with $U$ a MIC: $\sum_{j \in U} x_j \leq |U| - 1$. These MIC inequalities have been enhanced with a lifting procedure in 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 \leq |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) define 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. While MIC inequalities and associated liftings are applicable to the (SCPK), their expressive power is limited by the structure of the chain precedence constraints. In particular, in the (SCPK), precedence relations only occur within groups, which restricts the form of induced covers and their possible liftings.

**Property 2** (Bendotti et al. (2025)). Let $U$ be a MIC for the (SCPK). For all $(i, j) \in U_p$, the downlifting procedure yields $\alpha_{ij} = 0$.

Boland et al. (2012) define clique-based inequalities for the (PK). For this purpose, a disjunctive graph is introduced, where a vertex corresponds to an item. The edges are between each pair of vertices corresponding to a pair of item that cannot be into a feasible solution simultaneously without violating the capacity constraint. Such a type of inequality does not seem to adapt efficiently to the case of the (SCPK). Indeed, the disjunctive graph described does not have any edge if $C \geq 2 \sum_{j=1}^J w_j$, which is the case of the majority of large size instances of the (SCPK).

### Implications for the SCPK

The above review highlights that existing polyhedral approaches for the (BK), (DK), and (PK) do not fully exploit the specific structure of the (SCPK). In particular, none of these approaches explicitly accounts for the polyhedral symmetries induced by symmetric weights and for identical precedence chains across groups. This observation motivates the introduction of a new class of inequalities that directly leverages these symmetries and the chain precedence constraints. In Section 3, we introduce patterns, which provide a unifying framework to describe and analyze all facet-defining inequalities with binary coefficients for the (SCPK).
## 2.4 First polyhedral properties

**Definition 2** (Full-dimensional condition ($\mathcal{F}$)). An (SCPK) verifies ($\mathcal{F}$) if any item $(i, j)$, can be selected in at least one feasible solution.

**Property 3.** Any instance of the (SCPK) that does not verify ($\mathcal{F}$) can be transformed into an instance of the (SCPK) that verifies ($\mathcal{F}$), with the exact same solutions.

The proof is provided in Appendix 6.7. Without loss of generality, in the following we only consider (SCPK) instances verifying ($\mathcal{F}$).

**Definition 3** (Solution $X_{\mathcal{X}}$). For a variable set $\mathcal{X}$, solution $X_{\mathcal{X}}$ is the solution with $x_{ij} = 1$ for each $(i, j) \in N \times M$ such that $\exists j' \ge j$ and $(i, j') \in \mathcal{X}$, and $x_{ij} = 0$ otherwise.

We denote by $X_{ij}$ the set $\mathcal{X} = \{x_{ij}\}$, and $X_{\emptyset}$ the set $\mathcal{X} = \emptyset$. To ensure that the chain precedence constraints are taken into account while considering a solution $X_{\mathcal{X}}$, we introduce the set weights associated with a set of variables $\mathcal{X}$.

**Definition 4** (Set weights). For a given $\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 } x_{ij} \notin \mathcal{X}, \\ \sum_{k=j'+1}^{j} w_k & \text{if } x_{ij} \in \mathcal{X} \text{ with } j' = \max\{j'|x_{ij'} \in \mathcal{X}, j' < j\}, \\ \sum_{k=1}^{j} w_k & \text{if } x_{ij} \in \mathcal{X} \text{ and } x_{ij'} \notin \mathcal{X}, \forall j' < j. \end{cases}$$

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

We now define $\mathcal{Y}$ as a $k$-intersection of $\mathcal{X}$ if $\mathcal{Y}$ contains $k$ elements of $\mathcal{X}$ that can all be selected simultaneously in a feasible solution of the (SCPK).

**Definition 5** ($k$-intersection). Let $\mathcal{X}, \mathcal{Y}$ be sets of variables. Variable set $\mathcal{Y}$ is a $k$-intersection of $\mathcal{X}$ if $|\mathcal{Y} \cap \mathcal{X}| = k$, for each variable $x_{ij} \in \mathcal{Y}$ if $x_{ij'} \in \mathcal{X}$ with $j' \le j$, then $x_{ij'} \in \mathcal{Y}$ and $\sum_{x_{ij'} \in \mathcal{Y}} s_{ij}(\mathcal{Y}) \le C$.

If $\mathcal{Y}$ is $k$-intersection of $\mathcal{X}$, the reverse can also be true. Consequently, a $k$-intersection of $\mathcal{X}$ is not necessarily a subset of $\mathcal{X}$.

**Property 4.** Let $\mathcal{X}$ be a set of variables. Let $\mathcal{Y}$ be a $k$-intersection of $\mathcal{X}$. There exists a set $\mathcal{Y}' \subseteq \mathcal{Y}$, a $k$-intersection of $\mathcal{X}$ with $|\mathcal{Y}'| = k$.

*Proof.* Consider $\mathcal{Y}' = \mathcal{Y} \cap \mathcal{X}$. Clearly, $|\mathcal{Y}'| = k$ and $\mathcal{Y}' \cap \mathcal{X} = k$. Besides, $\mathcal{Y}' \subseteq \mathcal{Y}$, all weight of positives, and there are chain precedence constraints, hence if $X_{\mathcal{Y}}$ is valid, then so is $X_{\mathcal{Y}'}$. Consequently, $\mathcal{Y}'$ is also a $k$-intersection of $\mathcal{X}$. $\square$

**Example 1** ($k$-intersection). Let $(3, 3, [1, 3, 2], v, 12)$ be an instance of the (SCPK). Let $\mathcal{X} = \{x_{11}, x_{13}, x_{22}, x_{31}\}$ and $\mathcal{Y} = \{x_{11}, x_{13}, x_{21}, x_{22}\}$ be two variable sets. In this case, $\mathcal{Y}$ is a 3-intersection of $\mathcal{X}$. Indeed, $|\mathcal{X} \cap \mathcal{Y}| = 3$, $s_{11}(\mathcal{Y}) + s_{13}(\mathcal{Y}) + s_{21}(\mathcal{Y}) + s_{22}(\mathcal{Y}) = 1 + 5 + 1 + 3 = 10 \le C = 12$. However, $\mathcal{X}$ is not a 3-intersection of $\mathcal{Y}$. Indeed, $|\mathcal{X} \cap \mathcal{Y}| = 3$ and $s_{11}(\mathcal{X}) + s_{13}(\mathcal{X}) + s_{22}(\mathcal{X}) + s_{31}(\mathcal{X}) = 1 + 5 + 4 + 1 = 11 \le C = 12$, but there is $x_{21} \in \mathcal{Y}$ and $x_{21} \notin \mathcal{X}$ even if $x_{22} \in \mathcal{X}$.

**Theorem 3.** $P_{(SCPK)}$ is full dimensional.

The proof is provided in Appendix 6.3. With the dimension of $P_{(SCPK)}$ it becomes possible to characterize when chain precedence inequalities and trivial inequalities with bounds at 0 are facet-defining. Proofs of Theorems 4, 5 and 6 are provided in **Appendices** 6.4, 6.5 and 6.6.

**Theorem 4.** Inequalities $x_{ij} \ge 0$ are facet-defining for $P_{(SCPK)}$ if and only if $j = J$.

**Theorem 5.** Inequalities $x_{ij} \le x_{ij-1}$ are facet-defining for $P_{(SCPK)}$.

Contrary to trivial inequalities with bound at 0 and the chain precedence constraints which always contain facet-defining inequalities, the bounds 1 require a minimum capacity $C$ to contain facet-defining inequalities.
<figure><img src="image_4.png" /><figcaption>Figure 3: Graphical representation of pattern $\mathcal{P} = \{\{1,2\}, \{1,4\}, \{2,3\}, \{2,4\}\}$ for $I = 4$ and $J = 4$</figcaption></figure>

**Theorem 6.** Inequalities $x_{ij} \le 1$ are facet-defining for $P_{(SCPK)}$ if and only if $j = 1$ and $C \ge \sum_{j=1}^J w_j + w_1$.

Like the (BK), the (SCPK) features three types of facet-defining inequalities: the ones from the initial formulation, *binary inequalities* with 0-1 coefficients, and *integer inequalities*, with non-negative integer coefficients. In the following **Example 2** shows the convex hull of an instance of the (SCPK).

**Example 2 (Convex hull of the (SCPK)).** Let (4, 3, [3, 4, 2], v, 9) be an instance of the (SCPK). The convex hull obtained with PORTA (Christof and Löbel (2009)) contains the following inequalities of the formulation, proven to be facet-defining in **Theorem 4** and **Theorem 5**.

$$x_{13} \ge 0, \quad x_{23} \ge 0, \quad x_{33} \ge 0, \quad x_{43} \ge 0,$$

$$x_{11} \ge x_{12}, \quad x_{12} \ge x_{13}, \quad x_{21} \ge x_{22}, \quad x_{22} \ge x_{23},$$

$$x_{31} \ge x_{32}, \quad x_{32} \ge x_{33}, \quad x_{41} \ge x_{42}, \quad x_{42} \ge x_{43}$$

It contains also the following inequalities:

$$x_{12} + x_{22} + x_{32} + x_{41} \le 1, \quad x_{12} + x_{22} + x_{31} + x_{42} \le 1, \quad x_{12} + x_{21} + x_{32} + x_{42} \le 1,$$

$$x_{11} + x_{22} + x_{32} + x_{42} \le 1, \quad x_{11} + 2x_{12} + x_{21} + 2x_{22} + x_{31} + 2x_{32} + x_{41} + 2x_{42} \le 3.$$

This instance does not verify the condition described in Theorem 6, as $9 < 3 + 4 + 2 + 3 = 12$. Hence, none of the inequalities $x_{i1} \le 1$ are facet-defining in this example.

# 3 Pattern inequalities

In this section we introduce new valid inequalities for the (SCPK). To handle the polyhedral symmetries efficiently, we introduce a structure called pattern.

**Definition 6 (Pattern).** 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 permutation of item sets of the (SCPK). As the aim is to produce inequalities from the patterns, we define the variable sets associated with a pattern.

**Example 3 (Pattern).** Consider an instance of the (SCPK) with 4 groups and 4 items per group. One can define pattern $\mathcal{P} = \{\{1,2\}, \{1,4\}, \{2,3\}, \{2,4\}\}$, as represented on Figure 3. The idea behind pattern $\mathcal{P}$ is that it will represent any solution where a group selects items 1 and 2, another group selects items 1 and 4, another group selects items 2 and 3 and finally another group selects items 2 and 4.

**Definition 7 (Variable set $\mathcal{X}$ associated with $\mathcal{P}$).** A set of variables $\mathcal{X} \subseteq \mathcal{V}$ is associated with pattern $\mathcal{P}$ and a permutation $\pi$ of $\{1, \dots, I\}$ if: $x_{ij} \in \mathcal{X} \Leftrightarrow j \in S_{\pi(i)}(\mathcal{P})$.

We denote $\Omega(\mathcal{P})$ the set of all variable sets associated with $\mathcal{P}$. Note that $|\Omega(\mathcal{P})|$ is in general exponential. We also denote $\mathcal{X}(\mathcal{P})$ the variable set $\mathcal{X} \in \Omega(\mathcal{P})$ 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 and the proofs. The cardinality of a pattern $\mathcal{P}$ is the cardinality of any variable set associated with $\mathcal{P}$.
**Definition 8** (*card(P)*). The cardinality of a pattern *P* is $card(P) = \sum_{i \le I} |S_i(P)|$.

The rank of a pattern *P* is the valid upper bound for the sum of variables in *X(P)*. It can be polynomially computed with a shortest path algorithm (Bendotti et al. (2025)).

**Definition 9** (*rank(P)*). The rank of a pattern *P* is

$$ \mathrm{rank}(\mathcal{P}) = \left\{ \max \sum_{x_{ij} \in \mathcal{X}(\mathcal{P})} x_{ij} : \text{satisfying } (1) - (2) \right\}. $$

With *rank(P)* and *Ω(P)*, we can define the inequalities of a pattern *P* as follows.

**Definition 10** (Pattern inequalities). The pattern inequalities associated with a pattern *P* are the following, for any *X* ∈ Ω(*P*):

$$ \sum_{x_{ij} \in \mathcal{X}} x_{ij} \le \mathrm{rank}(\mathcal{P}) \quad (\mathrm{pi}(\mathcal{X})) $$

**Property 5.** Pattern inequalities are valid for $P_{(SCPK)}$.

*Proof.* By definition of the rank, and by symmetry of the weights, pattern inequalities are valid. □

We show in the following property that pattern inequalities can capture binary inequalities that are captured neither by minimal cover inequalities nor by (lifted) MIC inequalities.

**Property 6.** Pattern inequalities dominate minimal cover inequalities as well as MIC inequalities and binary lifted MIC inequalities.

*Proof.* Clearly, any binary inequality with the tightest right hand side can be represented by a pattern inequality. Hence, any binary inequality is either captured by pattern inequalities, or dominated by a pattern inequality. Besides, the following counter-example (Example 4) exhibits a facet-defining inequality of the (SCPK) which can be obtained neither by minimal cover inequalities nor by (lifted) MIC inequalities.

**Example 4** (Dominance of pattern inequalities). Let (4, 4, [5, 4, 2, 2], v, 20) be an instance of the (SCPK). The following inequality is part of the convex hull obtained with PORTA Christof and Löbel (2009): (i1) $x_{11} + x_{12} + x_{21} + x_{24} + x_{32} + x_{33} + x_{42} + x_{44} \le 3$

We show that inequality (i1) does not correspond to any of the inequalities introduced in Section 2.3 for the (PK). Inequality (i1) is not a minimal cover inequality. The set of variables associated with (i1) is $\mathcal{X} = \{x_{11}, x_{12}, x_{21}, x_{24}, x_{32}x_{34}, x_{42}, x_{44}\}$. Clearly, this set of variables is not a minimal cover, as both $x_{21}$ and $x_{24}$ are in this set, but $x_{22}$ and $x_{23}$ are not despite chain precedence constraints $x_{22} \le x_{21}$, $x_{23} \le x_{22}$ and $x_{24} \le x_{23}$. Inequality (i1) is not a MIC inequality. Indeed $\mathcal{X}$ is not a MIC, as its subsets are MIC. For example, $U_1 = \{x_{11}, x_{21}, x_{32}\}$ is subset of $\mathcal{X}$, and is a MIC. Inequality (i1) cannot be obtained with the lifting procedure of Park and Park (1997). In this lifting procedure the MIC inequality is lifted with variables having two successors in the MIC. However, by definition of a MIC, there cannot be two items in a MIC if there is a precedence constraint between them. In the case of the (SCPK), it means a MIC can only have 1 item per group. As precedence constraints are only between items in a same group, there cannot be an item with two successors in the MIC. Hence this lifting does not apply, and cannot yield (i1). Inequality (i1) cannot be obtained with the sequential lifting procedure of van de Leensel et al. (1999). Any minimal cover $U \subseteq \mathcal{X}$ has cardinality 3, meaning $|U| - 1 \le 2$. Indeed, the induced cover with minimum weight of cardinality 4 is $U_2 = \{x_{11}, x_{21}, x_{32}, x_{42}\}$, but is not minimal as $U_1 \subset U_2$ is also an induced cover. As coefficients $\alpha_{ij}$ are zero from Property 2, the right hand-side of a MIC inequality cannot change with this lifting. Hence, inequality (i1) cannot be obtained with this sequential lifting procedure.

One can define pattern *P* = {{1, 2}, {1, 4}, {2, 3}, {2, 4}}, as represented on Figure 3. This pattern is of rank 3. With *X(P)* = {x₁₁, x₁₂, x₂₁, x₂₄, x₃₂, x₃₃, x₄₂, x₄₄}, one can obtain inequality (i1). Such a result is due to pattern inequalities being a very large family of inequalities. □

As for any set of variables there is a pattern, and vice-versa, these pattern inequalities cover all the binary inequalities of the (SCPK).
# 4 Facial study of pattern inequalities

In this section, we define the conditions for a pattern to lead to tight pattern inequalities.

**Definition 11 (Facet-defining-pattern).** A pattern $\mathcal{P}$ is facet-defining if for every $\mathcal{X} \in \Omega(\mathcal{P})$, $(\mathrm{pi}(\mathcal{X}))$ is facet-defining.

Note that $\mathcal{P}$ is facet-defining if and only if inequality $(\mathrm{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})$. To simplify notations, inequality $(\mathrm{pi}(\mathcal{X}(\mathcal{P})))$ is denoted by $(\mathrm{pi}(\mathcal{P}))$.

## 4.1 Necessary facet defining conditions

In this section we define three necessary conditions for a pattern to be facet-defining. The first one is for a pattern to have at least one item in each if its sets.

**Property 7 (Condition (i): no empty group).** Let $\mathcal{P}$ be a pattern. If $\mathcal{P}$ is facet-defining-pattern, then it verifies condition (i): $|S_i(\mathcal{P})| \ge 1$, $\forall S_i(\mathcal{P}) \in \mathcal{P}$.

*Proof.* Let $\mathcal{P}$ be facet-defining of rank $k$. Clearly, if $|\mathcal{X}(\mathcal{P})| = k$, then the pattern inequality is dominated by the sum of the bound $x_{ij} \le 1$ for all $x_{ij} \in \mathcal{X}$. Hence, in the following, we suppose $\mathrm{card}(\mathcal{P}) = |\mathcal{X}(\mathcal{P})| > k$.

Suppose $S_i(\mathcal{P})$ does not verify (i) for a given $i$, i.e., $S_i(\mathcal{P}) = \emptyset$. Let $\mathcal{X}' = \mathcal{X}(\mathcal{P}) \cup \{x_{iJ}\}$. Because $x_{iJ}$ is the only variable of $\mathcal{X}'$ for group $i$, $s_{iJ}(\mathcal{X}') \ge s_{i'j'}(\mathcal{X}')$ for any $x_{i'j'} \in \mathcal{X}'$. Then, the following inequality is valid:

$$ \sum_{x_{i'j'} \in \mathcal{X}(\mathcal{P})} x_{i'j'} + x_{iJ} \le k. $$

Indeed, when $x_{iJ} = 0$, this inequality is valid by the rank of $\mathcal{P}$. When $x_{iJ} = 1$, there cannot be $k$ variables of $\mathcal{X}(\mathcal{P})$ to 1 simultaneously. Otherwise as $s_{iJ}(\mathcal{X}') \ge s_{i'j'}(\mathcal{X}')$ for any $x_{i'j'} \in \mathcal{X}'$, one could set $x_{iJ}$ to 0, and any other variable of $\mathcal{X}'$ to 1. This might reduce the total weight. In the case it does, this would lead to another solution. Such a solution would have $k + 1$ variables of $\mathcal{X}(\mathcal{P})$ to 1, which contradicts the rank of $\mathcal{P}$. Therefore this inequality is valid. This inequality dominates $(\mathrm{pi}(\mathcal{P}))$. Indeed, one could sum it with $-x_{iJ} \le 0$ to obtain $(\mathrm{pi}(\mathcal{P}))$. Thus a pattern $\mathcal{P}$ is facet-defining only if $\mathcal{P}$ verifies condition (i). $\square$

The following condition is that there exists a feasible solution with $(\mathrm{pi}(\mathcal{P}))$ to equality, and $x_{iJ} = 1$ for any group $i$.

**Property 8 (Condition (ii): selection of item J).** Let $\mathcal{P}$ be a pattern of rank $k$. If $\mathcal{P}$ is facet-defining, then $\mathcal{P}$ verifies condition (ii) :

For each group index $i \le I$, there is $\mathcal{Y} \subseteq \mathcal{V}$ a $k$-intersection of $\mathcal{X}(\mathcal{P})$ with $x_{iJ} \in \mathcal{Y}$.

*Proof.* Let $\mathcal{P}$ be a pattern of rank $k$. Suppose there is an $i \le I$ such that (ii) is not verified for $i$. This means that there is no feasible solution with $k$ variables of $\mathcal{X}(\mathcal{P})$ to 1, with $x_{iJ} = 1$. Therefore, the following inequality is valid: $\sum_{x_{i'j'} \in \mathcal{X}(\mathcal{P})} x_{i'j'} + x_{iJ} \le k$. Indeed, when $x_{iJ} = 0$, the inequality is valid by the rank of $\mathcal{P}$. When $x_{iJ} = 1$, the inequality is valid as there cannot be more than $k - 1$ variables of $\mathcal{X}(\mathcal{P})$ to 1, which sums to a total of at most $k$. This inequality dominates the inequality $(\mathrm{pi}(\mathcal{P}))$. Indeed, one could sum it with $-x_{iJ} \le 0$ to obtain $(\mathrm{pi}(\mathcal{P}))$. Thus, a pattern $\mathcal{P}$ is facet-defining only if $\mathcal{P}$ verifies condition (ii). $\square$

The following condition is quite similar to condition (ii), but for any variable $x_{ij-1}$ with $x_{ij} \in \mathcal{X}(\mathcal{P})$, instead of any variable $x_{iJ}$.

**Property 9 (Condition (iii): independence of an item from its predecessor).** Let $\mathcal{P}$ be a pattern of rank $k$. If $\mathcal{P}$ is facet-defining, then $\mathcal{P}$ verifies condition (iii) : For each variable $x_{ij} \in \mathcal{X}(\mathcal{P})$, there is $\mathcal{Y} \subseteq \mathcal{V}$ a $k$-intersection of $\mathcal{X}(\mathcal{P})$ with $x_{ij-1} \in \mathcal{Y}$ and $x_{ij'} \notin \mathcal{Y}$ for every $j' \ge j$.
Proof. Let $\mathcal{P}$ be a pattern of rank $k$. Suppose for some $(i, j)$, $x_{ij} \in \mathcal{X}(\mathcal{P})$ does not verify condition (iii). This means that there is no feasible solutions with a total of $k$ variables of $\mathcal{X}(\mathcal{P})$ to 1, with $x_{ij-1} = 1$ and $x_{ij} = 0$. Therefore, the following inequality is valid: $\sum_{x_{i'j'} \in \mathcal{X}(\mathcal{P})} x_{i'j'} + x_{ij-1} - x_{ij} \le k$. Indeed, when $x_{ij} = x_{ij-1} = 1$ or $x_{ij} = x_{ij-1} = 0$, this inequality is valid by the rank of $\mathcal{P}$. When $x_{ij-1} = 1$ and $x_{ij} = 0$, the inequality is valid as there cannot be more than $k-1$ variables of $\mathcal{X}(\mathcal{P})$ to 1, which sums to at most $k$. This inequality dominates inequality $(\pi(\mathcal{P}))$. Indeed, one could sum it with $-x_{ij-1} + x_{ij} \le 0$ (equivalent to $x_{ij} \le x_{ij-1}$) to obtain $(\pi(\mathcal{P}))$. Thus a pattern $\mathcal{P}$ is facet-defining only if $\mathcal{P}$ verifies condition (iii). $\square$

For a given pattern $\mathcal{P}$, conditions (i) can clearly be verified in linear time. Also, conditions (ii) and (iii) can be verified in polynomial time, by solving the shortest path algorithm described in Bendotti et al. (2025) at most once for each variable.

We define flexible patterns, namely the patterns satisfying all of three conditions.

**Definition 12 (Flexible pattern).** A pattern $\mathcal{P}$ is a flexible pattern if it verifies conditions (i), (ii) and (iii).

The patterns are said to be flexible, as any variable of $\mathcal{X}(\mathcal{P})$ can be set to 1 when $(\pi(\mathcal{P}))$ is to equality. Hence there is no restriction on which variable can be set to 1 when $(\pi(\mathcal{P}))$ is to equality. Clearly, flexible pattern inequalities dominate binary UMIC inequalities. Indeed, pattern inequalities dominate UMIC inequalities as proven in **Property 6**, and all binary facet-defining inequalities must verify (i), (ii) and (iii). Consequently, all binary facet-defining inequalities are flexible pattern inequalities. The following example illustrates conditions (i), (ii) and (iii) on inequality (i1) from **Example 4**.

**Example 5 (Conditions (i), (ii) and (iii)).** Let (4, 4, [5, 4, 2, 2], v, 20) be an instance of the (SCPK). The following inequality is part of the convex hull description obtained with PORTA Christof and Löbel (2009):

$$x_{11} + x_{12} + x_{21} + x_{24} + x_{32} + x_{34} + x_{42} + x_{44} \le 3 \quad (i1)$$

We show that inequality (i1) is a flexible pattern inequality. Let $\mathcal{P} = \{\{1, 2\}, \{1, 4\}, \{2, 3\}, \{2, 4\}\}$ and $\mathcal{X}(\mathcal{P}) = \{x_{11}, x_{12}, x_{21}, x_{24}, x_{32}, x_{34}, x_{42}, x_{44}\}$. Clearly, $\mathcal{X}(\mathcal{P})$ verifies condition (i). We now verify if condition (ii) holds. For $i = 1$ (resp. $i = 2$, $i = 3$, $i = 4$), variable set $\{x_{11}, x_{12}, x_{14}, x_{21}\}$ (resp. $\{x_{11}, x_{21}, x_{24}\}$, $\{x_{11}, x_{32}, x_{34}\}$, $\{x_{11}, x_{42}, x_{44}\}$) is a 3-intersection of $\mathcal{X}(\mathcal{P})$. Hence, condition (ii) holds. We now verify if condition (iii) holds. For $x_{11}$, variable set $\{x_{21}, x_{32}, x_{42}\}$ is a 3-intersection of $\mathcal{X}(\mathcal{P})$. For $x_{12}$, variable set $\{x_{11}, x_{21}, x_{24}\}$ is a 3-intersection of $\mathcal{X}(\mathcal{P})$. For $x_{21}$, variable set $\{x_{11}, x_{32}, x_{34}\}$ is a 3-intersection of $\mathcal{X}(\mathcal{P})$. For $x_{24}$, variable set $\{x_{11}, x_{12}, x_{21}, x_{23}\}$ is a 3-intersection of $\mathcal{X}(\mathcal{P})$. For $x_{32}$, variable set $\{x_{11}, x_{12}, x_{21}, x_{31}\}$ is a 3-intersection of $\mathcal{X}(\mathcal{P})$. For $x_{34}$, variable set $\{x_{11}, x_{12}, x_{32}, x_{33}\}$ is a 3-intersection of $\mathcal{X}(\mathcal{P})$. For $x_{42}$ (resp. $x_{44}$) one can reuse the 3-intersection for $x_{32}$ (resp. $x_{34}$) by inverting groups 3 and 4. Hence condition (iii) holds. Consequently, inequality (i1) is a pattern inequality associated with a flexible pattern.

The conditions on a flexible pattern $\mathcal{P}$ are not sufficient for $\mathcal{P}$ to be facet-defining. However, a minimum dimension can be guaranteed for the faces defined by flexible pattern inequalities.

## 4.2 Lower bound on the dimension of the faces defined by flexible pattern inequalities

In this section, we consider a flexible pattern $\mathcal{P}$. The idea of the following property is that for any $x_{ij} < J$ (resp. $x_{iJ}$) there is a valid solution with $x_{ij} = 1$, $x_{ij+1} = 0$ (resp. $x_{iJ} = 1$) and $(\pi(\mathcal{P}))$ to equality. In a sense it is a generalization of condition (ii) defined only for variables $x_{iJ}$, and condition (iii) defined only for variables $x_{ij}$ such that $x_{ij+1} \in \mathcal{X}(\mathcal{P})$.

**Property 10 (Generalization of (ii) and (iii) for any item of the (SCPK)).** Let $\mathcal{P}$ be a flexible pattern. For any item $(i, j)$, there is $\mathcal{Y} \subseteq \mathcal{V}$ a $k$-intersection of $\mathcal{X}(\mathcal{P})$ with $x_{ij} \in \mathcal{Y}$ and $x_{ij'} \notin \mathcal{Y}$ for every $j' > j$.
The complete proof is in Appendix **6.8**, it merely extends the proofs for conditions (ii) and (iii). Conditions (i), (ii) and (iii) are necessary for a pattern $\mathcal{P}$ to be facet-defining. Moreover, the following theorem provides a lower bound on the number of linearly independent points verifying inequalities $(\mathrm{pi}(\mathcal{P}))$ to equality when these three conditions are verified.

**Theorem 7** ($n - \mathrm{card}(\mathcal{P})$ linearly independent points). Let $\mathcal{P}$ be a flexible pattern. Let $n$ be the number of variables of the (SCPK). There are at least $n - \mathrm{card}(\mathcal{P})$ linearly independent points that verify inequality $(\mathrm{pi}(\mathcal{P}))$ to equality.

*Proof.* Let $\mathcal{P}$ be a pattern of rank $k$. **Property 10** stipulates that if $\mathcal{P}$ is a flexible pattern, then for any item $(i, j)$ there is a $k$-intersection $\mathcal{Y}_{ij} \subseteq \mathcal{V}$ of $\mathcal{X}(\mathcal{P})$; $x_{ij} \in \mathcal{Y}_{ij}$; $x_{ij'} \notin \mathcal{Y}_{ij}$ for each $j' > j$ and $X_{\mathcal{Y}_{ij}}$ is feasible. Consider $X_{\mathcal{Y}_{ij}}$ for each variable $x_{ij} \notin \mathcal{X}(\mathcal{P})$. Because $\mathrm{card}(\mathcal{P}) = |\mathcal{X}(\mathcal{P})|$, there are $n - \mathrm{card}(\mathcal{P})$ solutions. We can prove that $X_{\mathcal{Y}_{ij}}$ is the only solution with $x_{ij} = 1$ and $x_{ij+1} = 0$. Let $x_{ij} \notin \mathcal{X}(\mathcal{P})$ and $x_{i'j'} \notin \mathcal{X}(\mathcal{P})$ be two distinct variables. We assumed without loss of generality in **Property 10** that $\mathcal{Y}_{i'j'} \setminus \{x_{i'j'}\} \subseteq \mathcal{X}(\mathcal{P})$. As $x_{ij} \notin \mathcal{X}(\mathcal{P})$, there would be a contradiction if $X_{\mathcal{Y}_{i'j'}}$ had $x_{ij} = 1$ and $x_{ij+1} = 0$.

Solutions $X_{\mathcal{Y}_{ij}}$ for variables $x_{ij} \notin \mathcal{X}(\mathcal{P})$ are linearly independent, and proven to be valid in **Property 10**. As $\mathcal{Y}_{ij}$ is a $k$-intersection of $\mathcal{X}(\mathcal{P})$, all these solutions also verify $(\mathrm{pi}(\mathcal{P}))$ to equality. Hence, for a flexible pattern $\mathcal{P}$, there are $n - \mathrm{card}(\mathcal{P})$ linearly independent points verifying $(\mathrm{pi}(\mathcal{P}))$ to equality with $\mathcal{X}(\mathcal{P}) \in \mathcal{P}$. $\square$

**Theorem 7** provides a lower bound on the dimensions of the faces defined by flexible pattern inequalities. Recall that for a pattern to be flexible it solely requires to verify conditions (i), (ii) and (iii). It is shown in Bendotti et al. (2025) that verifying if these three conditions hold can be done in polynomial time. **Theorem 7** is used in the experimental results in Bendotti et al. (2025) to ensure only flexible pattern inequalities are separated.

The following section provides properties complementary to **Theorem 7**.

## 4.3 Properties of the lower sub-patterns

In this section, we first introduce new families of patterns, namely sub-patterns and lower sub-patterns for a given flexible pattern $\mathcal{P}$. We then derive multiple properties for the lower sub-patterns, which are used in **Section 4.4**, to prove that necessary facet-defining conditions (i), (ii) and (iii) are also sufficient for a quite large family of flexible patterns.

**Definition 13** (Sub-pattern). A pattern $\mathcal{P}'$ is sub-pattern of pattern $\mathcal{P}$ if there is a permutation $\pi$ such that $S_{\pi(i)}(\mathcal{P}') \subseteq S_i(\mathcal{P})$ for all $i \le I$.

If $\mathcal{P}$ is sub-pattern of $\mathcal{P}'$, then $\mathcal{P}'$ is super-pattern of $\mathcal{P}$. For the remainder of the paper, we consider without loss of generality that the required permutation $\pi$ is the identity permutation $\pi_{id}$.

We present a new set of sub-patterns for $\mathcal{P}$. In the following, properties are presented to show that these new patterns have large sub-patterns in common, thus inducing similarities. These similarities will be convenient to provide linearly independent points in the polytope $P_{(SCPK)}$.

**Definition 14** (Lower sub-patterns $Q_i$). Let $\mathcal{P}$ be a pattern of rank $k$. For a given $i \le I$, a lower sub-pattern $Q_i$ of $\mathcal{P}$ is a sub-pattern of $\mathcal{P}$ such that $S_i(Q_i) = S_i(\mathcal{P})$, $\mathrm{card}(Q_i) = k$, minimizing the sum of the set weights $s(\mathcal{X}(Q_i))$.

**Example 6** (Lower sub-patterns). Let $(4, 3, [3,4,2], v, 9)$ be an instance of the (SCPK). Let $\mathcal{P} = \{\{1,3\}, \{2\}, \{2\}, \{2\}\}$ be a pattern of rank 2. Lower sub-pattern $Q_1$ is $\{\{1,3\}, \emptyset, \emptyset, \emptyset\}$, as $S_1(\mathcal{P}) = 2 = \mathrm{rank}(\mathcal{P})$. As $w_1 < w_1 + w_2$, lower sub-pattern $Q_2$ is $\{\{1\}, \{2\}, \emptyset, \emptyset\}$, and cannot be $\{\emptyset, \{2\}, \{2\}, \emptyset\}$ by definition. Similarly, lower sub-pattern $Q_3$ (resp. $Q_4$) is $\{\{1\}, \emptyset, \{2\}, \emptyset\}$ (resp. $\{\{1\}, \emptyset, \emptyset, \{2\}\}$). $\square$

Let $\mathcal{P}$ be a pattern. For a given $i$, let $Q_i$ be a lower sub-pattern of $\mathcal{P}$. By construction, if $x_{ij} \in \mathcal{X}(Q_i)$, then for each variable $x_{ij'} \in \mathcal{X}(\mathcal{P})$ with $j' \le j$, $x_{ij'} \in \mathcal{X}(Q_i)$, hence justifying the name lower sub-patterns. Also note that lower sub-patterns $Q_i$ can be obtained via a shortest path algorithm similar to the ones proposed in Bendotti et al. (2025).
The idea now is to define minimum size of the sets of all lower sub-patterns. This is used in **Section 4.4** to prove that they have a common sub-pattern of cardinality $k-1$. This in turn is convenient to provide affinely independent points. For the remainder of the section, we consider a flexible pattern $\mathcal{P}$.

**Lemma 1.** Let $\mathcal{P}$ be a flexible pattern of rank $k$. Let $i \in \{1, ..., I\}$ and $Q_i$ a lower sub-pattern of $\mathcal{P}$. Variable set $\mathcal{X}(Q_i) \cup \{x_{iJ}\}$ is a $k$-intersection of $\mathcal{X}(\mathcal{P})$.

*Proof.* As $\mathcal{P}$ verifies condition (ii), there is a variable set that is a $k$-intersection of $\mathcal{X}(\mathcal{P})$ containing $x_{iJ}$. By definition $Q_i$ minimizes the sum of its set weights and all variables of group $i$ in $\mathcal{X}(\mathcal{P})$ are in $\mathcal{X}(Q_i) \cup \{x_{iJ}\}$. Hence, if condition (ii) for variable $x_{iJ}$ cannot be verified with $\mathcal{X}(Q_i) \cup \{x_{iJ}\}$, there is a contradiction as $Q_i$ cannot be minimizing the sum of its set weights. $\square$

**Remark 1.** As $\mathcal{X}(Q_i) \cup \{x_{iJ}\}$ is a $k$-intersection of $\mathcal{X}(\mathcal{P})$, then $\mathcal{X}(Q_i)$ is also a $k$-intersection of $\mathcal{X}(\mathcal{P})$. Indeed, if $x_{iJ} \in \mathcal{X}(\mathcal{P})$ then $x_{iJ} \in \mathcal{X}(Q_i)$ by definition of $Q_i$.

In the remainder of the paper, we consider for the sake of simplicity and without loss of generality that the sets of $\mathcal{P}$ are ordered such that $|S_i(\mathcal{P})| \le |S_{i+1}(\mathcal{P})|$. Therefore, $S_1(\mathcal{P})$ is a smallest set of $\mathcal{P}$, and $Q_1$ is the lower sub-pattern of $\mathcal{P}$ associated with $S_1(\mathcal{P})$. We define $U = |S_I(\mathcal{P})|$ and $V = |S_1(\mathcal{P})|$. Also, we denote by $S_i(\mathcal{P})(u)$ the $u^{th}$ lowest item index of $S_i(\mathcal{P})$ and $S_i(\mathcal{P})([u])$ the $u^{th}$ highest item index of $S_i(\mathcal{P})$.

**Example 7 (Notations for $S_i(\mathcal{P})$).** Let $\mathcal{P} = \{S_1(\mathcal{P}) = \{4\}, S_2(\mathcal{P}) = \{2, 5\}, S_3(\mathcal{P}) = \{1, 2\}, S_4(\mathcal{P}) = \{1, 3, 4\}\}$ be a pattern. In this case, $U = 3$ and $V = 1$. Also, $S_4(\mathcal{P})(1) = 1$, $S_4(\mathcal{P})(2) = 3$, $S_4(\mathcal{P})(3) = 4$, $S_4(\mathcal{P})([1]) = 4$, $S_4(\mathcal{P})([2]) = 3$ and $S_4(\mathcal{P})([3]) = 1$.

Recall that the aim is to provide a lower bound on the size of each set of the lower sub-patterns. We first start by providing a lower bound on the size of each set of sub-pattern $Q_1$ of $\mathcal{P}$.

**Property 11 (Minimum size on the sets of $Q_1$).** Lower sub-pattern $Q_1$ of $\mathcal{P}$ is such that for every $i \le I$, $S_i(Q_1)$ contains the $|S_i(\mathcal{P})| - V$ smallest indices of $S_i(\mathcal{P})$.

*Proof.* Let $\mathcal{P}$ be a flexible pattern. Suppose that there is $i \le I$ such that $S_i(Q_1)$ does not contain the $|S_i(\mathcal{P})| - V$ smallest indices of $S_i(\mathcal{P})$. By definition of $Q_1$, $S_1(Q_1) = S_1(\mathcal{P})$, meaning the property is trivially verified for $i = 1$. In the following we consider $i > 1$. Let $\mathcal{Y}$ be set $\mathcal{X}(Q_1)$ to which we add $x_{1J}$ if $x_{1J} \notin \mathcal{X}(\mathcal{P})$. The solution $X_{\mathcal{Y}}$ is feasible as proven in **Lemma 1**. Let $\mathcal{Y}'$ be the variables set $\mathcal{Y}$ from which we remove all variables of group 1, and to which we add all variables of group $i$ in $\mathcal{X}(\mathcal{P}) \setminus \mathcal{Y}$. Because of the symmetric weights, selecting every item $(1, j)$, $j \le J$ is at least as heavy as selecting items $(i, j)$, $j \le \max(S_i(\mathcal{P}))$. Consequently: $\sum_{x_{i'j'} \in \mathcal{Y}'} s_{i'j'}(\mathcal{Y}') \le \sum_{x_{i'j'} \in \mathcal{Y}} s_{i'j'}(\mathcal{Y})$. As solution $X_{\mathcal{Y}}$ is valid, solution $X_{\mathcal{Y}'}$ must also be valid. By construction, there are $V$ variables of group 1 in $\mathcal{Y} \setminus \mathcal{Y}'$. Also, as $|S_i(Q_1)| < |S_i(\mathcal{P})| - V$ by hypothesis, there are at least $V+1$ variables of group $i$ in $\mathcal{Y}' \setminus \mathcal{Y}$. Besides groups 1 and $i$, sets $\mathcal{Y}$ and $\mathcal{Y}'$ are identical, hence $|\mathcal{Y}'| > |\mathcal{Y}|$. As $\mathcal{Y}$ is a $k$-intersection of $\mathcal{X}(\mathcal{P})$, then $\mathcal{Y}'$ is at least a $k+1$-intersection of $\mathcal{X}(\mathcal{P})$, which contradicts the rank $k$ of $\mathcal{P}$. Thus, $Q_1$ must contain the $|S_i(\mathcal{P})| - V$ smallest indices of $S_i(\mathcal{P})$ for every $i \le I$. $\square$

**Remark 2.** For any $i \le I$ with $|S_i(\mathcal{P})| > V$, it is equivalent to say that $S_i(Q_1)$ contains the $|S_i(\mathcal{P})| - V$ smallest item indices of $S_i(\mathcal{P})$ and $S_i(\mathcal{P})([V+1] \in S_i(Q_1))$. In the following, the latter notation will be used (note that if $S_i(\mathcal{P})$ has exactly $V$ elements then $S_i(\mathcal{P})([V+1])$ does not exist).

The idea of the proof is illustrated by **Example 8** and **Figure 4**. In **Figure 4**, column $i$ starting from the left, and row $j$, starting from the bottom represent variable $x_{ij}$, in the same manner as in **Figure 1**. When cell $(i, j)$ is highlighted in (dark) gray, it means variable $x_{ij}$ is contained in the corresponding variable set.

**Example 8 (Proof of Property 11).** Let $(4, 5, w, v, C)$ be an instance of the (SCPK). Let $\mathcal{P} = \{S_1(\mathcal{P}) = \{3\}, S_2(\mathcal{P}) = \{2, 4\}, S_3(\mathcal{P}) = \{1, 2\}, S_4(\mathcal{P}) = \{1, 2, 3\}\}$ be a flexible pattern of rank 5. Let $Q_1 = \{S_1(Q_1) = \{3\}, S_2(Q_1) = \{2\}, S_3(Q_1) = \{1, 2\}, S_4(Q_1) = \{1\}\}$ be a lower sub-pattern of $\mathcal{P}$. In this case, $S_4(\mathcal{P})([V+1]) = 2 \notin S_4(Q_1)$, hence $Q_1$ does not verify **Property 11**. We show in the following
that it leads to a contradiction with the rank of $\mathcal{P}$. Here $\mathcal{X}(\mathcal{P}) = \{x_{13}, x_{22}, x_{24}, x_{31}, x_{32}, x_{41}, x_{42}, x_{43}\}$ and $\mathcal{X}(Q_1) = \{x_{13}, x_{22}, x_{31}, x_{32}, x_{41}\}$ as illustrated respectively in **Figure 4(a)** and **Figure 4(b)**. Let $\mathcal{Y}' = \mathcal{X}(Q_1) \cup \{x_{14}\}$ as illustrated in **Figure 4(c)**. From **Lemma 1** solution $X_{\mathcal{Y}'}$ is feasible. One can create a set $\mathcal{Y}'' = \mathcal{Y}' \setminus \{x_{13}, x_{14}\} \cup \{x_{42}, x_{43}\}$ as illustrated in **Figure 4(d)**. By removing $\{x_{13}, x_{14}\}$, there are no remaining variables in group 1, thus reducing the weight by $w_1 + w_2 + w_3 + w_4$. And as $x_{41} \in \mathcal{Y}'$, adding $\{x_{42}, x_{43}\}$ only increases the weight by $w_2 + w_3$. As the weights are non-negative, clearly $w_2 + w_3 \le w_1 + w_2 + w_3 + w_4$, hence $X_{\mathcal{Y}''}$ is feasible. However $\mathcal{Y}''$ is a $k+1$-intersection of $\mathcal{X}(\mathcal{P})$. Indeed, since $Q_1$ does not verify **Property 11**, only $V=1$ variable of $\mathcal{Y}' \setminus \mathcal{Y}''$ is in $\mathcal{X}(\mathcal{P})$, namely $x_{13}$ and $V+1=2$ variables of $\mathcal{Y}'' \setminus \mathcal{Y}'$ are in $\mathcal{X}(\mathcal{P})$, namely $x_{42}$ and $x_{43}$. As $X_{\mathcal{Y}''}$ is valid, there is a contradiction with the rank of $\mathcal{P}$.

<figure><img src="image_5.png" /><figcaption>Figure 4: Illustration of **Example 8**</figcaption></figure>

**Property 12** provides dependencies between the indices of $S_1(\mathcal{P})$ and any set $S_i(\mathcal{P})$, based on **Property 11**.

**Property 12** (Minimum indices for the smallest set). Let $\mathcal{P}$ be a flexible pattern and $i \in \{2, \dots, I\}$ be an index. For any $u \in \{1, \dots, V\}$, if $|S_i(\mathcal{P})| \ge u + V$ then $S_1(\mathcal{P})[u] \ge S_i(\mathcal{P})[u + V]$.

The proof is in **Appendix 6.9**. For now, we provided a lower bound on the size of the sets of $Q_1$ in **Property 11**. We also need similar bounds for the sets of any $Q_i$, $i \le I$, in order to characterize facet-defining patterns. This result is given in **Property 13**, based on **Property 12**. Note that, it is not a generalization of **Property 11**. Indeed, **Property 11** addresses only $Q_1$ and not any $Q_i$, but with a larger minimal bound than the one in **Property 13**.

**Property 13** (Minimum size of the sets of any $Q_i$). Let $\mathcal{P}$ be a flexible pattern. For every $i \le I$, the lower sub-pattern $Q_i$ of $\mathcal{P}$ is such that for a given $i' \le I$ if $|S_{i'}(\mathcal{P})| \ge 2V$ then $S_{i'}(\mathcal{P})[2V] \in S_{i'}(Q_i)$.

The proof is in **Appendix 6.10**. The previous conditions are valid for any pattern. However, in the special case where pattern $\mathcal{P}$ is with $|S_1(\mathcal{P})| = 1$, **Property 13** indicates that $S_{i'}(\mathcal{P})[2] \in S_{i'}(Q_i)$ for any $i' \le I$ and $i \le I$. Thus, the shape of all patterns $Q_i$ is very restricted, as each set $S_{i'}(Q_i)$ has at most one missing index set in comparison to $S_{i'}(\mathcal{P})$.

**Example 9 (Properties 11, 12, 13).** Let $\mathcal{P} = \{S_1(\mathcal{P}) = \{3\}, S_2(\mathcal{P}) = \{1, 3, 4\}, S_3(\mathcal{P}) = \{1, 2, 4\}, S_4(\mathcal{P}) = \{1, 2, 3, 4\}\}$ be a flexible pattern. Pattern $\mathcal{P}$ verifies **Property 12**, as $S_1(\mathcal{P})[1] = 3$ is greater or equal to $S_2(\mathcal{P})[2] = 3$, $S_3(\mathcal{P})[2] = 2$ and $S_4(\mathcal{P})[2] = 3$. Suppose $\text{rank}(\mathcal{P}) = 9$. Consider the lower sub-pattern $Q_1 = \{S_1(Q_1) = \{3\}, S_2(Q_1) = \{1, 3, 4\}, S_3(Q_1) = \{1, 2\}, S_4(Q_1) = \{1, 2, 3\}\}$. Pattern $Q_1$ verifies **Property 11**, as $V=1$ and there is at most $V=1$ missing index per set compared to $\mathcal{P}$. Consider the lower sub-pattern $Q_2 = \{S_1(Q_2) = \emptyset, S_2(Q_2) = \{1, 3, 4\}, S_3(Q_2) = \{1, 2, 3\}, S_4(Q_2) = \{1, 2, 3\}\}$. Pattern $Q_2$ verifies **Property 13**, as $V=1$ and there is at most $2V-1=1$ missing index per set compared to $\mathcal{P}$. $\square$

This restricted shape on the lower sub-pattern is used in the following section to prove necessary and sufficient conditions for all patterns containing a set of cardinality 1.

## 4.4 Necessary and sufficient facet-defining conditions for patterns with a cardinality 1 set

In this section, we focus on patterns with at least one set of cardinality 1, hence we consider throughout this section a flexible pattern $\mathcal{P}$ of rank $k$ and with $V=1$. It is proven with **Property 13** that for
such a pattern $\mathcal{P}$, its lower sub-patterns $Q_i$ have a restricted shape. Using this result, we will show that the lower sub-patterns share many elements in common. As mentioned in **Lemma 4**, for a given $i$, multiple lower sub-patterns $Q_i$ with the exact same set of weights can exist. From now on we only consider for each $i \le I$ the unique $Q_i$ verifying the following tie-break rule.

**Definition 15** (Tie-break rule). Consider a lower sub-pattern $Q_i$ of $\mathcal{P}$. For any two indices $i' < i'' \le I$ different than $i$, if

$$ \sum_{j=S_{i'}(\mathcal{P})[2]+1}^{S_{i'}(\mathcal{P})[1]} w_j = \sum_{j=S_{i''}(\mathcal{P})[2]+1}^{S_{i''}(\mathcal{P})[1]} w_j; $$

then $S_{i''}(\mathcal{P})[1] \in S_{i''}(Q_i)$ only if $S_{i'}(\mathcal{P})[1] \in S_{i'}(Q_i)$.

From **Property 13**, at most one index is missing in a set of $Q_i$ compared to $\mathcal{P}$. Hence, with such a rule there can only be one $Q_i$ for a given $i$.

**Example 10** (Tie-break rule). Let $(4, 4, [2, 1, 1, 1], v, C)$ be an instance of the (SCPK). Let $\mathcal{P} = \{S_1(\mathcal{P}) = \{3\}, S_2(\mathcal{P}) = \{1, 3\}, S_3(\mathcal{P}) = \{2, 4\}, S_4(\mathcal{P}) = \{2, 4\}\}$ be a flexible pattern of rank 5. In this case, $w_2 + w_3 = w_3 + w_4 = 2$, meaning that there are 3 possible lower sub-pattern $Q_1$ with the exact same weight: $\{\{3\}, \{1, 3\}, \{2\}, \{2\}\}; \{\{3\}, \{1\}, \{2, 4\}, \{2\}\}; \{\{3\}, \{1\}, \{2\}, \{2, 4\}\}$. The rule stipulates that $4 \in S_4(Q_1)$ only if $4 \in S_3(Q_1)$ and $3 \in S_2(Q_1)$. Also, the rule stipulates that $4 \in S_3(Q_1)$ only if $3 \in S_2(Q_1)$. Only the first option for $Q_1$ verifies the rule, and consequently is the only one considered. $\square$

To prove that the lower sub-patterns $Q_i$ share many elements, we provide a pattern $C$, sub-pattern to all $Q_i$. We then prove that $C$ is of cardinality $k-1$.

**Definition 16** (Common sub-pattern $C$ of all $Q_i$). For any $i \le I$, let $Q_i$ be the unique lower sub-pattern for $\mathcal{P}$ and index $i$ considering the tie-break rule. The pattern $C$ is the largest cardinality pattern such that $C$ is sub-pattern to all $Q_i$ with $i \le I$.

**Property 14** (Cardinality of $C$). Let $Q_i$ be the unique lower sub-pattern of $\mathcal{P}$ considering the tie-breaking rule, for all $i \le I$. The cardinality of $C$ is $\text{card}(C) = k-1$.

An example illustrating **Property 14** is provided in **Example 11**.

*Proof.* As $\mathcal{P}$ is a flexible pattern, **Property 13** holds, hence for any $i$ and $i'$ in $\{1, \dots, I\}$ such that $|S_{i'}(\mathcal{P})| \ge 2$, $S_{i'}(\mathcal{P})[2] \in S_{i'}(Q_i)$. In other words, there is at most one element of $S_{i'}(\mathcal{P})$ not in $S_{i'}(Q_i)$. Let $k'$ be an integer equal to $k - (\text{card}(\mathcal{P}) - I)$. Let $\mathcal{L}$ be the set of the $k'$ indices $i'$ such that $S_{i'}(Q_i) = S_{i'}(\mathcal{P})$. By definition of $Q_i$, $i \in \mathcal{L}$. Because $S_{i'}(\mathcal{P})[2] \in S_{i'}(Q_i)$ for any $i' \in \{1, \dots, I\}$, the $k' - 1$ sets $i' \neq i$ such that $S_{i'}(Q_i) = S_{i'}(\mathcal{P})$ are the ones minimizing $\sum_{j=S_{i'}(\mathcal{P})[2]+1}^{S_{i'}(\mathcal{P})[1]} w_j$. Consequently, $\mathcal{L}$ contains the $k' - 1$ indices minimizing this sum. Indeed, either $i$ is in these $k' - 1$ indices, hence $\mathcal{L}$ contains the $k'$ indices minimizing this sum, or $i$ is not in these $k' - 1$ indices, but by construction $\mathcal{L}$ contains these $k' - 1$ indices. As such, all patterns $Q_i$ are all super-patterns of common pattern $C$, with $\text{card}(C) = (\text{card}(\mathcal{P}) - I) + k' - 1 = k - 1$. $\square$

**Example 11** (Property 14). Let $(3, 4, [2, 1, 3, 2], v, C)$ be an instance of the (SCPK). Let $\mathcal{P} = \{S_1(\mathcal{P}) = \{3\}, S_2(\mathcal{P}) = \{1, 2\}, S_3(\mathcal{P}) = \{1, 3\}, S_4(\mathcal{P}) = \{1, 3, 4\}\}$ be a flexible pattern of rank 6. First we identify the lower sub-pattern $Q_1$. By definition, $S_1(Q_1) = S_1(\mathcal{P}) = \{3\}$. From **Property 13**, as $V = 1$, for any $i \le 4$, $S_i(\mathcal{P})[2] \in S_i(Q_1)$. In this case, $1 \in S_2(Q_1)$, $1 \in S_3(Q_1)$ and $1, 3 \in S_4(Q_1)$. By definition, $\text{card}(Q_1) = 6$, but only five elements have been identified yet. As $w_2 = 1 < w_4 = 2 < w_2 + w_3 = 4$ and $Q_1$ minimize the sum of the set weights of $\mathcal{X}(Q_1)$, then clearly $2 \in S_2(Q_1)$. In this case: $Q_1 = \{S_1(Q_1) = \{3\}, S_2(Q_1) = \{1, 2\}, S_3(Q_1) = \{1\}, S_4(Q_1) = \{1, 3\}\}$. With a similar process, we also deduce:

$$ \begin{aligned} Q_2 &= \{S_1(Q_2) = \emptyset, S_2(Q_2) = \{1, 2\}, S_3(Q_2) = \{1\}, S_4(Q_2) = \{1, 3, 4\}\} \\ Q_3 &= \{S_1(Q_3) = \emptyset, S_2(Q_3) = \{1, 2\}, S_3(Q_3) = \{1, 3\}, S_4(Q_3) = \{1, 3\}\} \\ Q_4 &= \{S_1(Q_4) = \emptyset, S_2(Q_4) = \{1, 2\}, S_3(Q_4) = \{1\}, S_4(Q_4) = \{1, 3, 4\}\} \end{aligned} $$
There is $\mathcal{C} = \{\{S_1(\mathcal{C}) = \emptyset, S_2(\mathcal{C}) = \{1,2\}, S_3(\mathcal{C}) = \{1\}, S_4(\mathcal{C}) = \{1,3\}\}$ of cardinality 5 that is sub-pattern to all the aforementioned lower sub-patterns $Q_i$. Note that only $S_2(\mathcal{C}) = S_2(\mathcal{P})$, which is because $s_{22}(\mathcal{X}(\mathcal{P})) < s_{44}(\mathcal{X}(\mathcal{P})) < s_{33}(\mathcal{X}(\mathcal{P})) < s_{13}(\mathcal{X}(\mathcal{P}))$ and by definition the lower sub-patterns $Q_i$ minimize the set weights of $\mathcal{X}(Q_i)$. $\square$

For the following results, we need to generalize the definition of lower sub-pattern.

**Definition 17** (Generalized lower sub-patterns $Q_i(u)$). For a given $i \le I$ and $u \in \{0, \dots, |S_i(\mathcal{P})|\}$, the generalized lower sub-pattern $Q_i(u)$ of $\mathcal{P}$ is such that $\mathrm{card}(Q_i(u)) = k$ and $S_i(Q_i(u))$ contains exactly the $u$ smallest indices of $S_i(\mathcal{P})$, minimizing the sum of set weights $s(\mathcal{X}(Q_i(u)))$.

As for lower sub-patterns $Q_i$, we can also find similarities between lower sub-patterns $Q_i(u)$.

**Property 15** (Common elements between $\mathcal{C}$ and $Q_i(u)$). For each $i \le I$ and $u \in \{0, \dots, |S_i(\mathcal{P})| - 1\}$, lower sub-pattern $Q_i(u)$ of $\mathcal{P}$ is such that for any $i' \neq i$, $S_{i'}(\mathcal{C}) \subseteq S_i(Q_i(u))$.

The proof is provided in **Appendix 6.11**. With all lower sub-patterns $Q_i(u)$ defined, the following theorem shows that a flexible pattern with a set of cardinality 1 is facet-defining.

**Theorem 8.** Let $\mathcal{P}$ be a pattern with $V = 1$. $\mathcal{P}$ is facet-defining if and only if $\mathcal{P}$ is a flexible pattern.

The proof is provided in **Appendix 6.12**. Recall that for a pattern to be flexible it solely requires to verify conditions (i), (ii) and (iii). Hence, a pattern with a set of cardinality 1 is facet-defining if conditions (i), (ii) and (iii) hold. It is shown in Bendotti et al. (2025) that verifying if these three conditions hold for a given pattern can be done in polynomial time. As for **Theorem 7**, the result of **Theorem 8** is used for the experimental results in Bendotti et al. (2025), to generate only strong valid inequalities within a symmetry-aware Branch-and-Cut framework.

# 5 Conclusion

In this paper, we conducted a polyhedral study of the Symmetric-weight Chain Precedence Knapsack Problem (SCPK), a knapsack variant in which symmetric item weights and identical precedence chains induce a rich group of polyhedral symmetries. Rather than viewing these symmetries as a source of redundancy to be eliminated, we showed that they can be exploited as a constructive principle for deriving strong valid inequalities. We introduced the notion of *patterns*, symmetry-invariant objects used to represent equivalence classes of valid inequalities. Pattern inequalities provide a unified framework that generalizes classical cover-type inequalities to the symmetric setting of the (SCPK). We proved that all facet-defining inequalities of the SCPK with binary coefficients can be characterized through pattern inequalities, and we derived necessary and, in a special case, sufficient conditions for facet-defining patterns.

Several directions for future research naturally arise from this work. A direct extension is to study valid inequalities with integer coefficients for the (SCPK) and their symmetries, as they are part of its convex hull. Moreover, the proposed pattern inequalities can be extended to other problems, such as the Hydro Unit Commitment problem whose core combinatorial structure corresponds to several nested (SCPK). From a modeling standpoint, it would also be of interest to extend the pattern framework to knapsack problems with *partial or approximate symmetries*, for instance when item weights are identical only within subsets of groups, or differ by bounded perturbations. Another extension concerns more general precedence structures, where chains are replaced by trees or forests sharing common structural properties across groups.

# 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.
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). Two-phase branch&cut for integer problems with symmetries, application to a knapsack variant.

Boland, N., Bley, A., Fricke, C., Froyland, G., and Sotirov, R. (2012). Clique-based facets for the precedence constrained knapsack problem. *Mathematical programming*, 133:481–511.

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

Ceria, S., Cordier, C., Marchand, H., and Wolsey, L. A. (1998). Cutting planes for integer programs with general integer variables. *Mathematical programming*, 81(2):201–214.

Christof, T. and Löbel, A. (2009). Polyhedron representation transformation algorithm. URL: https://porta.zib.de.

Croxton, K. L., Gendron, B., and Magnanti, T. L. (2003). A comparison of mixed-integer programming models for nonconvex piecewise linear cost minimization problems. *Management Science*, 49(9):1268–1273.

Del Pia, A., Linderoth, J., and Zhu, H. (2023). On the complexity of separating cutting planes for the knapsack polytope. *Mathematical Programming*, pages 1–27.

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.

Garey, M. R. and Johnson, D. S. (1979). *Computers and intractability. A guide to the theory of NP-completeness*.

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.

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.

Letchford, A. N. and Souli, G. (2020). Lifting the knapsack cover inequalities for the knapsack polytope. *Operations Research Letters*, 48(5):607–611.

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.

Markowitz, H. M. and Manne, A. S. (1957). On the solution of discrete programming problems. *Econometrica: journal of the Econometric Society*, pages 84–110.

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

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.

Zukerman, M., Jia, L., Neame, T., and Woeginger, G. J. (2001). A polynomially solvable special case of the unbounded knapsack problem. *Operations Research Letters*, 29(1):13–16.
# 6 Appendix: Proofs and lemmas

## 6.1 Proof of Theorem 1

*Proof.* Let $(M, w', v', C')$ be an instance of the (UIK) with $M$ items, item $j \le n$ has weight $w'_j$ and value $v'_j$. We assume without loss of generality that $w'_j > w'_{j-1}$. The aim is to maximize the value of the selected items, each can be selected multiple times, without any limitation, while satisfying the maximum knapsack capacity $C'$. From $(M, w', v', C')$, one can construct instance $(I, J, w, v, C)$ of the (SCPK) with same value. The number of elements is $J = n$, the number of groups is $I = \lceil \frac{C'}{\min(w'_j)} \rceil$. The weights are $w_1 = w'_1$ and $w_j = w'_j - w'_{j-1}$ for each $j > 1$. The values are $v_{i,1} = v'_1$ with $i \in \{1, \dots, I\}$ and $v_{i,j} = v'_j - v'_{j-1}$ for each $j \in \{2, \dots, J\}$ and $i \in \{1, \dots, I\}$. Finally, the capacity is $C = C'$. The aim is to maximize the value of the selected items, verifying the chain precedence constraints, and satisfying the maximum knapsack capacity $C$. For a solution of $(M, w', v', C)$ there is a corresponding solution of $(I, J, w, v, C)$ with same value. Let $p_j$ be the number of times item $j$ is selected in a solution of $(M, w', v', C)$. There is a solution of $(I, J, w, v, C)$ that is equivalent: for each element $j$, there are $p_j$ unique groups of $(M, w', v', C)$ where exactly elements 1 to $j$ are selected. Such a solution of $(I, J, w, v, C)$ exists as $I = \lceil \frac{C}{\min(w'_j)} \rceil$, then $\sum_{j=1}^n p_j \le I$. Similarly, for a solution of $(I, J, w, v, C)$ there is a solution of $(M, w', v', C)$ with same value. Let $p_j$ be the number of groups where exactly elements 1 to $j$ are selected in a solution of $(I, J, w, v, C)$. There is a solution of $(M, w', v', C)$ that is equivalent: each item $j$ is selected exactly $p_j$ times. Thus, the (UIK) is a special case of the (SCPK), and because the (UIK) is NP-hard Zukerman et al. (2001), the (SCPK) is NP-hard when $I \ge \frac{C}{w_1}$. $\square$

## 6.2 Proof of Theorem 2

*Proof.* Let $(S, W)$ be an instance of the (SSP), with $S = \{a_1, \dots, a_n\}$, $a_j > 0$ for all $j \le n$, and $W > 0$. Without loss of generality, we suppose $a_j \le a_{j+1}$ for all $j < n$. The aim is to find $S' \subseteq S$ such that $\sum_{i \in S'} a_i = W$.

From $(S, W)$, one can construct instance $(I, J, w, v, C)$ of the (SCPK) as follows. We set $J = |S|$, and the number of groups $I$ can have any value greater than or equal to $J$. For the purpose of this proof, we consider $I = J$. Weights are $w_1 = a_1$, $w_j = a_j - a_{j-1}$ for all $j > 1$. Values are $v_{ij} = 0$ if $j \ne i$ and $v_{ij} = a_j$ if $i = j$. Finally, capacity is $C = W$. We consider here the decision problem associated with the (SCPK), where the aim is to find a solution of value greater than or equal to $C$.

By construction of the weights and values, for a given group $i \le I$, $\sum_{j=1}^i w_j = \sum_{j=1}^i v_{ij} = a_j$, and for any $j' > 0$, $j' \ne i$, $\sum_{j=1}^{j'} w_j > \sum_{j=1}^{j'} v_{ij}$. The decision problem of the (SCPK) indicates that the solution must have value above or equal to $C$, and weight below or equal to $C$. Consequently, a feasible solution can only include, for a group $i$, exactly the $i$ first elements, or no element.

For a solution of $(I, J, w, v, C)$, there is a corresponding solution of $(S, W)$. One can consider $S'$ with all values $a_i$ if elements are selected in group $i$. Besides, solution of $(I, J, w, v, C)$ has its weight equal to its value, hence they must both be equal to $C = W$. Consequently, $\sum_{i \in S'} a_i = W$.

For a solution of $(S, W)$, there is a corresponding solution of $(I, J, w, v, C)$. Let $S'$ be the solution of the (SSP). For each $i \in S'$, select exactly the first $i$ elements of group $i$ in the (SCPK). By construction, this solution of the (SCPK) is valid, as it has both weight and value equal to $\sum_{i \in S'} a_i = W = C$. As the (SSP) is NP-hard (Garey and Johnson (1979)), then the (SCPK) is NP-hard when $I \ge J$. $\square$

## 6.3 Proof of Theorem 3

*Proof.* As there are $I$ groups and $J$ elements, solutions $X_{ij}$ and $X_\emptyset$ yield a total of $I \times J + 1 = n + 1$ different solutions, which are feasible, otherwise ($\mathcal{F}$) is not verified. For any $i$, solution $X_{iJ}$ is the only solution with $x_{iJ} = 1$, thus being affinely independent to other solutions. For any $i$, solution $X_{ij}$, $j < J$ is the only solution with $x_{ij} = 1$ and $x_{ij+1} = 0$, this being affinely independent to other solutions. Clearly, $X_\emptyset$ is affinely independent to other solutions, which means that there are $n + 1$ affinely independent solutions. $\square$
## 6.4 Proof of Theorem 4

*Proof.* As there are $I$ groups and $J$ elements, solutions $X_{ij}$ and $X_{\emptyset}$ yield a total of $I \times J + 1 = n + 1$ different solutions, which are feasible otherwise ($\mathcal{F}$) is not verified. For a given $i$, besides solution $X_{iJ}$, every of the other $n$ solutions verify $x_{iJ} \ge 0$ to equality, and are proven to be affinely independent. Inequalities $x_{iJ} \ge 0$ are then facet-defining for $P_{(SCPK)}$. Any other inequality $x_{ij} \ge 0$, $j \ne J$ cannot be facet-defining. Indeed, $x_{ij} \ge 0$ can be obtained by summing $x_{ij'} \le x_{ij'-1}$ for all $j' \in \{j+1, \dots, J\}$ and $0 \le x_{iJ}$.

## 6.5 Proof of Theorem 5

*Proof.* As there are $I$ groups and $J$ elements, solutions $X_{ij}$ and $X_{\emptyset}$ yield a total of $I \times J + 1 = n + 1$ different solutions, which are feasible otherwise ($\mathcal{F}$) is not verified. Besides $X_{ij-1}$, each of the $n$ solutions verifies $x_{ij} \le x_{ij-1}$ to equality, and is proven to be affinely independent. Inequalities $x_{ij} \le x_{ij-1}$ are then facet-defining for $P_{(SCPK)}$.

## 6.6 Proof of Theorem 6

*Proof.* Consider a group $i'$. For each item $(i, j)$, consider a solution $X'_{ij}$, similar to $X_{ij}$, with $x_{i'1} = 1$ if $i' \ne i$. As there are $I$ groups and $J$ elements, solutions $X'_{ij}$ yields a total of $I \times J = n$ different solutions, which are feasible if $C \ge \sum_{j=1}^J w_j + w_1$ and ($\mathcal{F}$) are verified. Each of the $n$ solutions verifies $x_{i'1} \le 1$ to equality, and is proven to be affinely independent in the same manner as solutions $X_{ij}$. Inequalities $x_{i'1} \le 1$ are then facet-defining for $P_{(SCPK)}$ if $C \ge \sum_{j=1}^J w_j + w_1$.

In the case where $C < \sum_{j=1}^J w_j + w_1$, clearly $x_{iJ} + x_{i'1} \le 1$ is valid, for any $i \le I$, $i' \le I$ and $i \ne i'$ because of the symmetric weights. In which case inequality $x_{iJ} \le 1$ is dominated and cannot be facet-defining in this case. Hence, inequalities $x_{i1} \le 1$ are facet-defining if and only if $C \ge \sum_{j=1}^J w_j + w_1$. Any other inequality $x_{ij} \le 1$, $j \ne 1$ cannot be facet-defining. Indeed, $x_{ij} \le 1$ can be obtained by summing $x_{ij'} \le x_{ij'-1}$ for all $j' \in \{2, \dots, j\}$ and $x_{i1} \le 1$.

## 6.7 Proof of Property 3

*Proof.* Let $(I, J, w, v, C)$ be an instance of the (SCPK) where an item $(i, j)$ cannot be selected in any feasible solution, and $(i, j-1)$ can be selected in a feasible solution. Clearly, $(I, J, w, v, C)$ does not verify ($\mathcal{F}$). Because of the symmetric weights, item $j$ cannot be selected in any group, therefore, for any $i \le I$ and $j' \ge j$, $x_{ij'} = 0$ in any integer solution. It is possible to create another instance of the (SCPK) $(I, j-1, w, v, C)$ with the exact same integer solutions. Because $(i, j-1)$ can be selected in a feasible solution, and because of the symmetric weight, any item of $(I, j-1, w, v, C)$ can be selected. Hence, $(I, j-1, w, v, C)$ verifies ($\mathcal{F}$).

## 6.8 Proof of Property 10

*Proof.* Let $(i, j)$ be an item such that there is $x_{ij'} \in \mathcal{X}(\mathcal{P})$ with $j' > j$. Assume without loss of generality that $j'$ is such that there are no $x_{ij''} \in \mathcal{X}(\mathcal{P})$, $j < j'' < j'$. As $\mathcal{P}$ is a flexible pattern, condition (iii) holds and the property is verified for item $(i, j')$ as $x_{ij'} \in \mathcal{X}(\mathcal{P})$. Let $\mathcal{Y}'$ be the set of variables verifying condition (iii) for item $(i, j')$. Let $\mathcal{Z}$ be the subset of $\mathcal{Y}'$ with all variables $x_{ij''} \in \mathcal{Y}', j'' \ge j$. One can build $\mathcal{Y} = \mathcal{Y}' \setminus \mathcal{Z} \cup \{x_{ij}\}$. We can prove that the set of variables $\mathcal{Y}$ verifies the property for item $(i, j)$. By construction, $x_{ij} \in \mathcal{Y}$ and $x_{ij''} \notin \mathcal{Y}$ for every $j'' > j$. As there are no $x_{ij''} \in \mathcal{X}(\mathcal{P})$, $j < j'' < j'$ and $\mathcal{Y}'$ is a $k$-intersection of $\mathcal{X}(\mathcal{P})$ by condition (iii), then $|\mathcal{Y} \cap \mathcal{X}(\mathcal{P})| = k$. Also, as the weights are non-negative, and solution $X_{j'}$ is valid by condition (iii), then $X_j$ is also valid. Consequently, $\mathcal{Y}$ is a $k$-intersection of $\mathcal{X}(\mathcal{P})$ and the property is verified for $x_{ij}$.

Let $(i, j)$ be an item such that for all $j' > j$, $x_{ij'} \notin \mathcal{X}(\mathcal{P})$. As $\mathcal{P}$ is a flexible pattern, condition (ii) holds and the property is verified for item $(i, J)$. The proof is the same as in the first case, with $\mathcal{Y}'$ the set of variables verifying condition (ii) for item $(i, J)$.

Thus, for any $(i, j)$, there exist a feasible solution with $x_{ij} = 1$, $x_{ij+1} = 0$ and a total of $k$ variables of $\mathcal{X}(\mathcal{P})$ to 1.
## 6.9 Proof of Property 12

*Proof.* The proof is divided in two possibles cases, each being supported by a lemma. In the case $S_i(Q_1) \subseteq S_i(P)$ with $S_i(P)[u] \in S_i(Q_1)$, the proof is provided by **Lemma 2**. In the case $S_i(Q_1) \subset S_i(P)$ with $S_i(P)[u] \notin S_i(Q_1)$, the proof is provided by **Lemma 3**. Hence, the property is always verified. □

**Lemma 2.** Let $\mathcal{P}$ be a flexible pattern. Let $i$ be an integer belonging to $\{2, \dots, I\}$. For any $u \in \{1, \dots, V\}$, if $S_i(\mathcal{P})[u] \in S_i(Q_1)$ and $|S_i(\mathcal{P})| \ge u + V$ then $S_1(\mathcal{P})[u] \ge S_i(\mathcal{P})[u + V]$.

The idea of the following proof is illustrated by **Example 12** and **Figure 5**.

**Example 12 (Proof of Lemma 2).** Let $(4, 5, w, v, C)$ be an instance of the (SCPK). Let $\mathcal{P} = \{S_1(\mathcal{P}) = \{1, 2\}, S_2(\mathcal{P}) = \{1, 3\}, S_3(\mathcal{P}) = \{1, 2, 3\}, S_4(\mathcal{P}) = \{2, 3, 4, 5\}\}$ be a flexible pattern of rank 7 and with $V = 2$. Suppose $Q_1 = \{\{1, 2\}, \{1\}, \emptyset, \{2, 3, 4, 5\}\}$. In this case $\mathcal{P}$ does not follow **Lemma 2**. Indeed, with $u = 2$, there is $S_1(\mathcal{P})[2] = 1 < S_4(\mathcal{P})[2 + 2] = 2$.

Set $\mathcal{X}(\mathcal{P}) = \{x_{11}, x_{12}, x_{21}, x_{23}, x_{31}, x_{32}, x_{33}, x_{42}, x_{43}, x_{44}, x_{45}\}$ as represented in **Figure 5a**. Let $\mathcal{Y} = \mathcal{X}(Q_1) = \{x_{11}, x_{12}, x_{31}, x_{42}, x_{43}, x_{44}, x_{45}\}$. As $\mathcal{P}$ is a flexible pattern, **Lemma 1** proves that solution $X_{\mathcal{Y} \cup \{x_{15}\}}$, as represented in **Figure 5b**, is feasible. Let $\mathcal{Z} = \{x_{21}, x_{32}\}$ be a variable set. By construction $|\mathcal{Z}| = u = 2$. Clearly, solution $X_{\mathcal{Y} \setminus \{x_{12}\} \cup \mathcal{Z}}$, as represented in **Figure 5c**, is unfeasible by the rank of $\mathcal{P}$. Hence, $w_2 + w_1 > w_2 + w_3 + w_4 + w_5$.

As $\mathcal{P}$ is a flexible pattern, $\mathcal{P}$ verifies **Property 10**. Hence there is a set $\mathcal{Y}'$ such that $x_{41} \in \mathcal{Y}'$, $x_{4j} \notin \mathcal{Y}'$ for every $j \in \{2, \dots, 5\}$ and $|\mathcal{Y}' \cap \mathcal{X}| = 7$ and $X_{\mathcal{Y}'}$ is a valid solution. Suppose in this example $\mathcal{Y}' = \{x_{11}, x_{12}, x_{21}, x_{23}, x_{31}, x_{32}, x_{33}, x_{41}\}$ represented in **Figure 5d**.

Note that $S_4(\mathcal{P})[u+V]-1 = S_4(\mathcal{P})[4]-1 = 1$, and by construction, $x_{4j} \notin \mathcal{Y}'$ for every $j \in \{1, \dots, 5\}$. Hence, there are $u+V = 4$ variables, namely $x_{21}, x_{23}, x_{32}, x_{33}$, in $\mathcal{Y}' \setminus \mathcal{Y}$. **Property 11** indicates that for every $i \le I$, $S_i(\mathcal{P})[V+1] \in S_i(Q_1)$. Thus, these 4 variables in $\mathcal{Y}' \setminus \mathcal{Y}$ are split into a set $O_2 \subset \mathcal{X}$ of 1 to $V = 2$ variables in a group, and a set $O_1 \subset \mathcal{X}$ of $u = 2$ to $u+V-1 = 3$ variables in the other groups. In this case, we arbitrarily chose $O_2 = \{x_{32}, x_{33}\}$ and $O_1 = \{x_{21}, x_{23}\}$. Because both $\mathcal{Z}$ and $O_1$ are subsets of $\mathcal{X} \setminus \mathcal{Y}$ and $|\mathcal{Z}| \le |O_1|$, then $w_1 + w_2 + w_3 \ge w_1 + w_2 > w_2 + w_3 + w_4 + w_5$. Hence, with $\mathcal{Y}'' = \mathcal{Y}' \setminus O_1 \cup \{x_{42}, x_{43}, x_{44}, x_{45}\}$ represented in **Figure 5e**, as solution $X_{\mathcal{X}'}$ is feasible, then solution $X_{\mathcal{Y}''}$ is also feasible. However $\mathcal{Y}''$ is an 8-intersection of $\mathcal{X}$, which contradicts the rank of $\mathcal{P}$.

<figure><img src="image_6.png" /><figcaption>Figure 5: Illustration of Example 12</figcaption></figure>

*Proof.* Let $\mathcal{P}$ be a flexible pattern of rank $k$ and $Q_1$ a lower sub-pattern of $\mathcal{P}$. Suppose that there is $u \le V$ and $i > 1$ such that $S_1(\mathcal{P})[u] \in S_i(Q_1)$ and $|S_i(\mathcal{P})| \ge u + V$ but $S_1(\mathcal{P})[u] < S_i(\mathcal{P})[u + V]$.

Let $\mathcal{X} = \mathcal{X}(\mathcal{P})$ and $\mathcal{Y} = \mathcal{X}(Q_1)$. By **Lemma 1**, solution $X_{\mathcal{Y} \cup \{x_{1J}\}}$ is feasible. However, for a variable set $\mathcal{Z}$, $\mathcal{Z} \subseteq \mathcal{X} \setminus \mathcal{Y}$, it is not possible to create a feasible solution from $X_{\mathcal{Y}}$ by setting every variable of $\mathcal{Z}$ to 1, and $|\mathcal{Z}| - 1$ variables of $\mathcal{Y}$ to 0. Otherwise there would be $k + 1$ variables of $\mathcal{X}$ to 1, which contradicts the rank of $\mathcal{P}$. With $|\mathcal{Z}| = u$, as $X_{\mathcal{Y} \cup \{x_{1J}\}}$ is a feasible solution, we deduce the following: $\sum_{x_{i'j'} \in \mathcal{Z}} s_{i'j'}(\mathcal{X}) > \sum_{j=S_1(\mathcal{P})[u]+1}^{J} w_j$. Because $\mathcal{P}$ is flexible, **Property 10** implies that for $j = S_i(\mathcal{P})[u + V]$ there exists a set $\mathcal{Y}' \in \mathcal{V}$ being a $k$-intersection of $\mathcal{X}$ with $x_{ij-1} \in \mathcal{Y}'$ and $x_{ij'} \notin \mathcal{Y}'$, $j' \ge j$, such that $X_{\mathcal{Y}'}$ is valid. From **Property 4** as $\mathcal{Y}$ is a $k$-intersection of $\mathcal{X}$, there is $\mathcal{Y}' \subseteq \mathcal{Y}$ a $k$-intersection of $\mathcal{X}$. Hence we suppose without loss of generality that $|\mathcal{Y}| = k$.

In the case $S_i(Q_1) = S_i(\mathcal{P})$, clearly there are $u + V$ more variables of group $i$ in $\mathcal{Y} \setminus \mathcal{Y}'$. As $\mathrm{card}(Q_1) = k$ and $\mathcal{Y} = \mathcal{X}(Q_1)$, then $|\mathcal{Y}| = |\mathcal{Y}'| = k$. Hence, there are $u + V$ variables of groups different than $i$ in $\mathcal{Y}' \setminus \mathcal{Y}$. **Property 11** indicates that for each $i' \le I$, $|S_{i'}(Q_1)| \ge |S_{i'}(\mathcal{P})| - V$. Thus,
these $u + V$ variables in $\mathcal{Y}' \setminus \mathcal{Y}$ are split into a set $\mathcal{O}_2 \subset \mathcal{X}$ of 1 to $V$ variables in a group, and a set $\mathcal{O}_1 \subset \mathcal{X}$ of $u$ to $u + V - 1$ variables in the other groups.

In the case $S_i(\mathcal{Q}_1) \subset S_i(\mathcal{P})$ with $S_i(\mathcal{P})[u] \in S_i(\mathcal{Q}_1)$ there are between $V+1$ and $u+V-1$ variables of group $i$ in $\mathcal{Y} \setminus \mathcal{Y}'$ and reciprocally between $V+1$ and $u+V-1$ variables of groups different than $i$ in $\mathcal{Y}' \setminus \mathcal{Y}$. In this case we consider $\mathcal{O}_1 \subset \mathcal{X}$ to be the set of $V+1$ to $u+V-1$ variables if $\mathcal{Y}' \setminus \mathcal{Y}$, and $\mathcal{O}_2 = \emptyset$. We know that $\mathcal{Z} \in \mathcal{X}$ and $\mathcal{Z} \cap \mathcal{Y} = \emptyset$ and similarly, $\mathcal{O}_1 \subset \mathcal{X}$ and $\mathcal{O}_1 \cup \mathcal{Y} = \emptyset$. Also, we know that $|\mathcal{O}_1| \ge u = |\mathcal{Z}|$. We deduce that:

$$ \sum_{x_{i'j'} \in \mathcal{O}_1} s_{i'j'}(\mathcal{X}) \ge \sum_{x_{i'j'} \in \mathcal{Z}} s_{i'j'}(\mathcal{X}) > \sum_{j=S_1(\mathcal{P})[u]+1}^{J} w_j. $$

By construction, $S_i(\mathcal{P})[1] \le J$ and by hypothesis, $S_i(\mathcal{P})[u+V] > S_1(\mathcal{P})[u]$, which means that:

$$ \sum_{j \in S_i(\mathcal{P}): j \ge S_i(\mathcal{P})[u+V]} s_{ij}(\mathcal{X}) = \sum_{j=S_j(\mathcal{P})[u+V]}^{S_i(\mathcal{P})[1]} w_j \le \sum_{j=S_1(\mathcal{P})[u]+1}^{J} w_j. $$

The $u+V$ variables of group $i$ that are in $\mathcal{Y}$ but not in $\mathcal{Y}'$ are lighter than the ones in $\mathcal{Z}$, thus lighter than variables of $\mathcal{O}_1$. Hence we build $\mathcal{Y}'' = \mathcal{Y}' \setminus \mathcal{O}_1$ to which we add all the $u+V$ variables of group $i$ in $\mathcal{X} \setminus \mathcal{Y}'$. As $X_{\mathcal{Y}''}$ is valid, then $X_{\mathcal{Y}''}$ is also valid. However $|\mathcal{O}_1| \le u+V-1$, meaning that the new solution has at least $k+1$ variables of $\mathcal{X}$ to 1, which contradicts the rank of $\mathcal{P}$. $\square$

**Lemma 3.** Let $\mathcal{P}$ be a flexible pattern and $\mathcal{Q}_1$ a lower sub-pattern of $\mathcal{P}$. Let $i$ be an integer belonging to $\{2, \dots, I\}$. For any $u \in \{1, \dots, V\}$, if $S_i(\mathcal{P})[u] \notin S_i(\mathcal{Q}_1)$ and $|S_i(\mathcal{P})| \ge u+V$ then $S_1(\mathcal{P})[u] \ge S_i(\mathcal{P})[u+V]$.

*Proof.* Suppose that there is $u \le V$ and $i > 1$ such that $S_i(\mathcal{P})[u] \notin S_i(\mathcal{Q}_1)$ and $|S_i(\mathcal{P})| \ge u+V$ but $S_1(\mathcal{P})[u] < S_i(\mathcal{P})[u+V]$. Let $\mathcal{X} = \mathcal{X}(\mathcal{P})$ and $\mathcal{Y} = \mathcal{X}(\mathcal{Q}_1)$. Because $\mathcal{P}$ is flexible, **Lemma 1** proves that solution $X_{\mathcal{Y} \cup \{x_{1j}\}}$ is valid. By definition, $S_i(\mathcal{P})[1] \le J$ and $S_i(\mathcal{P})[V+1] \ge S_i(\mathcal{P})[u+V]$ and by hypothesis $S_i(\mathcal{P})[u+V] > S_1(\mathcal{P})[u]$, which means that $\sum_{j=S_i(\mathcal{P})[V+1]+1}^{S_i(\mathcal{P})[1]} w_j \le \sum_{j=S_1(\mathcal{P})[u]+1}^{J} w_j$.

Hence, one can build $\mathcal{Y}' = \mathcal{Y} \cup \{x_{1j}\}$ from which we remove all variables $x_{1j} \in \mathcal{X}$, $j > S_1(\mathcal{P})[u]$ and to which we add all variables for group $i$: $x_{ij} \in \mathcal{X} \setminus \mathcal{Y}$, with solution $X_{\mathcal{Y}'}$ being valid. However, there are $u-1$ variables $x_{1j} \in \mathcal{X}$ such that $j > S_1(\mathcal{P})[u]$, and at least $u$ variables $x_{ij} \in \mathcal{X} \setminus \mathcal{Y}$ as $S_i(\mathcal{P})[u] \notin S_i(\mathcal{Q}_1)$. As $\mathcal{Y}$ is a $k$-intersection of $\mathcal{X}$, then $\mathcal{Y}'$ is at least a $k+1$-intersection of $\mathcal{X}$ which contradicts the rank of $\mathcal{P}$. $\square$

## 6.10 Proof of Property 13

*Proof.* The proof is divided in three possible cases, each being supported by a lemma. In the case $|S_1(\mathcal{Q}_1)| + |S_i(\mathcal{Q}_1)| = |S_1(\mathcal{Q}_i)| + |S_i(\mathcal{Q}_i)|$, the proof is provided by **Lemma 4**. In the case $|S_1(\mathcal{Q}_i)| = 0$, the proof is provided by **Lemma 5**. In the case $|S_1(\mathcal{Q}_i)| > 0$, the proof is provided by **Lemma 6**. Hence, the property is always verified. $\square$

**Lemma 4.** Let $\mathcal{P}$ be a flexible pattern of rank $k$ and $\mathcal{Q}_1$ a lower sub-pattern of $\mathcal{P}$. Let $\mathcal{Q}_i$ be a lower sub-pattern of $\mathcal{P}$ with $i > 1$. If $|S_1(\mathcal{Q}_1)| + |S_i(\mathcal{Q}_1)| = |S_1(\mathcal{Q}_i)| + |S_i(\mathcal{Q}_i)|$ and $|S_i(\mathcal{P})| \ge 2V$, then for each $i \le I$, there is $\mathcal{Q}_i$ such that for every $i' \le I$ with $|S_{i'}(\mathcal{P})| \ge 2V$, $S_{i'}(\mathcal{P})[2V] \in S_{i'}(\mathcal{Q}_i)$.

*Proof.* We are in the case $|S_1(\mathcal{Q}_1)| + |S_i(\mathcal{Q}_1)| = |S_1(\mathcal{Q}_i)| + |S_i(\mathcal{Q}_i)|$. Let $\mathcal{L} = \{1, \dots, I\} \setminus \{1, i\}$ be a set of indices. By definition, $\mathrm{card}(\mathcal{Q}_1) = \mathrm{card}(\mathcal{Q}_i) = k$ hence we deduce the following equation:

$$ \sum_{i' \in \mathcal{L}} |S_{i'}(\mathcal{Q}_1)| = \sum_{i' \in \mathcal{L}} |S_{i'}(\mathcal{Q}_i)|. $$

We suppose without loss of generality that $S_{i'}(\mathcal{Q}_1) = S_i(\mathcal{Q}_i)$ for each $i' \in \mathcal{L}$. Indeed, by definition $\mathcal{Q}_1$ and $\mathcal{Q}_i$ minimize the weight of their respective variable sets. Hence they have both the exact same weight for their variables sets restricted to indices in $\mathcal{L}$, otherwise it is clear that one of them do not
minimize the weight of its variable sets. Consequently, one can modify $\mathcal{Q}_i$ such that $S_{i'}(\mathcal{Q}_1) = S_{i'}(\mathcal{Q}_i)$ for each $i' \in \mathcal{L}$ without increasing the weight of the variable sets of $\mathcal{Q}_i$.

**Property 11** indicates that $S_{i'}(\mathcal{P})[V+1] \in S_{i'}(\mathcal{Q}_1)$. As $\mathcal{P}$ is flexible pattern, $V \ge 1$ by condition (i), and $V+1 \ge 2V$. Clearly the Lemma is verified for $\mathcal{Q}_1$. As $S_{i'}(\mathcal{Q}_1) = S_{i'}(\mathcal{Q}_i)$ for any $i' \in \mathcal{L}$, the Lemma is also verified for any $S_{i'}(\mathcal{Q}_i)$ with $i' \in \mathcal{L}$. By definition of $\mathcal{Q}_i$, $S_i(\mathcal{Q}_i) = S_i(\mathcal{P})$, trivially verifying the Lemma. As $|S_1(\mathcal{P})| = V < 2V$, the Lemma does not concern $S_1(\mathcal{Q}_i)$. Thus, the Lemma is verified for any set $S_{i'}(\mathcal{Q}_i)$ for which $|S_{i'}(\mathcal{Q}_i)| \ge 2V$. $\square$

**Lemma 5.** Let $\mathcal{P}$ be a flexible pattern of rank $k$. Let $\mathcal{Q}_i$ be a lower sub-pattern of $\mathcal{P}$ with $i > 1$. If $|S_1(\mathcal{Q}_i)| = 0$, then for each $i' \le I$ with $|S_{i'}(\mathcal{P})| \ge 2V$, $S_{i'}(\mathcal{P})[2V] \in S_{i'}(\mathcal{Q}_i)$.

The idea of the following proof is illustrated by **Example 13** and **Figure 6**.

**Example 13** (Idea of the proof of Lemma 5). Let $(5, 3, w, v, C)$ be an instance of the (SCPK). Let $\mathcal{P} = \{S_1 = \{3\}, S_2 = \{1, 2, 3\}, S_3 = \{1, 2, 3\}, S_4 = \{1, 2, 3\}, S_5 = \{1, 2, 3\}\}$ be a flexible pattern of rank 10. The smallest set of $\mathcal{P}$ is $S_1(\mathcal{P})$ hence $V = 1$. Suppose $\mathcal{Q}_1 = \{S_1 = \{3\}, S_2 = \{1, 2, 3\}, S_3 = \{1, 2\}, S_4 = \{1, 2\}, S_5 = \{1, 2\}\}$ and $\mathcal{Q}_2 = \{S_1 = \emptyset, S_2 = \{1, 2, 3\}, S_3 = \{1\}, S_4 = \{1, 2, 3\}, S_5 = \{1, 2, 3\}\}$. We are in the case of **Lemma 5** as $|S_1(\mathcal{Q}_2)| = 0$, but not in the case of **Lemma 4**, as $|S_1(\mathcal{Q}_1)| + |S_2(\mathcal{Q}_1)| = 4 \ne |S_1(\mathcal{Q}_2)| + |S_2(\mathcal{Q}_2)| = 3$. However, **Lemma 5** is not verified, as $S_3(\mathcal{P})[2V] = S_3(\mathcal{P})[2] = 2 \notin S_3(\mathcal{Q}_2)$. Let $\mathcal{Y} = \mathcal{X}(\mathcal{Q}_1) = \{x_{13}, x_{21}, x_{22}, x_{23}, x_{31}, x_{32}, x_{41}, x_{42}, x_{51}, x_{52}\}$ and $\mathcal{Y}' = \mathcal{X}(\mathcal{Q}_2) = \{x_{21}, x_{22}, x_{23}, x_{31}, x_{41}, x_{42}, x_{43}, x_{51}, x_{52}, x_{53}\}$. As $\mathcal{P}$ is pattern-flexible, **Lemma 1** proves that solution $X_{\mathcal{Y} \cup \{x_{14}\}}$ is valid. Also, $\mathcal{Q}_2$ minimizes the sum of the weights, $\{x_{43}, x_{53}\} \in \mathcal{Y}'$ and $\{x_{32}, x_{33}\} \notin \mathcal{Y}'$ hence $w_3 + w_3 \le w_2 + w_3$. Clearly, $w_3 + w_3 \le w_2 + w_3 \le w_1 + w_2 + w_3 + w_4$. With $\mathcal{O} = \mathcal{Y}' \setminus \mathcal{Y} = \{x_{43}, x_{53}\}$, the set $\mathcal{Y}'' = \mathcal{Y} \cup \{x_{14}\} \setminus \{x_{13}, x_{14}\} \cup \mathcal{O}$ yields a feasible solution $X_{\mathcal{Y}''}$. However, $\mathcal{Y}''$ is a 9-intersection of $\mathcal{X}$, which contradicts the rank of $\mathcal{P}$. $\square$

<figure><img src="image_7.png" /><figcaption>Figure 6: Illustration of **Example 13**</figcaption></figure>

*Proof.* Because of the shape of $\mathcal{Q}_1$ (see **Property 11**), $|S_1(\mathcal{Q}_1)| = V$ meaning that $|S_i(\mathcal{Q}_1)| \ge |S_i(\mathcal{P})| - V$. We first consider the case $|S_i(\mathcal{Q}_1)| = |S_i(\mathcal{P})| - V$. In such case, $|S_i(\mathcal{Q}_1)| + |S_1(\mathcal{Q}_1)| = |S_i(\mathcal{P})|$. By definition of $\mathcal{Q}_i$, $|S_i(\mathcal{Q}_i)| = S_i(\mathcal{P})$. As we are in the case $|S_1(\mathcal{Q}_i)| = 0$, then $|S_i(\mathcal{Q}_i)| + |S_1(\mathcal{Q}_i)| = |S_i(\mathcal{Q}_1)| + |S_1(\mathcal{Q}_1)|$ which is covered in **Lemma 4**.

Hence, we consider $|S_i(\mathcal{Q}_1)| \ge |S_i(\mathcal{P})| - V + 1$. Consequently, $|S_i(\mathcal{Q}_1)| + |S_1(\mathcal{Q}_1)| \ge |S_i(\mathcal{Q}_i)| + |S_1(\mathcal{Q}_i)| + 1$. Suppose there is $i' \ne 1$, $i' \ne i$ such that $S_{i'}(\mathcal{P})[2V] \notin S_{i'}(\mathcal{Q}_i)$. With $v \in [0, |S_{i'}(\mathcal{P})| - 2V]$, we have $|S_{i'}(\mathcal{Q}_i)| = |S_{i'}(\mathcal{P})| - 2V - v$, i.e., $S_{i'}(\mathcal{P})[2V + v] \notin S_{i'}(\mathcal{Q}_i)$. We know by the shape of $\mathcal{Q}_1$ that $|S_{i'}(\mathcal{Q}_1)| \ge |S_{i'}(\mathcal{P})| - V$ and thus $|S_{i'}(\mathcal{Q}_1)| \ge |S_{i'}(\mathcal{Q}_i)| + V + v$. This leads to the following result:
$$|S_1(\mathcal{Q}_1)| + |S_i(\mathcal{Q}_1)| + |S_{i'}(\mathcal{Q}_1)| - |S_1(\mathcal{Q}_i)| - |S_i(\mathcal{Q}_i)| - |S_{i'}(\mathcal{Q}_i)| \ge V + v + 1.$$

There must be a set of indices $\mathcal{L}$, $1 \notin \mathcal{L}$, $i \notin \mathcal{L}$, $i' \notin \mathcal{L}$ such that:

$$V + v + 1 \le \sum_{l \in \mathcal{L}} |S_l(\mathcal{Q}_i)| - |S_l(\mathcal{Q}_1)| \le 2V + v.$$

If not, then there is a set $l$ such that $|S_l(\mathcal{Q}_i)| - |S_l(\mathcal{Q}_1)| > V + 1$, which contradicts the shape of $\mathcal{Q}_1$ (see **Property 11**) which is that $|S_l(\mathcal{Q}_1)| \ge |S_l(\mathcal{P})| - V$. Let $\mathcal{X} = \mathcal{X}(\mathcal{P})$, $\mathcal{Y} = \mathcal{X}(\mathcal{Q}_1)$ and $\mathcal{Y}' = \mathcal{X}(\mathcal{Q}_i)$. Let $\mathcal{O}$ be the set of variables $x_{lj} \in \mathcal{Y}' \setminus \mathcal{Y}$ with $l \in \mathcal{L}$. Note that $V+v+1 \le |\mathcal{O}| \le 2V+v$. Also, $S_{i'}(\mathcal{P})[2V+v] \notin S_{i'}(\mathcal{Q}_i)$, $\mathcal{O}$ is sub-pattern of $\mathcal{Q}_i$ and by definition $\mathcal{Q}_i$ minimizes the sum of the weights and $\mathcal{O}$ is a sub-pattern of $\mathcal{Q}_i$, hence we deduce:

$$\sum_{x_{lj} \in \mathcal{O}} s_{lj} \le \sum_{j=S_{i'}(\mathcal{P})[2V+v+1]+1}^{S_{i'}(\mathcal{P})[1]} w_j \le \sum_{j=S_{i'}(\mathcal{P})[2V+v+1]+1}^{J} w_j \le \sum_{j=1}^{J} w_j.$$
As $\mathcal{P}$ is flexible pattern, **Lemma 1** provides a feasible solution $X_{\mathcal{Y}\cup\{x_{1J}\}}$. One could create a new feasible solution from $X_{\mathcal{Y}\cup\{x_{1J}\}}$ by setting all variables of group 1 to 0, and all variables of $\mathcal{O}$ to one, creating a lighter solution, thus valid. However, $|\mathcal{O}| \ge V + v + 1 \ge V + 1 > |S_1(Q_1)| = V$. The new solution has at least $k+1$ variables of $\mathcal{X}$ to 1, which contradicts the rank of $\mathcal{P}$. $\square$

**Lemma 6.** Let $\mathcal{P}$ be a flexible pattern of rank $k$. Let $Q_i$ be a lower sub-pattern of $\mathcal{P}$ with $i > 1$. If $|S_1(Q_i)| > 0$, then for each $i' \le I$ with $|S_{i'}(\mathcal{P})| \ge 2V$, $S_{i'}(\mathcal{P})[2V] \in S_{i'}(Q_i)$.

*Proof.* We consider the case where $|S_1(Q_1)| + |S_i(Q_1)| \ne |S_1(Q_i)| + |S_i(Q_i)|$, as otherwise it is the case of **Lemma 4**. Suppose there is $i' \ne 1$, $i' \ne i$ such that $S_{i'}(\mathcal{P})[2V] \notin S_{i'}(Q_i)$. Let $v \in [0, |S_{i'}(\mathcal{P})| - 2V]$ be such that $|S_{i'}(Q_i)| = |S_{i'}(\mathcal{P})| - 2V - v$. Let $u$ be the smallest value such that $S_1(\mathcal{P})[u] \in S_1(Q_i)$, i.e., $u = V - |S_1(Q_i)| + 1$. Let $\mathcal{X} = \mathcal{X}(\mathcal{P})$ and $\mathcal{Y} = \mathcal{X}(Q_i)$. We know that $X_{\mathcal{Y}}$ is a feasible solution. We also know by **Property 12** that a flexible pattern $\mathcal{P}$ is such that $S_1(\mathcal{P})[u] \ge S_{i'}(\mathcal{P})[u + V]$, which means that:

$$ \sum_{j' \le S_{i'}(\mathcal{P})[u+V]} s_{i'j'}(\mathcal{X}) \le \sum_{j \le S_1(\mathcal{P})[u]} s_{1j}(\mathcal{X}). $$

Hence, one can build $\mathcal{Y}' = \mathcal{Y}$ from which we remove all variables $x_{1j} \in \mathcal{Y}$ and to which we add all $x_{i'j'} \in \mathcal{X}$, $j' \le S_{i'}(\mathcal{P})[u + V]$. Clearly, as $X_{\mathcal{Y}}$ is a valid solution, so is $X_{\mathcal{Y}'}$. In group $i'$, by hypothesis there are $|S_{i'}(\mathcal{P})| - 2V - v$ variables in $\mathcal{Y}$, and by construction $|S_{i'}(\mathcal{P})| - (V + u) + 1$ in $\mathcal{Y}'$. Hence in group $i'$, there are $V + v - u + 1$ variables in $\mathcal{Y}' \setminus \mathcal{Y}$. In group 1, by hypothesis there are $V - u + 1$ variables in $\mathcal{Y}$, and by construction 0 variables in $\mathcal{Y}'$. For groups different than $i'$ and 1, $\mathcal{Y}$ and $\mathcal{Y}'$ are identical by construction. We deduce $|\mathcal{Y}'| - |\mathcal{Y}| = V + v - u + 1 - (V - u + 1) = v \ge 0$.

In the case $v \ge 1$, as $\mathcal{Y}$ is a $k$-intersection of $\mathcal{X}$, then $\mathcal{Y}'$ is at least a $k+1$-intersection of $\mathcal{X}$, which contradicts the rank of $\mathcal{P}$.

In the case $v = 0$, by construction $\mathcal{Y}$ and $\mathcal{Y}'$ contain the same variables for group $i$. Also by construction, the weight of $\mathcal{Y}'$ is lighter than or equals to the weight of $\mathcal{Y}$. Clearly, there is a $Q'_i$ such that $\mathcal{Y}' = \mathcal{X}(Q_{i'})$. However, by construction $S_1(Q_{i'})$ is empty, which cannot be possible as proven by **Lemma 5**. $\square$

## 6.11 Proof of Property 15

*Proof.* By definition $card(Q_i(u)) = k$ and $|S_i(Q_i(u))| = u$. From **Property 14** $card(C) = k - 1$, and from **Property 13** for any $i' \le I$ with $|S_{i'}(\mathcal{P})| \ge 2$, $S_{i'}(\mathcal{P})[2] \in S_{i'}(C)$. Let $K$ be the difference between $card(Q_i(u) \setminus S_i(Q_i)(u))$ and $card(C \setminus S_i(C))$, i.e.,

$$ K = card(Q_i(u) \setminus S_i(Q_i)(u)) - card(C \setminus S_i(C)) = (k - u) - (k - 1 - |S_i(C)|) = 1 + |S_i(C)| - u. $$

Note that $u \le |S_i(C)|$, meaning that $K \ge 1$. Because for each $i' \le I$, $S_{i'}(\mathcal{P})[2] \in S_{i'}(C)$, and both $C$ and $Q_i(u)$ are sub-patterns of $\mathcal{P}$, then there are $K$ sets such that $|S_{i'}(Q_i(u))| = |S_{i'}(C)| + 1 = |S_{i'}(\mathcal{P})|$.

Let $i'$ be the index of one of these $K$ sets. By definition, $card(Q_{i'}) = k$ and $card(C) = k - 1$, meaning that $card(Q_{i'} \setminus S_{i'}(Q_{i'})) = card(C \setminus S_{i'}(C))$. By definition $C$ is sub-pattern of $Q_{i'}$, hence $Q_{i'} \setminus S_{i'}(Q_{i'}) = C \setminus S_{i'}(C)$. Consequently, $S_i(Q_{i'}) = S_i(C)$ and we deduce:

$$ \begin{aligned} & card(Q_i(u) \setminus S_i(Q_i)(u)) - card(Q_{i'} \setminus S_i(Q_{i'})), \text{ then} \\ & (k - u) - (card(Q_{i'} \setminus |S_i(Q_{i'})|), \text{ then} \end{aligned} \quad (k - u) - (k - |S_i(C)|) = K - 1. $$

From **Property 13** and because $V = 1$, there are $K - 1$ sets of $Q_i(u)$ with one more element than the respective set of $Q_{i'}$. However:

$$ K - 1 = 1 + |S_i(C)| - u - 1 = |S_i(C)| - u = |S_i(Q_{i'})| - |S_i(Q_i(u))|. $$

The difference between $|S_i(Q_{i'})|$ and $|S_i(Q_i(u))|$ is exactly $K - 1$. From **Property 13** if $i' \le I$ is such that $|S_{i'}(\mathcal{P})| \ge 2$, $S_{i'}(\mathcal{P})[2] \in S_{i'}(C)$ and $C$ is a sub-pattern of $Q_{i'}$. Hence there are $K - 1$ indices $i''$ such that $|S_{i''}(Q_i(u))| = |S_{i''}(Q_{i'})| + 1$.

Let $\mathcal{L}$ be a set of indices, containing $i$ and the $K - 1$ aforementioned indices $i''$. Patterns $Q_i(u)$ and $Q_{i'}$ are such that $\sum_{i'' \in \mathcal{L}} |S_{i''}(Q_i(u))| = \sum_{i'' \notin \mathcal{L}} |S_{i''}(Q_{i'})|$. By definition, both $Q_i(u)$ and $Q_{i'}$ are of cardinality $k$, hence $\sum_{i'' \notin \mathcal{L}} |S_{i''}(Q_i(u))| = \sum_{i'' \notin \mathcal{L}} |S_{i''}(Q_{i'})|$. As both lower sub-patterns minimize their set weights we deduce that for any $i'' \notin \mathcal{L}$, $S_{i''}(Q_i(u)) = S_{i''}(Q_{i'})$. Hence, for all $i'' \ne i$, $S_{i''}(Q_{i'}) \subseteq S_{i''}(Q_i(u))$. As $C$ is a sub-pattern of $Q_i$, then for each $i'' \ne i$, $S_{i''}(C) \subseteq S_{i''}(Q_i(u))$. $\square$
## 6.12 Proof of Theorem 8

*Proof.* Recall that without loss of generality, pattern sets can be ordered such that $|S_i(\mathcal{P})| \le |S_{i+1}(\mathcal{P})|$, meaning $|S_1(\mathcal{P})| = 1$. Let $\mathcal{X} = \mathcal{X}(\mathcal{P})$. Consider the following lower sub-patterns: $Q_1, Q_i$ for every $i \le I$ such that $S_i(\mathcal{P})[1] \notin S_i(Q_1)$; $Q_{i'}(u)$ for every $i' \le I$ and $u \in \{0, \dots, |S_{i'}(\mathcal{C})| - 1\}$. For all mentioned sub-patterns $\mathcal{Q}$, we consider their respective variable set $\mathcal{X}(\mathcal{Q})$, respectively denoted by $\mathcal{X}_1; \mathcal{X}_i; \mathcal{X}_{i'}(u)$ and their respective solution $X_{\mathcal{X}_1}; X_{\mathcal{X}_i}; X_{\mathcal{X}_{i'}(u)}$. This results in a total of $\mathrm{card}(\mathcal{P})$ solutions. There is one solution $X_{\mathcal{X}_1}$. As $\mathcal{P}$ is of rank $k$, there are $\mathrm{card}(\mathcal{P}) - k$ solutions $X_{\mathcal{X}_i}$. As $\mathrm{card}(\mathcal{C}) = k - 1$, there are $k - 1$ solutions $X_{\mathcal{X}_{i'}(u)}$. By definition of lower sub-patterns $Q_i$ and $Q_i(u)$ and from **Property 10**, all mentioned variable sets are $k$-intersections of $\mathcal{X}$. Hence, all mentioned solutions are feasible and verify $(pi(\mathcal{X}))$ to equality.

Consider now the points associated with the afore-enumerated solutions. We can prove these points to be linearly independent. Start by considering first the point associated with $X_{\mathcal{X}_1}$. As it is the only point considered, it is necessarily linearly independent. From **Property 14**, $\mathcal{C}$ is sub-pattern to all $Q_i$ and of cardinality $k-1$. Consequently, $Q_i$ with $S_i(\mathcal{P})[1] \notin S_i(Q_1)$ is the only lower sub-pattern, excluding the generalized lower sub-patterns, with $S_i(\mathcal{P})[1] \in S_i(Q_i)$. It results that for each solution $X_{\mathcal{X}_i}$, the associated point is the only one with $x_{iS_i(\mathcal{P})[1]} = 1$, thus they are linearly independent. For each solution $X_{\mathcal{X}_{i'}(u)}$, starting with large $u$, the associated point is the first one with $x_{i'S_{i'}(\mathcal{P})[u]} = 0$, thus being linearly independent. The enumerated solutions yield $\mathrm{card}(\mathcal{P})$ linearly independent points. Moreover, from **Theorem 7**, for each variable $x_{ij} \notin \mathcal{X}$ there is a feasible solution with $x_{ij} = 1$ and $x_{ij+1} = 0$ that verifies $(pi(\mathcal{X}))$ to equality. Sequentially adding these points associated with their corresponding solutions to our pool of $\mathrm{card}(\mathcal{P})$ points still keeps them linearly independent, as there are the only ones with $x_{ij} = 1$ and $x_{ij+1} = 0$ with $x_{ij} \notin \mathcal{X}$. As there are $n - \mathrm{card}(\mathcal{P})$ of these new points, there is a total of $n$ linearly independent points. Thus, a pattern $\mathcal{P}$ with a set of cardinality 1 is a facet-defining-pattern if and only if it is a flexible-pattern. $\square$