Alexandre Heintzmann
email: alexandre.heintzmann@edf.fr

Pascale Bendotti
email: pascale.bendotti@edf.fr

Cécile Rottner
email: cecile.rottner@edf.fr

Two-phase Branch & Cut for the Symmetric Weight Matrix Knapsack polytope

come

Introduction

Consider N groups of M elements, where N and M are positive integers. Let item (i, j) be element j of group i. Item (i, j) has weight w ij and value v ij , both non-negative. Within each group, order constraints are such that any item (i, j) can be selected provided item (i, j -1) is selected. Let C be the maximum capacity. The Matrix Knapsack Problem (MKP) is to maximize the total value of the selected items, while the order constraints are verified, and the total weight of the selected items is less than or equal to C. The Symmetric Weight Matrix Knapsack Problem (SMKP) is a Matrix Knapsack Problem where item (i, j) has weight w ij = w j , i.e., the weight of item (i, j) does not depend on the group index i. It means that items (i, j) and (i ′ , j) have the same weight, thus the knapsack is symmetrically weighted with respect to the groups. We define (N, M, w, v, C) an instance of the (SMKP).

Two well known formulations can be used for both the (MKP) and (SMKP), namely the so-called incremental formulation and the multiple choice formulation. The former involves order constraints, where the latter uses disjunctive constraints instead. Both formulations yield the same LP relaxation [START_REF] Keely L Croxton | A comparison of mixed-integer programming models for nonconvex piecewise linear cost minimization problems[END_REF]. Note that in the incremental formulation, there is a particular precedence graph induced by order constraints as depicted in Figure1(a). In the multiple choice formulation, it is a conflict graph induced by disjunctive constraints, namely a graph with edges between any pair of items in the same group. Figure 1(b) also shows the corresponding matrix representation that will be convenient in the sequel to illustrate on examples some properties.

The motivation for (SMKP) is that it is the core structure of the Hydro Unit Commitment (HUC) [START_REF] Hechme-Doukopoulos | The short-term electricity production management problem at EDF[END_REF], which is a production scheduling problem relative to hydroelectric units.

The knapsack problem and its variants have been widely studied in the literature [START_REF] Hojny | Knapsack polytopes: a survey[END_REF]. The (SMKP) and the (MKP) have not been studied yet, but can be related to some variants of the knapsack problem in the literature. As the order constraints are a special case of precedence constraints, the (MKP) is a direct special case of the Precedence Knapsack Problem (PKP) [START_REF] Boyd | Polyhedral results for the precedence-constrained knapsack problem[END_REF]. Similarly as disjunctive constraints can be used alternatively for the (MKP), the (MKP) is also a special case of the Disjunctive Knapsack Problem (DKP) [START_REF] Ben | Optimization algorithms for the disjunctively constrained knapsack problem[END_REF]. Both the (PKP) and the (DKP) are generalizations of the classical Binary knapsack problem (BKP). Indeed, the (BKP) is a (PKP) without any precedence, as well as a (DKP) without any disjunctive constraints. Interestingly, the (MKP) is also a generalization of the (BKP), whereas the (SMKP) is not. Indeed, an (MKP) with exactly one item for each group does not have any order constraints, which is exactly a (BKP). However, the (SMKP) is not a generalization of the Figure 1: Graphic representation of the (SMKP) (BKP). Indeed, because of the symmetric weight, an (SMKP) with one item per group would be a trivial (BKP), where each item has the exact same weight. Furthermore, the (SMKP) is not a Multiple knapsack problem [START_REF] Ferreira | Solving multiple knapsack problems by cutting planes[END_REF] despite the presence of multiple groups. Indeed, a capacity constraint is applied on all groups simultaneously in the (SMKP), whereas it is applied for each group individually in the Multiple knapsack problem.

In this paper, the (SMKP) is proven to be NP-hard. A compact formulation is defined with its corresponding polytope. A literature review of facet-defining inequalities for problems related to the (SMKP) is exposed. The main contributions are the polyhedral study of the (SMKP) and a two-phase Branch & Cut (B&C) scheme. A new structure, called pattern, is defined, embedding the symmetries of the (SMKP). New inequalities, associated to the patterns and covering all the facets of the (SMKP) with 0-1 coefficients are introduced. Necessary facet-conditions are defined for these inequalities, which are also proven to be sufficient for a special case. An algorithm to generate patterns verifying these conditions is described and is used as pre-processing in the first phase of the B&C scheme. The separation algorithms, involved in the second phase of the B&C scheme, reduces to solve a maximum matching problem for the pool of the first phase generated patterns. To evaluate the efficiency of the corresponding inequalities, a numerical comparison shows that pattern inequalities largely outperform CPLEX generated cuts.

In Section 2 the complexity of the (SMKP) is stated and some polyhedral results from the literature for variants of the KP are reported. In Section 3 the patterns are defined as well as inequalities and facet-defining conditions are provided. In Section 4 the two-phase B&C scheme is described. In Section 5 are presented the experimental results on the efficiency of the proposed inequalities and compared to CPLEX. In Section 6, concluding remarks and perspectives for further research are drawn.

Complexity

To state the complexity of the (SMKP), we introduce the Unbounded Integer knapsack problem (UIKP), which is a knapsack problem where items can be selected an unlimited number of times. The (UIKP) is NP-hard [START_REF] Zukerman | A polynomially solvable special case of the unbounded knapsack problem[END_REF] and a reduction from this problem is considered.

Theorem 1. The (SMKP) is NP-hard Proof. Let (M , w ′ , v ′ , C) be an instance of the (UIKP) with M items, with w ′ j and v ′ j the weight and the value of item j ≤ M . The aim is to maximize the value of the selected items, each can be selected multiple times, while satisfying the maximum knapsack capacity C.

Let (N , M , w, v, C) be an instance of the (SMKP). The aim is to maximize the value of the selected items, verifying the order constraints within a group, and satisfying the maximum knapsack capacity C.

We set the following relations, without loss of generality, between the weights and the value of each knapsack: w ′ j = j k=1 w j and v ′ j = j k=1 v i,k As such, selecting once item j for (M , w ′ , v ′ , C) is equivalent to selecting elements 1 to j in a single group for (N , M , w, v, C). In the following, we make the reduction in the case N > C/ min(w ′ j ). For a solution of (M , w ′ , v ′ , C) there is a solution of (N , M , w, v, C). 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 (N , M , w, v, C) that is equivalent: for each element j, there are p j unique groups of (M , w ′ , v ′ , C) where only elements 1 to j are selected.

Similarly, for a solution of (N , M , w, v, C) there is a solution of (M , w ′ , v ′ , C). Let p j be the number of groups where only elements 1 to j are selected in a solution of (N , M , 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 (UIKP) is a special case of the (SMKP) where N > C/ min(w ′ j ), and because the (UIKP) is NP-hard, the (SMKP) is NP-hard.

The (SMKP), and the (MKP), are generalizations of the Unbounded Integer Knapsack problem (UIKP). Consequently, the (MKP) is a generalization of both the (BKP) and the (UIKP). The Bounded Integer Knapsack problem (BIKP) [START_REF] Ceria | Cutting planes for integer programs with general integer variables[END_REF] is also a generalization of the (BKP) and the (UIKP). Indeed, the (BKP) is a special case with upper bounds 1 on the number of repetition for each item, and the (UIKP) is a special case with finite upper bound sufficiently large to not be restrictive. However, the (BIKP) and the (SMKP) are not related. In fact, the (BIKP) considers a maximum number of repetitions for each item, while the (SMKP) would be closer to an Integer Knapsack problem with a shared upped bound on the total number of items, repetition included. This shared upper bound is the number of groups N .

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.

The Symmetric Weight Matrix Knapsack polytope

Let x ij be the binary variable such that x ij = 1 if item (i, j) is selected in the solution. We denote V the set of variables x ij for the (SMKP). The total number of variables is n = N × M . A compact incremental formulation of the (SMKP) is the following.

max

N i=1 M j=1 x ij v ij s.c. N i=1 M j=1
x ij w j ≤ C (1)

x ij ≤ x ij-1 ∀x ij ∈ V, j ≥ 2 (2)
x ij ∈ {0, 1} x ij ∈ V
In this formulation, the objective function is to maximize the total value of the selected items. Inequality [START_REF] Bellman | On a routing problem[END_REF] is the capacity constraint, inequalities (2) correspond to the order constraints within each group. We define the polytope P (SM KP ) the convex hull of the feasible solutions of the (SMKP):

P (SM KP ) = conv x ∈ {0, 1} n : x satifies (1) - (2)
Let z ij be the binary variable such that z ij = 1 if and only if items (i, 1) to (i, j) are selected in the solution. We denote W the set of variables z ij for the (SMKP). A compact multiple choice formulation of the (SMKP) is the following.

max N i=1 M j=1 z ij j k=1 v ik s.c. N i=1 M j=1 z ij j k=1 w k ≤ C (3) M j=1 z ij ≤ 1 ∀i ≤ N (4)
z ij ∈ {0, 1} ∀z ij ∈ W
The major difference is inequality (4), corresponding to the disjunctive constraints within each group. Otherwise these formulations are equivalent with respect to the variable change.

Because of the symmetric weights, if a solution is valid, then any symmetric solution with respect to the group indices is also valid. Moreover, the symmetries also appears in the facet-defining inequalities of the (SMKP).

Property 1. If an inequality is facet-defining for the (SMKP), any of its symmetries is also facetdefining for the (SMKP).

Proof. If an inequality is facet-defining for the (SMKP), there are n + 1 affinely independent valid solutions verifying the inequality to equality. As the weights are symmetric with respect to the groups, if a solution is valid, then any permutation of groups yields another valid solution. Hence, one can prove any symmetry of a facet-defining inequality to also be facet-defining, as it suffices to deduce the n + 1 valid solutions following the same permutation of groups. These new n + 1 points are necessarly affinely independent as they all undergo the exact same permutation of groups.

Example 1. Let (4, 3, [3, 4, 2], v, 9) be an instance of the (SMKP). Besides trivial facets and inequalities (2), the convex hull of the incremental formulation for (4, 3, [3, 4, 2], v, 9) contains 5 inequalities:

x 12 + x 22 + x 32 + x 41 ≤ 1 (i1)
x 12 + x 22 + x 31 + x 42 ≤ 1 (i2)

x 12 + x 21 + x 32 + x 42 ≤ 1 (i3) x 11 + x 22 + x 32 + x 42 ≤ 1 (i4) x 11 + 2x 12 + x 21 + 2x 22 + x 31 + 2x 32 + x 41 + 2x 42 ≤ 3 (i5)
Besides trivial facets and inequalities (4), the convex hull of the multiple choice formulation for (4, 3, [3, 4, 2], v, 9) also contains 5 inequalities:

x 12 + x 13 + x 22 + x 23 + x 32 + x 33 + x 41 + x 42 + x 43 ≤ 1 (m1)
+ x 41 + 3x 42 + 3x 43 ≤ 3 (m5)
One can notice that the 4 inequalities with 0-1 coefficients are symmetries of one another with respect to the group indices, for both formulations of the (SMKP). Also, each facet-defining inequality of one formulation has an equivalent for the other formulation, which is consistent with the LP relaxation of both formulations being the same [START_REF] Keely L Croxton | A comparison of mixed-integer programming models for nonconvex piecewise linear cost minimization problems[END_REF].

Based on the convex hull of many small instances, we experimentally distinguished three types of inequalities: the ones from the initial formulation, binary inequalities with 0-1 coefficients, and integer inequalities, with non-negative integer coefficients. In the article, the polyhedral study focuses on the binary inequalities, through a new structure to handle their symmetries.

Related knapsack polytopes

The (SMKP) is a knapsack variant. Indeed, it is a generalization of the (UIKP) [START_REF] Pochet | Integer knapsack and flow covers with divisible coefficients: polyhedra, optimization and separation[END_REF], as shown in Theorem 1. Thus, the facet-defining inequalities of the (UIKP) may not be facet-defining for the (SMKP).

The (SMKP) is neither a generalization, nor a special case of both the (BIKP) and the (BKP). Hence, the facet-defining inequalities of these problems may not be related to those of the (SMKP). However, we introduce some concepts of the (BKP) as they have been extended to variants that are related to the (SMKP).

Let V be a set of items, the (BKP) can be formulated as follows:

max j∈V v j x j j∈V w j x j ≤ C x j ∈ {0, 1} ∀j ∈ V A cover U ⊆ V is a set of items such that j∈U w j > C. A minimal cover U ⊆ V is a cover such that
no subset of U is also a cover, j∈V \{i} w j ≤ C, ∀i ∈ U . The minimal cover inequalities containing facet-defining inequalities of the (BKP), are as follows, with U a minimal cover:

j∈U x j ≤ |U | -1
The minimal cover and related inequalities have been extended to the (PKP), which is a generalization of the (SMKP). The (PKP), defined as follows. Let (V, ⪯) be a partial order set of items. Item j covers item i if there is no k such that j ≺ k ≺ i. A compact formulation of the (PKP) is:

max j∈V v j x j j∈V w j x j ≤ C x j ≤ x i if j covers i x j ∈ {0, 1} ∀j ∈ V A lower-ideal is a set U ⊂ V such that if i ∈ U and i ≺ j, then j ∈ U .
The minimal cover inequalities have been extended to the case of the (PKP) with U a minimal cover as well as a lower-ideal:

j∈U x j ≤ |U | -1
Such inequalities cannot contain the binary facet-defining inequalities of the (SMKP), as most of these inequalities are for variable sets that are not lower-ideals. When referring to the convex hull of incremental formulation of Example 1, inequality (i1) is facet-defining for the (SMKP), for the set of variables {x 12 , x 22 , x 32 , x 41 }. However, this set is not a lower ideal. In fact, it contains the second variable of groups 1 to 3, without containing the first variable of these groups despite the order constraints. The minimal cover inequalities have been enhanced in the literature with various liftings.

In [START_REF] Boyd | Polyhedral results for the precedence-constrained knapsack problem[END_REF] 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 (PKP).

The minimal cover can also be adapted to the (PKP) [12] [11] without the use of lower-ideals. The corresponding inequalities are more likely to be facet-defining inequalities of the (SMKP), which cannot be obtained with lower-ideals as previously mentioned. Let A be the arcs of the precedence graph. The arc set A is modified such that if (i, j) ∈ A and (j, k) ∈ A then (i, k) ∈ A. An induced cover is a set U ⊆ V , such that there is no arc between a pair of items in U and j∈U w j + (k,j)∈A,j∈V w k ≥ C. A minimal induced cover is an induced cover U such that j∈U \{i} w j + (k,j)∈A,j∈V w k ≥ C, ∀i ∈ U . The minimal induced cover inequalities are as follows, with U a minimal induced cover:

j∈U x j ≤ |U | -1
The minimal induced cover inequalities do not contain the facet-defining inequalities of the (SMKP). Indeed, most facet-defining inequalities are for induced covers that are not minimum. When referring to the convex hull of incremental formulation of Example 1, inequality (i1) is facet-defining for the set of variables {x 12 , x 22 , x 32 , x 41 }. However, this set is not a minimal induced cover, as its subset {x 12 , x 41 } is a minimal induced cover.

These minimal induced covers have been enhanced with a lifting [START_REF] Park | Lifting cover inequalities for the precedence-constrained knapsack problem[END_REF]. The procedure described uses items that have at least two successors in the precedence graph. For the (SMKP) instance (4, 3, [3, 4, 2], v, 9), this lifting only considers variables for the last item of each group. As mentioned previously, variable set {x 12 , x 22 , x 32 , x 41 } is not a minimal induced cover and it also excludes all variables for the last item of each group. Consequently, the inequality corresponding to the variable set {x 12 , x 22 , x 32 , x 41 } cannot be obtained through this lifting, and the lifting procedure described cannot produce the facet-defining inequalities of the (SMKP). A sequential lifting procedure has also been developed [START_REF] Robert Lmj Van De Leensel | Lifting valid inequalities for the precedence constrained knapsack problem[END_REF]. Consider U a minimal induced cover, with U p containing all variables i / ∈ U such that (i, j) ∈ A and j ∈ U , and with U r = V \ (U ∪ U p ). The sequential lifting procedure computes the coefficients α j , ∀j ∈ U p and β j , ∀j ∈ U r , leading to a lifted inequality:

j∈U x j j∈Up α j (1 -x j ) + j∈Ur β j x j ≤ |U | -1
Referring to Example 1 with the (SMKP) instance (4, 3, [3, 4, 2], v, 9), the procedure described can produce inequalities (i1) to (i4), but not (i5), meaning it could produce the binary inequality of the (SMKP). However, this is not always the case as shown with Example 2.

Example 2. Let (4, 3, [6, 3, 2], v, 18) be an instance of the (SMKP). The following inequality is facet-defining for the incremental formulation:

x 11 + x 13 + x 22 + x 32 + x 42 ≤ 3 (i6)
The only minimal induced cover with the variables of (i6) are U 1 = {x 11 , x 22 , x 32 }, U 2 = {x 13 , x 22 } or any of their symmetry with respect to the groups 2 to 4. The sequential lifting procedure could produce inequality (i6) from neither U 1 nor U 2 with the lifting process. No variable in inequality (i6) is in U p associated to U 1 , and |U 1 | -1 = 2, the bound 3 cannot be obtained with the sequential lifting procedure. Only one variable in (i6) is in U p associated to U 2 : x 11 . However, as |U 2 | -1 = 1 and x 11 has coefficient 1, the bound 3 cannot be obtained with the sequential lifting procedure. Hence, no variable set can lead to (i6) with the sequential procedure.

The (SMKP) can also be a special case of the (DKP) formulated as follows. Consider a disjunctive graph with vertex set V and edge set E. A compact multiple choice formulation of the (DKP) is:

max j∈V v j x j j∈V w j x j ≤ C x j + x i ≤ 1 if (j, i) ∈ E x j ∈ {0, 1} ∀j ∈ V
As for the precedence graph of the (SMKP), the corresponding disjunctive graph is very special. Indeed, the only edges are between any pair of items in the same group. Consequently, every group of items is a clique, and no item is adjacent to an item in another group. Five families of efficient inequalities have been reported for the (DKP) [START_REF] Ben | Optimization algorithms for the disjunctively constrained knapsack problem[END_REF]: the clique inequalities; the cover inequalities; oddcycle and hypergraph inequalities, the clique-cover inequalities; the clique-cover-partition inequalities. The cover inequality for a set U ⊆ V is close to the one of the (PKP): instead of U being a lower-ideal, U is such that there is no edge between two items of U in the disjunctive graph. Such inequalities cannot contain the binary facet-defining inequalities of the (SMKP), as most of these inequalities are for sets of variables with pairs of variables being neighbors in the disjunctive graph. When referring to the convex hulls of the multiple choice formulation for (SMKP) instance (4, 3, [3, 4, 2], v, 9) (see Example 1), the set of variables {x 12 , x 13 , x 22 , x 23 , x 42 , x 43 , x 41 , x 42 , x 43 } contains multiple items in a same group, hence being neighbors in the disjunctive graph. Yet, this set yields a facet-defining inequality of the (SMKP). Because of this specific disjunctive graphs, the cliques inequalities cannot be adapted to the (SMKP), and similarly for the odd-cycle and hypergraph inequalities. As the cliquecover and clique-cover-partition inequalities rely on the cliques, these inequalities cannot be adapted to the (SMKP) either.

First polyhedral properties

Definition 1 (Full-dimensional condition (fd)). An (SMKP) verifies (fd) if any item (i, j), j < M can be selected without item (i, j + 1) in at least one feasible solution, and any item (i, M ) can be selected in at least one feasible solution.

Let (N , M , w, v, C) be an instance of the (SMKP) where an item (i, j) cannot be selected in any feasible solution, and (i, j -1) can be selected in a feasible solution. Clearly, (N , M , w, v, C) does not verify (fd). Because of the symmetric weights, item j cannot be selected in any group, therefore x ij ′ = 0, ∀i ≤ N , ∀j ′ ≥ j in any integer solution. It is possible to create another instance of the (SMKP) (N, 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 (N, j -1, w, v, C) can be selected. Hence, (N, j -1, w, v, C) verifies (fd).

As any instance of the (SMKP) can be transformed into an instance of the (SMKP) verifying (fd), in the following we will only consider (SMKP) instances verifying (fd) without loss of generality.

Definition 2 (Solution X X ). For a variable set X , solution X X is the solution with for any i ≤ N , x ij = 1 if x ij ′ ∈ X and j ≤ j ′ and x ij = 0 otherwise. We define the special case

X ij if X = {x ij }, and X ∅ if X = ∅.
To ensure that the order constraints are taken into account while considering a solution X X , we introduce the set weights associated to a set of variables X . Definition 3 (Set weights). For a given set of variable X the set weights are

s ij (X ) =    0 if x ij / ∈ X j k=j ′ +1 w k if x ij ∈ X with j ′ = max{j ′ |x t,j ′ ∈ X , j ′ < j} j k=1 w k if x ij ∈ X and x ij ′ / ∈ X , ∀j ′ < j
The coefficient s ij (X ) embed the order constraints. Indeed, if x ij = 1, x ij ∈ X , then all x ij ′ = 1, j ′ ≤ j, even for x ij ′ / ∈ X . Thus, if x ij = 1 then the weights of all variable x ij ′ / ∈ X should be accounted for, which is the purpose of coefficients s ij (X ).

For the sake of simplicity, we define Y as a k-intersection of X if Y contains k elements of X .

Definition 4 (k-intersection). Let X , Y be sets of variables. Variable set Y is a k-intersection of X if |Y ∩ X | = k, ∀x ij ∈ Y if x ij ′ ∈ X with j ′ ≤ j, then x ij ′ ∈ Y and xij ∈Y s ij (Y) ≤ C.
If Y is k-intersection of X , the reverse can also be true. Consequently, a k-intersection is not necessarily a subset.

Example 3. Let (3, 3, [1, 3, 2], v, 12) be an instance of the (SMKP). Let two variable sets X = {x 11 , x 13 , x 22 , x 31 } and Y = {x 11 , x 13 , x 21 , x 22 }. In this case, Y is a 3-intersection of X . Indeed, |X ∩ Y| = 3, s 11 (X ) + s 13 (X ) + s 22 (X ) + s 31 (X ) = 1 + 5 + 4 + 1 = 11 ≤ C = 12, and x 12 / ∈ X . However, X is not a 3-intersection of Y. Indeed, |X ∩ Y| = 3 and s 11 (Y) + s 13 (Y) + s 21 (Y) + s 22 (Y) = 1 + 5 + 1 + 3 = 10 ≤ C = 12, but there is x 21 ∈ Y and x 21 / ∈ X even if x 22 ∈ X .

Theorem 2. P (SM KP ) is full dimensional.

Proof. As there are N items and M groups, solutions X ij and X ∅ yield a total of N × M + 1 = n + 1 different solutions, which are feasible, otherwise (fd) is not verified. For any i, solution X iM is the only solution with x iM = 1, thus being affinely independent to other solutions. For any i, solution X ij , j < M is the only solution with x ij = 1 and x ij+1 = 0, this being affinely independent to other solutions. Clearly, X ∅ is affinely independent to other solutions, which means that there are n + 1 affinely independent solutions.

With the dimensionality of P (SM KP ) it becomes possible to characterize when order inequalities and trivial inequalities with bounds at 0 are facet-defining. Property 2. Inequalities x iM ≥ 0 and x ij ≤ x ij-1 are facet-defining for P (SM KP ) .

Proof. As there are N items and M groups, solutions X ij and X ∅ yield a total of N × M + 1 = n + 1 different solutions, which are feasible otherwise (fd) is not verified.

For a given i, besides solution X iM , every of the other n solutions verify x iM ≥ 0 to equality, and are proven affinely independent. Inequalities x iM ≥ 0 are then facet-defining for P (SM KP ) .

Similarly, besides X ij-1 , each of the n solutions verifies x ij ≤ x ij-1 to equality, and is proven to be affinely independent. Inequalities x ij ≤ x ij-1 are then facet-defining for P (SM KP ) .

Contrary to trivial inequalities with bound at 0 and the order constraints which always contain facet-defining inequalities, the bounds 1 require a minimum capacity C to contain facet-defining inequalities.

Property 3. Inequalities x i1 ≤ 1 are facet-defining for P (SM KP ) if C ≥ M j=1 w j + w 1 .
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 ′ ̸ = i.
As there are N items and M groups, solutions X ′ ij yields a total of N × M = n different solutions, which are feasible if C ≥ M j=1 w j + w 1 and (fd) are verified. Each of the n solutions verifies x i ′ 1 ≤ 1 to equality, and is proven to be affinely independent in the same manner as solutions X ij . Inequalities x i ′ 1 ≤ 1 are then facet-defining for

P (SM KP ) if C ≥ M j=1 w j + w 1 .
In the case where C < M j=1 w j + w 1 , clearly x iM + x i ′ 1 ≤ 1 is valid, for any i ≤ N , i ′ ≤ N and i ̸ = i ′ because of the symmetric weights. In which case inequality x iM ≤ 1 is dominated and cannot be facet-defining in this case.

Hence, inequalities x iM ≤ 1 are facet-defining if and only if C ≥ M j=1 w j + w 1 .

Patterns inequalities

In this section we introduce new inequalities. We are interested in the faces defined by these inequalities, i.e., the set of points of the polytope P (SM KP ) verifying these inequalities to equality. To handle the symmetries of the inequalities without the need to explicitly define all of them, we introduce a new structure called pattern.

Definitions

Definition 5 (Pattern). A pattern P is a collection of N sets S i (P) ⊆ {1, ..., M }, i ≤ N .

A set S i (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 an item set of the (SMKP).

As the aim is to produce inequalities from the patterns, we define the variable sets associated to a pattern. Definition 6 (Variable set X associated to P). A variable set X ⊆ V is associated to pattern P and a permutation π of {1, ..., N } if:

x ij ∈ X ⇔ j ∈ S π(i) (P).
We denote χ (P) the set of all variable sets associated to P. Note that | χ (P)| is in general exponential.

The cardinality of a pattern P is the cardinality of any variable set associated to P.

Definition 7 (card(P)). The cardinality of a pattern P is card(P) = |X | with X ∈ χ (P).

The rank of a pattern P is the valid upper bound for the sum of variables in any variable set associated to P. Definition 8 (rank(P)). The rank of a pattern P is

rank(P) = max X ∈ χ (P) max xij ∈X x ij : satisfying (2) - (4)
The rank of a pattern can be computed with a shortest path algorithm [START_REF] Bellman | On a routing problem[END_REF] as described is Section 4.

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

Definition 9 (Pattern inequalities). The pattern inequalities associated to a pattern P are the following, for any X ∈ χ (P):

xij ∈X x ij ≤ rank(P) (pi(X ))
By definition of the rank, and because the weights are symmetric, the pattern inequalities are valid. As for any set of variables there is a pattern, and vice-versa, these pattern inequalities cover all the binary inequalities of the (SMKP). Also, because | χ (P)| can be exponential, each pattern is associated up to an exponential number of pattern inequalities. As the number of patterns of an (SMKP) is also exponential, we need to define the conditions for a pattern to lead to tight pattern inequalities.

Definition 10 (Pattern-facet). A pattern P is a pattern-facet if ∀X ∈ χ (P), (pi(X )) is facet-defining.

Necessary facet defining conditions

In this section we define three necessary conditions for a pattern to be pattern-facet. The first one is for a pattern to have at least one item in each if its sets. Property 4 (Condition (i): no empty group). If a pattern P is pattern-facet, then P verifies condition (i):

∀S i (P) ∈ P:

|S i (P)| ≥ 1 (i)
Proof. Let P be a pattern of rank k. Let X ∈ χ (P) with permutation π id . Suppose S i (P) does not verify (i) for a given i, i.e., S i

(P) = ∅. Let X ′ = X ∪ {x iM }. Because x iM is the only variable of X ′ for group i, s iM (X ′ ) ≥ s i ′ j ′ (X ′ ), ∀x i ′ j ′ ∈ X ′ .
Then, the following inequality is valid:

x i ′ j ′ ∈X x i ′ j ′ + x iM ≤ k
Indeed, when x iM = 0, this inequality is valid by the rank of P. When x iM = 1, there cannot be k variables of X to 1. Otherwise as s iM (X ′ ) ≥ s i ′ j ′ (X ′ ), ∀x i ′ j ′ ∈ X ′ , one could set x iM to 0, and any other variable of X ′ to 1. This would reduce the total weight, leading to another solution. Such solution would have k + 1 variables of X to 1, which contradicts the rank of P. Therefore this inequality is valid. This inequality dominates (pi(X )). Indeed, one could sum it with -x iM ≤ 0 to obtain (pi(X )). Thus a pattern P is pattern-facet only if P verifies condition (i).

The idea of the following condition is that for any X ∈ χ (P), there is a feasible solution with (pi(X )) to equality, and x iM = 1 for any group i.

Property 5 (Condition (ii): selection of item M ). Let k be the rank of P and X ∈ χ (P). If a pattern P is pattern-facet, then P verifies condition (ii) :

∀i ≤ N , ∃Y ⊆ V a k-intersection of X with x iM ∈ Y.
Proof. Let P be a pattern of rank k, and X ∈ χ (P). Suppose there is an i ≤ N such that (ii) is not verified for i. This means that there is no feasible solution with k variables of X to 1, with x iM = 1. Therefore, the following inequality is valid:

x i ′ j ′ ∈X x i ′ j ′ + x iM ≤ k
Indeed, when x iM = 0, the inequality is valid by the rank of P. When x iM = 1, the inequality is valid as there cannot be more than k -1 variables of X to 1, which sums to a total of at most k. This inequality dominates the inequality (pi(X )). Indeed, one could sum it with -x iM ≤ 0 to obtain (pi(X )).

Thus, a pattern P is pattern-facet only if P verifies condition (ii).

The following condition is quite similar to condition (ii), but for any variable x ij-1 with x ij ∈ X , instead of any variable x iM .

Property 6 (Condition (iii): independence of an item from its predecessor). Let k be the rank of P and X ∈ χ (P). If a pattern P is pattern-facet, then P verifies condition (iii) :

∀x ij ∈ X , ∃Y ⊆ V a k-intersection of X with x ij-1 ∈ Y and x ij ′ / ∈ Y ∀j ′ ≥ j.
Proof. Let P be a pattern of rank k. Let X ∈ χ (P). Suppose for some (i, j), x ij ∈ X does not verify condition (iii). This means that there is no feasible solutions with a total of k variables of X to 1, with x ij-1 = 1 and x ij = 0. Therefore, the following inequality is valid:

x i ′ j ′ ∈X x i ′ j ′ + x ij-1 -x ij ≤ k Indeed, when x ij = x ij-1 = 1 or x ij = x ij-1 = 0,
this inequality is valid by the rank of P. When x ij-1 = 1 and x ij = 0, the inequality is valid as there cannot be more than k -1 variables of X to 1, which sums to at most k. This inequality dominates the inequality (pi(X )). Indeed, one could sum it with

-x ij-1 + x ij ≤ 0 (equivalent to x ij ≤ x ij-1 ) to obtain (pi(X )).
Thus a pattern P is pattern-facet only if P verifies condition (iii).

For a given pattern P, conditions (i) can clearly be verified in linear time. Also, conditions (ii) and (iii) can be verified in polynomial time. More precisely, it requires to solve the shortest path algorithm described in Section 4 at most once for each variable. As these conditions are necessary, we define a flexible pattern, which verifies all of these three conditions.

Definition 11 (Flexible pattern). A pattern P is a flexible pattern if it verifies conditions (i), (ii) and (iii).

The conditions on a flexible pattern P are not sufficient for P to be pattern-facet. However, a minimum dimension can be guaranteed for the flexible patterns inequalities.

Lower bound on the dimension of the flexible patterns inequalities

In this section, we consider a flexible pattern P and variable set X ∈ χ (P). The idea of the following property is that for any x ij there is a valid solution with x ij = 1, x ij+1 = 0 and (pi(X )) to equality. In a sense it is a generalization of condition (ii) defined only for variables x iM and condition (iii) defined only for variables x ij such that x ij+1 ∈ X .

Property 7 (Generalization of (ii) and (iii) for any item of the (SMKP)). Let P be a flexible pattern and X ∈ χ (P). For any item

(i, j), ∃Y ⊆ V a k-intersection of X with x ij ∈ Y and x ij ′ / ∈ Y, ∀j ′ > j.
The complete proof is in A.1, as it merely extends the proofs for conditions (ii) and (iii). Conditions (i), (ii) and (iii) are necessary for a pattern P to be pattern-facet. Moreover, with X ∈ χ (P), the following theorem provides a lower bound on the number of linearly independent points verifying inequalities (pi(X )) to equality when these three conditions are verified.

Theorem 3 (n -card(P) linearly independent points). Let P be a flexible pattern. Let n be the number of variables of the (SMKP). There are at least n -card(P) linearly independent points that verify the inequalities of P to equality.

Proof. Let P be a pattern of rank k, and X a variable set of P. Property 7 stipulates that if P is a flexible pattern, then for any item (i, j) there is a set

Y ij ∈ V a k-intersection of X ; x ij ∈ Y ij ; x ij ′ / ∈ Y ij , ∀j ′ > j and X Yij is feasible. Consider X Yij ∀x ij / ∈ X . Because card(P) = |X |
, there are n -card(P) solutions. We can prove that X Yij is the only solution with x ij = 1 and x ij+1 = 0. Let two distinct variables x ij / ∈ X and x i ′ j ′ / ∈ X . We assumed without loss of generality in Property

7 that Y i ′ j ′ \ {x i ′ j ′ } ⊆ X . As x ij / ∈ X , there would be a contradiction if X Y i ′ j ′ had x ij = 1 and x ij+1 = 0.
Solutions X Yij ∀x ij / ∈ X are linearly independent, and proven to be valid in Property 7. As Y ij is a k-intersection of X , all these solutions also verify (pi(X )) to equality. Hence, for a flexible pattern P, there are n -card(P) linearly independent points verifying (pi(X )) to equality, ∀X ∈ P.

Theorem 3 provides a lower bound on the dimensions of the faces defined by flexible pattern inequalities. Recall that for a pattern to be a flexible pattern it solely requires to verify conditions (i), (ii) and (iii). It is shown in Section 4 that verifying if these three conditions hold for a given pattern can be done in polynomial time, and Theorem 3 is used in the experimental results in Section 5.

The following section provides properties complementary to Theorem 3.

Properties of the lower sub-patterns

In this section, we consider a flexible pattern P of rank k and variable set X ∈ χ (P). We extend the definition of a sub-set and a super-set to patterns.

Definition 12 (Sub-pattern). A pattern

P ′ is sub-pattern of P if ∃π a permutation such that S π(i) (P ′ ) ⊆ S i (P), ∀i ≤ N .
If P is sub-pattern of P ′ , then P ′ is super-pattern of P. We present a new set of sub-patterns for P. In the following, properties are presented to show that these new patterns have large sub-patterns in common, inducing similarities. These similarities will be convenient to provide linearly independent points in the polytope P (SM KP ) .

Definition 13 (Lower sub-patterns Q i ). For a given i, the lower sub-pattern

Q i of P is such that S i (Q i ) = S i (P), card(Q i ) = k, minimizing the sum of the set weights s(Y) with Y ∈ χ (Q i ).
Let Q i be a lower sub-pattern of P and Y ∈ χ (Q i ) for the permutation π as X . By construction, if x ij ∈ Y, then ∀x ij ′ ∈ X with j ′ ≤ j, x ij ′ ∈ Y, hence the name lower sub-patterns. Also, patterns Q i can be obtained via a shortest path algorithm defined in Section 4.

Lemma 1. Y is a k-intersection of X .
Proof. Let X ∈ χ (P) and Y ∈ χ (Q i ) with the permutation π id . For the sake of simplicity we consider permutation π id but the proof can be done for any permutation π.

As P verifies condition (ii), there exists a variable set that is a k-intersection of X containing x iM . By definition Q i minimizes the sum of its set weights and all variables of group i in X are in Y. Hence, if condition (ii) for variable x iM cannot be verified with Y, there is a contradiction as Q i cannot minimize the sum of its set weights.

Remark 1. Let X ∈ χ (P) and Y ∈ χ (Q i ) with permutation π id . As Y ∪ {x iM } is a k-intersection of X , then Y is also a k-intersection of X . Indeed, if x iM ∈ X then x iM ∈ Y by definition of Q i .
For the next properties, we consider for the sake of simplicity that the sets of P are ordered such that |S i (P)| ≤ |S i+1 (P)|. Therefore, S 1 (P) is the smallest set of P, and Q 1 is the lower sub-pattern of P associated to S 1 (P). We define U = |S N (P)| and V = |S 1 (P)|. Also, we define S i (P)(u) the u th lowest index of S i (P) and S i (P)[u] the u th highest index of S i (P). The following property provides a lower bound on the size of each set of sub-pattern Q 1 of P.

Property 8 (Minimum size on the sets of

Q 1 ). Lower sub-pattern Q 1 is such that ∀i ≤ N , S i (Q 1 ) contains the |S i (P)| -V smallest indices of S i (P).
Remark 2. It is equivalent to say that S i (Q 1 ) contains the |S i (P)| -V smallest indices of S i (P) and S i (P)[V + 1] ∈ S i (Q 1 ). In the following, the latter notation will be used.

1 = {S 1 (Q 1 ) = {3}, S 2 (Q 1 ) = {2}, S 3 (Q 1 ) = {1, 2}, S 4 (Q 1 ) = {1}}. In this case, S 4 (P)[V + 1] = 2 / ∈ S 4 (Q 1 )
, hence Q 1 does not verify Property 8. We show in the following that it leads to a contradiction with the rank of P.

Let X = {x 13 , x 22 , x 24 , x 31 , x 32 , x 41 , x 42 , x 43 } ∈ χ (P) and Y = {x 13 , x 22 , x 31 , x 32 , x 41 } ∈ χ (Q 1 ) as illustrated in Figure 3a and 3b. Let Y ′ = Y ∪ {x 14 } as illustrated in Figure 3c. From Lemma 1 solution X Y ′ is valid. One can create a set Y ′′ = Y ′ \ {x 13 , x 14 } ∪ {x 42 , x 43 } as illustrated in Figure 3d. 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 ∈ 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 ≤ w 1 + w 2 + w 3 + w 4 , hence X Y ′′ is valid. However Y ′′ is a k + 1-intersection of X . Indeed, since Q 1 does not verify Property 8, only V = 1 variable of Y ′ \ Y ′′ is in X , namely x 13 and V + 1 = 2 variables of Y ′′ \ Y ′ are
in X , namely x 42 and x 43 . As X Y ′′ is valid, there is a contradiction with the rank of P.

(a) Set X (b) Set Y (c) Set Y ′ (d) Set Y ′′
Let i ∈ {2, ..., N }. ∀u ∈ [1, V ], if |S i (P)| ≥ u+V then S 1 (P)[u] ≥ S i (P)[u + V ].
Proof. The proof is divided in two possibles cases, each being supported by a lemma. In the case S i (Q 1 ) ⊆ S i (P) with S i (P)[u] ∈ S i (Q 1 ), the proof is provided by Lemma 2. In the case S i (Q 1 ) ⊂ S i (P) with S i (P)[u] / ∈ S i (Q 1 ), the proof is provided by Lemma 3. Hence, the property is always verified. The two lemmas are in A.3.

The idea of Property 10 is to give a minimum size on the sets of any lower sub-pattern Q i based on the results of Property 9. Note that, it is not a generalization of Property 8. Indeed, Property 8 addresses only Q 1 and not any Q i , but the minimum size provided is larger than the one in Property 10.

Property 10 (Minimum size of the sets of any Q i ). For every i ≤ N , the sub-pattern

Q i of P is such that ∀i ′ ≤ N if |S i ′ (P)| ≥ 2V , S i ′ (P)[2V ] ∈ S i ′ (Q i )
Proof. The proof is divided in three possible cases, each being supported by a lemma. In the case

|S 1 (Q 1 )|+|S i (Q 1 )| = |S 1 (Q i )|+|S i (Q i )|, the proof is provided by Lemma 4. In the case |S 1 (Q i )| = 0, the proof is provided by Lemma 5. In the case |S 1 (Q i )| > 0, the proof is provided by Lemma 6.
Hence, the property is always verified. The three lemmas are in A.4

The previous conditions are valid for any pattern. However, in the special case where pattern P is with |S 1 (P)| = 1, Property 10 indicates that S i ′ (P) [START_REF] Boyd | Polyhedral results for the precedence-constrained knapsack problem[END_REF] Let the lower sub-pattern

∈ S i ′ (Q i ′ ), ∀i ′ ≤ N , ∀i ≤ N . 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 ′ (P).
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 8, as V = 1 and there is at most V = 1 missing index per set compared to P.

Let the lower sub-pattern

Q 2 = {S 1 (Q 2 ) = ∅, 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 10, as V = 1 and there are at most 2V -1 = 1 missing index per set compared to P. This restricted shape on the lower sub-pattern is used in the following section to prove necessary and sufficient conditions for patterns containing a set of cardinality 1.

Necessary and sufficient conditions for patterns with a set a cardinality 1

In this section, we focus on patterns with at least one set of cardinality 1, hence we define for this section P a flexible pattern of rank k and with V = 1. It is proven with Property 10 that for such pattern 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 weights can exist. From now on we only consider for each i ≤ N the unique Q i verifying the following tie-break rule: Definition 14 (Tie-break rule). For any two indices i ′ < i ′′ different than i, if

S i ′ (P)[1] j=S i ′ (P)[2]+1 w j = S i ′′ (P)[1] j=S i ′′ (P)[2]+1 w j then S i ′′ (P)[1] ∈ S i ′′ (Q i ) only if S i ′ (P)[1] ∈ S i ′ (Q i ).
From Property 10, at most one index is missing in a set of Q i compared to P. Hence, with such rule there can only be one Q i for a given i.

Example 7. Let (4, 4, [2, 1, 1, 1], v, C) be an instance of the (SMKP). Let a flexible pattern P = {S 1 (P) = {3}, S 2 (P) = {1, 3}, S 3 (P) = {2, 4}, S 4 (P) = {2, 4}} 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 ∈ S 4 (Q 1 ) only if 4 ∈ S 3 (Q 1 ) and 3 ∈ S 2 (Q 1 ). Also, the rule stipulates that 4 ∈ S 3 (Q 1 ) only if 3 ∈ S 2 (Q 1 ). Only the first option for Q 1 verifies the rule, and consequently is the only one considered.

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 15 (Common sub-pattern C of all Q i ). The pattern C is the largest cardinality pattern that is sub-pattern to all the lower sub-patterns Q i of a pattern

Property 11 (Cardinality of C). The cardinality of C is card(C) = k -1.
An example of Property 11 is provided in Example 8.

Proof. As P is a flexible pattern, Property 10 holds, hence ∀i, ∀i ′ , S i ′ (P) [START_REF] Boyd | Polyhedral results for the precedence-constrained knapsack problem[END_REF] ∈ S i ′ (Q i ). In other words, there is at most one element of

S i ′ (P) not in S i ′ (Q i ). Let k ′ = k -(card(P) -N ). Let L be the set of the k ′ indices i ′ such that S i ′ (Q i ) = S i ′ (P). By definition of Q i , i ∈ L. Because S i ′ (P)[2] ∈ S i ′ (Q i ), ∀i ′ , the k ′ -1 sets i ′ ̸ = i such that S i ′ (Q i ) = S i ′ (P)
are the ones minimizing:

S i ′ (P)[1] j=S i ′ (P)[2]+1 w j
Consequently, L contains the k ′ -1 indices minimizing this sum. Indeed, either i is in these k ′ -1 indices, hence L contains the k ′ indices minimizing this sum, or i is not in these k ′ -1 indices, but by construction L contains these k ′ -1 indices.

As such, all patterns Q i are all super-pattern of common pattern C, with card(C) = (card(P) -

N ) + k ′ -1 = k -1 . Example 8. Let (3, 4, [2, 1, 3, 2], v, C
) be an instance of the (SMKP). Let a flexible pattern P = {S 1 (P) = {3}, S 2 (P) = {1, 2}, S 3 (P) = {1, 3}, S 4 (P) = {1, 3, 4}} of rank 6. First we identify the lower sub-pattern

Q 1 . By definition, S 1 (Q 1 ) = S 1 (P) = {3}. From Property 10, as V = 1, ∀i ≤ 4, S i (P)[2] ∈ S i (Q 1 ) . In this case, 1 ∈ S 2 (Q 1 ), 1 ∈ S 3 (Q 1 ) and 1, 3 ∈ S 4 (Q 1 )
. By definition, 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 Y ∈ χ (Q 1 ), then clearly 2 ∈ 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:

Q 2 = {S 1 (Q 2 ) = ∅, S 2 (Q 2 ) = {1, 2}, S 3 (Q 2 ) = {1}, S 4 (Q 2 ) = {1, 3, 4}} Q 3 = {S 1 (Q 3 ) = ∅, S 2 (Q 3 ) = {1, 2}, S 3 (Q 3 ) = {1, 3}, S 4 (Q 3 ) = {1, 3}} Q 4 = {S 1 (Q 4 ) = ∅, S 2 (Q 4 ) = {1, 2}, S 3 (Q 4 ) = {1}, S 4 (Q 4 ) = {1, 3, 4}} There is C = {{S 1 (C) = ∅, S 2 (C) = {1, 2}, S 3 (C) = {1}, S 4 (C) = {1, 3}}
of cardinality 5 that is sub-pattern to all the aforementioned lower sub-patterns Q i . Note that only S 2 (C) = S 2 (P), which is because s 22 (X ) < s 44 (X ) < s 33 (X ) < s 13 (X ) and by definition the lower sub-patterns Q i minimize the set weights of Y ∈ χ (Q i ).

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

Definition 16 (Generalized lower sub-patterns Q i (u)). For a given i ≤ N and u ∈ {0, ..., |S i (P)|}, the generalized lower sub-pattern Q i (u) of P is such that card(Q i (u)) = k and S i (Q i (u)) contains the u smallest indices of S i (P), minimizing the sum of set weights s(Y) with Y ∈ χ (Q i (u)).

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

Property 12 (Common elements between C and Q i (u)). For each i ≤ N and u ∈ {0, ..., [START_REF] Boyd | Polyhedral results for the precedence-constrained knapsack problem[END_REF] ∈ S i ′ (C), and both C and Q i (u) are sub-patterns of P, then there are K sets where

|S i (P)| -1}, lower sub-pattern Q i (u) is such that ∀i ′ ̸ = i, S i ′ (C) ⊆ S i ′ (Q i (u)). Proof. By definition card(Q i (u)) = k and |S i (Q i (u))| = u. From Property 11 card(C) = k -1, and from Property 10 ∀i ′ ≤ N with |S i ′ (P)| ≥ 2, S i ′ (P)[2] ∈ S i ′ (C). Let K be the difference between card(Q i (u) \ S i (Q i )(u)) and card(C \ S i (C)), i.e., K = card(Q i (u) \ S i (Q i )(u)) -card(C \ S i (C)) = (k -u) -(k -1 -|S i (C)|) = 1 + |S i (C)| -u Note that u ≤ |S i (C)|, meaning that K ≥ 1. Because ∀i ′ ≤ N , S i ′ (P)
|S i ′ (Q i (u))| = |S i ′ (C)| + 1 = |S i ′ (P)|.
Let i ′ be one of these K sets. By definition, card(

Q i ′ ) = k and card(C) = k -1, meaning that card(Q i ′ \ S i ′ (Q i ′ )) = card(C \ S i ′ (C)). By definition C is sub-pattern of Q i ′ , hence Q i ′ \ S i ′ (Q i ′ ) = C \ S i ′ (C). Consequently, S i (Q i ′ ) = S i (C)
and we deduce:

card(Q i (u) \ S i (Q i )(u)) -card(Q i ′ \ S i (Q i ′ )) =(k -u) -card(Q i ′ ) -|S i (Q i ′ )| =(k -u) -k -|S i (C)| = K -1
From Property 10 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.
Consequently, for set i and the K -1 sets where Q i (u) contains one more element than Q i ′ , patterns Q i (u) and Q i ′ have the same number of elements. As both patterns are of cardinality k, then for the sets complementary to i and the K -1 sets where Q i (u) contains one more element than Q i ′ , patterns Q i (u) and Q i ′ have the same number of elements. As both lower sub-patterns minimize their set weights, they are equal for these complementary sets.

Hence, for all sets besides i,

Q i (u) contains all elements of Q i ′ , which itself contains all elements of C. Thus ∀i ′ ̸ = i, S i ′ (C) ⊆ S i ′ (Q i (u)).
With all lower sub-patterns Q i (u) defined, the following theorem shows that a flexible pattern with a set of cardinality 1 is pattern-facet.

Theorem 4. P is pattern-facet if and only if P is flexible pattern.

Proof. Recall that without loss of generality, pattern sets can be ordered such that |S i (P)| ≤ |S i+1 (P)|, meaning |S 1 (P)| = 1. Let X ∈ χ (P) with permutation π id . Consider the following lower sub-patterns:

Q 1 , Q i ∀i ≤ N such that S i (P)[1] / ∈ S i (Q 1 ); Q i ′ (u) ∀i ′ ≤ N , ∀u ∈ {0, .., |S i ′ (C)|-1}.
For all mentioned sub-patterns, we consider their respective variable set with permutation π id denoted X 1 ; X i ; X i ′ (u) and their respective solution X X1 ; X Xi ; X X i ′ (u) . This results in a total of card(P) solutions. There is one solution X X1 . As P is of rank k, there are card(P) -k solutions X Xi . As card(C) = k -1, there are k -1 solutions X X i ′ (u) .

By definition of lower sub-patterns Q i and Q i (u) and from Property 7, all mentioned variable sets are k-intersections of X . Hence, all mentioned solutions are feasible and verify (pi(X )) to equality.

Consider now the points associated to the afore-enumerated solutions. We can prove these points to be linearly independent. Start by considering first the point associated to X X1 . As it is the only point considered, it is necessarily linearly independent. From Property 11, C is sub-pattern to all Q i and of cardinality k -1. Consequently, Q i with S i (P) [START_REF] Bellman | On a routing problem[END_REF] / ∈ S i (Q 1 ) is the only lower sub-pattern, excluding the generalized lower sub-patterns, with S i (P) [START_REF] Bellman | On a routing problem[END_REF]

∈ S i (Q i ).
It results that for each solution X Xi , the associated point is the only one with x iSi(P) [START_REF] Bellman | On a routing problem[END_REF] = 1, thus they are linearly independent. For each solution X X i ′ (u) , starting with large u, the associated point is the first one with x i ′ S i ′ (P)[u] = 0, thus being linearly independent.

The enumerated solutions yield card(P) linearly independent points. Moreover, from Theorem 3, ∀x ij / ∈ X , there is a feasible solution with x ij = 1 and x ij+1 = 0 that verifies (pi(X )) to equality. Sequentially adding these points associated to their corresponding solutions to our pool of card(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 / ∈ X . As there are n -card(P) of these new points, there is a total of n linearly independent points.

Thus, a pattern P with a set of cardinality 1 is pattern-facet if and only if it is flexible pattern.

Recall that for a pattern to be flexible pattern it solely requires to verify conditions (i), (ii) and (iii). Hence, a pattern with a set of cardinality 1 is pattern-facet if conditions (i), (ii) and (iii) hold. It is shown in Section 4 that verifying if these three conditions hold for a given pattern can be done in polynomial time. As for Theorem 3, the result of Theorem 4 is used for the experimental results in Section 5, guaranteeing a flexible pattern to be pattern-facet if min i≤N |S i (P)| = 1, or a lower bound on the dimensions of the faces defined by the pattern inequalities of P otherwise.

Conditions for any pattern

For a pattern P such that min i≤N |S i (P)| ≥ 2, the conditions (i), (ii) and (iii) are necessary but not sufficient for P to be pattern-facet. This is because the lower sub-patterns Q i of P lose many of their structural properties in the general case. In the following, we present three new conditions, that will complement the aforementioned conditions. For this purpose, we present new patterns R u that will take the role of the lower sub-patterns Q i . The idea is to help constructing points with a common coefficients, which is convenient to provide independent points.

In the following, we consider P a flexible pattern of rank k.

Definition 17

(Nested sub-patterns R u ). Pattern{R u , 1 ≤ u ≤ U ′ } are nested sub-patterns of P if ∀u, card(R u ) = k -u, R u is a lower sub-pattern of P and R u sub-pattern of R u-1 .
For the following, we define U ′ = min u≤k {max i≤N {S i (P) -S i (R u )} ≥ u}. We consider the following subset of nested sub-patterns {R u , 1 ≤ u ≤ U ′ }. We also consider X ∈ χ (P) and Y u ∈ χ (R u ), ∀u ≤ U ′ with permutation π id .

In the following we define three new conditions. Condition (iv) indicates that there are kintersections of X with Y u and u variables in a same group. Condition (v) is similar, but with u variables in at least two different groups. Condition (vi) is a more constrained version of condition (iii), but only for variables in Y U ′ .

Definition 18 (Condition (iv): selection of items in the same group). For any u ≤ U ′ and i ≤ N such that |S i (P) -S i (R u )| ≥ u, there is a variables set Z containing the u variables with the smallest indices of group i in X \ Y u . The variable set Z ∪ Y u is a k-intersection of X .

Definition 19 (Condition (v): selection of items in different group). For any u ∈ {2, ..., U ′ }, ∃Z u ⊂ X of cardinality u such that Z u ∩ Y 1 = ∅, Z u contains variables in at least two different groups and the variable set

Y u ∪ Z u is a k-intersection of X .
Definition 20 (Condition (vi): constrained independence of an item from its predecessor). For any

x ij ∈ Y U ′ , ∃Z ⊆ V a k-intersection of X such that ∀x i ′ j ′ ∈ Y U ′ , if i ′ = i and j ′ ≥ j, then x i ′ j ′ / ∈ Z, otherwise x i ′ j ′ ∈ Z.
Note that contrary to conditions (i), (ii) and (iii), conditions (iv), (v) and (vi) do not apply on P but, instead, on the nested sub-patterns. In this example, the lower sub-pattern R 1 is the unique one of cardinality 3 minimizing the set weights of Y 1 . However, R 2 is not the one of cardinality 2 minimizing the set weights of Y 2 . In fact,

R 1 = {S 1 (R 1 ) = {1}, S 2 (R 1 ) = {2, 3}, S 3 (R 1 ) = ∅, S 3 (R 1 ) = ∅} and R 2 = {S 1 (R 2 ) = {1}, S 2 (R 2 ) = {2}, S 3 (R 2 ) = ∅, S 3 (R 2 ) = ∅}. Let X =
R ′ 2 = {S 1 (R ′ 2 ) = {1, 2}, S 2 (R ′ 2 ) = ∅, S 3 (R ′ 2 ) = ∅, S 3 (R ′ 2 )
= ∅} is of cardinality 2 and minimizes the set weights of Y ′ 2 ∈ χ (R ′ 2 ). Because R ′ 2 is not sub-pattern to R 1 , they cannot be nested sub-patterns. For a set of nested sub-patterns R u , conditions (iv) can be verified in polynomial time. Indeed, the k-intersection are explicitly defined, it only requires to compute the sum of its set weights. Also, verifying conditions (v) and (vi) requires to find a k-intersection, as for conditions (ii) and (iii). Hence, it can be verified in polynomial time, in a similar fashion as for conditions (ii) and (iii), using a variant of the shortest path algorithm. However, conditions (iv), (v) and (vi) apply on a set of nested sub-patterns, instead of on a single pattern P. As shown in Example 9, the lower sub-patterns of P minimizing the sum of the set weights of their respective variable sets may not be nested. Consequently, the difficulty is that one may need to enumerate all lower sub-patterns of P to find a set of nested sub-patterns verifying conditions (iv), (v) and (vi).

The following theorem shows that conditions (i) to (vi) are sufficient to prove any pattern to be pattern-facet.

Theorem 5 (Sufficient conditions for any pattern-facet). If nested sub-patterns {R u , 1 ≤ u ≤ U ′ } of P verify conditions (iv), (v) and (vi), then P is pattern-facet.

The complete proof is in Appendix A.5, relying on Lemma 7 defined in the same appendix. Even though conditions (iv) (v) and (vi) can provide pattern-facets, we will only be using flexible patterns for the experimental results. The rationale behind is that as shown in Example: 9, one may need to enumerate all sub-patterns of P to find nested patterns verifying conditions (iv), (v) and (vi). Another reason is that from Theorems 3 and 4, a flexible pattern P is pattern-facet if it has a set of cardinality one. Otherwise it has a lower bound on the dimensions of the faces defined by the pattern inequalities of P. As shown in Section 5, using flexible pattern, with or without the cuts of CPLEX, within a Branch and Cut framework can drastically reduce the number of nodes explored and the computational time required to solve instances of the (SMKP). Furthermore, experimental results in Section 5 show that for some instances, a few flexible patterns are generated. Consequently, adding conditions (iv) (v) and (vi) would further reduce the number of patterns generated, making it more difficult to measure their impact.

Algorithms

In this section, we define the two-phase B&C scheme. The first phase of this scheme generates flexible patterns as a pre-processing. The second phase separates the associated pattern inequalities within a B&C framework. The flexible-pattern generating algorithm is described in Section 4.2, based on two algorithms defined in Section 4.1. The separation algorithm is described in Section 4.3, producing the most violated inequality for a given pattern in polynomial time. The two-phase B&C scheme is described in Section 4.4

Graph model associated to variable sets

The shortest path problem and many of its variants are known to be easy to solve [START_REF] Bellman | On a routing problem[END_REF] [START_REF] Edsger | A note on two problems in connexion with graphs[END_REF]. In the case of the (SMKP), for a given pattern P, it is possible to define a graph associated to X ∈ χ (P), for which solving a variant of the shortest path problem gives the rank of P. This graph will be used to compute the rank of a pattern and to verify conditions (ii) and (iii). Such graph could also be used to compute the sub-patterns Q i or to verify conditions (v) and (vi).

Consider a pattern P and a variable set X ∈ χ (P). Let G = (W, A) be the graph defined as follows. The variable set X is associated to the vertex set W , a source vertex p and a sink vertex q are added to W . For convenience purposes, each vertex in W is denoted by the corresponding variable in X and the vertices associated to x ij ∈ X are renumbered with the same order in a compact sequence in X . More precisely consider the following renumbering, denoted by parentheses on the indices: For any x ij ∈ X , we consider x (i)(j) = x ij with (i) = i and (j) the number of variables x ij ′ ∈ X with j ′ ≤ j. To each couple (x (i)(j) , x (i)(j+1) ) ∈ X 2 corresponds an arc in A. To each x (i)(j) ∈ X corresponds an arc in A from x (i)(j) to x (i ′ )(1) , i ′ > i. To each x (i)(1) ∈ X corresponds an arc from source vertex p to x (i)(1) in A. Similarly, for each vertex x (i)(j) , it corresponds an arc from x (i)(j) to sink vertex q. Finally the weight of an arc heading to x (i)(j) is s ij (X ) and to sink vertex q is 0.

Example 10. Let (3, 3, [3, 2, 2], v, C) be an instance of the (SMKP). For X = {x 11 , x 12 , x 21 , x 22 , x 23 , x 31 , x 33 }, the vertex set is W = {p, q, x (1)(1) , x (1)(2) , x (2)(1) , x (2)(2) , x (2)(3) , x (3)(1) , x (3)(2) }. Figure 4 illustrates the graph G associated to X .

With graph G defined with respect to X , the following property makes the link between a path in G and a variable set Y ⊆ X . Property 13. Finding a shortest path in G featuring exactly k + 1 arcs is equivalent to finding Y ⊂ X , with Y featuring the following properties: 1)

|Y| = k, 2) ∀x ij ∈ Y, if x ij ′ ∈ X , and j ′ < j, then x ij ′ ∈ Y 3) Y minimizes its set weights s ij (Y).
Proof. 1) The path between p and q with exactly k + 1 arcs is a path with k + 2 vertices. Note that such path necessarily exists with k ∈ {1, ..., card(P)}. Indeed, by construction of G, there is a path going through all nodes x (i)(j) and there is an arc from any x (i)(j) to q. Also any arc (x (i)(j) ,x (i ′ )(j ′ ) ) is with (i ′ ) ≥ i or (j ′ ) > (j), thus there are no cycles in G. Hence, the k + 2 vertices are necessarily different. As p and q do not correspond to any variables of X , a path with exactly k +1 arcs represents a set Y with exactly k variables of X 2) By construction of G, the only arc towards x (i)(j) is from x (i)(j-1) with (j) > 1. Consequently, ∀x ij ∈ Y, if x ij ′ ∈ X , and j ′ < j, then x ij ′ ∈ Y.

3) By construction of G, for each x ij ∈ X , every arc towards x ij has a weight s ij (X ). As such, the weight of a path with a set Y ⊆ X of variables, has a weight equal to xij ∈Y s ij (X ). Hence, set Y corresponds to a shortest path minimizing the sum of its set weights.

Computing the rank Clearly, if the sum of the set weights of Y is smaller than or equal to C, then Y is a k-intersection of X . By definition, if a k-intersection of X exists, then there is a feasible solution with k variables of X to 1. Hence, the idea to compute the rank of a pattern P is to find a p x (1)(1)

x (1)(2)

x (2)(1) x (2)(2)
x (2)(3) maximum cardinality path in G associated to X ∈ χ (P), with its total weight being smaller than or equal to C. From Property 13, if the maximum cardinality path found is with k + 1 arcs, then the rank of P is k. Such rank computing algorithm is described in Algorithm 1.

x (3)(1) x (3)(3)
The procedure computeRank(P) in Algorithm 1 returns the rank of P. Indeed, this algorithm is similar to the Bellman-Ford algorithm [START_REF] Bellman | On a routing problem[END_REF], but with a different stopping condition. Because all weights are non-negative, if Algorithm 1 stops for a given nbArcs, then there cannot be a path of nbArcs arcs with a total weight smaller than or equal to C. Hence, the maximum cardinality path found is with nbArcs -1 arcs, containing nbArcs -2 vertices different than p and q. Consequently, the rank of P is k = nbArcs -2.

Verifying conditions (ii) and (iii) Let P be a pattern of rank k and X ∈ χ (P) with permutation π id . To verify if condition (ii) holds for a group i, one need to find a set Y, a k-intersection of X with x iM ∈ Y. To verify if condition (iii) holds for x ij , one need to find a set Y, a k-intersection of X with x ij-1 ∈ Y and x ij / ∈ Y. Let u be the number of variables x ij ′ ∈ X , with j ′ ≤ M for condition (ii), and with j ′ < j for condition (iii). Finding such k-intersection is to find a shortest path of length k -u + 1 in G, without any variable of group i. To do so, one can use a variant of the shortest path algorithm as described in Algorithm 2.

The procedure verifyCondition(P, i, j) in Algorithm 2, in the case j = M + 1, returns true only if (ii) is verified for i, and in the case j ∈ S i (P), returns true only if (iii) is verified for i and j. Indeed, this algorithm is similar to the Bellman-Ford algorithm [START_REF] Bellman | On a routing problem[END_REF], but with a different stopping condition. The path found is a shortest path with k -u + 1 arcs, thus with k -u + 2 vertices and with k -u vertices different than p and q. By construction of X ′ , this path is without any variables of group i. Consequently if the total weight of the generated shortest path plus j-1 j ′ =1 w j ′ is smaller than or equal to C, then there is a k-intersection of X , containing all variables in the generated shortest path and the variables x ij ′ ∈ V, j ′ < j. In the case j ≤ M , then the resulting k-intersection contains Algorithm 1 Computing the rank of a pattern procedure computeRank(pattern P):

build G = (W, A) associated to X ∈ χ (P) for a permutation π dist

[p] ← 0 dist[w] ← +∞, ∀w ∈ W \ {p} nbArcs ← 0 while min(dist) ≤ C do nDist[w] ← ∞, ∀w ∈ W for a ∈ A do nDist[a.head] ← min(nDist[a.head], dist[a.tail] + a.weight) end for dist ← nDist nbArcs ← nbArcs + 1 end while k ← nbArcs -2 return k end procedure
the variable x ij-1 but not x ij , which corresponds to condition (iii). In the case j = M + 1, then the resulting k-intersection contains x iM , which corresponds to the condition (ii). Algorithm 2 can also be extended to gather further information on a pattern as described in the following. These extensions are not used for the experimental results in Section 5. Only Algorithm 1 and Algorithm 2 are required to apply Theorem 3 and Theorem 4 Algorithm 2 Verifying conditions (ii) and (iii)

procedure verifyCondition(pattern P, i ∈ [1; N ], j ∈ [1; M + 1]): ▷ j ≤ M for condition (ii), j = M + 1 for condition (iii) u ← |{j ′ ∈ S i (P) : j ′ < j}| X ← set in χ (P) for permutation π id X ′ ← X \ {x ij ′ : j ′ ∈ S i (P)} build G = (W, A) associated to X ′ dist[p] ← 0 dist[w] ← +∞, ∀w ∈ W \ {p} nbArcs ← 0 while nbArcs ≤ rank(P) -u do nDist[w] ← ∞, ∀w ∈ W for a ∈ A do nDist[a.head] ← min(nDist[a.head], dist[a.tail] + a.weight) end for dist ← nDist nbArcs ← nbArcs + 1 end while return dist[q] + j-1 j ′ =1 w j ′ ≤ C end procedure
Computing generalized lower sub-patterns Q i (u) To find a flexible pattern, there is no need to compute the lower sub-patterns Q i (u). However, it is worth mentioning that finding Q i (u) can also be done with a variant of the shortest path algorithm. More precisely, finding Q i (u) can be obtained via Algorithm 2, for x ij+1 with j = S i (Q i (u))(u). The only modification is to add an extra step to memorize the paths, and to return the path to node q.

Verifying conditions (v) and (vi) Let P be a pattern and {R u , 1 ≤ u ≤ U ′ } the nested subpatterns of P. To verify if conditions (v) or (vi) hold for its nested sub-patterns R u , one needs to find k-intersections. Finding a k-intersection is also what is required to verify conditions (ii) and (iii). Hence, a similar algorithm as Algorithm 2 can be used to verify these conditions.

Pattern generation

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

In Algorithm 3, the lower bound on k ensures that the rank is high enough to create a flexible pattern. Indeed, because of condition (i), too small of a rank will lead to patterns that cannot be flexible patterns. The algorithm starts by initializing a pattern P containing N times the set {M }. By construction, P has at least one index per set, hence condition (i) is verified. In order for the pattern inequalities of P not to be trivial, it requires card(P) > rank(P). As the P is initialized with cardinality N , in the case rank(P) ≥ N one need to add elements to P. For the purpose of this algorithm, we start with elements of higher indices. To do so, we select a random i and add j -1 to S i (P), with j = S i (P)(1) the smallest index in S i (P). The sets are randomly selected in order to make it possible to generate different patterns for a same k. The core of the procedure is to modify P so that it verifies condition (ii) and (iii). We randomly select i and j such that j / ∈ S i (P) and j + 1 ∈ S i (P) or j = M and call the procedure verifyCondition(P, i, j). If verifyCondition(P, i, j) returns false, then in the case j < M we replace j + 1 by j in S i (P), and in the case j = M we add M to S i (P). The elements are also chosen randomly, so that two same patterns for the same rank k can Algorithm 3 Generating a flexible pattern

procedure generatePattern( instance (N, M, w, v, C) of the (SMKP)) lowerBound ← ⌈C/ M j=1 w j ⌉ k ← random integer in [lowerBound; n] P ← N sets {M } while card(P) < k do i ← random integer in [1; N ] such that |S i (P)| < M j ← S i (P)(1)
S i (P) ← S i (P) ∪ {j -1} end while while (ii) and (iii) not verified for P do X ← set in χ (P) for permutation π id x ij ← variable chosen randomly in X such that x ij+1 ∈ X or j = M if j = M and !verifyCondition(P, i, j) then ▷ (see Algorithm 2) S i (P) = S i (P) ∪ {M } end if if j < M and !verifyCondition(P, i, j) then ▷ (see Algorithm 2) S i (P) = S i (P) ∪ {j} \ {j + 1} end if end while if computeRank(P)=k then ▷ (see Algorithm 1) return P else pattern discarded end if end procedure yield two different flexible patterns through this procedure. Finally, because of the modifications of P, it is possible for it to have rank(P) > k, hence we need to compute it. If the rank is different than k, then P may not be flexible pattern, as verifying the conditions (ii) and (iii) depends on the rank k. One would need to restart the whole procedure to verify if (ii) and (iii) indeed hold for P. We chose to discard P in this case, in order to avoid to long computational time for each call to the procedure generatePattern((N, M, w, v, C)).

Procedure generatePattern((N, M, w, v, C)) only returns a pattern if it is a flexible pattern. As P is discarded if rank(P) ̸ = k, it ensures the rank of P to be exactly k. Similarly, pattern P verifies conditions (ii) and (iii). Indeed, condition (ii) is verified ∀i ∈ {1, ..., N } and (iii) is verified ∀i ∈ {1, ..., N } and j ∈ S i (P). Also, if a condition (ii) is verified for a given i, it is still verified if P is modified during the core of procedure generatePattern((N, M, w, v, C)). Similarly, if condition (iii) is verified for a given i and j ∈ S i (P), it is still verified if P is modified during the core of procedure generatePattern((N, M, w, v, C)). Indeed, as either one element is added, or an index j ′ is replaced by j ′ -1 in a set S i ′ (P), then the same k-intersection satisfying (ii) or (iii) can be found, or a k-intersection with lighter total set weights. As P is initialized with one element per set, and no element can be removed, condition (i) is clearly verified.

Note that generatePattern((N, M, w, v, C)) only needs the instance, more precisely the knapsack bound and the item weight from the instance, hence it can be only used in pre-processing. Indeed, only the constraints are needed to compute a pattern verifying (i), (ii) and (iii). Also, procedure generatePattern((N, M, w, v, C)) returns at most a single pattern, which may not be enough to make a large difference in a B&C framework. Consequently, we call this procedure multiple times as the pre-processing step of the two phase scheme, in order to generate various patterns. Note that each call is independent to the previous ones, meaning that multiple calls can be done in parallel on different threads. The set of patterns obtained with this procedure is then used within a B&C framework, with the separation algorithm described in the following section.

Separation algorithm for the (SMKP)

For the separation algorithm, we have two pieces of information: the fractional point X and the set of generated patterns. Recall that for a given pattern P, variables sets X ∈ χ (P), and their associated inequalities (pi(X )) exist for any permutation π. The aim of the separation algorithm is to find, for a given pattern, the permutation π maximizing the left hand side of (pi(X )) for X ∈ χ (P) with permutation π. However, the number of pattern-inequalities is exponential, as any permutation of groups is possible (see Section 3). Given a pattern P, in order to find the best permutation π, we can solve a Maximum Matching Problem (MMP).

Definition 21 (Maximum Matching Problem). Let H be a weighted bipartite graph. The (MMP) is to find the set of edges E, such that at most one edge of E is incident to each vertex of H, while maximizing the sum of the weight of E. Property 14. Finding a permutation π maximizing the violation of (pi(X )) with X ∈ χ (P) for permutation π is equivalent to solving the (MMP).

Proof. The aim is to find the permutation π of the sets of P, maximizing the left hand side of the inequality (pi(X )) with X ∈ χ (P). To do so, we can build a bipartite graph H = (H 1 , H 2 , E). Each vertex in H 1 corresponds to a group i ∈ {1, ..., N } of solution X and each vertex in H 2 corresponds to a set S i ′ (P), i ′ ∈ {1, ..., N }. In the set of edges E there is an edge (i, i ′ ) for each i ∈ H 1 , i ′ ∈ H 2 . The edge (i, i ′ ) has a weight equal to j∈S i ′ (P) x ij .

Solving this (MMP) to optimality yields a matching maximizing the weight of the considered edges. One can deduce a permutation from this matching: π(i) = i ′ if edge (i, i ′ ) is in the matching. As the (MMP) is solved to optimality, permuation π is such that the left hand side of (pi(X )) is maximized with X ∈ χ (P).

Example 11. Let (4, 4, w, v, C) be an instance of the (SMKP). Let X = [[1, 1, 0, 0], [1, 0.7, 0.7, 0], [0.6, 0, 0, 0], [1, 0, 0, 0]] be a fractional point and let P = {S 1 (P) = {1, 3}, S 2 (P) = {1, 2}, S 3 (P) = {1}, S 4 (P) = {1}} be a pattern with rank(P) = 5. Table 1 represents the weight matrix of H, with X[i] ∈ H 1 the vertex corresponding to the group i of X. In this example, the optimal solution to

X[1] X[2] X[3] X[4] S 1 (P) 1 1.7 0.6 1 S 2 (P) 2 1.7 0.6 1 S 3 (P) 1 1 0.6 1 S 4 (P) 1 1 0.6 1 Table 1: Weight matrix the (MMP) is: ( X[1], S 2 (P)), ( X[2]
, S 1 (P)), ( X[3], S 3 (P)), ( X[4], S 4 (P)). This solution has a value 2 + 1.7 + 0.6 + 1 = 5.3. The inequality with X ∈ χ (P), ordered with respect to the permutation corresponding to the solution of the (MMP) is:

x 11 + x 12 + x 21 + x 23 + x 31 + x 41 ≤ 5
This inequality cuts the fractional point X as the left hand side of the inequality equals 5.3.

To solve the (MMP), one can use the Hungarian algorithm [START_REF] Harold W Kuhn | The Hungarian method for the assignment problem[END_REF]. Initially the complexity of this algorithm was O((|H | + |H 2 |) 4 ), and a more recent version [START_REF] Edmonds | Theoretical improvements in algorithmic efficiency for network flow problems[END_REF] 3 ). In the scope of the separation algorithm, |H 1 | = |H 2 | = N . Thus, the separation algorithm is polynomial for a pattern, as it is of complexity O((2N ) 3 ). However the number of patterns can be very large. As the Hungarian algorithm solves the (MMP) to optimality, the inequality built for a given P is the one with the permutation of the groups maximizing the left hand side of the inequality. Hence, for a given P, solving the (MMP) produces the most violated inequality associated to P if such inequality exists.

is of complexity O((|H 1 | + |H 2 |)

Two-phase B&C scheme

The first phase is to generate flexible patterns using Algorithm 3 as pre-processing. Because of the symmetries of the (SMKP), each flexible pattern encodes an exponential number of pattern inequalities. From Theorem 3, there is a lower bound on the dimensions of the faces defined by these inequalities, and they are facet-defining in the case of a flexible pattern with a set of cardinality 1.

The second phase is to use inequalities associated to generated patterns within a B&C framework. However, adding all these inequalities would be counter-productive, as only enumerating them would take too long, hence the need of a separation algorithm. As the patterns have already been generated, the separation algorithm only requires to find the permutation π leading to the most violated inequality for each pattern. Such permutation can be found for a given pattern by solving the (MMP), with a polynomial time algorithm.

Experimental results

Results are computed on a single thread of an Intel(R) Xeon(R) Platinum 8260 CPU @ 2.40GHz (Cascade Lake) processor, with 2 CPUs of 24 cores, with Linux as operating system. All algorithms are developed with C++. Version 12.8 of CPLEX is used.

Instance description

A set of 15 (SMKP) instances are as follows: instances 1 to 5 with N = 20 M = 5; instances 6 to 10 with N = 30 M = 5; instances 11 to 15 with N = 20 M = 10. These 15 instances are selected amongst a pool of hundreds of instances as difficult enough to see the impact of the cuts. The selection criteria is for these instances to take at least 60 seconds to be solved by CPLEX, with all the default options of CPLEX enabled but the cuts. As such, there is enough room in terms of time and number of nodes to see the impact of the pattern inequalities and CPLEX cuts.

Pattern generation

As the pattern generating process is random based, for each instance, 10 sets of patterns (Pi for i ∈ {0, ..., 9}) are generated with different seeds, with a time limit of 60 seconds for each generation. Also, an eleventh set P10 is generated with a time limit of 3600 seconds. Pattern sets P0 to P9 represent a more practical case, where a limited time is attributed to the pattern generation. Pattern set P10 represents an ideal case, where a larger number of patterns are generated, to have more room to see the effects of the pattern inequalities to solve the (SMKP). Even if the pattern generation procedure could be parallelized, we used a single thread.

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

• #iter : the number of iterations of the generation process • #find : the number of iteration where a flexible pattern is found • #patt: the number of different flexible patterns found • %facet: the proportion of them guaranteed to be pattern-facet, i.e., with a set of cardinality 1

Firstly, one can see that the generation becomes slower on larger instances, thus with the same time limit, fewer iterations can be performed, namely thousands of iterations for instances 1 to 5, whereas around one thousand for instances 6 to 10, and around 300 for instances 11 to 15. Consequently, fewer patterns are found for larger instances. Note that many iterations of the pattern generation procedure fail to produce a flexible pattern in a majority of cases. Indeed, for instances 4, 7, 9, 11, 12, 13, 14 and 15, the ratio #find/#iter is very small. In fact, around 90% of the iterations do not generate a flexible pattern. Generally speaking, the larger the instances, the higher the proportion of failed iterations.

Moreover, when #find is large, most of the flexible patterns are generated multiple times, as #patt is much smaller, namely for instances 1, 2, 3, 5, 6 and 8. As the procedure is random based, when #find is large, there is a higher chance to generate duplicates. It is especially visible as P10 rarely generated more than 10 times the number of patterns compared to P0 to P9, even if the total time allocated to P10 is 60 times longer.

Results in the following show that %facet does not seem to be related to the computational time or the number of pattern cuts. In the case where the pattern cuts lead to a short computational time, it could mean that many of the flexible patterns without a set of cardinality 1 are also pattern-facet. In the case where pattern cuts do not reduce the computational time, it could mean that only inequalities with integer coefficients would be efficient.

Separation of the pattern inequalities

The separation of the (SMKP) is done within a user cut callback from CPLEX. For a given pattern set Pi, it solves the (MMP) for each pattern in Pi (see Section 4.3), hence creating one inequality per pattern, and retains the most violated inequality. Preliminary results shows that this strategy is, on average, more efficient than retaining the first violated inequality, or all the violated inequalities. In the separation, we only consider the inequalities that are violated by at least 0.4 by the fractional point. As shown in the next section, the pattern inequalities are very tight. Hence, this violation Table 2: Patterns generations bound serves to filter the less efficient violated inequalities. A too high violation bound would be to selective, and a too small number of inequalities would be added despite the dedicated time to generate them. This process is repeated at each node, as long as a violated inequality is found. This means that the separation of the (SMKP) is made at least once per node. Recall that it solves a (MMP) for each pattern, and from Table 2 the number of patterns can reach hundreds. This results to the separation taking up to 90% of the total computational time. To avoid such cases, we only use the separation algorithm while less than 1000 cuts have been added, or less than 10,000 nodes have been explored. These limits cover the case where lots of violated inequalities are found, but also the opposite case where very little inequalities are found.

Resolution of the (SMKP)

The B&C framework is limited to a single thread, and a maximum of 3600 seconds of computational time. Multiple combinations are considered in order to compare the introduced inequalities. For this purpose, we define default CPLEX, CPLEX with all default options enabled, and no-cut CPLEX, which is default CPLEX with the cuts disabled. Three combinations are considered:

• Cplx: default CPLEX • Psep: no-cut CPLEX with pattern inequalities separation.

• Cplx+Psep: default CPLEX with pattern inequalities separation.

As P10 is always outperformed by P0 to P9, results for P10 are not included in the following. This is due to the fact that P10 contains to many patterns, which increases the number of time the (MMP) is solved, without necessarily producing more efficient cuts. For all these combinations, the results for pattern sets P0 to P9 are quite similar. Hence, the following metrics, used in the Table 3 to compare the aforementioned combinations, are averaged for P0 to P9 besides #s.

• #s: the number of pattern sets for which the instance is solved with respect to the total number of pattern sets • C-cuts: the number of CPLEX cuts added • P-cuts: the number of pattern cuts added • Pvv : the average violation value of the pattern cuts added • r-value: the linear relaxation value at the root node • user-time: the proportion of the computational time dedicated to the separation • #nodes-s: the number of nodes explored when the instance is solved • #nodes-us: the number of nodes explored when the instance is unsolved • gap: the gap when the instance is not solved • time: the total computational time The relaxation value r-value resulting from using Psep is often higher than the one obtained using Cplx, instances 1 and 3 being the only two exceptions. This could mean that the pattern inequalities are the most efficient when some branching have already occurred.

Besides instances 8 and 9, using Psep instead of Cplx leads to much smaller computational times. For instance 1, only 77 nodes are 2 seconds are required with Psep, while Cplx needs 580 seconds and 3.6 million nodes. The difference is even more visible for instance 3, where Psep solves the (SMKP) in 0 seconds at the root node, while Cplx needs 275 seconds and 1.8 million nodes. In general, Psep is very efficient because of the violation value of the added cuts. Indeed, metric Pvv is very high, over 0.5 in most case, and over 0.9 for instances 3 and 7.

For instances 10 and 13, Psep yields smaller computational times than Cplx even if no inequality is added. This means that the cuts added by CPLEX for these instances are slowing down the LP without significantly cutting the fractional points. This is visible on the number of nodes developed, Psep explores 28.5 million nodes in 2400 seconds, while Cplx explores 8 million nodes in 3600 seconds.

For the majority of the instances, Cplx+Psep is the second best combination. For instance 1, Cplex+Psep requires 124 nodes and 2.5 seconds, while Psep requires 77 nodes and 2.0 seconds, and Cplex requires 3.6 nodes and 580 seconds. It is worth mentioning that for instances 6 and 11, Cplex+Psep seems to be complementary, as they yield the smallest computational time. More specifically, for instance 6 Cplex+Psep can solve the instance at the root node in 0 seconds, with only 4 CPLEX cuts and 1 patern cut, while Cplx did not solve the instance in 3600 seconds with 600 CPLEX cuts, and Psep required 73 seconds with 700 pattern cuts. Also, Cplx+Psep always leads to the smallest root node relaxation value r-value. These results show that the pattern cuts added are different than the CPLEX cuts, and in addition the pattern cuts can help CPLEX finding more efficient inequalities. match the patterns with the fractional point in order to produce a violated inequality. This algorithm is used within a B&C framework in the second phase of the scheme. Experimental results demonstrate the efficiency of the inequalities and algorithms presented, as they significantly speed up the solving process of difficult instances compared to default CPLEX.

An extension of this work would be to study the integer inequalities for the (SMKP). The proposed patterns can also be extended to other problems, such as the use case of the Hydro Unit Commitment problem whose core structure corresponds to the (SMKP). A promising perspective would be to see how a two phase B&C scheme could be generalized to other problems facing numerous symmetries.

A Proofs and lemmas

A.1 Proof of Property 7

Proof. Let (i, j) be an item such that ∃j ′ > j, x ij ′ ∈ X . Assume without loss of generality that j ′ is such that there are no x ij ′′ ∈ X , j < j ′′ < j ′ . As P is pattern-facet, condition (iii) holds and the property is verified for item (i, j ′ -1). Let Y ′ be the set of variable verifying condition (iii) for item (i, j ′ -1). Let Z be the subset of Y ′ with all variables x ij ′′ ∈ Y ′ , j ′′ ≥ j. One can build Y = Y ′ \ Z ∪ {x ij }. We can prove that the set of variable Y verifies the property for item (i, j). By construction, x ij ∈ Y and x ij ′′ / ∈ Y, ∀j ′′ > j. As there are no x ij ′′ ∈ X , j < j ′′ < j ′ and Y ′ is a k-intersection of X by condition (iii), then |Y ∩ X | = k. Also, as the weights are non-negative, and solution X Y ′ is valid by condition (iii), then X Y is also valid. Consequently, Y is a k-intersection of X and the property is verified for x ij .

Let (i, j) be an item such that ∀j ′ > j, x ij ′ / ∈ X . As P is pattern-facet, condition (ii) hold and the property is verified for item (i, M ). The proof is the same as in the first case, with Y ′ the set of variable verifying condition (ii) for item (i, M ). 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 X to 1.

A.2 Proof of Property 8

Proof of Property 8. Let P be a flexible pattern. Suppose that there is i ≤ N such that S i (Q 1 ) does not contain the |S i (P)| -V smallest indices of S i (P). By definition of Q 1 , S 1 (Q 1 ) = S 1 (P), meaning the property is trivially verified for i = 1. In the following we consider i > 1. Let X ∈ χ (P) with permutation π id . Let Y ∈ χ (Q 1 ) with permutation π id , to which we add x 1M if x 1M / ∈ X . The solution X Y is valid as proven in Lemma 1. Let Y ′ be the variables set Y to which we remove all variables of group 1, and to which we add all variables of group i in X \ Y. Because of the symmetric weights, selecting every item (1, j), j ≤ M is at least as heavy as selecting items (i, j), j ≤ max(S i (P)). Consequently:

x i ′ j ′ ∈Y ′ s i ′ j ′ (Y ′ ) ≤ x i ′ j ′ ∈Y s i ′ j ′ (Y)
As solution X Y is valid, solution X Y ′ must also be valid. By construction, there are V variables of group 1 in Y \ Y ′ . Also, as |S i (Q 1 )| < |S i (P)| -V by hypothesis, there are at least V + 1 variables of group i in Y ′ \ Y. Besides groups 1 and i, sets Y and Y ′ and identical, hence

|Y ′ | > |Y|. As Y is a k-intersection of X , then Y ′ is at least a k + 1-intersection of X , which contradicts the rank k of P. Thus, Q 1 must contain the |S i (P)| -V smallest indices of S i (P), ∀i ≤ N .
A.3 Lemmas for Property 9

Lemma 2. Let P be a flexible pattern. Let i ∈ {2, ..., N }. For any u ∈ 5e, as solution X X ′ is valid, then solution X Y ′′ is also valid. However Y ′′ is an 8-intersection of X , which contradicts the rank of P. Proof. Let P be a flexible pattern of rank k. Suppose that there is u ≤ V and i > 1 such that

[1, V ], if S i (P)[u] ∈ S i (Q 1 ) and |S i (P)| ≥ u + V then S 1 (P)[u] ≥ S i (P)[u + V ].
S 1 (P)[u] ∈ S i (Q 1 ) and |S i (P)| ≥ u + V but S 1 (P)[u] < S i (P)[u + V ]. Let X ∈ χ (P) (resp. Y ∈ χ (Q 1 )
) with permutation π id . By definition of Q 1 , solution X Y∪{x 1M } is feasible. However, for a variable set Z, Z ⊆ X \ Y, it is not possible to create a feasible solution from X Y by setting every variable of Z to 1, and |Z| -1 variables of Y to 0. Otherwise there would be k + 1 variables of X to 1, which contradicts the rank of P. With |Z| = u, as X Y∪{x 1M } is a feasible solution, we deduce the following:

x i ′ j ′ ∈Z s i ′ j ′ (X ) > M j=S1(P)[u]+1 w j Because P is flexible, Property 7 stands, it is possible for j = S i (P)[u + V ] to have a set Y ′ ∈ V a k-intersection of X with x ij-1 ∈ Y ′ and x ij ′ / ∈ Y ′ , j ′ ≥ j, such that X Y ′ is valid. In the case S i (Q 1 ) = S i (P), clearly there are u + V more variables of group i in Y \ Y ′ . However, as |Y| = |Y ′ | = k, there are u + V variables of groups different than i in Y ′ \ Y. Property 8 indicates that ∀i ′ ≤ N , |S i ′ (Q 1 )| ≥ |S i ′ (P)| -V . Thus, these u + V variables in Y ′ \ Y are splitted into a set O 2 ⊂ X of 1 to V variables
in a group, and a set O 1 ⊂ X of u to u + V -1 variables in the other groups.

In the case S i (Q 1 ) ⊂ S i (P) with S i (P)[u] ∈ S i (Q 1 ) there are between V + 1 and u + V -1 variables of group i in Y \ Y ′ and reciprocally between V + 1 and u + V -1 variables of groups different than i in Y ′ \ Y. In this case we consider O 1 ⊂ X to be the set of

V + 1 to u + V -1 variables if Y ′ \ Y, and O 2 = ∅.
We know that Z ∈ X and Z ∪ Y = ∅ and similarly, O 1 ∈ X and O 1 ∪ Y = ∅. Also, we know that |O 1 | ≥ u = |Z|. We deduce that:

x i ′ j ′ ∈O1 s i ′ j ′ (X ) ≥ x i ′ j ′ ∈Z s i ′ j ′ (X ) > M j=S1(P)[u]+1 w j
By construction, S i (P) [START_REF] Bellman | On a routing problem[END_REF] ≤ M and by hypothesis, S i (P)[u + V ] > S 1 (P) [u], which means that:

j∈Si(P):j≥Si(P)[u+V ] s ij (X ) = Si(P)[1] j=Sj (P)[u+V ] w j ≤ M j=S1(P)[u]+1 w j
The u + V variables of group i that are in Y but not in Y ′ are lighter than the ones in Z, thus lighter than variables of O 1 . Hence we build Y ′′ = Y ′ \ O 1 to which we add all the u + V variables of group i in X \ Y ′ . As X Y ′ is valid, then X Y ′′ is also valid. However |O 1 | ≤ u + V -1, meaning that the new solution has at least k + 1 variables of X to 1, which contradicts the rank of P. Proof. Suppose that there is u ≤ V and i > 1 such that S i (P)[u] / ∈ S i (Q 1 ) and |S i (P)| ≥ u + V but S 1 (P)[u] < S i (P)[u + V ].

Let X ∈ χ (P) (resp. Y ∈ χ (Q 1 )) with permutation π id . Because P is flexible, Lemma 1 proves that solution X Y∪{x 1M } is valid. By construction, S i (P) [START_REF] Bellman | On a routing problem[END_REF] ≤ M and S i (P)[V + 1] ≥ S i (P)[u + V ] and by hypothesis S i (P)[u + V ] > S 1 (P) [u], which means that: Si(P) [START_REF] Bellman | On a routing problem[END_REF] j=Si(P)[V +1]+1

w j ≤ M j=S1(P)[u]+1
w j Hence, one can build Y ′ = Y ∪ {x 1M } to which we remove all variables x 1j ∈ X , j > S 1 (P)[u] and to which we add all variables for group i: x ij ∈ X \ Y, with solution X Y ′ being valid. However, there are u -1 variables x 1j ∈ X such that j > S 1 (P)[u], and at least u variables x ij ∈ X \ Y as S i (P)[u] / ∈ S i (Q 1 ). As Y is a k-intersection of X , then Y ′ is at least a k + 1-intersection of X which contradicts the rank of P.

A.4 Lemmas for Property 10

Lemma 4. Let P be a flexible pattern of rank k. Let Q i be a lower sub-patterns of P with i > 1.

If |S 1 (Q 1 )| + |S i (Q 1 )| = |S 1 (Q i )| + |S i (Q i )|
and |S i (P)| ≥ 2V , then it is possible for Q i to be such that ∀i ′ ≤ N with |S i ′ (P)| ≥ 2V , S i ′ (P)[2V ] ∈ S i ′ (Q i ) Proof. We are in the case

|S 1 (Q 1 )| + |S i (Q 1 )| = |S 1 (Q i )| + |S i (Q i )|. Let L = {1, .
., N } \ {1, i}. By definition, card(Q 1 ) = card(Q i ) = k hence we deduce the following equation:

i ′ ∈L |S i ′ (Q 1 )| = i ′ ∈L |S i ′ (Q i )|
By definition Q 1 and 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 L, otherwise it is clear that one of them do not minimize the weight of its variable sets. Consequently, one can modify the sets of index in L in Q i by the ones in Q 1 .

Property 8 indicates that S i ′ (P)[V + 1] ∈ S i ′ (Q 1 ). As P is flexible pattern, V ≥ 1 by condition (i), and V + 1 ≥ 2V . Clearly the Lemma is verified for Q 1 .

As S i ′ (Q 1 ) = S i ′ (Q i ) for any i ′ ∈ L, the Lemma is also verified for any S i ′ (Q i ) with i ′ ∈ L. By definition of Q i , S i (Q i ) = S i (P), trivially verifying the Lemma. As |S 1 (P)| = V < 2V , the Lemma does not concern S 1 (Q i ). Thus, the Lemma is verified for any set S i ′ (Q i ) for which |S i ′ (Q i )| ≥ 2V . ∈ S i ′ (Q i ). We know by the shape of

Q 1 that |S i ′ (Q 1 )| ≥ |S i ′ (P)| -V and thus |S i ′ (Q 1 )| ≥ |S i ′ (Q i )| + V + v.
This leads to the following result:

|S 1 (Q 1 )| + |S i (Q 1 )| + |S i ′ (Q 1 )| -|S 1 (Q i )| -|S i (Q i )| -|S i ′ (Q i )| ≥ V + v + 1
There must be a set of groups L, 1 / ∈ L, i / ∈ L, i ′ / ∈ L such that:

V + v + 1 ≤ l∈L |S l (Q i )| -|S l (Q 1 )| ≤ 2V + v
If not, then there is a set l such that |S l (Q i )| -|S l (Q 1 )| > V + 1, which contradicts the shape of Q 1 (see Property 8) which is that

|S l (Q 1 )| ≥ |S l (P)| -V . Let X ∈ χ (P) (resp. Y ∈ χ (Q 1 ), Y ′ ∈ χ (Q i ))
with permutation π id . Let O be the set of variables x lj ∈ Y ′ \ Y with l ∈ L. Note that V + v + 1 ≤ |O| ≤ 2V + v. Also, S i ′ (P)[2V + v] / ∈ S i ′ (Q i ), O is sub-pattern of Q i and by definition Q i minimizes the sum of the weights and O is a sub-pattern of Q i , hence we deduce:

x lj ∈O s lj ≤ S i ′ (P) [START_REF] Bellman | On a routing problem[END_REF] j=S i ′ (P)[2V +v+1]+1 As P is flexible pattern, Lemma 1 provides a feasible solution X Y∪{x 1M } . One could create a new feasible solution from X Y∪{x 1M } by setting all variables of group 1 to 0, and all variables of O to one, creating a lighter solution, thus valid. However, |O| ≥ V + v + 1 ≥ V + 1 > |S 1 (Q 1 )| = V . The new solution has at least k + 1 variables of X to 1, which contradicts the rank of P.

From these two cases, we deduce that if the Lemma is verified for x ij , it is verified ∀x ij ′ ∈ X \ Y 1 , with j ′ ≤ j.

Finaly, by definition of R U ′ , there is at most U ′ variables in S i (P) \ S i (R U ′ ). Hence this Lemma is necessarily verified ∀x ij ∈ X such that x ij ′ / ∈ X , j ′ > j. Because of the initialisation with Y 1 , the recursive rule between Y u and Y u+1 , and because ∀x ij ∈ X , x ij ′ / ∈ X , j ′ > j the Lemma is verified, then the Lemma is verified ∀x ij ∈ X \ R 1 .

Proof. Proof of Theorem 5 Let X ∈ χ (P) and Y u ∈ χ (R u ) with permutation π id . The points will be enumerated iteratively. First, from Lemma 7, we know that ∀x ij ∈ X \ Y 1 , x ij ′ / ∈ X \ Y 1 , j ′ < j, there is a feasible solution with x ij = 1 and with x ij+1 = 0, with all variables of Y 1 to 1. These solutions are all linearly independent, as for each x ij considered, it is the only solution with x ij = 1.

As condition (v) holds, there is a feasible solution with all variables of Y 2 to 1, and two variables x ij , x i ′ j ′ / ∈ Y 1 , i ̸ = i ′ to 1. This solution is linearly independent to the previously mentioned, as it is the only one with a variable of Y 1 to 0.

From Lemma 7, we know that there is a feasible solution with Y 2 and two variables x ij , x ij ′ ∈ X \ Y 2 , j ′ ̸ = j. For each solution where both x ij and x ij ′ are not in Y 1 is linearly independent to the others, as it is the only one with x ij ′ = 1.

One can keep enumerating points with the same process. With Lemma 7, |X | -|Y 1 | linearly independent points are generated. With condition (v), one linearly independent point is generated ∀2 ≤ u < U ′ , which is a total of U ′ -1 linearly independent points.

With condition (vi), for each x ij ∈ Y U ′ , there is a set Z containing all variables x ij ′ ∈ Y U ′ , j ′ < j and all variables x i ′ j ′ ∈ Y U ′ , i ′ ̸ = i, without x ij and with Z being a k-intersection of X . Hence, starting with greater j, each new solution is the first one with x ij = 0, being linearly independent to the others. With condition (vi), one new feasible solution is created ∀x ij ∈ Y U ′ , meaning |Y U ′ | new linearly independent points.

A total of |X |-|Y 1 |+U ′ -1+|Y U ′ | = card(P)-(k-1)+U ′ -1+(k-U ′ ) linearly independent points are generated, i.e., card(P) linearly independent points. Moreover, from Theorem 3, ∀x ij / ∈ X , there is a feasible solution with x ij = 1 and x ij+1 = 0 that verifies (pi(X )) to equality. Sequentially adding these points associated to their corresponding solutions to our pool of card(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 / ∈ X . As there are n -card(P) of these new points, there is a total of n linearly independent points.

Figure 2 :

 2 Figure 2: Generalization orders of some variants of the knapsack problem

Example 4 .

 4 Let a pattern P = {S 1 = {4}, S 2 = {2, 5}, S 3 = {1, 2}, S 4 = {1, 3, 4}}. In this case, U = 3 and V = 1. Also, S 4 (P)(1) = 1, S 4 (P)(2) = 3 S 4 (P)(3) = 4, S 4 (P)[1] = 4, S 4 (P)[2] = 3 and S 4 (P)[3] = 1.

2 Example 5 .

 25 The idea of the proof is illustrated by Example 5 and Figure3. The complete proof is in A.Let (4, 5, w, v, C) be an instance of the (SMKP). Let a flexible pattern P = {S 1 (P) = {3}, S 2 (P) = {2, 4}, S 3 (P) = {1, 2}, S 4 (P) = {1, 2, 3}} of rank 5. Let Q

Figure 3 :

 3 Figure 3: Illustration of Example 5

Example 6 .

 6 Let a flexible pattern P = {S 1 (P) = {3}, S 2 (P) = {1, 3, 4}, S 3 (P) = {1, 2, 4}, S 4 (P) = {1, 2, 3, 4}}. Pattern P verifies Property 9, as S 1 (P)[1] = 3 is greater or equal to S 2 (P)[2] = 3, S 3 (P)[2] = 2 and S 4 (P)[2] = 3. Consider rank(P) = 9.

Example 9 .

 9 Let (4,[START_REF] Keely L Croxton | A comparison of mixed-integer programming models for nonconvex piecewise linear cost minimization problems[END_REF][START_REF] Hechme-Doukopoulos | The short-term electricity production management problem at EDF[END_REF][START_REF] Keely L Croxton | A comparison of mixed-integer programming models for nonconvex piecewise linear cost minimization problems[END_REF][START_REF] Boyd | Polyhedral results for the precedence-constrained knapsack problem[END_REF][START_REF] Ceria | Cutting planes for integer programs with general integer variables[END_REF], v, 37) an instance of the (SMKP). Let P = {S 1 (P) = {1, 2}, S 2 (P) = {2, 3}, S 3 (P) = {2, 4}, S 4 (P) = {2, 4}} of rank 4. Let the nested sub-patterns

Figure 4 :

 4 Figure 4: G for Example 10

Remark 3 .Theorem 6 .

 36 Both algorithms described run in polynomial time with respect to |W |, with |W | = card(P) + 2 in Algorithm 1, and |W | = card(P) + 2 -|S i (P)| in Algorithm 2. In the case of Algorithm 1, the while loop can occur |W | time, and in the case of Algorithm 2, the while loop can occur rank(P) ≤ |W | time. In both cases, in the while loop we iterate over the arcs of A, meaning |A| ≤ |W | 2 operations. Hence, both algorithms have a worst case time complexity of O(|W | 3 ). It is worth mentioning that because of the structure of G, |A| is usually much smaller than |W | 2 , and the while loop rarely iterates |W | times. Hence, these algorithms usually requires much less than |W | 3 operations. Verifying condition (i), (ii) and (iii) is in polynomial time. Proof. Condition (i) requires to verify if each set is non-empty, which is linear with respect to the number of sets N . Condition (ii) requires to run Algorithm 2 for each x iM , i ≤ N , which is an algorithm of complexity O(|W | 3 ), |W | ≤ n a total of N ≤ n times. Condition (ii) can be verified in O(n 4 ) time. Condition (iii) requires to run Algorithm 2 for each x ij ∈ X , which is an algorithm of complexity O(|W | 3 ), |W | ≤ n a total of |X | ≤ n times. Condition (iii) can be verified in O(n 4 ) time.

Remark 4 .

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

  (a) Set X (b) Set Y ∪ x45 (c) Non feasible set (d) Set Y ′ (e) Set Y ′′

Figure 5 :

 5 Figure 5: Illustration of Example 12

Lemma 3 .

 3 Let P be a flexible pattern. Let i ∈ {2, ..., N }.For any u ∈ [1, V ], if S i (P)[u] / ∈ S i (Q 1 ) and |S i (P)| ≥ u + V then S 1 (P)[u] ≥ S i (P)[u + V ].

Lemma 5 .

 5 Let P be a flexible pattern of rank k. Let Q i be a lower sub-patterns of P with i > 1.If |S 1 (Q i )| = 0, then ∀i ′ ≤ N with |S i ′ (P)| ≥ 2V , S i ′ (P)[2V ] ∈ S i ′ (Q i )The idea of the following proof is illustrated by Example 13 and Figure6.Example 13. Let (5, 3, w, v, C) be an instance of the (SMKP). Let a flexible patternP = {S 1 = {3}, S 2 = {1, 2, 3}, S 3 = {1, 2, 3}, S 4 = {1, 2, 3}, S 5 = {1, 2, 3}} of rank 10. The smallest set of P is S 1 (P) hence V = 1. Suppose Q 1 = {S 1 = {3}, S 2 = {1, 2, 3}, S 3 = {1, 2}, S 4 = {1, 2}, S 5 = {1, 2}} and Q 2 = {S 1 = ∅, 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 (Q 2 )| = 0, but not in the case of Lemma 4, as |S 1 (Q 1 )|+|S 2 (Q 1 )| = 4 ̸ = |S 1 (Q 2 )|+|S 2 (Q 2 )| = 3. However, Lemma 5 is not verified, as S 3 (P)[2V ] = S 3 (P)[2] = 2 / ∈ S 3 (Q 2 ). Let Y = {x 13 , x 21 , x 22 , x 23 , x 31 , x 32 , x 41 , x 42 , x 51 , x 52 } ∈ χ (Q 1 ) and Y ′ = {x 21 , x 22 , x 23 , x 31 , x 41 , x 42 , x 43 , x 51 , x 52 , x 53 } ∈ χ (Q 2 ). As P is pattern-flexible, Lemma 1 proves that solution X Y∪{x14}} is valid. Also, Q 2 minimizes the sum of the weights, {x 43 , x 53 } ∈ Y ′ and {x 32 ,x 33 } / ∈ Y ′ hence w 3 + w 3 ≤ w 2 + w 3 . Clearly, w 3 + w 3 ≤ w 2 + w 3 ≤ w 1 + w 2 + w 3 + w 4 . With O = Y ′ \ Y = {x 43 , x 53 },the set Y ′′ = Y ∪ {x 14 } \ {x 13 , x 14 } ∪ O yields a feasible solution X Y ′′ . However, Y ′′ is a 9-intersection of X , which contradicts the rank of P.

  (a) Set Y (b) Set Y ′ (c) Set Y ∪ {x14} (d) Set Y ′′

Figure 6 :

 6 Figure 6: Illustration of Example 13

  w j ≤ M j=S i ′ (P)[2V +v+1]+1 w j ≤ M j=1 w j

  {x 11 , x 12 , x 22 , x 23 , x 32 , x 34 , x 42 , x 44 } , Y 1 = {x 11 , x 22 , x 23 } and Y 2 = {x 11 , x 22 }. Condition (iv) is verified. For Y 1 the following variable sets are 4-intersections of X : {x 11 , x 12 , x 22 , x 23 }, {x 11 , x 22 , x 23 , x 32 }, {x 11 , x 22 , x 23 , x 42 }. For Y 2 the following variable sets are 4-intersections of X : {x 11 , x 22 , x 32 , x 34 }, {x 11 , x 22 , x 42 , x 44 }. Condition (v) is verified. For Y 2 the following variable set is a 4-intersection of X : {x 11 , x 12 , x 22 , x 32 }, with x 12 and x 32 being in different groups, while not being in Y 1 . Condition (vi) is verified. For Y 2 , the following variable sets are 4-intersections of X : {x 11 , x 12 , x 32 , x 34 } and {x 22 , x 23 , x 32 , x 34 }. The first one contains all variables of Y 2 but x 22 , and the second one contains all variables of Y 2 but x 11 .

  The idea of the following proof is illustrated by Example 12 and Figure5. Figure5aand Y = {x 11 , x 12 , x 31 , x 42 , x 43 , x 44 , x 45 } ∈ χ (Q 1 ). As P is a flexible pattern, Lemma 1 proves that solution X Y∪{x15} , as represented in Figure5b, is valid. Let Z = {x 21 , x 32 }, by construction |Z| = u = 2. Clearly, solution X Y\{x12}∪Z , as represented in Figure5c, is unfeasible by the rank of P. Hence, w 2 + w 1 > w 2 + w 3 + w 4 + w 5 .As P is pattern-facet, P verifies Property 7. Hence there is a setY ′ such that x 41 ∈ Y ′ , x 4j / ∈ Y ′ ∀j ∈ [2, .., 5] and |Y ′ ∪ X | = 7 and X Y ′ is a valid solution. Suppose in this example 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 (P)[u + V ] -1 = S 4 (P)[4] -1 = 1, and by construction, x 4j / ∈ Y ′ ∀j ∈ [2, .., 5]. Hence, there are u + V = 4 variables, namely x 21 , x 23 , x 32 , x 33 , in Y ′ \ Y. Property 8 indicates that ∀i ≤ N , S i (P)[V + 1] ∈ S i (Q 1 ). Thus, these 4 variables in Y ′ \ Y are splitted into a set O 2 ⊂ X of 1 to V = 2 variables in a group, and a set O 1 ⊂ X of u = 2 to u + V -1 = 3 variables in the other groups. In this case, we arbitrary chose O 2 = {x 32 , x 33 } and O 1 = {x 21 , x 23 }. Because both Z and O 1 are subsets of X \ Y and |Z| ≤ |O 1 |, then w 1 + w 2 + w 3 ≥ w 1 + w 2 > w 2 + w 3 + w 4 + w 5 . Hence, with Y ′′ = Y ′ \ O 1 ∪ {x 42 , x 43 , x 44 , x 45 } represented in Figure

	Example 12. Let (4, 5, w, v, C) be an instance of the (SMKP). Let a flexible pattern P = {S 1 (P) =
	{1, 2}, S

2 (P) = {1, 3}, S 3 (P) = {1, 2, 3}, S 4 (P) = {2, 3, 4, 5}} of rank 7 and with V = 2. Suppose Q 1 = {{1, 2}, {1}, ∅, {2, 3, 4, 5}}. In this case P does not follow Lemma 2. Indeed, with u = 2, there is S 1 (P)

[START_REF] Boyd | Polyhedral results for the precedence-constrained knapsack problem[END_REF]

= 1 < S 4 (P)[2 + 2] = 2. Let X = {x 11 , x 12 , x 21 , x 23 , x 31 , x 32 , x 33 , x 42 , x 43 , x 44 , x 45 } ∈ χ (P) as represented in

The Symmetric Weight Matrix Knapsack problemWe first prove the NP-hardness of the (SMKP). A literature review of related problems is done, and first polyhedral properties are provided.

Conclusion

In this paper, the (SMKP) is considered as a new variant of the knapsack problem. Two main contributions, namely the polyedral study and the two-phase B&C scheme, are proposed, revolving around the patterns. We derived pattern inequalities as a new class of valid inequalities embedding symmetries with respect to the groups. Necessary facet-defining conditions are defined for these inequalities, which are also sufficient in the case of a pattern with a set of cardinality 1. An algorithm is presented to generate a set of patterns verifying such conditions as pre-processing and first phase of the scheme. A separation algorithm based on the generated patterns is presented and reduces to Lemma 6. Let P be a flexible pattern of rank k. Let Q i be a lower sub-patterns of

Proof. We consider the case where

Let X (resp. Y) be the set of variables of P (resp. Q i ) with permutation π id . We know that X Y is a feasible solution. We also know by Property 9 that a flexible pattern P is such that S 1 (P)[u] ≥ S i ′ (P)[u + V ], which means that:

Hence, one can build Y ′ = Y from which we remove all variables x 1j ∈ Y and to which we add all

Clearly, as X Y is a valid solution, so is X Y ′ . In group i ′ , by hypothesis there are |S i ′ (P)| -2V -v variables in Y, and by construction

In group 1, by hypothesis there are V -u + 1 variables in Y, and by construction 0 variables in Y ′ . For groups different than i ′ and 1 variables sets Y and Y ′ are identical by construction. We deduce

In the case v ≥ 1, as Y is a k-intersection of X , then Y ′ is at least a k + 1-intersection of X , which contradicts the rank of P.

In the case v = 0, by construction Y and Y ′ contain the same variables for group i. Also by construction, the weight of Y ′ is lighter or equals the weight of Y. Clearly, there is a

However, by construction S 1 (Q i ′ ) is empty, which cannot be possible as proven by Lemma 5.

A.5 Proof of Theorem 5

The following Lemma aims to use condition (iv) to provide feasible solutions for any variable in X ∈ χ (P). The idea is for these solutions to have at least all variables of Y U ′ to 1, with Y U ′ ∈ χ (R U ′ ). As these solutions have many variables to 1 in common, this will be convenient to prove them to be linearly independent in Theorem 5. Lemma 7. If the nested sub-patterns {R u , 1 ≤ u ≤ U ′ } verify (iv), then for any

Proof. Let P be a pattern verifying (iv). Let X ∈ χ (P) and

Firstly, by definition of R 1 , there is a feasible solution with all variables of Y 1 to 1, and

Secondly, we can define a recursive rule. Let x ij be a variable such that x ij ∈ X \ Y 1 . Suppose for x ij ′ the Lemma is verified for R u , with j ′ such that x ij ′′ / ∈ X , j ′ < j ′′ < j. In other word, there is a feasible solution with x ij ′ to 1 and all variables of Y u to 1. Note that x ij = 0 in this solution. By definition of the nested sub-pattern R u+1 , there is a feasible solution with all variables of Y u+1 and the u + 1 variables x ij ′ ∈ X \ Y u , j ′ ≤ j. We distinguish two cases:

The first case is |S i (R u+1 )| = |S i (R u )|. By hypothesis, there is a Z containing u variables of group i from X \ Y u , with x ij ′ ∈ Z, x ij / ∈ Z such that Z ∪ Y u is a k-intersection of X . As (iv) holds, then clearly there is Z ′ containing u + 1 variables of group i from X \ Y u+1 , such that Z ′ ∪ Y u+1 is a k-intersection of X . As x ij ′′ / ∈ X , j ′ < j ′′ < j, then x ij ∈ Z ′ and x ij ′′ / ∈ Z with j ′′ ≥ j. Hence the Lemma is verified for x ij .

The second case is |S i (R u+1 )| = |S i (R u )| -1. In which case, with Z ′ containing u + 1 variables of group i from X \ Y u+1 , Z ∪ Y u = Z ′ ∪ Y u+1 . Consequently x ij / ∈ Z.