1 Introduction

In this paper we study cutting-planes related to covers of 0–1 knapsack sets. A 0-1 knapsack set is a set of the form

$$\begin{aligned} K_{\text{ knap }}{:}{=} \{x \in \{0,1\}^n \mid a^T x \le b\}, \end{aligned}$$

with \((a, b) \in \mathbb {Z}^{n+1}_+\), and a cover is a subset \(C \subseteq \{1, \ldots , n\}\) such that \(\sum _{j \in C} a_j > b\). The associated cover inequality (CI)

$$\begin{aligned} \sum _{j \in C} x_j \le |C| - 1 \end{aligned}$$

is valid for the knapsack polytope \({\text {conv}}(K_{\text{ knap }})\) and is not satisfied by the incidence vector of C. There is a long and rich literature on (lifted) cover inequalities for the knapsack polytope [1, 10, 12, 16, 23], and the reader is directed to the recent survey [13] for a thorough introduction.

In this paper we consider the 0–1 multiple knapsack set

$$\begin{aligned} K = \{x \in \{0,1\}^n \mid Ax \le b\}, \end{aligned}$$
(1)

where \([A, b] \in \mathbb {Z}^{m \times (n+1)}_+\). A standard and computationally useful way for generating valid inequalities for \({\text {conv}}(K)\) is to generate lifted cover inequalities (LCIs) for the knapsack sets defined by the individual constraints of K [6]. In this way, the extensive literature regarding valid inequalities for \({\text {conv}}(K_{\text{ knap }})\) can be leveraged to solve integer programs whose feasible region is K. In contrast to \({\text {conv}}(K_{\text{ knap }})\), very little is known about the polyhedral structure of \({\text {conv}}(K)\). In this paper, we introduce a family of cutting-planes, called multi-cover inequalities (MCIs), that are derived by simultaneously considering multiple covers that satisfy a certain condition. The covers may come from any inequality in the formulation, as long as the weights appearing in the knapsack inequalities are totally-ordered. Moreover, when only a single cover is given, the associated MCI reduces to a CI.

More formally, we present a new approach to generate valid inequalities for a special multiple knapsack set, called the totally-ordered multiple knapsack set (TOMKS). The multiple knapsack set K in (1) is called a TOMKS if the column vectors \(\{A_{\cdot 1}, A_{\cdot 2}, \ldots , A_{\cdot n}\}\) of the constraint matrix \(A \in \mathbb {Z}^{m \times n}_+\) form a chain ordered by component-wise order. Without loss of generality we may assume \(A_{\cdot 1} \ge A_{\cdot 2} \ge \ldots \ge A_{\cdot n}\).

TOMKS can arise in the context of chance-constrained programming. Specifically, consider a knapsack constraint where the weights of the items (a) depend on a random variable \((\xi \)), and we wish to satisfy the chance constraint

$$\begin{aligned} \mathbb {P} \{ a(\xi )^T x \le \beta \} \ge 1-\epsilon , \end{aligned}$$
(2)

selecting a subset of items (\(x \in \{0,1\}^n\)) so that the likelihood that these items fit into the knapsack is sufficiently high. In the scenario approximation approach proposed in [5, 18], an independent Monte Carlo sample of N realizations of the weights \((a(\xi ^1), \ldots a(\xi ^N))\) is drawn and the deterministic constraints

$$\begin{aligned} a(\xi ^i)^T x \le \beta \quad \forall i=1\ldots ,N \end{aligned}$$
(3)

are enforced. In [17] it is shown that for every \(\delta \in (0,1)\), if the sample size N is sufficiently large:

$$\begin{aligned} N \ge \frac{1}{2 \epsilon ^2} \left( \log \left( \frac{1}{\delta } \right) + n \log (2) \right) , \end{aligned}$$

then any feasible solution to (3) satisfies the constraint (2) with probability at least \(1-\delta \). If the random weights of the items \(a_1(\xi ), a_2(\xi ), \ldots a_n(\xi )\) are independently distributed with means \(\mu _1 \ge \mu _2 \ldots \ge \mu _n\), then the feasible region in (3) may either be a TOMKS, or the constraints can be (slightly) relaxed to obey the ordering property.

The TOMKS may arise in more general situations as well. For a general binary set, if two knapsack inequalities \(a_1^T x \le b_1\) and \(a_2^T x \le b_2\) have non-zero coefficients in few common variables, their intersection may be totally-ordered, and the MCI would be applicable in this case. In the general case, if variables are fixed to zero or one, the induced face may be a TOMKS, and the resulting inequalities could then be lifted to be valid for the original set. In the special case where the multiple covers come from the same knapsack set, the MCI can also produce interesting inequalities. For example, the well-known (1, k)-configuration inequalities for \({\text {conv}}(K_{\text{ knap }})\) [20] are a special case of MCI where two covers come from the same inequality and have particular structure (see Proposition 2). We also give an example where a facet of \({\text {conv}}(K_{\text{ knap }})\) generated by a recent lifting procedure described by Letchford and Souli [16] is a MCI.

Interestingly, as observed by Laurent and Sassano [15], the convex hull of a TOMKS can be exactly characterized by all the associated minimal CIs if and only if the set of minimal covers has no minor isomorphic to \(J_q = \{\{2,\ldots , q\}, \{1,i\} \text { for } i = 2, \ldots , q\}\) with \(q \ge 3\), where the definition of minor can be found in Sect. 4. When the set of minimal covers does have a minor isomorphic to \(J_q\), our new inequalities are important. In particular, when the minimal cover set is exactly \(J_q\), \({\text {conv}}(K)\) can be fully described by bound constraints, CIs, and a single MCI.

MCIs are generated by a simple algorithm (Algorithm 1) that takes as input a special family of covers \(\mathscr {C}= \{C_1, C_2, \ldots C_k\}\) that obeys a certain maximality criterion (see Definition 3). For many types of cover-families \(\mathscr {C}\), the MCI may be given in closed-form. We also give a condition under which an MCI defines a facet of \({\text {conv}}(K)\) in Sect. 4, as well as a condition for the MCIs to fully describe \({\text {conv}}(K)\).

MCIs may be generated by simultaneously considering multiple knapsack inequalities defining K. Another mechanism to generate inequalities taking into account information from multiple constraints of the formulation is to aggregate inequalities together, forming the set

$$\begin{aligned} \mathcal {A}(A,b) {:}{=} \bigcap _{\lambda \in \mathbb {R}^m_+} {\text {conv}}(\{x \in \{0,1\}^n \ \mid \lambda ^T A x \le \lambda ^T b \}. \end{aligned}$$

Inequalities valid for \(\mathcal {A}(A,b)\) are known as aggregation cuts, and have been shown to be quite powerful from both an empirical [9] and theoretical [4] viewpoint. The well-known Chvátal-Gomory (CG) cuts, lifted cover inequalities, and weight inequalities [22] are all aggregation cuts. In Example 6, we show that MCIs are not aggregation cuts. Furthermore, in Example 7, we show that MCIs cannot be obtained as a (rank-1) Chvátal-Gomory cut from the linear system consisting of all minimal cover inequalities from K.

The paper is structured as follows: In Sect. 2, we define a certain type of dominance relationship between covers that is necessary to introduce the MCIs. The MCIs are defined in Sect. 3, where we also provide some examples to demonstrate that MCIs are not dominated by other well-known families of cutting-planes. Utilizing a combinatorial property of the multi-cover, in Sect. 3.2 we introduce a strengthening procedure for MCI. In Sect. 4 we provide a sufficient condition for the MCI to be facet-defining for \({\text {conv}}(K)\), and we show a family of instances where the MCI inequalities are the only non-trivial inequalities besides cover inequalities for \({\text {conv}}(K)\). Lastly in Sects. 5 and 6 we discuss the separation problem for MCIs, and we present numerical experiments showing the additional integrality gap that can be closed by MCIs when compared to CIs.

Next, we detail the differences between this paper and the preliminary IPCO version [7]. First, the MCI defined in [7] is referred to as the simple-MCI in this paper, while the MCI defined in this paper refers to a larger, more general, class of inequalities. This family contains both the simple-MCI and the antichain multi-cover inequalities AMCI in [7] as special cases. For that reason, the AMCI section in [7] is not present in this paper. Moreover, in Sect. 3 we introduce an analogous concept of extended cover inequality (ECI) for MCI, namely the extended MCI, and in Sect. 4 we provide a special scenario for MCIs to fully describe \({\text {conv}}(K)\). Lastly, Sects. 5 and 6 contain new results about separation and numerical experiments.

To conclude this section, we introduce some notation that will be used in the rest of the paper. For a positive integer n, we denote by \([n] {:}{=} \{1,\dots ,n\}\). The incidence vector of a set \(S \subseteq [n]\) is denoted by \(\chi ^S\). Therefore, given a TOMKS K, we say that a set \(S \subseteq [n]\) is a cover for K if \(\chi ^S \notin K\). For a vector \(x \in \mathbb {R}^n\) and a set \(S \subseteq [n]\), we define \(x(S) {:}{=} \sum _{i \in S} x_i\). This in particular implies \(x(\emptyset ) = 0.\) We denote the power set of a set S by \(2^S\), which is the set of all subsets of S. Lastly, we denote by \(e^j\) the j-th unit vector of the ambient space.

2 A dominance relation

In this section we define a dominance relation between covers and show some of its properties. Throughout this section, for any set \(S \subseteq [n]\) and \(i \in [|S|]\), we denote by \(S_{(i)}\) the ith smallest element in S.

Definition 1

(Dominance) For \(S, T \subseteq [n]\), we say that S dominates T and write \(S \triangleright T\), if \(|S| \ge |T|\) and \(S_{(i)} \le T_{(i)}\) for \(i=1, \ldots , |T|\).

The dominance relation in Definition 1 is reflexive, antisymmetric, and transitive, so \((2^{[n]}, \triangleright )\) forms a partially ordered set. For two sets \(S, T \subseteq [n]\), we say S and T are comparable if \(S \triangleright T\) or \(T \triangleright S\). The dominance relation has a natural use in the context of covers. In fact, if \(C_2\) is a cover for a TOMKS K and \(C_1\) dominates \(C_2\), then \(C_1\) is also a cover for K. By Definition 1, we have the following equivalent statement.

Observation 1

For \(S, T \subseteq [n]\), we have \(S \triangleright T\) if and only if for every \(x \in \mathbb {R}\),

$$\begin{aligned} |\{s \in S \mid s \le x\}| \ge |\{t \in T \mid t \le x\}|. \end{aligned}$$

Proof

First, we show the “only if” direction. Arbitrarily pick \(x \in \mathbb {R}\) and let \(\kappa {:}{=} |\{t \in T \mid t \le x\}|\). If \(\kappa = 0\) then we clearly have \(|\{s \in S \mid s \le x\}| \ge 0\). If \(\kappa \ge 1\), then from \(S \triangleright T\), we know that the \(\kappa \)th smallest element of S is not larger than the \(\kappa \)th smallest element of T, which is also not larger than x. Hence we obtain that \(|\{s \in S \mid s \le x\}| \ge \kappa \).

Now we show the “if” direction. By picking x sufficiently large, we have \(|S| \ge |T|\). Now we assume for a contradiction that \(S_{(i)} > T_{(i)}\) for some \(i \in [|T|]\). Then by picking \(x {:}{=} (S_{(i)} + T_{(i)})/2\), we obtain \(|\{s \in S \mid s \le x\}| \le i-1 < i \le |\{t \in T \mid t \le x\}|\), which violates the initial condition. \(\square \)

Next we present two technical lemmas about dominance which follow from Observation 1.

Lemma 1

Let \(S, T \subseteq [n]\) with \(S \ne T\). Then for every \(S' \subseteq S \cap T\), we have \(S \triangleright T\) if and only if \(S \setminus S' \triangleright T \setminus S'\).

Proof

By Observation 1, it suffices to show that, for every \(x \in \mathbb {R}\), we have \(|\{s \in S \mid s \le x\}| \ge |\{t \in T \mid t \le x\}|\) if and only if \(|\{s \in S \setminus S' \mid s \le x\}| \ge |\{t \in T \setminus S' \mid t \le x\}|\).

Note that for every \(x \in \mathbb {R}\), we have

$$\begin{aligned}&|\{s \in S \mid s \le x\}| = |\{s \in S' \mid s \le x\}| + |\{s \in S \setminus S' \mid s \le x\}|, \\&|\{t \in T \mid t \le x\}| = |\{t \in S' \mid t \le x\}| + |\{t \in T \setminus S' \mid t \le x\}|. \end{aligned}$$

This completes the proof of the lemma. \(\square \)

Lemma 2

Let \(S \subseteq [n]\) and let \(S ,T \subseteq S'\). Then, \(S\triangleright T\) if and only if \(S' \setminus T \triangleright S' \setminus S\).

Proof

By Observation 1, it suffices to show that, for every \(x \in \mathbb {R},\) we have \(|\{s \in S \mid s \le x\}| \ge |\{t \in T \mid t \le x\}|\) if and only if \(|\{s \in S' \setminus S \mid s \le x\}| \le |\{t \in S' \setminus T \mid t \le x\}|\).

Note that for any \(x \in \mathbb {R}\), we have

$$\begin{aligned} |\{s \in S' \mid s \le x\}|&= |\{s \in S' \setminus S \mid s \le x\}| + |\{s \in S \mid s \le x\}|, \\&= |\{t \in S' \setminus T \mid t \le x\}| + |\{t \in T \mid t \le x\}|. \end{aligned}$$

This completes the proof of the lemma. \(\square \)

3 Multi-cover inequalities and variation

Throughout this section, we consider a TOMKS \(K {:}{=} \{x \in \{0,1\}^n \mid Ax \le b\}\), and we introduce the multi-cover inequalities (MCIs), which form a novel family of valid inequalities for K. Each MCI can be obtained from a special family of covers \(\{C_1, \ldots , C_k\}\) for K that we call a multi-cover. In order to define a multi-cover, we first introduce the discrepancy family.

Definition 2

(Discrepancy family) For a family of sets \(\mathscr {C}= \{C_1, \ldots , C_k\}\), we say that \(\{C_1 \setminus \cap _{h=1}^k C_h, \ldots , C_k \setminus \cap _{h=1}^k C_h\}\) is the discrepancy family of \(\mathscr {C}\), and we denote it by \({\mathcal {D}}(\mathscr {C})\).

Now we can define the concept of a multi-cover.

Definition 3

(Multi-cover) Let \(\mathscr {C}\) be a family of covers for K. We then say that \(\mathscr {C}\) is a multi-cover for K if for any set \(T \subseteq \cup _{D \in {\mathcal {D}}(\mathscr {C})} D\), there exists some \(D' \in \mathcal {D}(\mathscr {C})\) such that \(T \triangleright D'\) or \(D' \triangleright T\).

Example 1

Consider the TOMKS:

$$\begin{aligned} K{:}{=} \{x \in \{0,1\}^5 \mid \&19 x_1 + 11x_2 + 5x_3 + 4x_4 + 2x_5 \le 31, \\&16 x_1 + 10 x_2 + 7 x_3 + 5 x_4 + 3 x_5 \le 30\}. \end{aligned}$$

We have that \(\mathscr {C}= \{C_1, C_2\} {:}{=} \{\{1,2,5\},\{1,3,4,5\}\}\) is a multi-cover. In fact, it is simple to check that \(C_1\) and \(C_2\) are covers for K. Furthermore, the discrepancy family of \(\mathscr {C}\) is \(\mathcal {D}(\mathscr {C}) = \{\{2\}, \{3,4\}\}\), and for any \(T \subseteq \{2,3,4\}\), if \(|T| = 1\) we have \(\{2\} \triangleright T\), while if \(|T| \ge 2\) we have \(T \triangleright \{3,4\}\). \(\diamond \)

For a given family of covers \(\{C_1, \ldots , C_k\}\) for K, throughout this paper, for ease of notation we define \(C_0 {:}{=} \cap _{h=1}^k C_h\), \(C {:}{=} \cup _{h=1}^k C_h\), \({\bar{C}}_h {:}{=} C \setminus C_h\) for \(h \in [k]\), and similarly \({\bar{T}} {:}{=} C \setminus T\) for any \(T \subseteq C\).

We are now ready to introduce our multi-cover inequalities for K. These inequalities are defined by the following algorithm.

figure a

We remark that in Algorithm 1, in the case where we take the minimum or maximum over an empty set (see Step 4 and 6), the corresponding minimum or maximum should be set to zero. It is worth noting that, within this Algorithm 1, once a value is assigned to some \(\alpha _i\) at At Step 2 and 6, it will never change throughout the proceeding of this algorithm.

For the above algorithm, we have the following easy observation.

Observation 2

Given a multi-cover \(\{C_h\}_{h=1}^k\), Algorithm 1 performs a number of operations that is polynomial in |C| and k. Furthermore, \({\text {supp}}(\alpha ) = C\).

At Step 4 and 6 of Algorithm 1, when the \(\ge \) is fixed to \(=\), the obtained MCI is called the simple-MCI, which was given in [7]. Note that given a multi-cover, we can obtain several MCIs, but only one simple-MCI.

Definition 4

(simple-MCI) Given a multi-cover \(\{C_1, \ldots , C_k\}\) and one of its MCIs \(\alpha ^T x \le \beta \), if for every \(i \in C \setminus C_0\), \(\alpha _i = \max _{h \in [k]: i \in C_h} \max _{\ell \in {\bar{C}}_h: \ell >i} \alpha _\ell + 1\) and for every \(j \in C_0\), \(\alpha _j = \min _{h \in [k]} \max \big \{ \max _{\ell <j, \ell \in {\bar{C}}_h} \alpha _\ell , \sum _{t>j, t \in {\bar{C}}_h} \alpha _t + 1 \big \}\), then such MCI \(\alpha ^T x \le \beta \) is called a simple-MCI (S-MCI).

The main result of this section is that, given a multi-cover for K, then any of its MCI is valid for \({\text {conv}}(K)\). Before presenting the theorem, we will need the following auxiliary result.

Proposition 1

Let \(\{C_h\}_{h=1}^k\) be a multi-cover and let \(\alpha ^T x \le \beta \) be one of its associated MCIs. If there exists \(T \subseteq C \setminus C_0\) with \(T \notin \{{\bar{C}}_h\}_{h=1}^k\) and \(T \triangleright {\bar{C}}_{h'}\) for some \(h' \in [k]\), then \(\alpha (T) > \alpha ({\bar{C}}_{h'})\).

We remark that Proposition 1 does not depend on the specific property of multi-covers. That is, it holds for any family of covers.

Proof

Let T and \({\bar{C}}_{h'}\) be the sets as assumed in the statement of this proposition, with \(T \triangleright {\bar{C}}_{h'}\). Let \(T_0 {:}{=} T \cap {\bar{C}}_{h'}\), \(T_1 {:}{=} T \setminus T_0,\) and \(T_2{:}{=} {\bar{C}}_{h'} \setminus T_0\). Then \(T = T_0 \cup T_1\), \({\bar{C}}_{h'} = T_0 \cup T_2\). Since \(T \ne {\bar{C}}_{h'}\) and \(T \triangleright {\bar{C}}_{h'}\), then we know \(T_1 \ne \emptyset \). By Lemma 1, we know that \(T_1 \triangleright T_2\). If \(T_2 = \emptyset \), then \(\alpha (T) = \alpha (T_0) + \alpha (T_1) > \alpha (T_0) = \alpha ({\bar{C}}_{h'})\). Hence we assume \(T_2 \ne \emptyset \). Let \(T_2{:}{=} \{j_1, \ldots , j_t\}\). Since \(T_1 \triangleright T_2\) and \(T_1 \cap T_2 = \emptyset \), we know there exists \(\{k_1, \ldots , k_t\} \subseteq T_1\) such that \(k_1< j_1, \ldots , k_t < j_t\).

W.l.o.g., consider \(k_1\) and \(j_1\). By definition, we have \(k_1 < j_1, k_1 \notin {\bar{C}}_{h'}, j_1 \in {\bar{C}}_{h'}\), or equivalently: \(k_1 < j_1\), \(k_1 \in C_{h'}\), \(j_1 \in {\bar{C}}_{h'}\). Therefore, \(j_1 \in \{\ell \mid \ell > k_1, \ell \in {\bar{C}}_{h'}, k_1 \in C_{h'}\}\). By construction of MCI, we know that \(\alpha _{k_1} > \alpha _{j_1}\). For the remaining \(k_2\) and \(j_2, \ldots , k_t\) and \(j_t\), the same argument yields \(\alpha _{k_2}> \alpha _{j_2}, \ldots , \alpha _{k_t} > \alpha _{j_t}\).

Therefore, \(\alpha (T) = \alpha (T_1) + \alpha (T_0) \ge \alpha _{k_1} + \ldots + \alpha _{k_t} + \alpha (T_0) > \alpha _{j_1} + \ldots + \alpha _{j_t} + \alpha (T_0) = \alpha (T_2) + \alpha (T_0) = \alpha ({\bar{C}}_{h'})\), which concludes the proof. \(\square \)

Now we are ready to present the first main result of this paper.

Theorem 1

Given a multi-cover \(\{C_h\}_{h=1}^k\) for a TOMKS K, then the corresponding MCIs are valid for \({\text {conv}}(K)\).

Proof

Since \({\text {supp}}(\alpha ) = C\), in order to show that \(\alpha ^T x \le \beta \) is valid for \({\text {conv}}(K)\), it suffices to show that, for any \(T \subseteq C\) with \(\alpha (T) \ge \beta + 1\), T must be a cover for K. Note that by Step 7 of Algorithm 1, we have \(\beta + 1= \max _{h=1}^k \alpha (C_h)\), and for any \(T_1, T_2 \subseteq C\), \(\alpha (T_1) \ge \alpha (T_2)\) is equivalent to \(\alpha ({\bar{T}}_1) \le \alpha ({\bar{T}}_2)\). Therefore from Lemma 2, it suffices to show that, for any \(T \subseteq C\) with \(\alpha ({\bar{T}}) \le \min _{h=1}^k\alpha ({\bar{C}}_h)\), there exists some \(h^* \in [k]\) such that \({\bar{C}}_{h^*} \triangleright {\bar{T}}\). We will assume that \(T \notin \{C_h\}_{h=1}^k\) since otherwise \({\bar{C}}_{h^*} \triangleright {\bar{T}}\) trivially holds. In the following, the proof is subdivided into two cases, depending on whether \({\bar{T}} \cap C_0 = \emptyset \) or not.

In the first case we assume \({\bar{T}} \cap C_0 = \emptyset \). In this case, we have \(C_0 \subseteq T\). By Definition 3 of multi-cover, we know there must exist \(h^* \in [k]\) such that either \(C_{h^*} \setminus C_0 \triangleright T \setminus C_0\), or \( T \setminus C_0 \triangleright C_{h^*} \setminus C_0\). By the above assumption \(C_0 \subseteq T\) and Lemma 1, we know that either \(C_{h^*} \triangleright T\) or \(T \triangleright C_{h^*}\). If \(T \triangleright C_{h^*}\), then Lemma 2 implies \({\bar{C}}_{h^*} \triangleright {\bar{T}}\), which completes the proof. So we assume \(C_{h^*} \triangleright T\), or equivalently, \({\bar{T}} \triangleright {\bar{C}}_{h^*}\). Since \({\bar{T}} \subseteq C \setminus C_0\) and \({\bar{T}} \ne {\bar{C}}_{h^*}\), by Proposition 1 we obtain that \(\alpha ({\bar{T}}) > \alpha ({\bar{C}}_{h^*})\), and this contradicts the assumption that \(\alpha ({\bar{T}}) \le \min _{h=1}^k\alpha ({\bar{C}}_h)\). This concludes our first case.

In the second case we assume \({\bar{T}} \cap C_0 \ne \emptyset \). In this case, it suffices to construct \({\bar{D}} \subseteq C\) with \({\bar{D}} \cap C_0 = \emptyset \), \(\alpha ({\bar{D}}) \le \alpha ({\bar{T}})\), and \({\bar{D}} \triangleright {\bar{T}}\). Then since \(\alpha ({\bar{T}}) \le \min _{h=1}^k\alpha ({\bar{C}}_h)\), we have \(\alpha ({\bar{D}}) \le \min _{h=1}^k\alpha ({\bar{C}}_h)\) where \({\bar{D}} \cap C_0 = \emptyset \). According to our discussion in the previous case, we know that there exists some \(h^* \in [k]\) such that \({\bar{C}}_{h^*} \triangleright {\bar{D}}\), which implies \({\bar{C}}_{h^*} \triangleright {\bar{T}}\) since \(\triangleright \) forms a partial order, and the proof is completed.

Thus, in order to conclude our second case, we now show how to construct \({\bar{D}}\) as discussed above. We arbitrarily pick \(t^* \in {\bar{T}} \cap C_0\). Then by Step 6 of Algorithm 1, we know that there exists \(h^* \in [k]\), such that:

$$\begin{aligned} \alpha _{t^*} \ge \max \left\{ \max _{\ell <t^*, \ell \in {\bar{C}}_{h^*}} \alpha _\ell , \sum _{t>t^*, t \in {\bar{C}}_{h^*}} \alpha _t + 1 \right\} . \end{aligned}$$

If \(\{\ell \in {\bar{C}}_{h^*} \mid \ell < t^*\} \subseteq {\bar{T}}\), then we have \(\alpha ({\bar{T}}) \ge \sum _{\ell < t^*, \ell \in {\bar{C}}_{h^*}} \alpha _\ell + \alpha _{t^*}\), which is at least \(\sum _{\ell < t^*, \ell \in {\bar{C}}_{h^*}} \alpha _\ell + \sum _{t>t^*, t \in {\bar{C}}_{h^*}} \alpha _t + 1\). Since \(t^* \notin {\bar{C}}_{h^*}\), we know that \(\sum _{\ell < t^*, \ell \in {\bar{C}}_{h^*}} \alpha _\ell + \sum _{t>t^*, t \in {\bar{C}}_{h^*}} \alpha _t + 1 = \alpha ({\bar{C}}_{h^*}) + 1\). Hence \(\alpha ({\bar{T}}) > \alpha ({\bar{C}}_{h^*})\), and this contradicts the initial assumption \(\alpha ({\bar{T}}) \le \min _{h=1}^k\alpha ({\bar{C}}_h)\). Therefore we can find some \(\ell ^* \in {\bar{C}}_{h^*}, \ell ^* < t^*\) such that \(\ell ^* \notin {\bar{T}}\). Now define \({\bar{D}}{:}{=} {\bar{T}} \cup \{\ell ^*\} \setminus \{t^*\}\). Since \(\ell ^* < t^*\), clearly \({\bar{D}} \triangleright {\bar{T}}\). Also \(\alpha ({\bar{T}}) - \alpha ({\bar{D}}) = \alpha _{t^*} - \alpha _{\ell ^*}\), since \(\alpha _{t^*} \ge \max _{\ell <t^*, \ell \in {\bar{C}}_{h^*}} \alpha _\ell \), we know that \(\alpha ({\bar{T}}) - \alpha ({\bar{D}}) \ge 0\). If \({\bar{D}} \cap C_0 = \emptyset \), then we are done. Otherwise, we can replace \({\bar{T}}\) by \({\bar{D}}\), consider any index in \({\bar{D}} \cap C_0\) and apply once more the above discussion. Every time we are able to obtain a set \({\bar{D}}\) with \(|{\bar{D}} \cap C_0|\) decreased by 1. At the end we will obtain a set \({\bar{D}}\) with the desired property: \({\bar{D}} \cap C_0 = \emptyset \), \(\alpha ({\bar{D}}) \le \alpha ({\bar{T}})\), and \({\bar{D}} \triangleright {\bar{T}}\). This concludes our second case.

From the discussion of the above two cases, we have concluded the proof that the MCI \(\alpha ^T x \le \beta \) is a valid inequality for \({\text {conv}}(K)\). \(\square \)

3.1 Illustrative examples

In this section, we provide some examples to showcase the novelty of our cut-generating procedure. We start with a simple example to help understand Algorithm 1.

Example 2

Consider a multi-cover \(\{C_1, C_2\} = \{\{1,2,3,4\}, \{1,2,4,5,6,7\}\}\), here \(C = [7]\), \(C_0 = \{1,2,4\}\), and \(\{i_1, i_2, i_3, i_4\} = \{3,5,6,7\}\). Next, we compute the coefficients of one particular MCI.

The coefficient \(\alpha _7\) is initialized as 1. For \(t=3\), the coefficient \(\alpha _6 \ge \max _{h \in [2]: 6 \in C_h} \max _{\ell \in \bar{C}_h: \ell > 6} \alpha _\ell + 1 = 1\), and we pick \(\alpha _6 = 1\). Similarly, for \(t=2\), we pick \(\alpha _5 = 1\). For \(t=1\), we have \(\alpha _3 \ge \max _{h \in [2]: 3 \in C_h} \max _{\ell \in \bar{C}_h: \ell > 3} \alpha _\ell + 1 = 2\), and we pick \(\alpha _3 = 3\). For \(j \in C_0 = \{1,2,4\}\), from Step 6, we have:

$$\begin{aligned}&\alpha _1 \ge \min _{h \in [2]} \max \{\max _{\ell< 1, \ell \in \bar{C}_h} \alpha _\ell , \sum _{\ell> 1, \ell \in \bar{C}_h} \alpha _\ell + 1\} = 4,\\&\alpha _2 \ge \min _{h \in [2]} \max \{\max _{\ell< 2, \ell \in \bar{C}_h} \alpha _\ell , \sum _{\ell> 2, \ell \in \bar{C}_h} \alpha _\ell + 1\} = 4,\\&\alpha _4 \ge \min _{h \in [2]} \max \{\max _{\ell < 4, \ell \in \bar{C}_h} \alpha _\ell , \sum _{\ell > 4, \ell \in \bar{C}_h} \alpha _\ell + 1\} = 3. \end{aligned}$$

Here we pick \(\alpha _j\) as small as possible, for \(j \in C_0\). Hence \(\alpha = (4,4,3,3,1,1,1)\), and from Step 7, we have \(\beta = \max _{h \in [2]}\alpha (C_h) - 1 = 13\). Therefore, we obtain the MCI \(4x_1 + 4x_2 + 3x_3 + 3x_4 + x_5 + x_6 + x_7 \le 13\). Note that such MCI is not an S-MCI, because at Step 4 for \(t=1\), we selected \(\alpha _{i_1} = 3\) instead of the lower bound 2. \(\diamond \)

In fact, for some multi-covers with a specific discrepancy family, we are able to write some MCIs in closed form. The next example can be seen as a generalization of the multi-cover in Example 2.

Example 3

Consider \(\{C_1, C_2\}\) with discrepancy family \(\{\{i_1\}, \{i_2, \ldots , i_t\}\}\), with \(i_1< \ldots < i_{t}\) and \(t \ge 3\). Here the family of covers \(\{C_1, C_2\}\) is a multi-cover, and the following inequality is one of its associated MCIs:

$$\begin{aligned}&\sum _{i<i_1, i \in C} t x_i + \sum _{i_1 \le i< i_2, i \in C} (t-1) x_i\\&\qquad + \sum _{\ell =3}^{t} \sum _{i_{\ell -1}< i < i_\ell , i \in C} (t-\ell +2) x_i + \sum _{\ell =2}^t x_{i_\ell } + \sum _{i>i_t, i \in C} x_i \le \beta , \end{aligned}$$

where \(\beta \) is the left-hand-side term evaluated at the point \(\chi ^{C_1} (\text {or } \chi ^{C_2})\) minus 1. \(\diamond \)

In the next example we consider the S-MCI formula for another multi-cover with a specific structure.

Example 4

Consider \(\{C_1, C_2\}\) with discrepancy family \(\{\{i_1, i_{t+1}\}, \{i_2, \ldots , i_t\}\}\) for some \(t \ge 3\), with \(i_1< \ldots < i_{t+1}\). It is simple to verify that \(\{C_1, C_2\}\) is a multi-cover, and the obtained S-MCI is:

$$\begin{aligned} \begin{aligned}&\sum _{i<i_1, i \in C} (2t - 1) x_i + \sum _{i_1 \le i< i_2, i \in C} (2t - 3) x_i + \sum _{\ell =3}^{t} \sum _{i_{\ell -1}< i< i_\ell , i \in C} (2t-2\ell +3) x_i + \\&\qquad + \sum _{\ell =2}^t 2 x_{i_\ell } + \sum _{i_t< i< i_{t+1}, i \in C} 2 x_i + x_{i_{t+1}} + \sum _{i > i_{t+1}, i \in C} 2x_i \le \beta , \end{aligned} \end{aligned}$$

where \(\beta \) is the left-hand-side term evaluated at the point \(\chi ^{C_1} (\text {or }\chi ^{C_2})\) minus 1. \(\diamond \)

Next, we provide another simple example of S-MCI.

Example 5

Consider \(\{C_1, C_2, C_3\}\) with discrepancy family \(\{\{i_1, i_3\},\{i_1, i_4, i_5\},\) \(\{i_2, i_3, i_5\}\}\), with \(i_1< \ldots < i_{5}\). Here the family of covers \(\{C_1, C_2, C_3\}\) is a multi-cover, and the obtained S-MCI is:

$$\begin{aligned} \begin{aligned}&\sum _{i< i_1, i \in C} 5x_i + \sum _{i_1 \le i< i_2, i \in C} 3x_i + 2 x_{i_2} + \sum _{i_2< i< i_3, i \in C} 3x_i + 2x_{i_3} + \\&\qquad + \sum _{i_3< i< i_4, i \in C} 2x_i + x_{i_4} + \sum _{i_4< i < i_5, i \in C} 2x_i + x_{i_5} + \sum _{i > i_5, i \in C} 2x_i \le \beta , \end{aligned} \end{aligned}$$
(4)

where \(\beta \) is the left-hand-side term evaluated at the point \(\chi ^{C_1} (\text {or } \chi ^{C_2}, \chi ^{C_3})\) minus 1. \(\diamond \)

Next, we present some illustrative examples to showcase the utility of MCIs. The first example shows that, unlike LCIs or CG cuts, S-MCIs are not aggregation cuts for the original linear system.

Example 6

Consider the TOMKS K and the multi-cover \(\{C_1, C_2\}\) defined in Example 1. Note that point \(\chi ^{C_1}\) only violates the first knapsack constraint, and point \(\chi ^{C_2}\) only violates the second knapsack constraint. The associated S-MCI is

$$\begin{aligned} 3 x_ 1 + 2 x_2 + x_3 + x_4 + x_5 \le 5, \end{aligned}$$
(5)

and (5) is violated by both \(\chi ^{C_1}\) and \(\chi ^{C_2}\).

One can further check that the S-MCI (5) is facet-defining for \({\text {conv}}(K)\). In fact, \({\text {conv}}(K)\) can be exactly characterized by this S-MCI, along with the bound constraints \(0 \le x_i \le 1\), \(\forall i \in [5]\), and the following four CIs: \(x_1 + x_2 + x_5 \le 2\), \(x_1 + x_2 + x_4 \le 2\), \(x_1 + x_2 + x_3 \le 2\), \(x_1 + x_3 + x_4 + x_5 \le 3\).

Now consider an aggregation of the knapsack inequalities for K given by inequality \(\lambda _1 (19,11,5,4,2)^T x + \lambda _2 (16,10,7,5,3)^T x \le 31\lambda _1 + 30 \lambda _2\), where \(\lambda _1, \lambda _2 \ge 0\). For any choice of \(\lambda _1 \ge 0, \lambda _2 \ge 0\), it can be verified that \(C_1\) and \(C_2\) cannot both be covers for the knapsack set given by this single inequality, so any aggregation cut for K can cut off at most one vector among \(\chi ^{C_1}\) and \(\chi ^{C_2}\). Therefore, the inequality (5) is not an aggregation cut. In some cases, it may be possible to obtain an S-MCI as a CG cut for the original linear system augmented with its minimal cover inequalities. In this example, consider the set

$$\begin{aligned} K_{CI} := \{x \in \{0,1\}^5 \mid \&19 x_1 + 11x_2 + 5x_3 + 4x_4 + 2x_5 \le 31, \\&16 x_1 + 10 x_2 + 7 x_3 + 5 x_4 + 3 x_5 \le 30,\\&x_1 + x_2 + x_3 \le 2, x_1 + x_2 + x_4 \le 2,\\&x_1 + x_2 + x_5 \le 2, x_1 + x_3 + x_4 + x_5 \le 3 \}. \end{aligned}$$

The inequality (5) is indeed a CG cut with respect to \(K_{CI}\), as shown by multipliers \(\frac{1}{12} \cdot (19, 11, 5,4,2) + \frac{1}{4} \cdot (1,1,1,0,0) + \frac{1}{3} \cdot (1,1,0,1,0) + \frac{1}{2} \cdot (1,1,0,0,1) + \frac{1}{3} \cdot (1,0,1,1,1) = (3,2,1,1,1)\), \(\frac{1}{12} \cdot 31 + \frac{1}{4} \cdot 2 + \frac{1}{3} \cdot 2 + \frac{1}{2} \cdot 2 + \frac{1}{3} \cdot 3 = 5.75.\) Hence \((3,2,1,1,1)^T x \le \lfloor 5.75 \rfloor = 5\) is a CG cut for \(K_{CI}\). \(\diamond \)

Example 6 demonstrates that MCIs can be obtained from multiple knapsack sets simultaneously. Specifically, the inequality (5) is facet-defining for \({\text {conv}}(K)\), but it is neither valid for \(\{x \in \{0,1\}^5 \mid 19 x_1 + 11x_2 + 5x_3 + 4x_4 + 2x_5 \le 31 \}\) nor for \(\{x \in \{0,1\}^5 \mid 16 x_1 + 10 x_2 + 7 x_3 + 5 x_4 + 3 x_5 \le 30\}\). Example 6 also shows that an S-MCI can be a CG cut for the linear system given by the original knapsack constraints along with all their minimal cover inequalities. In the next example, we will see that this is not always the case.

Example 7

Consider the following TOMKS:

$$\begin{aligned} K{:}{=} \{x \in \{0,1\}^8 \mid \&28 x_1 + 24x_2+20x_3+19x_4+15x_5+10x_6+7x_7+6x_8 \le 96, \\&27x_1+24x_2+21x_3+19x_4+13x_5+12x_6+7x_7+4x_8 \le 96\}. \end{aligned}$$

Define covers \(C_1 = \{2,3,4,5,6,7,8\}\), \(C_2 = \{1,3,4,5,6,8\},\) \(C_3 = \{1,2,3,5,6\}\), \(C_4 = \{1,2,3,5,7,8\}\). We have \(C = [8]\), \(C_0 = \{3,5\}\), and the discrepancy family is \(\mathcal {D}(\mathscr {C}) = \{\{2,4,6,7,8\}, \{1,4,6,8\}, \{1,2,6\}, \{1,2,7,8\}\} =: \{D_1, D_2, D_3, D_4\}\).

First, we verify that \(\mathscr {C}\) is a multi-cover. For any set \(T \subseteq C \setminus C_0\) and \(T \notin \mathcal {D}(\mathscr {C})\), if \(1 \in T\), \(|T| = 2\), then T is clearly dominated by either \(D_2, D_3\) or \(D_4\). If \(1 \in T\), \(|T| = 3\), then either \(T \triangleright D_3\) or \(D_3 \triangleright T\). If \(1 \in T\), \(|T| = 4\), then T must be comparable with \(D_2\) or \(D_3\). If \(1 \in T\), \(|T| = 5\), then \(T \triangleright D_1\). If \(1 \notin T,\) then clearly \(D_1 \triangleright T\) since \(T \subseteq D_1\). Hence we have shown that for any \(T \subseteq C \setminus C_0\) and \(T \notin \mathcal {D}(\mathscr {C})\), T must be comparable with some set in \(\mathcal {D}(\mathscr {C})\). Therefore \(\mathscr {C}\) is a multi-cover.

When Algorithm 1 is applied to \(\mathscr {C}\), we obtain the S-MCI \(\alpha ^T x \le \beta \) given by

$$\begin{aligned} 4x_1+3x_2+3x_3+2x_4+3x_5+2x_6+x_7+x_8 \le 14, \end{aligned}$$
(6)

and it can be shown that (6) is facet-defining for \({\text {conv}}(K)\).

Consider the linear system given by all the minimal cover inequalities for K, as well as the original two linear constraints. We refer to this linear system as \(K_{CI}\), which consists of 30 inequalities. Solving \(\max \{\alpha ^T x \mid x \in K_{CI}\}\) gives the optimal value 15.307, so the corresponding CG cut with respect to \(K_{CI}\) with the same left-hand-side coefficient vector \(\alpha \) is \(\alpha ^T x \le 15\), which is weaker than inequality (6). \(\diamond \)

Even when the cover-family consists of covers all coming from the same knapsack inequality, the MCI can produce interesting inequalities. In the next example, we show an MCI that cannot be obtained as an LCI, regardless of the lifting order.

Example 8

(Example 3 in [16]) Let \(K {:}{=} \{x \in \{0,1\}^5 \mid 10 x_1 + 7 x_2 + 7 x_3 + 4 x_4 + 4 x_5 \le 16\}\), and consider the multi-cover \(\mathscr {C}{:}{=} \{ \{1, 3\}, \{1, 4, 5\}, \{2, 3, 5\}\}\). From inequality (4) of Example 5, we know that the corresponding S-MCI is

$$\begin{aligned} 3x_1 + 2x_2 + 2x_3 + x_4 + x_5 \le 4. \end{aligned}$$
(7)

The inequality (7) is the same inequality produced by the new lifting procedure described in [16], and the authors of [16] state that (7) is a facet of \({\text {conv}}(K)\) and it cannot be obtained from any cover inequality by standard sequential lifting methods, regardless of the lifting order. \(\diamond \)

Next, we discuss how the well-known (1, k)-configuration inequality can be derived as an MCI.

Proposition 2

Consider a knapsack set \(K = \{x \in \{0,1\}^n \mid a^T x \le b\}\), a nonempty subset \(Q \subseteq [n]\), and \(t \in [n] \setminus Q\). Assume that \(\sum _{i \in Q} a_i \le b\) and that \(H \cup \{t\}\) is a minimal cover for all \(H \subset Q\) with \(|H| = k\). Then for any \(T(r) \subseteq Q\) with \(|T(r)| = r\), \(k \le r \le |Q|\), the (1, k)-configuration inequality

$$\begin{aligned} (r-k+1) x_t + \sum _{j \in T(r)}x_j \le r \end{aligned}$$

can be obtained from an MCI associated with two covers of K.

Proof

When \(r = k\), then the inequality in the statement reduces to a CI. Hence we assume \(r > k\). W.l.o.g. we assume \(a_1 \ge \ldots \ge a_n\). Consider a new knapsack set \(K'{:}{=} \{x \in \{0,1\}^{n+1} \mid a^{\prime T} x \le b\}\), with \(a'_i = a_i \ \forall i \le t\), \(a'_{t+1} = a_t\), \(a'_j = a_{j-1} \ \forall j > t+1.\) Then clearly we have \(a'_1 \ge \ldots \ge a'_{n+1}\).

Since for any \(H \subset Q\) with \(|H| = k\), \(H \cup \{t\}\) is a cover for K, we know that for any \(j \in Q\), the set \(Q \cup \{t\} \setminus \{j\}\) is also a cover for K, i.e., \(\sum _{i \in Q} a_i - a_j + a_t > b\). From the assumption that \(\sum _{i \in Q}a_i \le b\), we have \(a_t > a_j\), or equivalently, \(t < j\) for any \(j \in Q\). Now for any \(T(r) \subseteq Q\) with \(|T(r)| = r\), \(k \le r \le |Q|\), let \(T(r){:}{=} \{j_1, \ldots , j_r\}\) with \(j_1< \ldots < j_r\), so we have \(t < j_1\) from above. Then consider \(C_1{:}{=} \{t\} \cup \{j_{r-k+1}, \ldots , j_r\}\), \(C'_1{:}{=} \{t\} \cup \{j_{r-k+1} + 1, \ldots , j_r + 1\}\), and \(C'_2 {:}{=} \{t+1\} \cup \{j_{1} + 1, \ldots , j_r + 1\}\). Since \(\{j_{r-k+1}, \ldots , j_r\} \subset Q\) with \(|\{j_{r-k+1}, \ldots , j_r\}| = k\), we know that \(C_1\) is a cover for K, so \(C'_1\) is a cover for \(K'\) from the construction of \(K'\). Furthermore \(C'_2\) is a cover for \(K'\) since \(a'_{t+1} = a'_t\). Note that the discrepancy family of \(\{C'_1, C'_2\}\) is \(\{\{t\}, \{t+1, j_1 + 1, \ldots , j_{r-k} + 1\}\}\), thus by Example 3, the inequality

$$\begin{aligned} (r-k+1) x_t + x_{t+1} + \sum _{\ell =1}^r x_{j_\ell + 1} \le r \end{aligned}$$
(8)

is an MCI for \(K'\) associated with \(\{C'_1, C'_2\}\). Since K can be obtained by projecting out of the variable \(x_{t+1}\) of \(K'\), we project out the variable \(x_{t+1}\) in (8) and relabel the indices. We obtain the following (1, k)-configuration inequality for K:

$$\begin{aligned} (r-k+1) x_t + \sum _{\ell =1}^r x_{j_\ell } = (r-k+1) x_t + \sum _{j \in T(r)}x_j \le r. \end{aligned}$$

\(\square \)

3.2 Extended MCI

In this section, we propose a procedure to strengthen, or extend, an MCI in a similar fashion to a well-known procedure for CIs [1]. We call the strengthened inequalities extended MCI (E-MCI).

For any set \(C \subseteq [n]\), let \(\min (C)\) denote the least element in C. Recall that for a cover \(C \subseteq [n]\), its corresponding extended cover inequality ECI is simply:

$$\begin{aligned} x([\min (C)-1] \cup C) \le |C| - 1, \end{aligned}$$
(9)

where the coefficient of each index i that is less than \(\min (C)\) is increased from 0 to 1. For a multi-cover \(\{C_1, \ldots , C_k\}\) one can perform a similar extension: let \(\alpha ^T x \le \beta \) be an MCI of this multi-cover, then the inequality \(x([\min (C) - 1]) + \alpha ^T x \le \beta \) is also valid for K. However, the improved coefficients in general can be larger than 1, and the indices of the variables included in the inequality do not have to be limited in the set \([\min (C) - 1]\). Before introducing the formal definition for our extended inequality, for any \(C_h\) with \(|C_h| \ge 2\) and vector \(\alpha \), we denote by \(\alpha _{2, C_h}\) the second least number in the multiset \(\{\alpha _i, i \in C_h\}\), which allows duplication. Here when \(C_h\) is a singleton, we also use \(\alpha _{2, C_h}\) to simply denote the unique element of \(C_h\). In cases where multiple minimum numbers exist in \(\{\alpha _i, i \in C_h\}\), then \(\alpha _{2, C_h}\) is simply \(\min _{i \in C_h} \alpha _i\).

Definition 5

(Extended MCI) Given an MCI \(\alpha ^T x \le \beta \) generated from a multi-cover \(\{C_1, \ldots , C_k\}\). Then the following inequality

$$\begin{aligned} \sum _{i \in [n] \setminus C} \big (\max _{h \in [k]: i < \min (C_h)} \alpha _{2, C_h} \big ) x_i + \alpha ^T x \le \beta \end{aligned}$$
(10)

is called an extended MCI (E-MCI).

Similarly to the remark after Algorithm 1, here for an index i with \(\{h \in [k] \mid i < \min (C_h)\} = \emptyset \), the maximum over this empty set is set to be zero. It is easy to observe that, when (10) is applied to a normal CI, this inequality gives the same ECI as (9). Next, we prove that inequality (10) is indeed a valid inequality for K.

Theorem 2

For a TOMKS K and an MCI \(\alpha ^T x \le \beta \) generated from a multi-cover \(\{C_1, \ldots , C_k\}\), the E-MCI (10) is valid for K.

Proof

In order to show that inequality (10) is valid for K, it suffices to show that for any \(S \subseteq [n]\) whose incidence vector \(\chi ^S\) violates the inequality (10), then S must be a cover for K. Let \(E{:}{=} \{i \in [n] \setminus C \mid \exists h \in [k] \ \text {s.t.}\ i < \min (C_h)\}\). The proof is by induction on \(|S \cap E|\).

If \(|S \cap E| = 0\), \(\chi ^S\) violates inequality (10) if and only if \(\chi ^S\) violates the original MCI \(\alpha ^T x \le \beta \), which implies that S is a cover for K since we know that \(\alpha ^T x \le \beta \) is valid for K.

Now we prove the inductive step. We assume that when \(|S \cap E| = N\), for \(N<|E|\), our statement is true. Assume now that \(|S \cap E| = N+1\) and we show that \(\chi ^S\) is not in K. Arbitrarily pick \(i^* \in S \cap E\), with \(\max _{h \in [k]: i^* < \min (C_h)} \alpha _{2, C_h} = \alpha _{2, C_{h^*}}\) for some \(h^* \in [k]\). To conclude the proof of the inductive step we consider separately two cases.

In the first case we assume \(\{i \in C_{h^*} \mid \alpha _i \ge \alpha _{2, C_{h^*}}\} \subseteq S\). By definition of \(\alpha _{2, C_{h^*}}\), we know that \(\{i \in C_{h^*} \mid \alpha _i < \alpha _{2, C_{h^*}}\}\) has at most one element, and that element is larger than \(i^*\) since \(i^* < \min (C_h^*)\). Therefore, we obtain

$$\begin{aligned} S&\supseteq \{i^*\} \cup \{i \in C_{h^*} \mid \alpha _i \ge \alpha _{2, C_{h^*}}\} \\&\triangleright \{i \in C_{h^*} \mid \alpha _i < \alpha _{2, C_{h^*}}\} \cup \{i \in C_{h^*} \mid \alpha _i \ge \alpha _{2, C_{h^*}}\} \\&= C_{h^*}, \end{aligned}$$

which indicates that S must also be a cover for K. This concludes our first case.

In the second case we assume that there exists \(j^* \in \{i \in C_{h^*} \mid \alpha _i \ge \alpha _{2, C_{h^*}}\}\) and \(j^* \notin S\). Then we have \(\alpha _{j^*} \ge \alpha _{2, C_{h^*}}\), which is the coefficient of \(x_{i^*}\) in equality (10). Consider \(S'{:}{=} S \setminus \{i^*\} \cup \{j^*\}\), which is dominated by S since \(i^* < \min (C_h^*)\). Since \(\chi ^S\) violates inequality (10), we know that \(\chi ^{S'}\) also violates inequality (10). Note that \(|S' \cap E| = |S \cap E| - 1 = N\), so by the inductive hypothesis, we know that \(S'\) must be a cover for K. Since \(S \triangleright S'\), we obtain that S must also be a cover for K. This concludes our second case and the proof of the inductive step. \(\square \)

The next example is obtained from Example 8 by simply adding two more variables.

Example 9

Let \(K{:}{=} \{x \in \{0,1\}^7 \mid 10 x_1 + 10 x_2 + 7 x_3 + 7 x_4 + 7 x_5 + 4 x_6 + 4 x_7 \le 16\}\), and we consider the multi-cover \(\mathscr {C}: = \{ \{2, 5\}, \{2, 6, 7\}, \{4, 5, 7\}\}\). From Example 5, we have the following S-MCI:

$$\begin{aligned} 3x_2 + 2x_4 + 2x_5 + x_6 + x_7 \le 4. \end{aligned}$$

Now we lift the coefficients of indices 1 and 3. For index 3, note that \(\{h \in [3] \mid 3 < \min (C_h)\} = \{3\}\), and the second smallest number in \(\{\alpha _4, \alpha _5, \alpha _7\}\) is 2, so the extended coefficient for \(x_3\) is 2. Similarly, for index 1 we have \(\{h \in [3] \mid 1 < \min (C_h)\} = \{1,2,3\},\) and \(\alpha _{2, C_1} = 3\), \(\alpha _{2, C_2} = 1\), \(\alpha _{2, C_3} = 2\), so the extended coefficient for \(x_1\) is 3. Therefore, we obtain the following E-MCI:

$$\begin{aligned} 3x_1 + 3x_2 + 2x_3 + 2x_4 + 2x_5 + x_6 + x_7 \le 4. \end{aligned}$$

In fact, this inequality turns out to be the only non-trivial facet-defining inequality of \({\text {conv}}(K)\) that is not an ECI. \(\diamond \)

We give another interesting example with only one knapsack constraint.

Example 10

Let \(K{:}{=} \{x \in \{0,1\}^6 \mid 66 x_1 + 61 x_2 + 54 x_3 + 33 x_4 + 21 x_5 + 16 x_6 \le 130\}\). From the multi-cover \(\{C_1, C_2\}{:}{=} \{\{2,3,6\},\{2,4,5,6\}\}\) we obtain an MCI: \(3 x_2 + 2x_3 + x_4 + x_5 + x_6 \le 5\). Note that \(\alpha _{2, C_1} = 2\), \(\alpha _{2, C_2} = 1\), so from (10) we obtain the corresponding E-MCI \(2x_1 + 3 x_2 + 2x_3 + x_4 + x_5 + x_6 \le 5\), which is also a facet-defining inequality for \({\text {conv}}(K)\). \(\diamond \)

4 Facet-defining inequalities

In this section, we provide a sufficient condition for an S-MCI to define a facet of \({\text {conv}}(K)\). We also give a family of instances in which all the non-trivial facet-defining inequalities of \({\text {conv}}(K)\) are given by MCIs.

Given a multi-cover \(\{C_1,\dots ,C_k\}\) and an S-MCI \(\alpha ^T x \le \beta \), we denote by \(\{i_{t,1}, \ldots , i_{t, n_t}\}{:}{=} \{i \in C \setminus C_0 \mid \alpha _i = t\}\) the set of indices in \(C \setminus C_0\) whose S-MCI coefficients are all t, where \(i_{t, 1}< \ldots < i_{t, n_t}\).

Theorem 3

Let \(\{C_1,\dots ,C_k\}\) be a multi-cover for a TOMKS K, and let \(\alpha ^T x \le \beta \) be the corresponding S-MCI. Assume that the following conditions hold:

  1. 1.

    \(C_0 = \emptyset \);

  2. 2.

    For each \(h \in [k]\), cover \(C_h\) is a minimal cover;

  3. 3.

    For any \(t = 2, \ldots , \max _{i=1}^n \alpha _i\), there exists some \(\ell _t \in [n_{t-1}]\) and \(h_t \in [k]\), such that \( i_{t-1, \ell _t} \notin C_{h_t}\), \(i_{t,1}, i_{1,n_1} \in C_{h_t}\), and \(C_{h_t} \cup \{i_{t-1, \ell _t}\} \setminus \{i_{t, n_t}\}\) is not a cover;

  4. 4.

    There exists some \(h_1 \in [k]\), such that \(i_{1, 1} \in C_{h_1}\) and for any \(i' \notin C\), \(C_{h_1} \cup \{i'\} \setminus \{i_{1, 1}\}\) is not a cover.

  5. 5.

    For any \(t = 1, \ldots , \max _{i=1}^n \alpha _i\), \(\alpha (C_{h_t}) = \beta + 1\).

Then \(\alpha ^T x \le \beta \) is a facet-defining inequality of \({\text {conv}}(K)\).

The proof of this theorem is deferred to “Appendix A”.

Example 11

Consider the TOMKS and the multi-cover in Example 8, where the knapsack constraint \(a^T x \le b\) is given by \((10,7,7,4,4)^T x \le 16\). We have \(C_1 = \{1, 3\}\), \(C_2 = \{1, 4, 5\}\), \(C_3 = \{2, 3, 5\}\), Then the corresponding S-MCI \(\alpha ^T x \le \beta \) is \(3x_1 + 2x_2 + 2x_3 + x_4 + x_5 \le 4\). Here we have \(i_{1,1} = 4\), \(i_{1,2} = 5\), \(i_{2,1} = 2\), \(i_{2,2} = 3\), \(i_{3,1} = 1\).

Clearly condition 1 in Theorem 3 holds. Since \(a(C_1) - a_3 = 10 \le 16\), \(a(C_2) - a_5 = 14 \le 16\), \(a(C_3) - a_5 = 14 \le 16\), condition 2 holds as well. For \(t = 2,\) let \(C_{h_2} = C_3\), then \(i_{1,1} \notin C_{h_2}, i_{1,2} \in C_{h_2}\), \(i_{2,1} \in C_{h_2}\), and \(C_{h_2} \cup \{i_{1,1}\} \setminus \{i_{2,2}\} = \{2, 4, 5\}\) is not a cover. For \(t = 3\), let \(C_{h_3} = C_2\), then \(i_{2,1} \notin C_{h_3}\), \(i_{1,2} \in C_{h_3}\), \(i_{3,1} \in C_{h_3}\), and \(C_{h_3} \cup \{i_{2,1}\} \setminus \{i_{3,1}\} = \{2,4,5\}\) is not a cover. So condition 3 holds. Let \(C_{h_1} = C_2\), then \(i_{1,1} \in C_{h_1}\), since here \(C = [5]\), condition 4 holds. Lastly, \(\alpha (C_{h_1}) = \alpha (C_{h_2}) = \alpha (C_{h_3}) = 5\), so condition 5 also holds. Hence Theorem 3 yields that this S-MCI is facet-defining. \(\diamond \)

A clutter is a family of subsets of a ground set with the property that no subset in the clutter is contained in any other subset in the clutter. It is simple to check that the set of minimal covers \({\mathcal {C}}\) of a knapsack set is a clutter, which we call the minimal cover set. For a clutter \({\mathcal {C}}\) and a subset Z of [n], the deletion with respect to Z is defined as \(\{A \in {\mathcal {C}} \mid A \cap Z =\emptyset \}\), and the contraction with respect to Z is defined as \(\{A \setminus Z \mid A \in {\mathcal {C}}\}\). A minor of \({\mathcal {C}}\) is a clutter that may be obtained from \({\mathcal {C}}\) by a sequence of deletions and contractions. For a minimal cover set of a TOMKS, we have the following theorem that was mentioned in Sect. 1.

Theorem 4

Let \({\mathcal {C}}\) be the minimal cover set of a TOMKS K. Then \({\text {conv}}(K) = \{x \in [0,1]^n \mid x(C) \le |C|-1, \forall C \in {\mathcal {C}}\}\) if and only if \({\mathcal {C}}\) has no minor isomorphic to \(J_q = \{\{2,\ldots , q\}, \{1,i\} \text { for } i = 2, \ldots , q\}\) with \( q \ge 3.\)

Theorem 4 follows easily from Theorem 1.1 in [15] (see also [21]) and the fact that the minimal cover set \({\mathcal {C}}\) of a TOMKS K is indeed a shift clutter as defined in [3]. For completeness, we provide a proof in “Appendix B”.

From Theorem 4, we know that in order for \({\text {conv}}(K)\) to have non-trivial facet-defining inequalities other than CIs, the minimal cover set \({\mathcal {C}}\) must have minors isomorphic to \(J_q\). Now we consider a special clutter \(\{\{1, \ldots , p-1, p+1, \ldots , q\}, \{1, \ldots , p, i\} \text { for }i=p+1, \ldots , q\}\) for some \(p = 1, \ldots , q-2\), \(q \le n\). After contracting \(\{1, \ldots , p-1\}\), we obtain a minor \(\{\{p+1, \ldots , q\}, \{p, i\} \text { for } i = p+1, \ldots , q\}\) that is isomorphic to \(J_{q-p+1}\). The next theorem states that, if the minimal cover set is this particular clutter, then we can provide the complete linear description of \({\text {conv}}(K)\).

Theorem 5

Let K be a TOMKS whose minimal cover set is \(\{\{1, \ldots , p-1, p+1, \ldots , q\}, \{1, \ldots , p, i\} \text { for }i=p+1, \ldots , q\}\) for some \(p = 1, \ldots , q-2\), \(q \le n\). Then \({\text {conv}}(K)\) can be described by the bound constraints, the CIs: \(\sum _{i=1}^p x_i + x_j \le p\), for \(j=p+1, \ldots , q,\) \(\sum _{i=1}^{p-1} x_i + \sum _{i=p+1}^q x_i \le q-2\), and one MCI: \((q-p) \sum _{i=1}^{p-1} x_i + (q-p-1)x_p + \sum _{i=p+1}^q x_i \le p(q-p)-1\).

Since CI is a special case of MCI, Theorem 5 can be seen as a particular instance where the facet-defining inequalities are all given by MCIs. The proof of this theorem can be found in “Appendix C”.

5 Separation problem

The separation problem for a multiple knapsack set K is: “Given a vector \({\tilde{x}} \in [0,1]^n\), either find an inequality that is valid for K and violated by \({\tilde{x}}\), or prove that no such inequality exists”. Even though the separation problems for some well-known classes of inequalities, e.g., CIs, simple LCIs and general LCIs, have all been shown to be \({\mathcal {N}}{\mathcal {P}}\)-hard [8, 11, 14], several efficient heuristics and exact separation algorithms have been proposed [6, 10, 22, 24]. In this section, we propose a mixed-integer programming (MIP) formulation to solve the exact separation problem for MCIs.

First, we introduce the following concept of a skeleton. For \(D \subseteq [n]\) and a function \(f: D \rightarrow \mathbb {N}\), we denote by \(f(D): = \{f(i) \mid i \in D\}\) the image of D under f.

Definition 6

(Skeleton) Let \(\mathscr {C}\subseteq 2^{[n]}\). For any \(i \in \cup _{D \in \mathcal {D}(\mathscr {C})} D\), let \(f(i) {:}{=} k\) if i is the k-th least element of \(\cup _{D \in \mathcal {D}(\mathscr {C})} D\). Then we say that \(\{f(D) \mid D \in \mathcal {D}(\mathscr {C})\}\) is the skeleton of \(\mathscr {C}\).

In other words, the skeleton of \(\mathscr {C}\) is isomorphic to \(\mathcal {D}(\mathscr {C})\) by relabelling the elements of \(\cup _{D \in \mathcal {D}(\mathscr {C})} D\) with their order in the set.

Due to the lack of a complete understanding of multi-covers, it is currently challenging to derive an efficient scheme to separate MCIs. In fact, we conjecture that it is \({\mathcal {N}}{\mathcal {P}}\)-hard to decide whether a given family of covers is a multi-cover. However, different multi-covers with the same (or similar) skeleton structure tend to have very similar combinatorial properties. It turns out that for any fixed skeleton, we are able to formulate as a MIP problem the separation problem for MCIs whose associated multi-covers have that skeleton. We present the exact formulation in “Appendix D”. Here we mainly introduce a different formulation, which enables us to separate a sub-family of MCIs whose associated multi-cover’s skeleton is either \(\{\{1\}, \{2, \ldots , t\}\}\) or \(\{\{1,t+1\}, \{2, \ldots , t\}\}\), for any \(t \ge 3\). These are the inequalities given in Examples 3 and 4. Given a vector \({\tilde{x}} \in [0,1]^n\), we provide below the formulation for the corresponding separation problem.

$$\begin{aligned} \begin{aligned} \min \quad&t + \sum _{i \in [n]} \gamma _i - \sum _{i \in [n]} (\alpha _i + \beta _i + \gamma _i) {\tilde{x}}_i \\ \text {s.t.}\quad&t \ge \sum _{i \in [n]} \alpha _i, \ t \ge \sum _{i \in [n]} \beta _i, \\&u_i + v_i + w_i \le 1, \quad \forall i \in [n] \\&\alpha _i \ge \beta _j + (1+M)u_i - M, \ \beta _i \ge \alpha _j + (1+M) v_i - M, \quad \forall i,j \in [n], \ j> i\\&w_{1,i} + w_{2,i} = w_i, \quad \forall i \in [n] \\&\alpha _i \le M u_i, \ \beta _i \le M v_i, \ \gamma _i \le M w_i, \quad \forall i \in [n] \\&\gamma _i \ge \sum _{j>i} \alpha _j + (1+nM)w_{1,i} -nM, \ \gamma _i\\&\quad \ge \sum _{j>i} \beta _j + (1+nM) w_{2,i} -nM, \quad \forall i \in [n]\\&\gamma _i \ge \alpha _j + Mw_{1,i}-M, \ \gamma _i \ge \beta _j + M w_{2,i} - M, \quad \forall i,j \in [n], \ j< i \\&\sum _{i \in [n]} A_{j,i} (u_i + w_i) \ge (b_j+1) \cdot \lambda _j, \ \sum _{i \in [n]} A_{j,i} (v_i + w_i)\\&\quad \ge (b_j+1) \cdot \mu _j, \quad \forall j \in [m] \\&\sum _{j \in [m]} \lambda _j \ge 1, \sum _{j \in [m]} \mu _j \ge 1,\\&\sum _{i \in [n]} v_i \ge 2, \ \sum _{j<i} u_j \ge v_i, \ v_i + \sum _{j \le i} u_j \le 2, \quad \forall i \in [n] \\&\lambda _j, \mu _j \in \{0,1\}, \quad \forall j \in [m] \\&u_i, v_i, w_i, w_{1,i}, w_{2,i}, z_i \in \{0,1\}, \quad \forall i \in [n] \\&\alpha _i, \beta _i, \gamma _i \in \mathbb {Z}, \quad \forall i \in [n]. \end{aligned} \end{aligned}$$
(Sep2)

We remark that M is the only pre-fixed parameter for this formulation, which represents the selected upper bound for all the coefficients of the MCI. Next we show that the separation problem for MCIs from multi-covers with skeleton \(\{\{1\}, \{2, \ldots , t\}\}\) or \(\{\{1,t+1\}, \{2, \ldots , t\}\}\) can be exactly solved by solving the above MIP problem.

Theorem 6

Given a TOMKS K and a point \({\tilde{x}}\), there exists a multi-cover \(\mathscr {C}\) whose skeleton is \(\{\{1\}, \{2, \ldots , t\}\}\) or \(\{\{1,t+1\}, \{2, \ldots , t\}\}\) for some \(t \ge 3\) and an associated MCI separates \({\tilde{x}}\) from K, if and only if (Sep2) has optimal value less than 1.

Proof

First, we explain the meaning of the variables in (Sep2). Let \(C_1\) and \(C_2\) be two covers. For any \(i \in [n]\), we define , and . So we have the second constraint \(u_i + v_i + w_i \le 1\) in (Sep2). Variables \(\alpha _i, \beta _i, \gamma _i\) denote the coefficients for index i in \(C_1 \setminus C_2\), \(C_2 \setminus C_1\), and \(C_1 \cap C_2\) respectively, which is enforced by \(\alpha _i \le M u_i\) etc., through some “big-M” constant. From Step 7 of Algorithm 1,

$$\begin{aligned} \sum _{i \in [n]} (\alpha _i + \beta _i + \gamma _i) x \le \max (\sum _{i} \alpha _i + \sum _{i} \gamma _i, \sum _{i} \beta _i + \sum _{i}\gamma _i) - 1 \end{aligned}$$

is the MCI we will obtain. Introducing an additional variable t and constraints \(t \ge \sum _i \alpha _i\), \(t \ge \sum _i \beta _i\), we obtain the objective function and the first constraint of (Sep2). In particular, the objective value is strictly less than 1 if and only if the obtained inequality is violated by \({\tilde{x}}\). Using a big-M formulation, \(\alpha _i \ge \beta _j + (1+M)u_i - M\) formulates the constraint of Step 4 of Algorithm 1: for \(i \in C_1 \setminus C_2\), \(\alpha _i \ge \max _{j >i, j \in C_2 \setminus C_2} \beta _j + 1\). By splitting the binary variable \(w_i\) into two binary variables \(w_{1,i}\) and \(w_{2,i}\), and using the big-M formulation \(\gamma _i \ge \sum _{j>i} \alpha _j + (1+nM)w_{1,i} -nM\), \(\gamma _i \ge \alpha _j + Mw_{1,i}-M\) etc., we are able to formulate the constraint of Step 6 of Algorithm 1:

$$\begin{aligned} \begin{aligned}&\gamma _i \ge \max \{\max _{j<i, j \in C_1 \setminus C_2} \alpha _j, \sum _{j>i, j \in C_1 \setminus C_2} \alpha _j + 1\} \text { or } \\&\gamma _i \ge \max \{\max _{j<i, j \in C_2 \setminus C_1} \beta _j, \sum _{j>i, j \in C_2 \setminus C_1} \beta _j + 1\}. \end{aligned} \end{aligned}$$

Constraints \(\sum _{i \in [n]} A_{j,i} (u_i + w_i) \ge (b_j+1) \cdot \lambda _j\), \(\sum _{i \in [n]} A_{j,i} (v_i + w_i) \ge (b_j+1) \cdot \mu _j\), and \(\sum _i \lambda \ge 1\), \(\sum _i \mu _i \ge 1\) enforce that \(C_1\) and \(C_2\) are two covers of K. Lastly, the constraints \(\sum _{i \in [n]} v_i \ge 2\), \(\sum _{j<i} u_j \ge v_i, v_i + \sum _{j \le i} u_j \le 2\) enforce the skeleton structures \(\{\{1\}, \{2, \ldots , t\}\}\) or \(\{\{1,t+1\}, \{2, \ldots , t\}\}\) with \(t \ge 3\). In particular, constraint \(\sum _{j<i} u_j \ge v_i\) means \(\min \{i \mid i \in C_1 \setminus C_2\} < \min \{i \mid i \in C_2 \setminus C_1\}\), and constraint \(v_i + \sum _{j \le i} u_j \le 2\) means \(|C_1 \setminus C_2| \le 2\), and \(\max \{i \mid i \in C_1 \setminus C_2\} > \max \{i \mid i \in C_2 \setminus C_1\}\) if \(|C_1 \setminus C_2| = 2\). These are exactly the conditions for \(\{C_1, C_2\}\) to have skeleton \(\{\{1\}, \{2, \ldots , t\}\}\) or \(\{\{1,t+1\}, \{2, \ldots , t\}\}\). \(\square \)

It is worth mentioning that the constraint \(\sum _{i \in [n]} v_i \ge 2\) in (Sep2) can actually be removed. In that case, (Sep2) will also be able to separate MCIs with skeleton \(\{\{1\}, \{2, \ldots , t\}\}\) or \(\{\{1,t+1\}, \{2, \ldots , t\}\}\) for some \(t \le 2\), as well as the normal CIs, since the optimal solution to (Sep2) with binary variables \(u=v=0\) corresponds to a separating CI, where the cover is given by the support of the w vector.

6 Numerical experiments

In this section we present results of numerical experiments designed to test the optimality gap closed by our proposed cutting-planes and their variants.

For a given fractional solution, we use the separation formulation (Sep2) to produce MCIs that arise from multi-covers with two specific skeletons. We also relax the constraint \(\sum _{i \in [n]} v_i \ge 2\) therein, so the separation problem may separate CIs as well. The numerical experiments are conducted as follows: for a given totally-ordered multiple knapsack problem, in the i-th iteration we optimize the linear objective function over the current linear relaxation, and obtain an optimal solution \(x^i\). We terminate the experiment if the separation problem (Sep2) associated with \(x^i\) has optimal value 1 or more. Otherwise, if the optimal value is strictly less than 1, we add the separating cutting-plane generated from (Sep2) into the current linear relaxation, then proceed to the next step. The linear relaxation in the first iteration is initialized as the natural LP relaxation of the problem.

For our experiments, we create synthetic instances of the multiple knapsack problem: \(\max \{c^T x \mid Ax \le b, x \in \{0,1\}^n\}\), where \(A \in \mathbb {Z}^{m \times n}_+, c \in \mathbb {Z}^n_+\), \(b \in \mathbb {Z}^m_+\). For each row of the matrix \(A_j\), we generate n random integers in the range \([1, n^2]\) and then sort them in non-increasing order. The right-hand-side number \(b_j\) is generated as a random integer number in the range \([A_{j,1}, \sum _i (A_{j,i})]\). The objective vector c is also generated from sorting n random integer numbers in \([1, n^2]\) in non-increasing order. We create ten instances of sizes \(n \in \{20,30\}\) and with \(m \in \{1,2,3\}\) constraints.

We compare the MCI inequality and two of its variants against analogous CIs. Specifically, we will compare the MCI against the original CI, the E-MCI against the classical ECI, and a lifted version of MCI (L-MCI) with a lifted CI (LCI). To obtain a lifted CI or a lifted MCI, we start with the original CI or MCI, and then apply the simple sequential up-lifting procedure of [19], lifting the variables in the order \(1,2,\ldots ,n\). In subsequent tables and figures, we use the following abbreviations:

LP:

: Denotes the natural LP relaxation.

MCI:

: Denotes the linear relaxation after iteratively solving the separation problem (Sep2) to add all CIs and MCIs whose associated multi-covers have skeleton \(\{\{1\}, \{2, \ldots , t\}\}\) or \(\{\{1,t+1\}, \{2, \ldots , t\}\}\).

E-MCI:

: Denotes the linear relaxation where each MCI found is strengthened/extended as in (10).

L-MCI:

: Denotes the linear relaxation where each MCI is lifted.

CI:

: Denotes the linear relaxation obtained after adding all CIs. Here the separation problem is solved exactly by solving an IP, as in [6].

ECI:

: Denotes the linear relaxation where each additional inequality is the ECI of the separating CI in the current iteration.

LCI:

: Denotes the linear relaxation where each additional inequality is the LCI of the separating CI in the current iteration.

We report the summary of numerical results in Tables 1 and 2, and more details can be found in Appendix 5. For different combinations of (n, m), in Table 1, we list the average optimality gap obtained from optimizing over the different relaxations studied. In Table 2, we list the total number of instances that have been solved to optimality for each method. From these two tables, one can see quite clearly that the L-MCI is able to close much more optimality gap than its LCI counterpart, and solve most (\(60-80\%\)) of the instances to optimality. The difference between the two methods on each instance is shown directly in Fig. 1, where we see that instances with over 3% optimality gap using LCI may be solved at the root node to optimality with LMCI.

Table 1 Average optimality gap of different cutting-plane closure. (%)
Full size table
Table 2 Number of instances solved to optimality. (out of 10)
Full size table
Fig. 1
figure 1

The x-axis and y-axis of each dot represent the optimality gap closed by LCI and L-MCI for each instance, respectively

Full size image

Because our separation method is based on the solution of a difficult MIP problem (Sep2), we only conduct our experiments for small-sized knapsack instances. However, we believe the computational results are promising enough to encourage others to seek efficient heuristic separation methods for this large family of inequalities.

7 Conclusion

In this work, we introduced a new family of valid inequalities for the intersection of knapsack sets and exhibited several scenarios in which the inequalities are not implied by other known families of cutting-planes. The numerical experiments demonstrated the potential for this new family of cuts to strengthen the linear programming relaxation more than known classes of inequalities. Our work is among the very first that explicitly studies the polyhedral structure of the intersection of multiple knapsack sets, and we hope that the ideas presented here will give rise to new methods for generating strong valid inequalities for complex binary sets that arise in practical settings.