∎

11institutetext: Haoran Zhu 22institutetext: Department of Industrial and
Systems Engineering, University of Wisconsin-Madison,
Madison, WI, 53705, USA
<EMAIL_ADDRESS>11institutetext: Alberto Del Pia 22institutetext: Department
of Industrial and Systems Engineering, University of Wisconsin-Madison,
Wisconsin Institute for Discovery,
Madison, WI, 53705, USA
<EMAIL_ADDRESS>33institutetext: Jeff Linderoth 44institutetext: Department of
Industrial and Systems Engineering, University of Wisconsin-Madison,
Wisconsin Institute for Discovery,
Madison, WI, 53705, USA
<EMAIL_ADDRESS>55institutetext: Haoran Zhu 66institutetext: Department of
Industrial and Systems Engineering, University of Wisconsin-Madison,
Madison, WI, 53705, USA
<EMAIL_ADDRESS>
# Multi-cover Inequalities for Totally-Ordered Multiple Knapsack Sets
††thanks: A. Del Pia is partially funded by ONR grant N00014-19-1-2322. Any
opinions, findings, and conclusions or recommendations expressed in this
material are those of the authors and do not necessarily reflect the views of
the Office of Naval Research.

Alberto Del Pia  Jeff Linderoth  Haoran Zhu

###### Abstract

We propose a method to generate cutting-planes from multiple covers of
knapsack constraints. The covers may come from different knapsack inequalities
if the weights in the inequalities form a totally-ordered set. Thus, we
introduce and study the structure of a totally-ordered multiple knapsack set.
The valid _multi-cover inequalities_ we derive for its convex hull have a
number of interesting properties. First, they generalize the well-known
$(1,k)$-configuration inequalities. Second, they are not aggregation cuts.
Third, they cannot be generated as a rank-1 Chvátal-Gomory cut from the
inequality system consisting of the knapsack constraints and all their minimal
cover inequalities. We also provide conditions under which the inequalities
are facets for the convex hull of the totally-ordered knapsack set, as well as
conditions for those inequalities to fully characterize its convex hull. We
give an integer program to solve the separation and provide numerical
experiments that showcase the strength of these new inequalities.

###### Keywords:

Multiple knapsack problem Cutting-planes Knapsack polytope

##  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

$K_{\mbox{\scriptsize\sc knap}}:=\\{x\in\\{0,1\\}^{n}\mid a^{T}x\leq b\\},$

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)_

$\sum_{j\in C}x_{j}\leq|C|-1$

is valid for the _knapsack polytope_
$\operatorname{conv}(K_{\mbox{\scriptsize\sc 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 balas1975facets ; hammer1975facet
; wolsey1976facets ; gu1998lifted ; letchford2019lifted , and the reader is
directed to the recent survey hojny2019knapsack  for a thorough introduction.

In this paper we consider the _0-1 multiple knapsack set_

$\displaystyle K=\\{x\in\\{0,1\\}^{n}\mid Ax\leq b\\},$ (1)

where $[A,b]\in\mathbb{Z}^{m\times(n+1)}_{+}$. A standard and computationally
useful way for generating valid inequalities for $\operatorname{conv}(K)$ is
to generate _lifted cover inequalities (LCIs)_ for the knapsack sets defined
by the individual constraints of $K$ crowder1983solving . In this way, the
extensive literature regarding valid inequalities for
$\operatorname{conv}(K_{\mbox{\scriptsize\sc knap}})$ can be leveraged to
solve integer programs whose feasible region is $K$. In contrast to
$\operatorname{conv}(K_{\mbox{\scriptsize\sc knap}})$, very little is known
about the polyhedral structure of $\operatorname{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}\geq A_{\cdot 2}\geq\ldots\geq A_{\cdot n}$.

The 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

$\mathbb{P}\\{a(\xi)^{T}x\leq\beta\\}\geq 1-\epsilon,$ (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 MR2232597 ; nemirovski.shapiro:05 , an
independent Monte Carlo sample of $N$ realizations of the weights
$(a(\xi^{1}),\ldots a(\xi^{N}))$ is drawn and the deterministic constraints

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

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

$N\geq\frac{1}{2\epsilon^{2}}\left(\log\left(\frac{1}{\delta}\right)+n\log(2)\right),$

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}\geq\mu_{2}\ldots\geq\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\leq b_{1}$ and $a_{2}^{T}x\leq
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
$\operatorname{conv}(K_{\mbox{\scriptsize\sc knap}})$ padberg19801  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 $\operatorname{conv}(K_{\mbox{\scriptsize\sc knap}})$ generated by a
recent lifting procedure described by Letchford and Souli letchford2019lifted
is a MCI.

Interestingly, as observed by Laurent and Sassano laurent1992characterization
, 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\geq 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},\operatorname{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 (defined in 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
$\operatorname{conv}(K)$ in Section 4, as well as a condition for the MCIs to
fully describe $\operatorname{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

$\mathcal{A}(A,b):=\bigcap_{\lambda\in\mathbb{R}^{m}_{+}}\operatorname{conv}(\\{x\in\\{0,1\\}^{n}\
\mid\lambda^{T}Ax\leq\lambda^{T}b\\}.$

Inequalities valid for $\mathcal{A}(A,b)$ are known as _aggregation cuts_ ,
and have been shown to be quite powerful from both an empirical
fukasawa.goycoolea:11  and theoretical MR3844541  viewpoint. The well-known
Chvátal-Gomory (CG) cuts, lifted cover inequalities, and weight inequalities
weismantel19970  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 Section 2, we define a certain type of
dominance relationship between covers that is necessary to introduce the MCIs.
The MCIs are defined in Section 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
Section 3.2 we introduce a strengthening procedure for MCI. In Section 4 we
provide a sufficient condition for the MCI to be facet-defining for
$\operatorname{conv}(K)$, and we show a family of instances where the MCI
inequalities are the only non-trivial inequalities besides cover inequalities
for $\operatorname{conv}(K)$. Lastly in Section 5 and Section 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 del2021multi . First, the MCI defined in del2021multi  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
del2021multi  as special cases. For that reason, we remove the _AMCI_ section
in del2021multi  from this paper. Moreover, in Section 3 we introduce an
analogous concept of _extended cover inequality (ECI)_ for MCI, namely the
_extended MCI_ , and in Section 4 we provide a special scenario for MCIs to
fully describe $\operatorname{conv}(K)$. Lastly, Section 5 and Section 6 have
completely new results about separation and numerical experiments.

#### Notation.

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
means $x(\emptyset)=0.$ We denote the _power set_ of a set $S$, the set of all
subsets of $S$, as $2^{S}$. Lastly, we denote $e^{j}$ to be 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 important properties.

######  Definition 1 (Dominance)

For $S_{1},S_{2}\subseteq[n]$, we say that $S_{1}$ _dominates_ $S_{2}$ and
write $S_{1}\triangleright S_{2}$, if there exists an injective function
$f:S_{2}\to S_{1}$ with $f(i)\leq i\ \forall i\in S_{2}$.

The dominance relation in Definition 1 is reflexive, antisymmetric, and
transitive, so $(2^{[n]},\triangleright)$ forms a partially ordered set. For
two sets $S_{1},S_{2}\subseteq[n]$, we say $S_{1}$ and $S_{2}$ are
_comparable_ if $S_{1}\triangleright S_{2}$ or $S_{2}\triangleright S_{1}$.

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$. Next, we present two technical lemmas about
dominance.

###### Lemma 1

Let $S_{1},S_{2}\subseteq[n]$ with $S_{1}\neq S_{2}$. Then for any
$S^{\prime}\subseteq S_{1}\cap S_{2}$, $S_{1}\triangleright S_{2}$ if and only
if $S_{1}\setminus S^{\prime}\triangleright S_{2}\setminus S^{\prime}$.

###### Proof

Let $S_{0}:=S_{1}\cap S_{2}$. First, we show that for any $S^{\prime}\subseteq
S_{0}$, $S_{1}\setminus S^{\prime}\triangleright S_{2}\setminus S^{\prime}$
implies that $S_{1}\triangleright S_{2}$. From Definition 1, there exists an
injective function $g:S_{2}\setminus S^{\prime}\to S_{1}\setminus S^{\prime}$
such that $g(i)\leq i\ \forall i\in S_{2}\setminus S^{\prime}$. Now we define
the function $f$ as follows: for any $i\in S_{2}$, if $i\in S^{\prime}$, then
$f(i):=i$; if $i\in S_{2}\setminus S^{\prime}$, then $f(i):=g(i)$. So $f$ is a
function maps elements from $S_{2}$ to $S_{1}$. Apparently this function $f$
is an injective function, with $f(i)\leq i\ \forall i\in S_{2}$, therefore we
have proven that $S_{1}\triangleright S_{2}$.

Next we show that $S_{1}\triangleright S_{2}$ implies $S_{1}\setminus
S_{0}\triangleright S_{2}\setminus S_{0}$. From Definition 1, there exists an
injective function $g:S_{2}\to S_{1}$ such that $g(i)\leq i\ \forall i\in
S_{2}$. We define the function $f$ as follows: for any $i\in S_{2}\setminus
S_{0}$, $f(i):=g^{t(i)}(i)$ where $t(i)$ is the smallest integer number $t\geq
1$ such that $g^{t}(i)\in S_{1}\setminus S_{0}$, and $g^{t}=g\circ
g\circ\ldots\circ g$ is the $t$th functional power of $g$. Since $g$ is an
injective function from $S_{2}$ to $S_{1}$, we know for any $i\in
S_{2}\setminus S_{0}$, there must exist $t\in\mathbb{N}$ such that
$g^{t}(i)\in S_{1}\setminus S_{0}$. Hence the function $f$ is well defined and
it is from $S_{2}\setminus S_{0}$ to $S_{1}\setminus S_{0}$. It remains to
show that $f$ is an injective function and that $f(i)\leq i\ \forall i\in
S_{2}\setminus S_{0}$. The fact that $f(i)\leq i\ \forall i\in S_{2}\setminus
S_{0}$ follows directly from the property $g(i)\leq i\ \forall i\in S_{2}$ and
the definition of $f$. Finally, we show that $f$ is injective. Assume, for a
contradiction, that $f$ is not injective. Then there exists $i,j\in
S_{2}\setminus S_{0}$ with $i\neq j$ such that $f(i)=f(j)$, i.e.,
$g^{t(i)}(i)=g^{t(j)}(j)$. By eventually switching $i$ and $j$, we can assume
without loss of generality that $t(i)\leq t(j)$. Since $g$ is injective, we
know that $i=g^{t(j)-t(i)}(j)$. If $t(j)-t(i)=0$, then $i=j$ which gives us a
contradiction. Thus we now assume $t(j)-t(i)\geq 1.$ In this case, the fact
that $g^{t(j)-t(i)}(j)$ is in $S_{2}\setminus S_{0}$ contradicts the fact that
the codomain of $g$ is $S_{1}$. We have thereby shown that $f$ is injective,
and this concludes the proof of $S_{1}\setminus S_{0}\triangleright
S_{2}\setminus S_{0}$.

Lastly, we want to show that, for any $S^{\prime}\subseteq S_{0}$,
$S_{1}\triangleright S_{2}$ implies that $S_{1}\setminus
S^{\prime}\triangleright S_{2}\triangleright S^{\prime}$. If
$S^{\prime}=S_{0}$, then from above, we have already shown that
$S_{1}\setminus S_{0}\triangleright S_{2}\setminus S_{0}$. If
$S^{\prime}\subsetneq S_{0},$ let $S^{\prime\prime}=S_{0}\setminus
S^{\prime}$, then $S_{1}\setminus S^{\prime}=(S_{1}\setminus S_{0})\cup
S^{\prime\prime},S_{2}\setminus S^{\prime}=(S_{2}\setminus S_{0})\cup
S^{\prime\prime}$. From $S_{1}\setminus S_{0}\triangleright S_{2}\setminus
S_{0}$, we can easily know that $(S_{1}\setminus S_{0})\cup
S^{\prime\prime}\triangleright(S_{2}\setminus S_{0})\cup S^{\prime\prime}$,
which is just $S_{1}\setminus S^{\prime}\triangleright S_{2}\setminus
S^{\prime}$. ∎

###### Lemma 2

Let $S\subseteq[n]$ and let $S_{1},S_{2}\subseteq S$. Then,
$S_{1}\triangleright S_{2}$ if and only if $S\setminus S_{2}\triangleright
S\setminus S_{1}$.

###### Proof

It suffices to prove the implication from left to right, i.e., that
$S_{1}\triangleright S_{2}$ implies $S\setminus S_{2}\triangleright S\setminus
S_{1}$. In fact, once this implication is proven, it is simple to observe that
the reverse implication holds as well. To see this, assume $S\setminus
S_{2}\triangleright S\setminus S_{1}$. Using the implication from left to
right, we then obtain $S\setminus(S\setminus S_{1})\triangleright
S\setminus(S\setminus S_{2})$, which can be rewritten as $S_{1}\triangleright
S_{2}$. Hence, in the remainder of the proof we show the implication from left
to right.

From Definition 1, we know that there exists an injective function $f:S_{2}\to
S_{1}$ with $f(i)\leq i\ \forall i\in S_{2}$. Define
$\tilde{S}_{1}:=f(S_{2})$. To complete the proof, it suffices to show that
$S\setminus S_{2}\triangleright S\setminus\tilde{S}_{1}$. In fact, since
$\tilde{S}_{1}\subseteq S_{1}$, then $S\setminus\tilde{S}_{1}\supseteq
S\setminus S_{1}$, thus using the identity function we obtain
$S\setminus\tilde{S}_{1}\triangleright S\setminus S_{1}$. Since the domination
relation is transitive, we then obtain $S\setminus S_{2}\triangleright
S\setminus\tilde{S}_{1}\triangleright S\setminus S_{1}$, as desired. Hence we
now show that that $S\setminus S_{2}\triangleright S\setminus\tilde{S}_{1}$.

Note that $|\tilde{S}_{1}|=|S_{2}|$, thus also
$|S\setminus\tilde{S}_{1}|=|S\setminus S_{2}|$, and we denote the latter
cardinality by $t$. Let $S\setminus\tilde{S}_{1}=\\{i_{1},\ldots,i_{t}\\}$ and
$S\setminus S_{2}=\\{j_{1},\ldots,j_{t}\\}$, where $i_{1}<\ldots<i_{t}$ and
$j_{1}<\ldots<j_{t}$. It suffices to show that $j_{h}\leq i_{h}\ \forall
h\in[t]$. In fact, then we can consider the injective function
$g:S\setminus\tilde{S}_{1}\to S\setminus S_{2}$ defined by $g(i_{h}):=j_{h}$,
and obtain that $S\setminus S_{2}\triangleright S\setminus\tilde{S}_{1}$.
Thus, in the remainder of the proof we show that $j_{h}\leq i_{h}\ \forall
h\in[t]$. We prove this statement by contradiction, thus we suppose that there
exists at least one index $h$ such that $j_{h}>i_{h}$, and we define $h^{*}$
to be the minimum such index, i.e., $h^{*}:=\min\\{h\mid j_{h}>i_{h}\\}$.

We now show that $\\{j\in S\setminus S_{2}\mid j\leq
i_{h^{*}}\\}=\\{j_{1},\ldots,j_{h^{*}-1}\\}$. The containment $\subseteq$
holds because, by definition of $h^{*}$, we have $j_{h^{*}}>i_{h^{*}}$. To
prove the containment $\supseteq$, we just need to show that $j_{h^{*}-1}\leq
i_{h^{*}}$. If not, we have $j_{h^{*}-1}>i_{h^{*}}$, thus
$j_{h^{*}-1}>i_{h^{*}}>i_{h^{*}-1}$, which contradicts the choice of $h^{*}$.

Now we consider the sets $T_{1}:=\\{j\in\tilde{S}_{1}\mid j\leq i_{h^{*}}\\}$
and $T_{2}:=\\{j\in S_{2}\mid j\leq i_{h^{*}}\\}$. Since
$\tilde{S}_{1},S_{2}\subseteq S$, we have
$\tilde{S}_{1}=S\setminus(S\setminus\tilde{S}_{1})$ and
$S_{2}=S\setminus(S\setminus S_{2})$. We obtain

$\displaystyle|T_{1}|$ $\displaystyle=|\\{j\in S\mid j\leq
i_{h^{*}}\\}|-|\\{j\in S\setminus\tilde{S}_{1}\mid j\leq
i_{h^{*}}\\}|=|\\{j\in S\mid j\leq i_{h^{*}}\\}|-h^{*},$
$\displaystyle|T_{2}|$ $\displaystyle=|\\{j\in S\mid j\leq
i_{h^{*}}\\}|-|\\{j\in S\setminus S_{2}\mid j\leq i_{h^{*}}\\}|=|\\{j\in S\mid
j\leq i_{h^{*}}\\}|-h^{*}+1,$

therefore $|T_{1}|<|T_{2}|$. To obtain a contradiction we now show
$|T_{1}|\geq|T_{2}|$. Since $f(S_{2})=\tilde{S}_{1}$ and $f(j)\leq j\ \forall
j\in S_{2}$, we obtain

$\displaystyle|T_{1}|=|\\{j\in\tilde{S}_{1}\mid j\leq i_{h^{*}}\\}|=|\\{j\in
f(S_{2})\mid j\leq i_{h^{*}}\\}|\geq|\\{j\in S_{2}\mid j\leq
i_{h^{*}}\\}|=|T_{2}|.$

We have derived a contradiction. Therefore, we have shown that $j_{h}\leq
i_{h}\ \forall h\in[t]$, and this concludes the proof. ∎

##  3 Multi-cover Inequalities and Variation

Throughout this section, we consider a TOMKS $K:=\\{x\in\\{0,1\\}^{n}\mid
Ax\leq 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$ with
$T\notin\mathcal{D}(\mathscr{C})$, there exists some
$D^{\prime}\in\mathcal{D}(\mathscr{C})$ such that $T\triangleright D^{\prime}$
or $D^{\prime}\triangleright T$.

###### Example 1

Consider the TOMKS:

$\displaystyle K:=\\{x\in\\{0,1\\}^{5}\mid\ $ $\displaystyle
19x_{1}+11x_{2}+5x_{3}+4x_{4}+2x_{5}\leq 31,$ $\displaystyle
16x_{1}+10x_{2}+7x_{3}+5x_{4}+3x_{5}\leq 30\\}.$

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|\geq 2$ we have $T\triangleright\\{3,4\\}$. $\hfill\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.

Algorithm 1 Multi-cover inequality (MCI)

Input: A multi-cover $\\{C_{1},\ldots,C_{k}\\}$ for $K$.
Output: A multi-cover inequality.

1:Let $\\{i_{1},\ldots,i_{m}\\}:=C\setminus C_{0}$, with $i_{1}<\ldots<i_{m}$.

2:Set $\alpha_{i}:=1$ if $i\in\\{i_{1},\ldots,i_{m}\\}$, and $\alpha_{i}:=0$
otherwise.

3:for $t=m-1,\ldots,1$ do

4: let $\alpha_{i_{t}}$ be any integer $\geq\max_{h\in[k]:i_{t}\in
C_{h}}\max_{\ell\in\bar{C}_{h}:\ell>i_{t}}\alpha_{\ell}+1$.

5:for $j\in C_{0}$ do

6: let $\alpha_{j}$ be any integer
$\geq\min_{h\in[k]}\max\big{\\{}\max_{\ell<j,\ell\in\bar{C}_{h}}\alpha_{\ell},\sum_{\ell>j,\ell\in\bar{C}_{h}}\alpha_{\ell}+1\big{\\}}$.

7:Set $\beta:=\max_{h=1}^{k}\alpha(C_{h})-1.$

8:return the inequality $\alpha^{T}x\leq\beta$.

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.

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

###### Observation 1

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

At Step 4 and 6 of Algorithm 1, when the $\geq$ is fixed to $=$, the obtained
MCI is called the _simple-MCI_ , which was given in del2021multi . 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\leq\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\leq\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 $\operatorname{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\leq\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^{\prime}}$ for some $h^{\prime}\in[k]$, then
$\alpha(T)>\alpha(\bar{C}_{h^{\prime}})$.

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^{\prime}}$ be the sets as assumed in the statement of
this proposition, with $T\triangleright\bar{C}_{h^{\prime}}$. Let
$T_{0}:=T\cap\bar{C}_{h^{\prime}}$, $T_{1}:=T\setminus T_{0},$ and
$T_{2}:=\bar{C}_{h^{\prime}}\setminus T_{0}$. Then $T=T_{0}\cup T_{1}$,
$\bar{C}_{h^{\prime}}=T_{0}\cup T_{2}$. Since $T\neq\bar{C}_{h^{\prime}}$ and
$T\triangleright\bar{C}_{h^{\prime}}$, then we know $T_{1}\neq\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^{\prime}})$.
Hence we assume $T_{2}\neq\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, there is
$k_{1}<j_{1},k_{1}\notin\bar{C}_{h^{\prime}},j_{1}\in\bar{C}_{h^{\prime}}$, or
equivalently: $k_{1}<j_{1},k_{1}\in
C_{h^{\prime}},j_{1}\in\bar{C}_{h^{\prime}}$. Therefore,
$j_{1}\in\\{\ell\mid\ell>k_{1},\ell\in\bar{C}_{h^{\prime}},k_{1}\in
C_{h^{\prime}}\\}$. By construction of MCI, we know that
$\alpha_{k_{1}}>\alpha_{j_{1}}$. For the remaining $j_{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})\geq\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^{\prime}})$,
which concludes the proof. ∎

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

###### Theorem 3.1

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

###### Proof

Since $\operatorname{supp}(\alpha)=C$, in order to show that
$\alpha^{T}x\leq\beta$ is valid for $\operatorname{conv}(K)$, it suffices to
show that, for any $T\subseteq C$ with $\alpha(T)\geq\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})\geq\alpha(T_{2})$ is equivalent to
$\alpha(\bar{T}_{1})\leq\alpha(\bar{T}_{2})$. Therefore from Lemma 2, it
suffices to show that: for any $T\subseteq C$ with
$\alpha(\bar{T})\leq\min_{h=1}^{k}\alpha(\bar{C}_{h})$, there must exist 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.

First, we consider the case $\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}\neq\bar{C}_{h^{*}}$, by Proposition 1 we obtain that
$\alpha(\bar{T})>\alpha(\bar{C}_{h^{*}})$, and this contradicts to the
assumption that $\alpha(\bar{T})\leq\min_{h=1}^{k}\alpha(\bar{C}_{h})$.

Next, we consider the case $\bar{T}\cap C_{0}\neq\emptyset$. In this case, we
want to construct a $\bar{D}\subseteq C$ with $\bar{D}\cap
C_{0}=\emptyset,\alpha(\bar{D})\leq\alpha(\bar{T})$, and
$\bar{D}\triangleright\bar{T}$. Then since
$\alpha(\bar{T})\leq\min_{h=1}^{k}\alpha(\bar{C}_{h})$, we have
$\alpha(\bar{D})\leq\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.

Next, 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:

$\alpha_{t^{*}}\geq\max\big{\\{}\max_{\ell<t^{*},\ell\in\bar{C}_{h^{*}}}\alpha_{\ell},\sum_{t>t^{*},t\in\bar{C}_{h^{*}}}\alpha_{t}+1\big{\\}}.$

If $\\{\ell\in\bar{C}_{h^{*}}\mid\ell<t^{*}\\}\subseteq\bar{T}$, then we have
$\alpha(\bar{T})\geq\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})\leq\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^{*}}\geq\max_{\ell<t^{*},\ell\in\bar{C}_{h^{*}}}\alpha_{\ell}$, we
know that $\alpha(\bar{T})-\alpha(\bar{D})\geq 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})\leq\alpha(\bar{T})$, and
$\bar{D}\triangleright\bar{T}$. This completes the proof of the case
$\bar{T}\cap C_{0}\neq\emptyset$.

Therefore from the discussion of the above two cases, we have concluded the
proof that the MCI $\alpha^{T}x\leq\beta$ is a valid inequality for
$\operatorname{conv}(K)$. ∎

###  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}\geq\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}\geq\max_{h\in[2]:3\in
C_{h}}\max_{\ell\in\bar{C}_{h}:\ell>2}\alpha_{\ell}+1=2$, and we pick
$\alpha_{3}=3$. For $j\in C_{0}=\\{1,2,4\\}$, from Step 6, we have:

$\displaystyle\alpha_{1}\geq\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,$
$\displaystyle\alpha_{2}\geq\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,$
$\displaystyle\alpha_{4}\geq\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.$

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}\leq 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$. $\hfill\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\geq 3$. Here the family of covers $\\{C_{1},C_{2}\\}$ is a multi-cover, and
the following inequality is one of its associated MCIs:

$\sum_{i<i_{1},i\in C}tx_{i}+\sum_{i_{1}\leq i<i_{2},i\in
C}(t-1)x_{i}+\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}\leq\beta,$ (4)

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

Here is 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\geq 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{split}&\sum_{i<i_{1},i\in C}(2t-1)x_{i}+\sum_{i_{1}\leq 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}+\\\
&+\sum_{\ell=2}^{t}2x_{i_{\ell}}+\sum_{i_{t}<i<i_{t+1},i\in
C}2x_{i}+x_{i_{t+1}}+\sum_{i>i_{t+1},i\in C}2x_{i}\leq\beta,\end{split}$ (5)

where $\beta$ is the left-hand-side term evaluated at the point
$\chi^{C_{1}}(\text{or }\chi^{C_{2}})$ minus 1. $\hfill\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{split}&\sum_{i<i_{1},i\in C}5x_{i}+\sum_{i_{1}\leq i<i_{2},i\in
C}3x_{i}+2x_{i_{2}}+\sum_{i_{2}<i<i_{3},i\in C}3x_{i}+2x_{i_{3}}+\\\
&+\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}\leq\beta,\end{split}$ (6)

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. $\hfill\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

$3x_{1}+2x_{2}+x_{3}+x_{4}+x_{5}\leq 5,$ (7)

and (7) is violated by both $\chi^{C_{1}}$ and $\chi^{C_{2}}$.

One can further check that this S-MCI (7) is facet-defining for
$\operatorname{conv}(K)$. In fact, $\operatorname{conv}(K)$ can be exactly
characterized by this S-MCI, along with the bound constraints $0\leq x_{i}\leq
1\ \forall i\in[5]$, and the following four CIs: $x_{1}+x_{2}+x_{5}\leq
2,x_{1}+x_{2}+x_{4}\leq 2,x_{1}+x_{2}+x_{3}\leq 2,x_{1}+x_{3}+x_{4}+x_{5}\leq
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\leq
31\lambda_{1}+30\lambda_{2}$, where $\lambda_{1},\lambda_{2}\geq 0$. For any
choice of $\lambda_{1}\geq 0,\lambda_{2}\geq 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 (7)
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

$\displaystyle K_{CI}:=\\{x\in\\{0,1\\}^{5}\mid\ $ $\displaystyle
19x_{1}+11x_{2}+5x_{3}+4x_{4}+2x_{5}\leq 31,$ $\displaystyle
16x_{1}+10x_{2}+7x_{3}+5x_{4}+3x_{5}\leq 30,$ $\displaystyle
x_{1}+x_{2}+x_{3}\leq 2,x_{1}+x_{2}+x_{4}\leq 2,$ $\displaystyle
x_{1}+x_{2}+x_{5}\leq 2,x_{1}+x_{3}+x_{4}+x_{5}\leq 3\\}.$

The inequality (7) 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\leq\lfloor 5.75\rfloor=5$ is a CG cut for
$K_{CI}$. $\hfill\diamond$

Example 6 demonstrates that MCIs can be obtained from multiple knapsack sets
simultaneously. Specifically, the inequality (7) is facet-defining for
$\operatorname{conv}(K)$, but it is neither valid for
$\\{x\in\\{0,1\\}^{5}\mid 19x_{1}+11x_{2}+5x_{3}+4x_{4}+2x_{5}\leq 31\\}$ nor
for $\\{x\in\\{0,1\\}^{5}\mid 16x_{1}+10x_{2}+7x_{3}+5x_{4}+3x_{5}\leq 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:

$\displaystyle K:=\\{x\in\\{0,1\\}^{8}\mid\ $ $\displaystyle
28x_{1}+24x_{2}+20x_{3}+19x_{4}+15x_{5}+10x_{6}+7x_{7}+6x_{8}\leq 96,$
$\displaystyle
27x_{1}+24x_{2}+21x_{3}+19x_{4}+13x_{5}+12x_{6}+7x_{7}+4x_{8}\leq 96\\}.$

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\leq\beta$ given by

$4x_{1}+3x_{2}+3x_{3}+2x_{4}+3x_{5}+2x_{6}+x_{7}+x_{8}\leq 14,$ (8)

and it can be shown that (8) is facet-defining for $\operatorname{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 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\leq 15$, which is weaker than
inequality (8). $\hfill\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 letchford2019lifted )

Let $K:=\\{x\in\\{0,1\\}^{5}\mid 10x_{1}+7x_{2}+7x_{3}+4x_{4}+4x_{5}\leq
16\\}$, and consider the multi-cover
$\mathscr{C}:=\\{\\{1,3\\},\\{1,4,5\\},\\{2,3,5\\}\\}$. From inequality (6) of
Example 5, we know that the corresponding S-MCI is

$3x_{1}+2x_{2}+2x_{3}+x_{4}+x_{5}\leq 4.$ (9)

The inequality (9) is the same inequality produced by the new lifting
procedure described in letchford2019lifted , and the authors of
letchford2019lifted  state that (9) is both a facet of
$\operatorname{conv}(K)$ and cannot be obtained from any cover inequality by
standard sequential lifting methods, regardless of the lifting order.
$\hfill\diamond$

Next, we discuss how the well-known _$(1,k)$ -configuration inequality_ can be
derived from the MCI.

###### Proposition 2

Consider a knapsack set $K=\\{x\in\\{0,1\\}^{n}\mid a^{T}x\leq b\\}$, a
nonempty subset $Q\subseteq[n]$, and $t\in[n]\setminus Q$. Assume that
$\sum_{i\in Q}a_{i}\leq 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\leq r\leq|Q|$, the $(1,k)$-configuration inequality

$(r-k+1)x_{t}+\sum_{j\in T(r)}x_{j}\leq r$

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}\geq\ldots\geq a_{n}$. Consider a new
knapsack set $K^{\prime}:=\\{x\in\\{0,1\\}^{n+1}\mid a^{\prime T}x\leq b\\}$,
with $a^{\prime}_{i}=a_{i}\ \forall i\leq t$, $a^{\prime}_{t+1}=a_{t}$,
$a^{\prime}_{j}=a_{j-1}\ \forall j>t+1.$ Then clearly we have
$a^{\prime}_{1}\geq\ldots\geq a^{\prime}_{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}\leq 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\leq
r\leq|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^{\prime}_{1}:=\\{t\\}\cup\\{j_{r-k+1}+1,\ldots,j_{r}+1\\}$, and
$C^{\prime}_{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^{\prime}_{1}$ is a cover for $K^{\prime}$ from the construction of
$K^{\prime}$. Furthermore $C^{\prime}_{2}$ is a cover for $K^{\prime}$ since
$a^{\prime}_{t+1}=a^{\prime}_{t}$. Note that the discrepancy family of
$\\{C^{\prime}_{1},C^{\prime}_{2}\\}$ is
$\\{\\{t\\},\\{t+1,j_{1}+1,\ldots,j_{r-k}+1\\}\\}$, thus by Example 3, the
inequality

$(r-k+1)x_{t}+x_{t+1}+\sum_{\ell=1}^{r}x_{j_{\ell}+1}\leq r$ (10)

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

$(r-k+1)x_{t}+\sum_{\ell=1}^{r}x_{j_{\ell}}=(r-k+1)x_{t}+\sum_{j\in
T(r)}x_{j}\leq r.$

∎

###  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 balas1975facets . 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:

$x([\min(C)-1]\cup C)\leq|C|-1,$ (11)

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\leq\beta$ be an MCI of this
multi-cover, then the inequality $x([\min(C)-1])+\alpha^{T}x\leq\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}$ 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. 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\leq\beta$ generated from a multi-cover
$\\{C_{1},\ldots,C_{k}\\}$. Then the following inequality

$\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\leq\beta$
(12)

is called an _extended MCI_ (E-MCI).

Same as the remark we made 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 (12) is applied to the
normal CI, this inequality gives the same ECI as (11).

Next, we prove that inequality (12) is indeed a valid inequality for $K$.

###### Theorem 3.2

For a TOMKS $K$ and an MCI $\alpha^{T}x\leq\beta$ generated from a multi-cover
$\\{C_{1},\ldots,C_{k}\\}$, the E-MCI (12) is valid for $K$.

###### Proof

In order to show that inequality (12) is valid for $K$, it suffices to show
that for any $S\subseteq[n]$ whose incidence vector $\chi^{S}$ violates the
inequality (12), 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|$.

When $|S\cap E|=0$, $\chi^{S}$ violates inequality (12) if and only if
$\chi^{S}$ violates the original MCI $\alpha^{T}x\leq\beta$, which implies
that $S$ is a cover for $K$ since we know that $\alpha^{T}x\leq\beta$ is valid
for $K$. Now we assume that when $|S\cap E|=N(N<|E|)$ our statement is true.
Consider the case where $|S\cap E|=N+1$. We want to 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]$. We consider two cases.

  1. 1.

If $\\{i\in C_{h^{*}}\mid\alpha_{i}\geq\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

$\displaystyle S$ $\displaystyle\supseteq\\{i^{*}\\}\cup\\{i\in
C_{h^{*}}\mid\alpha_{i}\geq\alpha_{2,C_{h^{*}}}\\}$
$\displaystyle\triangleright\\{i\in
C_{h^{*}}\mid\alpha_{i}<\alpha_{2,C_{h^{*}}}\\}\cup\\{i\in
C_{h^{*}}\mid\alpha_{i}\geq\alpha_{2,C_{h^{*}}}\\}$ $\displaystyle=C_{h^{*}},$

which indicates that $S$ must also be a cover for $K$.

  2. 2.

If there exists $j^{*}\in\\{i\in
C_{h^{*}}\mid\alpha_{i}\geq\alpha_{2,C_{h^{*}}}\\}$ and $j^{*}\notin S$, then
we have $\alpha_{j^{*}}\geq\alpha_{2,C_{h^{*}}}$, which is the coefficient of
$x_{i^{*}}$ in equality (12). Consider
$S^{\prime}:=S\setminus\\{i^{*}\\}\cup\\{j^{*}\\}$, which is dominated by $S$
since $i^{*}<\min(C_{h}^{*})$. Since $\chi^{S}$ violates inequality (12), we
know that $\chi^{S^{\prime}}$ also violates inequality (12). Note that
$|S^{\prime}\cap E|=|S\cap E|-1=N$, so by the inductive hypothesis, we know
that $S^{\prime}$ must be a cover for $K$. Since $S\triangleright S^{\prime}$,
we obtain that $S$ must also be a cover for $K$.

By induction, we conclude the proof. ∎

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

###### Example 9

Let $K:=\\{x\in\\{0,1\\}^{7}\mid
10x_{1}+10x_{2}+7x_{3}+7x_{4}+7x_{5}+4x_{6}+4x_{7}\leq 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:

$3x_{2}+2x_{4}+2x_{5}+x_{6}+x_{7}\leq 4.$

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:

$3x_{1}+3x_{2}+2x_{3}+2x_{4}+2x_{5}+x_{6}+x_{7}\leq 4.$ (13)

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

We give another interesting example with only one knapsack constraint.

###### Example 10

Let $K:=\\{x\in\\{0,1\\}^{6}\mid
66x_{1}+61x_{2}+54x_{3}+33x_{4}+21x_{5}+16x_{6}\leq 130\\}$. From the multi-
cover $\\{C_{1},C_{2}\\}:=\\{\\{2,3,6\\},\\{2,4,5,6\\}\\}$ we obtain an MCI:
$3x_{2}+2x_{3}+x_{4}+x_{5}+x_{6}\leq 5$. Note that $\alpha_{2,C_{1}}=2$,
$\alpha_{2,C_{2}}=1$, so from (12) we obtain the corresponding E-MCI
$2x_{1}+3x_{2}+2x_{3}+x_{4}+x_{5}+x_{6}\leq 5$, which is also a facet-defining
inequality for $\operatorname{conv}(K)$. $\hfill\diamond$

##  4 Facet-defining Inequalities

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

Given a multi-cover $\\{C_{1},\dots,C_{k}\\}$ and an S-MCI
$\alpha^{T}x\leq\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 whose S-MCI coefficients are all
$t$, where $i_{t,1}<\ldots<i_{t,n_{t}}$.

###### Theorem 4.1

Let $\\{C_{1},\dots,C_{k}\\}$ be a multi-cover for a TOMKS $K$, and let
$\alpha^{T}x\leq\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
$i_{t-1,\ell_{t}}\notin C_{h_{t}}\in\\{C_{h}\\}_{h=1}^{k}$ with $i_{t,1}\in
C_{h_{t}}$ and $i_{1,n_{1}}\in C_{h_{t}}$, such that
$C_{h_{t}}\cup\\{i_{t-1,\ell_{t}}\\}\setminus\\{i_{t,n_{t}}\\}$ is not a
cover;

  4. 4.

There exists some $C_{h_{1}}\in\\{C_{h}\\}_{h=1}^{k}$, such that $i_{1,1}\in
C_{h_{1}}$ and for any $i^{\prime}\notin C$,
$C_{h_{1}}\cup\\{i^{\prime}\\}\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\leq\beta$ is a facet-defining inequality of
$\operatorname{conv}(K)$.

The proof of this theorem is deferred to Appendix A.

###### Example 11

Consider the TOMKS and the multi-cover in Example 8. We have
$C_{1}=\\{1,3\\}$, $C_{2}=\\{1,4,5\\}$, $C_{3}=\\{2,3,5\\}$, Then the
corresponding S-MCI $\alpha^{T}x\leq\beta$ is
$3x_{1}+2x_{2}+2x_{3}+x_{4}+x_{5}\leq 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 4.1 holds. Since
$\alpha(C_{1})-\alpha_{3}=10\leq 16$, $\alpha(C_{2})-\alpha_{5}=14\leq 16$,
$\alpha(C_{3})-\alpha_{5}=14\leq 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 4.1 yields that this S-MCI is facet-defining.
$\hfill\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 every subset $Z$ of $[n]$, the _deletion_ is defined as
$\\{A\in\mathcal{C}\mid A\cap Z=\emptyset\\}$, and the _contraction_ is
defined as $\\{A-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 Section 1.

###### Theorem 4.2

Let $\mathcal{C}$ be the minimal cover set of a TOMKS $K$. Then
$\operatorname{conv}(K)=\\{x\in[0,1]^{n}\mid x(C)\leq|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\geq
3.$

Theorem 4.2 follows easily from Theorem 1.1 in laurent1992characterization
(see also seymour1977matroids ) and the fact that the minimal cover set
$\mathcal{C}$ of a TOMKS $K$ is indeed a _shift clutter_ as defined in
bertolazzi1987mn . For completeness, we provide a proof in Appendix B.

From Theorem 4.2, we know that in order for $\operatorname{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\leq 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 $\operatorname{conv}(K)$.

###### Theorem 4.3

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\leq n$. Then
$\operatorname{conv}(K)$ can be described by the bound constraints, the CIs:
$\sum_{i=1}^{p}x_{i}+x_{j}\leq p\text{ for }j=p+1,\ldots,q,$
$\sum_{i=1}^{p-1}x_{i}+\sum_{i=p+1}^{q}x_{i}\leq 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}\leq p(q-p)-1$.

Since CI is a special case of MCI, Theorem 4.3 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{NP}$-hard ferreira1996solving ; gu1999lifted ; klabjan1998complexity
, several efficient heuristics and exact separation algorithms have been
proposed crowder1983solving ; gu1998lifted ; wolsey1999integer ;
weismantel19970 . 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\to\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 various MCIs altogether.
In fact, for any given family of covers, we conjecture that it is
$\mathcal{NP}$-hard to decide whether or not it 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\geq 3$. There 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:

$\displaystyle\begin{split}\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\geq\sum_{i\in[n]}\alpha_{i},\
t\geq\sum_{i\in[n]}\beta_{i},\\\ &u_{i}+v_{i}+w_{i}\leq 1,\quad\forall
i\in[n]\\\ &\alpha_{i}\geq\beta_{j}+(1+M)u_{i}-M,\
\beta_{i}\geq\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}\leq Mu_{i},\
\beta_{i}\leq Mv_{i},\ \gamma_{i}\leq Mw_{i},\quad\forall i\in[n]\\\
&\gamma_{i}\geq\sum_{j>i}\alpha_{j}+(1+nM)w_{1,i}-nM,\
\gamma_{i}\geq\sum_{j>i}\beta_{j}+(1+nM)w_{2,i}-nM,\quad\forall i\in[n]\\\
&\gamma_{i}\geq\alpha_{j}+Mw_{1,i}-M,\
\gamma_{i}\geq\beta_{j}+Mw_{2,i}-M,\quad\forall i,j\in[n],\ j<i\\\
&\sum_{i\in[n]}A_{j,i}(u_{i}+w_{i})\geq(b_{j}+1)\cdot\lambda_{j},\
\sum_{i\in[n]}A_{j,i}(v_{i}+w_{i})\geq(b_{j}+1)\cdot\mu_{j},\quad\forall
j\in[m]\\\ &\sum_{j\in[m]}\lambda_{j}\geq 1,\sum_{j\in[m]}\mu_{j}\geq 1,\\\
&\sum_{i\in[n]}v_{i}\geq 2,\ \sum_{j<i}u_{j}\geq v_{i},\ v_{i}+\sum_{j\leq
i}u_{j}\leq 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{split}$ (Sep2)

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 5.1

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\geq 3$ and an associated MCI
to separate $\tilde{x}$ from $K$, if and only if (Sep2) has an 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 $u_{i}:=\mathbbm{1}\\{i\in
C_{1}\setminus C_{2}\\}$, $v_{i}:=\mathbbm{1}\\{i\in C_{2}\setminus C_{1}\\}$,
and $w_{i}:=\mathbbm{1}\\{i\in C_{1}\cap C_{2}\\}$. So we have the second
constraint $u_{i}+v_{i}+w_{i}\leq 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}\leq Mu_{i}$ etc., through some
“big-M” constant. From Step 7 of Algorithm 1,

$\sum_{i\in[n]}(\alpha_{i}+\beta_{i}+\gamma_{i})x\leq\max(\sum_{i}\alpha_{i}+\sum_{i}\gamma_{i},\sum_{i}\beta_{i}+\sum_{i}\gamma_{i})-1$

is the MCI we will obtain. Introducing an additional variable $t$ and
constraints $t\geq\sum_{i}\alpha_{i}$, $t\geq\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}\geq\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}\geq\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}\geq\sum_{j>i}\alpha_{j}+(1+nM)w_{1,i}-nM,\gamma_{i}\geq\alpha_{j}+Mw_{1,i}-M$
etc., we are able to formulate the constraint of Step 6 of Algorithm 1:

$\displaystyle\begin{split}&\gamma_{i}\geq\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}\geq\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{split}$

Constraints $\sum_{i\in[n]}A_{j,i}(u_{i}+w_{i})\geq(b_{j}+1)\cdot\lambda_{j},\
\sum_{i\in[n]}A_{j,i}(v_{i}+w_{i})\geq(b_{j}+1)\cdot\mu_{j}$ and
$\sum_{i}\lambda\geq 1,\sum_{i}\mu_{i}\geq 1$ enforce that $C_{1}$ and $C_{2}$
are two covers of $K$. Lastly, the constraints $\sum_{i\in[n]}v_{i}\geq
2,\sum_{j<i}u_{j}\geq v_{i},v_{i}+\sum_{j\leq i}u_{j}\leq 2$ enforce the
$\\{\\{1\\},\\{2,\ldots,t\\}\\}$ or $\\{\\{1,t+1\\},\\{2,\ldots,t\\}\\}$
skeleton structures with $t\geq 3$. In particular, constraint
$\sum_{j<i}u_{j}\geq 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\leq i}u_{j}\leq 2$ means $|C_{1}\setminus C_{2}|\leq 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\\}\\}$. ∎

It’s worth mentioning that, the constraint $\sum_{i\in[n]}v_{i}\geq 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\leq 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}\geq 2$ therein, so the separation
problem may separate CI as well. The numerical experiment proceeds 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}$ does not have optimal value
being strictly less than 1. Otherwise, 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\leq 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
padberg1975note , 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 (12).

  * _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 exactly solved by solving an IP, as in crowder1983solving .

  * _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 Table 1 and Table 2, and more
details can be found in Appendix E. For different combinations of $(n,m)$, in
Table 1, we list the average optimality gap obtained from optimizing over the
different relaxations studied, and 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 Figure 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. (%) (n,m) |  LP |  MCI |  E-MCI |  L-MCI |  CI |  ECI |  LCI
---|---|---|---|---|---|---|---
(20, 1) |  3.93 |  1.08 |  0.27 |  0.11 |  2.00 |  0.65 |  0.63
(20, 2) |  6.01 |  2.90 |  1.02 |  0.21 |  4.23 |  1.69 |  1.12
(20, 3) |  6.03 |  3.89 |  0.73 |  0.27 |  4.67 |  1.17 |  1.12
(30, 1) |  6.34 |  4.78 |  0.59 |  0.24 |  5.24 |  0.68 |  0.65
(30, 2) |  4.76 |  2.95 |  0.89 |  0.19 |  3.51 |  1.09 |  0.83
(30, 3) |  3.13 |  2.50 |  0.83 |  0.31 |  2.67 |  0.90 |  0.80
Table 2: Number of instances been solved to optimality. (out of 10) (n,m) |  LP |  MCI |  E-MCI |  L-MCI |  CI |  ECI |  LCI
---|---|---|---|---|---|---|---
(20, 1) |  0 |  3 |  4 |  6 |  1 |  1 |  2
(20, 2) |  0 |  0 |  2 |  6 |  0 |  1 |  2
(20, 3) |  0 |  1 |  4 |  8 |  0 |  2 |  2
(30, 1) |  0 |  1 |  3 |  7 |  1 |  3 |  3
(30, 2) |  0 |  1 |  5 |  7 |  0 |  4 |  5
(30, 3) |  0 |  1 |  2 |  6 |  1 |  2 |  2
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.

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.

## References

  * (1) Balas, E.: Facets of the knapsack polytope.  Mathematical programming 8(1), 146–164 (1975)
  * (2) Balas, E., Jeroslow, R.: Canonical cuts on the unit hypercube.  SIAM Journal on Applied Mathematics 23(1), 61–69 (1972)
  * (3) Bertolazzi, P., Sassano, A.: An $O(mn)$ algorithm for regular set-covering problems.  Theoretical Computer Science 54(2-3), 237–247 (1987)
  * (4) Bodur, M., Del Pia, A., Dey, S.S., Molinaro, M., Pokutta, S.: Aggregation-based cutting-planes for packing and covering integer programs.  Math. Program. 171(1-2, Ser. A), 331–359 (2018).  DOI 10.1007/s10107-017-1192-x.  URL https://doi.org/10.1007/s10107-017-1192-x
  * (5) Calafiore, G.C., Campi, M.C.: The scenario approach to robust control design.  IEEE Trans. Automat. Control 51(5), 742–753 (2006).  DOI 10.1109/TAC.2006.875041.  URL https://doi.org/10.1109/TAC.2006.875041
  * (6) Crowder, H., Johnson, E.L., Padberg, M.: Solving large-scale zero-one linear programming problems.  Operations Research 31(5), 803–834 (1983)
  * (7) Del Pia, A., Linderoth, J., Zhu, H.: Multi-cover inequalities for totally-ordered multiple knapsack sets.  Proceedings of IPCO (2021)
  * (8) Ferreira, C.E., Martin, A., Weismantel, R.: Solving multiple knapsack problems by cutting planes.  SIAM Journal on Optimization 6(3), 858–877 (1996)
  * (9) Fukasawa, R., Goycoolea, M.: On the exact separation of mixed integer knapsack cuts.  Mathematical Programming 128, 19–41 (2011)
  * (10) Gu, Z., Nemhauser, G.L., Savelsbergh, M.W.: Lifted cover inequalities for 0-1 integer programs: Computation.  INFORMS Journal on Computing 10(4), 427–437 (1998)
  * (11) Gu, Z., Nemhauser, G.L., Savelsbergh, M.W.: Lifted cover inequalities for 0-1 integer programs: Complexity.  INFORMS Journal on Computing 11(1), 117–123 (1999)
  * (12) Hammer, P.L., Johnson, E.L., Peled, U.N.: Facet of regular 0–1 polytopes.  Mathematical Programming 8(1), 179–206 (1975)
  * (13) Hojny, C., Gally, T., Habeck, O., Lüthen, H., Matter, F., Pfetsch, M.E., Schmitt, A.: Knapsack polytopes: a survey.  Annals of Operations Research pp. 1–49 (2019)
  * (14) Klabjan, D., Nemhauser, G.L., Tovey, C.: The complexity of cover inequality separation.  Operations Research Letters 23(1-2), 35–40 (1998)
  * (15) Laurent, M., Sassano, A.: A characterization of knapsacks with the max-flow-min-cut property.  Operations Research Letters 11(2), 105–110 (1992)
  * (16) Letchford, A.N., Souli, G.: On lifted cover inequalities: A new lifting procedure with unusual properties.  Operations Research Letters 47(2), 83–87 (2019)
  * (17) Luedtke, J., Ahmed, S.: A sample approximation approach for optimization with probabilistic constraints.  SIAM J. Optim. 19(2), 674–699 (2008).  DOI 10.1137/070702928.  URL https://doi.org/10.1137/070702928
  * (18) Nemirovski, A., Shapiro, A.: Scenario approximation of chance constraints.  In: G. Calafiore, F. Dabbene (eds.) Probabilistic and Randomized Methods for Design Under Uncertainty, pp. 3–48. Springer (2005)
  * (19) Padberg, M.W.: A note on zero-one programming.  Operations Research 23(4), 833–837 (1975)
  * (20) Padberg, M.W.: (1, k)-configurations and facets for packing problems.  Mathematical Programming 18(1), 94–99 (1980)
  * (21) Seymour, P.D.: The matroids with the max-flow min-cut property.  Journal of Combinatorial Theory, Series B 23(2-3), 189–222 (1977)
  * (22) Weismantel, R.: On the 0/1 knapsack polytope.  Mathematical Programming 77(3), 49–68 (1997)
  * (23) Wolsey, L.A.: Facets and strong valid inequalities for integer programs.  Operations research 24(2), 367–372 (1976)
  * (24) Wolsey, L.A., Nemhauser, G.L.: Integer and combinatorial optimization, vol. 55.  John Wiley & Sons (1999)

##  Appendix A Proof of Theorem 4.1

First, by Step 4 in Algorithm 1, we have the following easy observation.

###### Observation 2

Let $\\{C_{1},\dots,C_{k}\\}$ be a multi-cover and let $\alpha^{T}x\leq\beta$
its corresponding S-MCI. If there exist some $t\in\mathbb{N},\ell\in[n_{t}]$
and $h^{\prime}\in[k]$ such that $i_{t,\ell}\in C_{h^{\prime}}$, then
$\\{i_{t,\ell},\ldots,i_{t,n_{t}}\\}\subseteq C_{h^{\prime}}$.

Now we can prove Theorem 4.1.

######  Proof (Proof of Theorem 4.1)

Consider the set of binary points whose support is in one of the following
sets:

$\displaystyle\mathscr{S}_{1}:=\\{C_{h_{t}}\cup\\{i_{t-1,\ell_{t}}\\}\setminus\\{i_{t,\ell}\\}\mid
t=2,\ldots,\max_{i=1}^{n}\alpha_{i},\ell=1,\ldots,n_{t}\\},$ (14)
$\displaystyle\mathscr{S}_{2}:=\\{C_{h_{t}}\setminus\\{i_{1,n_{1}}\\}\mid
t=2,\ldots,\max_{i=1}^{n}\alpha_{i}\\},$ (15)
$\displaystyle\mathscr{S}_{3}:=\\{C_{h_{1}}\setminus\\{i_{1,\ell}\\}\mid\ell=1,\ldots,n_{1}\\},$
(16)
$\displaystyle\mathscr{S}_{4}:=\\{C_{h_{1}}\cup\\{i^{\prime}\\}\setminus\\{i_{1,1}\\}\mid
i^{\prime}\notin C\\}.$ (17)

First, we want to prove that any set in (14)-(17) is not a cover for $K$. By
condition 3, we know $i_{1,n_{1}}\in C_{h_{t}}$ for any
$t=2,\ldots,\max_{i=1}^{n}\alpha_{i}$, and by condition 4, we know $i_{1,1}\in
C_{h_{1}}$. From Observation 2, there is
$\\{i_{1,1},\ldots,i_{1,n_{1}}\\}\subseteq C_{h_{1}}$. Hence by condition 2,
we know that for any
$t=2,\ldots,\max_{i=1}^{n}\alpha_{i},C_{h_{t}}\setminus\\{i_{1,n_{1}}\\}$ is
not a cover for $K$, and for any
$\ell=1,\ldots,n_{1},C_{h_{1}}\setminus\\{i_{1,\ell}\\}$ is not a cover for
$K$. So any set in $\mathscr{S}_{2}\cup\mathscr{S}_{3}$ is not a cover.
Condition 4 directly states that any set in $\mathscr{S}_{4}$ is not a cover.
Furthermore, condition 3 states that $i_{t,1}\in C_{h_{t}}$, then by
Observation 2, we know that for any $\ell\in[n_{t}],i_{t,\ell}\in C_{h_{t}}$.
Also, condition 3 states that
$C_{h_{t}}\cup\\{i_{t-1,\ell_{t}}\\}\setminus\\{i_{t,n_{t}}\\}$ is not a
cover, so $C_{h_{t}}\cup\\{i_{t-1,\ell_{t}}\\}\setminus\\{i_{t,\ell}\\}$ is
also not a cover of $K$. Hence any set in $\mathscr{S}_{1}$ is not a cover of
$K$.

Now we want to show that $\alpha^{T}x=\beta$ is the only hyperplane that
contains all the incidence vectors of the sets in
$\mathscr{S}_{1}\cup\mathscr{S}_{2}\cup\mathscr{S}_{3}\cup\mathscr{S}_{4}$.
Let $u^{T}x=v$ be the hyperplane that contains all those binary points. Then,
from the sets in $\mathscr{S}_{3}$, we know that
$u_{i_{1,1}}=\ldots=u_{i_{1,n_{1}}}$, and we denote it to be $\kappa$. Since
for any $t=2,\ldots,\max_{i=1}^{n}\alpha_{i}$ and
$\ell=1,\ldots,n_{t},u(C_{h_{t}}\cup\\{i_{t-1,\ell_{t}}\\}\setminus\\{i_{t,\ell}\\})=v$,
we know that for any
$t=2,\ldots,\max_{i=1}^{n}\alpha_{i},u_{i_{t,1}}=\ldots=u_{i_{t,n_{t}}}$.
Furthermore, since
$u(C_{h_{t}}\cup\\{i_{t-1,\ell_{t}}\\}\setminus\\{i_{t,\ell}\\})=u(C_{h_{t}}\setminus\\{i_{1,n_{1}}\\})=v$,
we obtain that for any $t=2,\ldots,\max_{i=1}^{n}\alpha_{i}$ and
$\ell=1,\ldots,n_{t},u_{i_{t,\ell}}-u_{i_{t-1,\ell_{t}}}=u_{i_{1,n_{1}}}=\kappa$.
Lastly, from the points in $\mathscr{S}_{3}$ and in $\mathscr{S}_{4}$, we know
that $u_{i^{\prime}}=0$ for any $i^{\prime}\notin C$. Hence we obtain that,
for any $t=1,\ldots,\max_{i=1}^{n}\alpha_{i},\ell=1,\ldots,n_{t}$, there is
$u_{i_{t,\ell}}=\kappa\cdot t$, and for any $i^{\prime}\notin
C,u_{i^{\prime}}=0$. Since $\alpha_{i_{t,\ell}}=t$ and $\alpha_{i^{\prime}}=0$
for any
$t=1,\ldots,\max_{i=1}^{n}\alpha_{i},\ell=1,\ldots,n_{t},i^{\prime}\notin C$,
and $\\{i_{t,1},\ldots,i_{t,n_{t}}\\}=\\{i\in C\setminus
C_{0}\mid\alpha_{i}=t\\}$, we know that $u_{i}=\kappa\cdot\alpha_{i}$ for any
$i\notin C_{0}$. By condition 1, we have $u=\kappa\cdot\alpha$. Using
condition 5, it is simple to check that
$v=u(C_{h_{t}})-\kappa=\kappa\cdot\alpha(C_{h_{t}})-\kappa=\kappa\cdot\beta$
for any $t=1,\ldots,\max_{i=1}^{n}\alpha_{i}$. Thus, we obtain that
$(u,v)=\kappa\cdot(\alpha,\beta)$, and this concludes the proof that
$\alpha^{T}x=\beta$ is the only hyperplane that contains all the incidence
vectors of sets in
$\mathscr{S}_{1}\cup\mathscr{S}_{2}\cup\mathscr{S}_{3}\cup\mathscr{S}_{4}$,
which are all in the TOMKS $K$. Since the S-MCI $\alpha^{T}x\leq\beta$ is a
valid inequality for $\operatorname{conv}(K)$, we obtain that
$\alpha^{T}x\leq\beta$ is a facet-defining inequality for
$\operatorname{conv}(K)$. ∎

##  Appendix B Proof of Theorem 4.2

Here we restate Theorem 1.1 in laurent1992characterization .

######  Theorem B.1 (Theorem 1.1 laurent1992characterization )

If a clutter $\mathscr{L}$ has no $P_{4}:=\\{\\{1,2\\},\\{2,3\\},\\{3,4\\}\\}$
minor, then

$\operatorname{conv}(\\{x\in\mathbb{Z}^{n}_{+}\mid x(L)\geq 1,\forall
L\in\mathscr{L}\\})=\\{x\in\mathbb{R}^{n}_{+}\mid x(L)\geq 1,\forall
L\in\mathscr{L}\\}$

if and only if $\mathscr{L}$ has no minor isomorphic to one of the following
clutters:

  1. 1.

$Q_{6}=\\{\\{1,3,5\\},\\{1,4,6\\},\\{2,3,6\\},\\{2,4,5\\}\\}$;

  2. 2.

$J_{q}=\\{\\{2,\ldots,q\\},\\{1,i\\}\text{ for }i=2,\ldots,q\\},q\geq 3$.

######  Proof (Proof of Theorem 4.2)

Let $\mathcal{C}$ be a minimal cover set of a TOMKS $K$. We have the following
claim.

###### Claim

$\mathcal{C}$ has no minor isomorphic to $P_{4}$ or $Q_{6}$.

  * Proof of claim  Let $\\{\\{i_{1},i_{2}\\},\\{i_{2},i_{3}\\},\\{i_{3},i_{4}\\}\\}$ be the subset of one of the minors $M$ of $\mathcal{C}$, with $\\{\\{i_{1},i_{2}\\},\\{i_{2},i_{3}\\},\\{i_{3},i_{4}\\}\\}$ being isomorphic to $P_{4}$ and $i_{1}<\ldots<i_{4}$. Then by the TOMKS property of $K$, $M$ should also contain $\\{\\{i_{1},i_{3}\\},\\{i_{1},i_{4}\\},\\{i_{2},i_{4}\\}\\}$. This is a contradiction.

Now assume that
$\\{\\{i_{1},i_{3},i_{5}\\},\\{i_{1},i_{4},i_{6}\\},\\{i_{2},i_{3},i_{6}\\},\\{i_{2},i_{4},i_{5}\\}\\}$
is the subset of one of the minors $M$ of $\mathcal{C}$, such that it is
isomorphic to $Q_{6}$. W.l.o.g. we assume that $i_{1}<\ldots<i_{6}$. Then $M$
must also contain $\\{i_{2},i_{3},i_{5}\\}$, and this gives us a
contradiction. For any other possible ordering of the indices, we can obtain a
symmetric argument. $\hfill\diamond$

From Claim B and Theorem B.1, we obtain the following statement: If
$\mathcal{C}$ is the minimal cover set of a TOMKS $K$, then
$\operatorname{conv}(\\{y\in\mathbb{Z}^{n}_{+}\mid y(C)\geq 1,\forall
C\in\mathcal{C}\\})=\\{y\in\mathbb{R}^{n}_{+}\mid y(C)\geq 1,\forall
C\in\mathcal{C}\\}$ if and only if $\mathcal{C}$ has no minor isomorphic to a
clutter $J_{q}$, with $q\geq 3$. Therefore, all extreme points of the polytope
$\\{y\in[0,1]^{n}\mid y(C)\geq 1,\forall C\in\mathcal{C}\\}$ are integral if
and only if $\mathcal{C}$ has no minor isomorphic to $J_{q}$. By substituting
the variable $y$ with $1-x$, we know that
$\operatorname{conv}(\\{x\in\\{0,1\\}^{n}\mid x(C)\leq|C|-1,\forall
C\in\mathcal{C}\\})=\\{x\in[0,1]^{n}\mid x(C)\leq|C|-1,\forall
C\in\mathcal{C}\\}$ if and only if $\mathcal{C}$ has no minor isomorphic to
$J_{q}$. Moreover, it was shown in balas1972canonical  that,
$\operatorname{conv}(K)=\operatorname{conv}(\\{x\in\\{0,1\\}^{n}\mid
x(C)\leq|C|-1,\forall C\in\mathcal{C}\\})$, and this completes the proof. ∎

##  Appendix C Proof of Theorem 4.3

###### Proof

Let $\pi^{T}x\leq\pi_{0}$ be a non-trivial facet-defining inequality for
$\operatorname{conv}(K)$. Then clearly we have that
$\pi\in\mathbb{R}^{n}_{+},\pi_{0}>0$ (see also hammer1975facet ). W.l.o.g. we
can assume $\pi_{0}=1$. Denote $X:=\\{x\in K\mid\pi^{T}x=1\\}$, which has
dimension $n-1$ since $\pi^{T}x\leq 1$ is facet-defining. First, we obtain the
following claims.

###### Claim

$\pi_{i}=0$ for all $i=q+1,\ldots,n$.

  * Proof of claim  For any $i\in[n]\setminus[q]$, there exists some $x^{\prime}\in X$ with $x^{\prime}_{i}=0$, since otherwise $X\subseteq\\{x\mid x_{i}=1,\pi^{T}x=1\\},$ which has dimension $n-2$. If $\operatorname{supp}(x^{\prime})\cup\\{i\\}$ is a cover for $K$, then it must contain some minimal cover in $J_{q}$. However, $\operatorname{supp}(x^{\prime})$ does not contain any minimal cover (since $x^{\prime}$ is feasible), and $i\in[n]\setminus[q]$ is not contained in any minimal cover. Hence we know that $x^{\prime}+e^{i}\in K$, which has $\pi^{T}(x^{\prime}+e^{i})\leq 1$. Because $\pi^{T}x^{\prime}=1$, we obtain that $\pi_{i}=0$. $\hfill\diamond$

###### Claim

$\pi_{1}=\ldots=\pi_{p-1}=\pi([n])-1>0$.

  * Proof of claim  Suppose $\pi_{i}=0$ for some $i\in[p-1]$. From the minimal cover structure of $K$, we know that $[n]\setminus\\{i\\}$ is not a cover for $K$. Hence $\pi([n])=\pi([n]\setminus\\{i\\})\leq 1=\pi_{0}$, which means that $\pi^{T}x\leq 1$ is dominated by the bound constraints $x_{j}\leq 1,\forall j\in[n]$, a contradiction. Furthermore, for any $i\in[p-1]$, there exists some point $x^{\prime}\in X$ with $x^{\prime}_{i}=0$, since otherwise $X\subseteq\\{x\mid x_{i}=1,\pi^{T}x=\pi_{0}\\}$ which has dimension $n-2$. Hence $1=\pi^{T}x^{\prime}\leq\pi([n]\setminus\\{i\\})\leq 1$, which gives $\pi_{i}=\pi([n])-1$, for any $i\in[p-1]$. $\hfill\diamond$

###### Claim

If $\pi_{p}>0$, then $\pi([p])=1$.

  * Proof of claim  Since $\sum_{i=1}^{p}x_{i}=p-1$ is not valid for $K$, and $X$ is $(n-1)$-dimensional, we know that there exists $x^{\prime}\in X$ with $x^{\prime}([p])=p$ or $p-2$. If $x^{\prime}([p])=p-2$, then there must exist $i,j\in[p]$ such that $x^{\prime}_{i}=x^{\prime}_{j}=0$. From Claim C and the assumption of $\pi_{p}>0$, we know it’s impossible. Hence there exists $x^{\prime}\in X$ with $x^{\prime}_{i}=1$ for any $i\in[p]$. From the minimal cover set $K$, we know $x^{\prime}_{j}=0$ for any $j\in[q]\setminus[p]$. Therefore, $1=\pi^{T}x^{\prime}=\pi([p])=1$. $\hfill\diamond$

Next, we consider three different cases.

  1. 1.

Case $\pi_{p}=0$. In this case, we want to show that $\pi^{T}x\leq 1$ is the
same as the CI $\sum_{i=1}^{p-1}x_{i}+\sum_{i=p+1}^{q}x_{i}\leq q-2$. First,
we prove that $x([q])-x_{p}=q-2$ for any $x\in X$. If not, then there exists
some $x^{\prime}\in X$ and $i,j\in[q]\setminus\\{p\\}$, such that
$x^{\prime}_{i}=x^{\prime}_{j}=0$. We construct a new point $x^{\prime\prime}$
from $x^{\prime}$ by switching the $j$-th component from 0 to 1, and setting
$x^{\prime\prime}_{p}=0$. Since $x^{\prime\prime}_{p}=x^{\prime\prime}_{i}=0$,
we know that $x^{\prime\prime}\in K$. Note that
$1\geq\pi^{T}x^{\prime\prime}=\pi^{T}x^{\prime}+\pi_{j}=1+\pi_{j}$, thus we
have $\pi_{j}=0$. Hence $\pi([n]\setminus\\{p,j\\})=\pi([n])$. However,
$[n]\setminus\\{p,j\\}$ is not a cover, and we obtain $\pi([n])\leq 1$, which
means that the inequality $\pi^{T}x\leq 1$ is dominated by the bound
constraints, a contradiction. Therefore $x([q])-x_{p}=q-2$ for any $x\in X$.
Since $X=\\{x\in K\mid\pi^{T}x=1\\}$ is assumed to have dimension $(n-1)$, we
know that $\pi^{T}x\leq 1$ must be the same inequality as the CI:
$\sum_{i=1}^{p-1}x_{i}+\sum_{i=p+1}^{q}x_{i}\leq q-2$.

  2. 2.

Case $\pi_{p}>0$, and there exists $x^{\prime}\in X$ with $x^{\prime}_{p}=0$,
such that $x^{\prime}_{i}=1$ for any
$i\in\operatorname{supp}(\pi)\cap\\{p+1,\ldots,q\\}$. In this case consider
such point $x^{\prime}$. From Claim C, we have $\pi([n]\setminus\\{i\\})=1$
for any $i\in[p-1]$, thus we know that $x^{\prime}_{i}=1$ for any $i\in[p-1]$.
Hence $\pi^{T}x^{\prime}=\pi([n])-\pi_{p}=1$, from Claim C we have
$\pi_{1}=\ldots=\pi_{p-1}=\pi_{p}$. Also by Claim C, we have
$\pi_{1}=\ldots=\pi_{p}=\frac{1}{p}$. So the original inequality $\pi^{T}x\leq
1$ is just
$(\frac{1}{p},\ldots,\frac{1}{p},\pi_{p+1},\ldots,\pi_{q},0,\ldots,0)^{T}x\leq
1$, and from Claim C, there is
$\sum_{i=p+1}^{q}\pi_{i}=1-\frac{1}{p}\cdot(p-1)=\frac{1}{p}$. Multiplying
each CI $\sum_{i=1}^{p}x_{i}+x_{j}\leq p$ by a non-negative number $\pi_{j}$
for each $j=p+1,\ldots,q$, and summing them up, we obtain that our facet-
defining inequality $\pi^{T}x\leq 1$ is dominated by the CIs
$\sum_{i=1}^{p}x_{i}+x_{j}\leq p\text{ for }j=p+1,\ldots,q$. This means that
$\pi^{T}x\leq 1$ coincides with one of these CIs.

  3. 3.

Case $\pi_{p}>0$, and for any $x^{\prime}\in X$ with $x^{\prime}_{p}=0$, there
is $x^{\prime}_{j}=0$ for some index
$j\in\operatorname{supp}(\pi)\cap\\{p+1,\ldots,q\\}$. In this case, we have
the following claim.

###### Claim

$\pi_{p+1}=\ldots=\pi_{q}=\pi_{1}-\pi_{p}>0$.

     * Proof of claim  First, we show that $\pi_{i}>0$ for any $i\in[q]\setminus[p]$. If not, there is $i\in[q]\setminus[p]$ such that $\pi_{i}=0$. Arbitrarily pick a point $x^{\prime}\in X$ with $x^{\prime}_{p}=0$. By the assumption of this case, then there must exist $j\in[q]\setminus[p]$ such that $x^{\prime}_{j}=0$ and $\pi_{j}>0$. Then we construct another point $x^{\prime\prime}$ from $x^{\prime}$ by setting the $i$-th component to 0. Since $\pi_{i}=0$, we have $\pi^{T}x^{\prime\prime}=\pi^{T}x^{\prime}=1$, where $x^{\prime\prime}_{p}=x^{\prime}_{p}=0,x^{\prime\prime}_{j}=x^{\prime}_{j}=0,x^{\prime\prime}_{i}=0$. Note that $x^{\prime\prime}+e^{j}$ is also a feasible point in $K$. However, $1=\pi^{T}x^{\prime\prime}<\pi^{T}(x^{\prime\prime}+e^{j})$, a contradiction.

Next, we show that $\pi_{i}=\pi_{1}-\pi_{p}$ for any $i\in[q]\setminus[p]$.
Note that since $[q]\setminus\\{p\\}$ is a minimal cover, we know that
$[q]\setminus\\{p,i\\}$ is not a cover for any $i\in[q]\setminus[p]$. Hence
$\pi([q]\setminus\\{p,i\\})\leq 1$. Then from Claim C and C, we obtain
$\pi_{p}+\pi_{i}\geq\pi_{1}$, for any $i\in[q]\setminus[p]$. If for some
$i^{\prime}\in[q]\setminus[p]$ there is $\pi_{p}+\pi_{i^{\prime}}>\pi_{1}$,
then $\pi([q]\setminus\\{p,i^{\prime}\\})<1$, which yields that
$\sum_{i=1}^{p}x_{i}+x_{i^{\prime}}=p$ for any $x\in X$. Thus $\pi^{T}x\leq 1$
coincides with the CI $\sum_{i=1}^{p}x_{i}+x_{i^{\prime}}\leq p$. However, we
have shown that $\pi_{i}>0$ for any $i\in[q]\setminus[p]$, and this gives a
contradiction because $p\leq q-2$. Therefore, for any $i\in[q]\setminus[p]$,
we have $\pi_{p}+\pi_{i}=\pi_{1}$. $\hfill\diamond$

Let $\pi_{1}:=\lambda$, then Claim C gives $\pi_{q+1}=\ldots=\pi_{n}=0$, Claim
C gives $\pi_{1}=\ldots=\pi_{p-1}=\lambda$, Claim C gives
$\pi_{p}=1-(p-1)\lambda$, and Claim 3 gives
$\pi_{p+1}=\ldots=\pi_{q}=p\lambda-1$. Also from Claim C, we have
$\pi([n])-\lambda=1$, hence: $\lambda=(q-p)(p\lambda-1)$, which gives
$\lambda=\frac{q-p}{p(q-p)-1}$. Therefore, the original facet-defining
inequality $\pi^{T}x\leq 1$ coincides with
$(q-p)\sum_{i=1}^{p-1}x_{i}+(q-p-1)x_{p}+\sum_{i=p+1}^{q}x_{i}\leq p(q-p)-1$.
Note that for the multi-cover
$\\{\\{1,\ldots,p-1,p+1,\ldots,q\\},\\{1,\ldots,p,q\\}\\}$, the inequality has
the same structure as the one given in Example 3, and the corresponding MCI is
$(q-p)\sum_{i=1}^{p-1}x_{i}+(q-p-1)x_{p}+\sum_{i=p+1}^{q}x_{i}\leq p(q-p)-1$.

The above discussion concludes the proof. ∎

##  Appendix D Separation Formulation in Section 5

Let $\mathscr{C}$ be a cover-family. From the definition of multi-cover,
$\mathscr{C}$ is a multi-cover if and only its skeleton $\mathscr{S}$
satisfies the property: For any $T\subseteq\cup_{S\in\mathscr{S}}S$, there
exists some $S^{\prime}\in\mathscr{S}$ such that $T$ is comparable with
$S^{\prime}$. Henceforth all skeletons are assumed to have such property. Now
for a given skeleton $\mathscr{S}:=\\{S_{1},\ldots,S_{k}\\}$ and a fractional
solution $\tilde{x}$, we consider the following MIP. We let
$S:=\cup_{i=1}^{k}S_{i}$ and $\bar{S}_{h}:=S\setminus S_{h}$ for any
$h\in[k]$.

$\displaystyle\begin{split}\min\quad&t+\sum_{i\in[n]}\gamma_{i}-\sum_{i\in[n]}(\gamma_{i}+\sum_{s\in
S}\alpha^{s}_{i})\tilde{x}_{i}\\\
\text{s.t.}\quad&t\geq\sum_{i\in[n]}\sum_{s\in
S_{h}}\alpha^{s}_{i},\quad\forall h\in[k]\\\ &\sum_{s\in S}u^{s}_{i}+w_{i}\leq
1,\ \alpha^{s}_{i}\leq Mu^{s}_{i},\ \gamma_{i}\leq Mw_{i}\quad\forall
i\in[n]\\\ &\sum_{i\in[n]}u^{s}_{i}=1,\quad\forall s\in S\\\
&\alpha^{s}_{i}\geq\alpha^{s^{\prime}}_{j}+(1+M)u^{s}_{i}-M,\quad\forall
i,j\in[n],j>i,s\in S,s^{\prime}\in\Pi(s)\\\
&w_{i}=\sum_{h\in[k]}w^{h}_{i},\quad i\in[n]\\\
&\gamma_{i}\geq\sum_{j>i}\sum_{s\in\bar{S}_{h}}\alpha^{s}_{j}+(1+n|\bar{S}_{h}|M)w^{h}_{i}-n|\bar{S}_{h}|M,\quad\forall
i\in[n],h\in[k]\\\
&\gamma_{i}\geq\sum_{s\in\bar{S}_{h}}\alpha^{s}_{j}+|\bar{S}_{h}|Mw^{h}_{i}-|\bar{S}_{h}|M,\quad\forall
i,j\in[n],j<i,h\in[k]\\\ &\sum_{i\in[n]}(\sum_{s\in
S_{h}}u^{s}_{i}+w_{i})A_{j,i}\geq(b_{j}+1)\lambda^{h}_{j},\quad\forall
h\in[k],j\in[m]\\\ &u^{s}_{i}+\sum_{j<i}u^{s+1}_{j}\leq 1,\quad\forall
s=1,\ldots,|S|-1\\\ &\sum_{j=1}^{m}\lambda^{h}_{j}\geq 1,\quad\forall
h\in[k]\\\ &u^{s}_{i}\in\\{0,1\\},\alpha^{s}_{i}\in\mathbb{Z},\
w_{i},w^{h}_{i},\lambda^{h}_{j}\in\\{0,1\\},\quad\forall s\in
S,i\in[n],j\in[m],h\in[k].\end{split}$ (Sep-$\mathscr{S}$)

Here $\Pi(s):=\\{s^{\prime}\in S\mid\exists h\in[k],\text{s.t.}\ s\in
S_{h},s^{\prime}\notin S_{h},s^{\prime}>s\\}.$ Then, the separation problem of
MCIs with skeleton $\mathscr{S}$ can be solved exactly using the MIP
(Sep-$\mathscr{S}$).

###### Theorem D.1

Given a TOMKS $K$. For any given skeleton $\mathscr{S}$ and a point
$\tilde{x}$, there exists a multi-cover $\mathscr{C}$ whose skeleton is
$\mathscr{S}$ and an associated MCI that separates $\tilde{x}$ from $K$ if and
only if (Sep-$\mathscr{S}$) admits an optimal value less than 1.

###### Proof

In (Sep-$\mathscr{S}$), binary $u^{s}_{i}$ denotes whether or not the index
$i$ of variables corresponds to the index $s$ in the skeleton;
$\alpha^{s}_{i}$ denotes the MCI coefficient of variable $x_{i}$, when
$u^{s}_{i}$ = 1; Binary $w_{i}$ denotes whether or not variable index $i$
appears in the intersection of the multi-cover; $\gamma_{i}$ denotes the MCI
coefficient of variable $x_{i}$, when $w_{i}$ = 1; For any $h\in[k]$ and
$j\in[m]$, binary $\lambda^{h}_{j}$ denotes whether or not the cover $C_{h}$
corresponding to the skeleton $S_{h}$ violates the $j$-th knapsack constraint
of the problem; $t+\sum_{i\in[n]}\gamma_{i}$ represents the maximum value of
$\alpha(C_{h}),h\in[k]$. Therefore, the associated MCI is represented by the
inequality:

$\sum_{i\in[n]}(\gamma_{i}+\sum_{s\in S}\alpha^{s}_{i})x_{i}\leq
t+\sum_{i\in[n]}\gamma_{i}-1.$

Hence the optimal value of (Sep-$\mathscr{S}$) is strictly less than 1 if and
only if the MCI is a separating inequality.

Now we verify that the meaning of those variables can be formulated by the
constraints in (Sep-$\mathscr{S}$). For each index $s\in S$, since it only
corresponds to one variable index $i\in[n]$, so we have constraint
$\sum_{i\in[n]}u^{s}_{i}=1,\forall s\in S$. Similarly, for each index
$i\in[n]$, since it either appears in the intersection of the covers, or
corresponds to a single index $s\in S$, or is not contained by any cover, so
we have constraint $\sum_{s\in S}u^{s}_{i}+w_{i}\leq 1,\forall i\in[n]$.
Constraint $\alpha^{s}_{i}\geq\alpha^{s^{\prime}}_{j}+(1+M)u^{s}_{i}-M,\forall
j>i,s\in S,s^{\prime}\in\Pi(s)$ formulates the Step 4 of Algorithm 1, and
constraints
$\gamma_{i}\geq\sum_{j>i}\sum_{s\in\bar{S}_{h}}\alpha^{s}_{j}+(1+n|\bar{S}_{h}|M)w^{h}_{i}-n|\bar{S}_{h}|M,\forall
i\in[n],h\in[k],\gamma_{i}\geq\sum_{s\in\bar{S}_{h}}\alpha^{s}_{j}+|\bar{S}_{h}|Mw^{h}_{i}-|\bar{S}_{h}|M,\forall
j<i,h\in[k]$ as well as $w_{i}=\sum_{h\in[k]}w^{h}_{i}$ formulate the Step 6
of Algorithm 1. Constraint $u^{s}_{i}+\sum_{j<i}u^{s+1}_{j}\leq 1,\forall
s=1,\ldots,|S|-1$ formulates the bijective relation between skeleton and the
discrepancy family of multi-cover: if index $i\in[n]$ corresponds to the
skeleton index $s\in S$, then for any skeleton index $s^{\prime}>s$, it only
corresponds to the index $j>i$. The remaining constraints are easy to
interpret. ∎

##  Appendix E Numerical Results Report

The following two tables present the detailed results for the optimality gap
we obtained from solving different linear relaxation problems.

(n, m, seed) |  LP |  MCI |  E-MCI |  L-MCI |  CI |  ECI |  LCI
---|---|---|---|---|---|---|---
(20, 1, 1) |  1.05 |  0.81 |  0.58 |  0.48 |  0.87 |  0.59 |  0.59
(20, 1, 2) |  3.7 |  1.92 |  0.17 |  0 |  2.55 |  0.82 |  0.82
(20, 1, 3) |  0.87 |  0.24 |  0.24 |  0.22 |  0.68 |  0.63 |  0.63
(20, 1, 4) |  1.78 |  0 |  0 |  0 |  1.00 |  0.16 |  0
(20, 1, 5) |  6.15 |  1.06 |  1.06 |  0.14 |  2.79 |  2.07 |  2.07
(20, 1, 6) |  9.90 |  5.69 |  0.22 |  0 |  6.47 |  1.01 |  1.01
(20, 1, 7) |  7.29 |  0 |  0 |  0 |  0 |  0 |  0
(20, 1, 8) |  3.06 |  0.41 |  0.40 |  0.29 |  1.99 |  0.54 |  0.54
(20, 1, 9) |  1.48 |  0.65 |  0 |  0 |  0.87 |  0.49 |  0.49
(20, 1, 10) |  4.03 |  0 |  0 |  0 |  2.81 |  0.15 |  0.15
average |  3.93 |  1.08 |  0.27 |  0.11 |  2.00 |  0.65 |  0.63
(20, 2, 1) |  3.37 |  1.79 |  0.89 |  0.60 |  1.83 |  1.50 |  0.83
(20, 2, 2) |  12.50 |  7.18 |  3.16 |  0 |  8.68 |  4.98 |  0
(20, 2, 3) |  1.45 |  0.27 |  0.05 |  0 |  0.81 |  0.10 |  0.08
(20, 2, 4) |  3.96 |  1.66 |  0.65 |  0.10 |  2.79 |  0.83 |  0.83
(20, 2, 5) |  3.15 |  1.65 |  1.39 |  1.03 |  2.04 |  1.65 |  1.65
(20, 2, 6) |  5.43 |  1.73 |  0 |  0 |  4.34 |  0 |  0
(20, 2, 7) |  9.63 |  3.69 |  0.23 |  0 |  6.36 |  0.67 |  0.67
(20, 2, 8) |  2.49 |  0.50 |  0.46 |  0 |  1.52 |  1.06 |  1.06
(20, 2, 9) |  14.64 |  8.82 |  2.66 |  0 |  10.67 |  2.83 |  2.83
(20, 2, 10) |  3.45 |  1.67 |  0.73 |  0.41 |  3.24 |  3.24 |  3.24
average |  6.01 |  2.90 |  1.02 |  0.21 |  4.23 |  1.69 |  1.12
(20, 3, 1) |  5.53 |  3.27 |  0 |  0 |  3.27 |  0 |  0
(20, 3, 2) |  4.46 |  2.88 |  1.64 |  0 |  3.88 |  3.08 |  3.08
(20, 3, 3) |  25.31 |  19.53 |  0 |  0 |  19.80 |  0 |  0
(20, 3, 4) |  3.77 |  3.03 |  1.74 |  1.64 |  3.60 |  2.00 |  2.00
(20, 3, 5) |  4.97 |  2.32 |  1.46 |  0 |  4.12 |  1.67 |  1.67
(20, 3, 6) |  1.87 |  0 |  0 |  0 |  0.28 |  0.12 |  0.12
(20, 3, 7) |  3.72 |  0.88 |  0 |  0 |  3.15 |  1.46 |  1.46
(20, 3, 8) |  3.31 |  1.66 |  0.41 |  0 |  1.96 |  0.83 |  0.83
(20, 3, 9) |  1.29 |  0.87 |  0.44 |  0 |  1.08 |  0.62 |  0.16
(20, 3, 10) |  6.11 |  4.42 |  1.58 |  1.09 |  5.53 |  1.90 |  1.90
average |  6.03 |  3.89 |  0.73 |  0.27 |  4.67 |  1.17 |  1.12
(n, m, seed) |  LP |  MCI |  E-MCI |  L-MCI |  CI |  ECI |  LCI
---|---|---|---|---|---|---|---
(30, 1, 1) |  7.95 |  5.29 |  0.64 |  0 |  6.05 |  0.76 |  0.76
(30, 1, 2) |  2.48 |  0.91 |  0.20 |  0 |  1.38 |  0.25 |  0.25
(30, 1, 3) |  24.75 |  23.35 |  0.70 |  0 |  24.24 |  0.70 |  0.70
(30, 1, 4) |  2.84 |  1.37 |  1.27 |  0.81 |  1.48 |  1.48 |  1.48
(30, 1, 5) |  1.66 |  0 |  0 |  0 |  0 |  0 |  0
(30, 1, 6) |  9.45 |  6.74 |  1.53 |  0.77 |  7.60 |  1.84 |  1.84
(30, 1, 7) |  1.43 |  1.27 |  1.17 |  0.83 |  1.31 |  1.25 |  1.25
(30, 1, 8) |  3.81 |  2.84 |  0.42 |  0 |  3.17 |  0.47 |  0.22
(30, 1, 9) |  6.20 |  4.66 |  0 |  0 |  5.23 |  0 |  0
(30, 1, 10) |  2.83 |  1.34 |  0 |  0 |  1.91 |  0 |  0
average |  6.34 |  4.78 |  0.59 |  0.24 |  5.24 |  0.68 |  0.65
(30, 2, 1) |  5.73 |  4.42 |  0.67 |  0 |  4.78 |  0.69 |  0.69
(30, 2, 2) |  5.14 |  3.25 |  3.25 |  0.30 |  4.05 |  3.78 |  3.78
(30, 2, 3) |  9.94 |  7.20 |  0 |  0 |  8.11 |  0 |  0
(30, 2, 4) |  3.02 |  0.63 |  0 |  0 |  1.38 |  0 |  0
(30, 2, 5) |  2.98 |  2.46 |  0 |  0 |  2.46 |  0 |  0
(30, 2, 6) |  4.93 |  2.78 |  0 |  0 |  3.42 |  0 |  0
(30, 2, 7) |  3.40 |  2.10 |  1.99 |  0 |  2.80 |  2.80 |  0.74
(30, 2, 8) |  5.86 |  5.06 |  1.35 |  0.20 |  5.45 |  1.35 |  1.35
(30, 2, 9) |  3.04 |  0 |  0 |  0 |  0.86 |  0.58 |  0
(30, 2, 10) |  3.59 |  1.61 |  1.61 |  1.37 |  1.77 |  1.73 |  1.73
average |  4.76 |  2.95 |  0.89 |  0.19 |  3.51 |  1.09 |  0.83
(30, 3, 1) |  3.76 |  2.94 |  1.19 |  0 |  3.14 |  1.32 |  0.71
(30, 3, 2) |  4.13 |  3.26 |  0.37 |  0 |  3.68 |  0.38 |  0.19
(30, 3, 3) |  14.64 |  13.62 |  3.92 |  1.67 |  13.98 |  4.04 |  4.04
(30, 3, 4) |  1.57 |  1.49 |  1.37 |  0.89 |  1.55 |  1.41 |  1.41
(30, 3, 5) |  1.09 |  1.00 |  0.60 |  0.37 |  1.05 |  0.61 |  0.42
(30, 3, 6) |  1.46 |  0 |  0 |  0 |  0 |  0 |  0
(30, 3, 7) |  0.99 |  0.88 |  0.11 |  0 |  0.92 |  0.11 |  0.11
(30, 3, 8) |  1.23 |  0.55 |  0 |  0 |  0.80 |  0 |  0
(30, 3, 9) |  0.99 |  0.77 |  0.41 |  0.19 |  0.83 |  0.51 |  0.51
(30, 3, 10) |  1.46 |  0.53 |  0.37 |  0 |  0.70 |  0.60 |  0.60
average |  3.13 |  2.50 |  0.83 |  0.31 |  2.67 |  0.90 |  0.80