On bounded pitch inequalities for the
min-knapsack polytope
Yuri Faenza∗

Igor Malinović†

Monaldo Mastrolilli‡

Ola Svensson†

arXiv:1801.08850v1 [] 26 Jan 2018

January 29, 2018

Abstract
In the min-knapsack problem one aims at choosing a set of objects with minimum total
cost and total profit above a given threshold. In this paper, we study a class of valid
inequalities for min-knapsack known as bounded pitch inequalities, which generalize the
well-known unweighted cover inequalities. While separating over pitch-1 inequalities is NPhard, we show that approximate separation over the set of pitch-1 and pitch-2 inequalities
can be done in polynomial time. We also investigate integrality gaps of linear relaxations
for min-knapsack when these inequalities are added. Among other results, we show that,
for any fixed t, the t-th CG closure of the natural linear relaxation has the unbounded
integrality gap.
Keywords: bounded pitch, integrality gap, min-knapsack

1

Introduction

The min-knapsack problem (MinKnap)
min cT x s.t. pT x ≥ 1, x ∈ {0, 1}n

(1)

is the variant of the max knapsack problem (MaxKnap) where, given a cost vector c and a
profit vector p, we want to minimize the total cost given a lower bound on the total profit.
MinKnap is known to be NP-Complete, even when p = c. Moreover, it is easy to see that the
classical FPTAS for MaxKnap [9, 13] can be adapted to work for MinKnap, thus completely
settling the complexity of MinKnap.
However, pure knapsack problems rarely appear in applications. Hence, one aims at developing techniques that remain valid when less structured constraints are added on top of
the original knapsack one. This can be achieved by providing strong linear relaxations for the
problem: then, any additional linear constraint can be added to the formulation, providing a
good starting point for any branch-and-bound procedure. The most common way to measure
the strength of a linear relaxation is by measuring its integrality gap, i.e. the maximum ratio
between the optimal solutions of the linear and the integer programs (or of its inverse if the
problem is in minimization form) over all the objective functions.
∗

IEOR, Columbia University, USA. Email: yf2414@columbia.edu
SB/IC, EPFL, Switzerland. Email: firstname.lastname@epfl.ch
‡
IDSIA, USI-SUPSI, Switzerland. Email: monaldo@idsia.ch

†

1

Surprisingly, if we aim at obtaining linear relaxations with few inequalities and bounded
integrality gap, MinKnap and MaxKnap seem to be very different. Indeed, the standard
linear relaxation for MaxKnap has integrality gap 2, and this can be boosted to (1 + ǫ) by an
extended formulation with nŌ(1/ǫ) many variables and constraints, for ǫ > 0 [2]. Conversely,
the standard linear relaxation for MinKnap has unbounded integrality gap, and this remains
true even after Θ(n) rounds of the Lasserre hierarchy [12]. No linear relaxation for MinKnap
with polynomially many constraints and constant integrality gap can be obtained in the original
space [6]. It is an open problem whether an extended relaxation with this properties exists.
Recent results showed the existence [1] and gave an explicit construction [7] of a linear relaxation
for MinKnap of quasi-polynomial size with integrality gap 2 + ǫ. This is obtained by giving
an approximate formulation for Knapsack Cover inequalities (KC) (see [4] and the references
therein). Adding those (exponentially many) inequalities gives an integrality gap of 2, and can
be approximately separated [4]. The bound on the integrality gap is tight, even in the simpler
case when p = c. One can then look for other classes of well-behaved inequalities that can
be added to further reduce the integrality gap. A prominent family is given by the so called
bounded pitch inequalities [3] defined in Section 2. Here, we remark that the pitch is a parameter
measuring the complexity of an inequality, and the associated separation problem is NP-Hard
already for pitch-1. The pitch-1 inequalities are often known in the literature as unweighted
cover inequalities (see e.g. [1]).
In this paper, we study structural properties and separability of bounded pitch inequalities
for MinKnap, and the strength of linear relaxations for MinKnap when they are added. Let
F be the set given by pitch-1, pitch-2, and inequalities from the linear relaxation of (1). We
first show that, for any arbitrarily small precision, we can solve in polynomial time the weak
separation problem for the set F. Even better, our algorithm either certifies that the given point
x∗ violates an inequality from F, or outputs a point that satisfies all inequalities from F and
whose objective function value is arbitrarily close to that of x∗ . We define such an algorithm as
a (1 + ǫ)-oracle in Section 2; see Section 3 for the construction. A major step of our procedure
is showing that non-redundant pitch-2 inequalities have a simple structure.
It is then a natural question whether bounded pitch inequalities can help to reduce the
integrality gap below 2. We show that, when p = c, if we add to the linear relaxation of
(1) pitch-1 and pitch-2 inequalities, the integrality gap is bounded by 3/2; see Section 4.1.
However, this is false in general. Indeed, we also prove that KC plus bounded pitch inequalities
do not improve upon the integrality gap of 2; see Section 4.4. Moreover, bounded pitch alone
can be much weaker than KC: we show that, for each fixed k, the integrality gap may be
unbounded even if all pitch-k inequalities are added. Using the relation between bounded pitch
and Chvátal-Gomory (CG) closures established in [3], this implies that, for each fixed t, the
integrality gap of the t-th CG closure can be unbounded; see Section 4.2. For an alternative
proof that having all KC inequalities bounds the integrality gap to 2 see Section 4.3.

2

Basics

A MinKnap instance is a binary optimization problem of the form (1), where p, c ∈ Qn and
we assume 0 ≤ p1 ≤ p2 ≤ · · · ≤ pn ≤ 1, 0 < ci ≤ 1, ∀i ∈ [n]. We will often deal with its natural
linear relaxation
min cT x s.t. pT x ≥ 1, x ∈ [0, 1]n .
(2)

2

The NP-Hardness of MinKnap immediately follows from the fact that MaxKnap is NP-Hard
[10], and that a MaxKnap instance
max v T x s.t. wT x ≤ 1, x ∈ {0, 1}n .

(3)
{0, 1}n

can be reduced into a MinKnap instance (1) as follows: each x ∈
is mapped via
wi
n
n
P
π : R → R with π(x) = 1 − x; pi = n wi −1 and ci = vi for i ∈ [n]. Note that the reduction
i=1
is not approximation-preserving.
We say that an inequality wT x ≥ β with w ≥ 0 is dominated by a set of inequalities F
if w′T x ≥ β ′ can be written as a conic combination of inequalities in F for some β ′ ≥ β and
w′ ≥ w. wT x ≥ β is undominated if any set of valid inequalities dominating wT x ≥ β contains
a positive multiple of it.
Consider a family F of inequalities valid for (1). We refer to [8] for the definition of weak
separation oracle, which is not used in this paper. We say that F admits a (1 + ǫ)-oracle
if, for each fixed ǫ > 0, there exists an algorithm that takes as input a point x̄ and, in time
polynomial in n, either outputs an inequality from F that is violated by x̄, or outputs a point
ȳ, x̄ ≤ ȳ ≤ (1 + ǫ)x̄ that satisfies all inequalities in F. In particular, if F contains the linear
relaxation
P of (1), 0 ≤ ȳ ≤ 1.
Let i∈T wi xi ≥ β be a valid inequality for (1), with wP
i > 0 for all i ∈ T . Its pitch is the
minimum k such that, for each
I
⊆
T
with
|I|
=
k,
we
have
i∈I wi ≥ β. Undominated pitch-1
P
inequalities are of the form i∈T xi ≥ 1. Note that the map from MaxKnap to MinKnap
instances defined above gives a bijection between minimal cover inequalities
X
xi ≤ |I| − 1
i∈I

for MaxKnap and undominated pitch-1 inequalities for the corresponding MinKnap instance.
Since, given a MaxKnap instance, it is NP-Hard to separate minimal cover inequalities [11],
we conclude the following.
Theorem 1. It is NP-Hard to decide whether a given point satisfies all valid pitch-1 inequalities
for a given MinKnap instance.
P
Given a set S ⊆ [n], such that β := 1− i∈S pi > 0, the Knapsack cover inequality associated
to S is given by
X
min{pi , β}xi ≥ β
(4)
i∈[n]\S

and it is valid for (1).
For a set S ⊆ [n], we denote by χS its characteristic vector. An ǫ-approximate solution for
a minimization integer programming problem is a solution x̄ that is feasible, and whose value
is at most (1 + ǫ) times the value of the optimal solution. An algorithm is called a polynomial
time approximation scheme (PTAS) if for each ǫ > 0 and any instance of the given problem it
returns an ǫ-approximate solution in time polynomial in the size of the input. If in addition the
running time is polynomial in 1/ǫ, then the algorithm is a fully polynomial time approximation
scheme (FPTAS).
Given a rational polyhedron P = {x ∈ Rn : Ax ≥ b} with A ∈ Zm×n and b ∈ Zm , the first
Chvátal-Gomory (CG) closure [5] of P is defined as follows:
P (1) = {x ∈ Rn : ⌈λ⊤ A⌉x ≥ ⌈λ⊤ b⌉, ∀λ ∈ Rm }.

Equivalently, one can consider all λ ∈ [0, 1]m such that λ⊤ A ∈ Zn . For t ∈ Z≥2 , the t-th CG
closure of P is recursively defined as P (t) = (P (t−1) )(1) . The CG closure is an important tool
for solving integer programs, see again [5].
3

A (1 + ǫ)-oracle for pitch-1 and pitch-2 inequalities

3

In this section, we show the following:
Theorem 2. Given a MinKnap instance (1), there exists a (1 + ǫ)-oracle for the set F containing: all pitch-1 inequalities, all pitch-2 inequalities and all inequalities from the natural
linear relaxation of (1).
We start with a characterization of inequalities of interest for Theorem 2.
Lemma 3. Let K be the set of feasible solutions of a MinKnap instance (1). All pitch-2
inequalities valid for K are implied by the set composed of:
i) Non-negativity constraints xi ≥ 0 for i ∈ [n];
ii) All valid pitch-1 inequalities;
iii) All inequalities of the form

X

xi + 2

i∈I2

i∈I1

where I ⊆ [n], |I| ≥ 2, β(I) := 1−

P

i∈[n]\I

X

xi ≥ 2

(5)

pi , I1 := {i ∈ I : pi < β(I)} =
6 ∅ and I2 := I \I1 .

The inequalities in iii) are pitch-2 and valid.
Proofs of Lemma 5 and Theorem 2 are given in Section 3.1 and Section 3.2, respectively.

3.1

Restricting the set of valid pitch-2 inequalities

We will build on two auxiliary statements in order to prove Lemma 3.
Claim 1. If wT x ≥ β and uT x ≥ β are distinct inequalities valid for and u ≥ w, then the latter
inequality is dominated by the former.
Proof. uT x ≥ β can be obtained summing nonnegative multiples of wT x ≥ β and xi ≥ 0 for
i ∈ [n], which are all valid inequalities.
Claim 2. Let

X

i∈T1

xi + 2

X

i∈T2

xi ≥ 2

(6)

be a valid inequality for MinKnap, with T1 ∩ T2 = ∅ and T1 , T2 ⊆ [n]. Then, (6) is dominated
by the inequality in iii) with I = T1 ∪ T2 .
Proof. One readily verifies that Inequality (5) with I as above is valid. Suppose now that
i ∈ T1 \ I1 . Then the integer solution that takes all elements in ([n] \ I) ∪ {i} is feasible for
MinKnap, but it does not satisfy (6), a contradiction. Hence T1 ⊆ I1 . Since T2 = I \ Ti ⊇
I \ I1 = I2 , (5) dominates (6) componentwise, and the thesis follows by Claim 1.

4

Proof of Lemma 3. The fact that an inequality of the form (5) is pitch-2 and valid
is immediate. Because of Claim 2, it is enough to show the thesis with (5) replaced by (6).
Consider a pitch-2 inequality valid for K:
X
wi xi ≥ 1,
(7)
i∈T

|T |

where T ⊆ [n] is the support of the inequality, w ∈ R+ . Without loss of generality one can
assume that T = [h] for some h ≤ n and w1 ≤ w2 ≤ · · · ≤ wh . Since (7) is pitch-2 we
have
P that w1 + wi ≥ 1 for all i ∈ [h] \ {1}. We can also assume wh ≤ 1, since otherwise
i∈[h−1] wi xi + xh ≥ 1 is valid and dominates (7) by Claim 1.
Let j ∈ [h] be the maximum index such that wj < 1. Note that such j exists, since, if
w1 ≥ 1, then (7) is a pitch-1 inequality. If 1 − w1 ≤ 1/2, then, by Claim 1, (7) is dominated by
the valid pitch-2 inequality
h
X
X
xi ≥ 2,
(8)
xi + 2
i=j+1

i∈[j]

which again is of the type (6). Hence 1 − w1 > 1/2 and again via Claim 1, (7) is dominated by
w1 x1 +

j
h
X
X
xi ≥ 1,
(1 − w1 )xi +

(9)

i=j+1

i=2

since wi + w1 ≥ 1 for all i 6= 1, so one has wi ≥ 1 − w1 > 1/2. Thus, we can assume that (7)
has the form (9). Note that inequality
h
X
i=2

xi ≥ 1

(10)

is a valid pitch-1 inequality, since we observed w1 < 1. Therefore, (7) is implied by (8) and (10),
taken with the coefficients w1 and 1 − 2w1 respectively. Recalling that (8) is a valid pitch-2
inequality of the form (6) concludes the proof.


3.2

A (1 + ǫ)-oracle

We will prove Theorem 2 in a sequence of intermediate steps. Our argument extends the weak
separation of KC inequalities in [4].
Let x̄ be the point we want to separate. Note that it suffices to show how to separate over
inequalities i)-ii)-iii) from Lemma 3. Separating over i) is trivial. We first show how to separate
over iii).
Claim 3. For α ∈]0, 1], let z α be the optimal solution to the following IP Pα , and v(z α ) its
value:
X
X
X
min
x̄i zi + 2
x̄i zi s.t.
pi (1 − zi ) ≤ 1 − α, z ∈ {0, 1}n .
(11)
i∈[n]: pi <α

i∈[n]: pi ≥α

i∈[n]

If v(z α ) < 2, then x̄ violates Inequality (5) with I := {i ∈ [n] : ziα = 1}, otherwise x̄ does not
violate any Inequality (5) with β(I) = α.

5

Proof. Fix a feasible solution z̄ to (11), and let I := {i ∈ [n] : z̄i = 1}. Then:
X
X
β := β(I) = 1 −
pi = 1 −
pi (1 − z̄i ) ≥ α.
i∈[n]\I

i∈[n]

Hence:
P

i∈I: pi <β

x̄i + 2

P

i∈I: pi ≥β

P
x̄i =
Pi∈[n]:
≤
i∈[n]:

P
x̄i z̄i + 2 i∈[n]: pi ≥β x̄i
P
pi <α x̄i z̄i + 2
i∈[n]: pi ≥α x̄i z̄i = v(z̄),

pi <β

where the central inequality holds at equality if α = β. Hence, if v(z α ) < 2, the inequality with
I := {i ∈ [n] : ziα = 1} from (11) is violated by x̄. Else, all inequalities from (11) with β(I) = α
are satisfied.
Note that Pα is a MinKnap instance, hence we can use the appropriate FPTAS to find, for
each ǫ > 0, an ǫ-approximate solution for it.
Since all data are rationals, we can assume there exists q ∈ N such that, for each i ∈ [n],
pi = ri /q for some ri ∈ N.
Claim 4. Let r ∈ {ri + 1 : i ∈ [n]} and, for α = r/q, let z̄ α be the solution output by the
FPTAS for problem Pα and v̄ α its objective function value. If v̄ α < 2 for some α, then x̄
violates Inequality (5) with I = {i ∈ [n] : z̄ α = 1}. Else, (1 + ǫ)x̄ satisfies all inequalities in
Lemma 3.iii).
Proof. Let r = ri + 1 for some i ∈ [n]. If v̄ α < 2 then by Claim 3 x̄ violates the corresponding
inequality (5). Otherwise, v α ≥ 2/(1 + ǫ), and (1 + ǫ)x̄ is feasible for any pitch-2 Inequality (5)
induced by I with β(I) = α.
∗
Now let I ∗ ⊆ [n] with β(I ∗ ) = rq < 1. There exists i∗ ∈ [n] such that ri∗ < r ∗ ≤ ri∗ +1 ≤ q
(with rn+1 = q). Let α := ri∗q+1 ≤ α∗ := β(I ∗ ). The set of feasible solutions of Pα contains
∗
that of Pα∗ , and {i ∈ [n] : pi < α} = {i ∈ [n] : pi < α∗ }. Hence, v α ≥ v α and consequently
∗
v α < 2 implies v α < 2. Thus, for separating all inequalities in Lemma 3.iii), it suffices to check
(11) for all α = qr as in the statement of the claim.

The following claim follows in a similar fashion to the previous one by observing that, for
β(I ∗ ) = 1q , (11) separates over undominated pitch-1 inequalities.
Claim 5. Let α = 1/q, and z̄ α be the solution output by the FPTAS for problem Pα , and
v̄ α its objective function value. If v̄ α < 2, then x̄ violates the pitch-1 inequality with support
I = {i ∈ [n] : z̄ α = 1}. Else, (1 + ǫ)x̄ satisfies all valid pitch-1 inequalities.
Next claim shows how to round a point in the unit cube that almost satisfies all pitch-1 and
pitch-2 inequalities, to one that satisfies them and is still contained in the unit cube.
Claim 6. Let x̄ ∈ [0, 1]n be such that (1 + ǫ)x̄ satisfies all inequalities from Lemma 3, and
n
define ȳ ∈ Rn as follows: ȳi = min{1, 1+ǫ
1−ǫ x̄i } for i ∈ [n]. Then ȳ ∈ [0, 1] and ȳ satisfies all
inequalities from Lemma 3.

6

Proof. Clearly ȳ ∈ [0, 1]n . Let J = {i ∈ [n] : ȳi = 1}. If J = ∅, (1 + ǫ)x̄ < ȳ ≤ 1, hence ȳ
satisfies all pitch-2 inequalities. Thus, J 6= ∅. Consider a pitch-2 inequality of the form
P (5),
and note that the left-hand side of the inequality computed in ȳ is lower bounded
by
i∈J αi ,
P
where αi is the coefficient of P
xi . First assume there exists j ∈ J ∩ I2 . Then i∈J αi ≥ αj = 2.
Similarly, if j, j ′ ∈ J, then
i∈J αi ≥ αj + αj ′ ≥ 2. In both cases, ȳ satisfies the pitch-2
inequality. Hence, we can assume J = {j} ⊆ I1 . Then:
X
i∈I

X

i∈I\{j}

X
i∈I

αi x̄i ≥

αi x̄i ≥

αi ȳi =

X

2
, from which we deduce
1+ǫ

2
2
1−ǫ
− x̄j ≥
−1=
and
1+ǫ
1+ǫ
1+ǫ
αi ȳi + 1 =

1+ǫ X
αi x̄i + 1 ≥ 2,
1−ǫ
i∈I\{j}

i∈I\{j}

as
P required. A similar (simpler) argument shows that ȳ also satisfies all pitch-1 inequalities
i∈I xi ≥ 1.
Proof of Theorem 2. We can now sum up our (1+ǫ)-oracle, see Algorithm 1. Correctness
and polynomiality follow from the discussion above.

Algorithm 1
ǫ
.
1: Let ǫ′ = 2+ǫ
2: For r ∈ {ri + 1 : i ∈ [n]} and for α = r/q, run the FPTAS for Pα with approximation
factor ǫ′ . If any of the output solution z̄ α has value v̄ α < 2, output inequality (5) with
I = {i ∈ [n] : z̄ α = 1} and stop.
3: For α = 1/q, run the FPTAS for Pα with approximation factor ǫ′ . If the output solution
P
z̄ α has value v̄ α < 2, output inequality i:z̄ α =1 xi ≥ 1 and stop.
′
4: Output point ȳ constructed as in Claim 6 with ǫ′ and stop. Note that x̄ ≤ ȳ ≤ 1+ǫ
1−ǫ′ x̄ =
(1 + ǫ)x̄.

3.3

Separating inequalities of pitch k ≥ 3 with fixed support

Here, we give an example showing that inequalities of pitch-3 and higher do not have the nice
structure of pitch-2. Let
P = {x ∈ [0, 1]7 : 5x1 + 6x2 + 11x3 + 16x4 + 17x5 + 18x6 + 21x7 ≥ 41}.

(12)

Inequality x1 +x3 +x4 +2x5 +x6 +2x7 ≥ 3 is a facet of the first CG closure P (1) (although not of
the integer hull of P ) and thus a valid pitch-3. Observe that the coefficient of x5 is higher than
x6 in this pitch-3, while it is the opposite in (12). Such situations we call inversions and they do
not occur in (relevant) pitch-2 inequalities. Inequality x1 + x2 + 2x3 + 3x4 + 4x5 + 3x6 + 4x7 ≥ 8
is an inverted facet of both the integer hull and the first CG closure.
For later use (in Section 4.4), we observe here that when I ⊆ [n] is fixed, we can efficiently
and exactly solve the separation problem over inequalities with support I just by solving an LP.
Clearly, we are only interested in valid inequalities αT x ≥ 1 with α ≥ 0 and points 0 ≤ x∗ ≤ 1.
7

Let β = 1 − p([n] \ I). We can assumePβ > 0, otherwise there is no valid inequality as above
with support I. Call J ⊆ I massive if i∈J pi ≥ β. Consider the following LP:
min
s.t.

P

i∈I

P

αi x∗i

i∈J

αi ≥ 1
α ≥ 0

for all massive J ⊆ I

(13)

Note that, for each feasible solution ᾱ to the previous LP, we have that ᾱT x ≥ 1 is a valid
inequality for the original MinKnap instance, and conversely that all inequalities with support
I can be obtained in this way. Hence, let α∗ be the optimal solution to the previous LP. If
(α∗ )T x∗ < 1, we obtain an inequality whose support is contained in I, that is violated by x∗ .
The support of the inequality can be extended to I by setting αi = ǫ for all i ∈ I with αi = 0.
On the other hand, if (α∗ )T x∗ ≥ 1, x∗ satisfies all inequalities with support I.

4
4.1

Integrality gap for MinKnap with bounded pitch inequalities
When p = c

Theorem 4. Consider an instance of MinKnap (1) with p = c. Denote by K the linear
relaxation of (1) to which all pitch-1 and pitch-2 inequalities have been added. The integrality
gap of K is at most 3/2.
Proof. Let p = c, and let x̄ be the optimal integer solution to (1). We can assume pT x̄ > 1.5,
else we are done.
Claim 7. The support of x̄ has size 2.
Proof. Let k be the size of the support of x̄. If k = 1, then x̄ is also the optimal fractional
solution. Now assume k ≥ 3. Remove from x̄ the cheapest item as to obtain x̄′ . We have


1
2
p T x′ ≥ 1 −
pT x̄ > · 1.5 = 1,
k
3
contradicting the fact that x̄ is the optimal integral solution.

Hence, we can assume that the support of x̄ is given by {i, j}, with 0 < pi ≤ pj ≤ 1. Since
pi + pj > 1.5, we deduce pj > .75. Since pj ≤ 1, we deduce pi > .5.
Claim 8. Let ℓ < j and ℓ 6= i. Then pℓ < .25.
Proof. Recall that for S ⊆ [n] we denote its characteristic vector with χS . If 0.25 ≤ pℓ < pi ,
then χ{ℓ,j} is a feasible integral solution of cost strictly less than x̄. Else if 0.5 < pi ≤ pℓ < pj ,
then χ{ℓ,i} is a feasible integral solution of cost strictly less than x̄. In both cases we obtain a
contradiction.
Because of the previous claim, we can assume w.l.o.g. j = i + 1.
P
Claim 9. pn + i−1
ℓ=1 pℓ < 1.
8

P
Proof. Suppose pn + i−1
ℓ=1 pℓ ≥ 1. Since pℓ < .25 for all ℓ = 1, . . . , i − 1, there exists k ≤ i − 1
Pk
such that xn + ℓ=1 pk ∈ [1, 1.25[. Hence x{1,...,k,n} is a feasible integer solution of cost at most
1.25, a contradiction.
P
Because of the previous claim, the pitch-2 inequality nk=i xk ≥ 2 is valid. The fractional
solution of minimum cost that satisfies this inequality is the one that sets xi = xj = 1 (since
j = i + 1) and all other variables to 0. This is exactly x̄.


4.2

CG closures of bounded rank of the natural MinKnap relaxation

For t ∈ N, let K t be the linear relaxation of the (1) given by: the original knapsack inequality;
non-negativity constraints; all pitch-k inequalities, for k ≤ t.
Lemma 5. For t ≥ 2, the integrality gap of K t is at least max{ 12 , t−2
t−1 } times the integrality
gap of K t−1 .
Proof. Fix t ≥ 2, and let C be the cost of the optimal integral solution to (1). Let C/v ′ be
the integrality gap of K t . Since v ′ is the optimal value of K t , by the strong duality theorem (and
Caratheodory’s theorem), there exist nonnegative multipliers α, α1 , . . . , αn , γ1 , . . . , γn+1 such
that the inequality cT x ≥ v ′ can be obtained as a conic combination of the original knapsack
inequality (with multiplier α), non-negativity constraints (with multipliers α1 , . . . , αn ), and at
most n + 1 inequalities of pitch at most t (with multipliers γ1 , . . .P
, γn+1 ). By scaling, we can
assume that the rhs of the latter inequalities is 1. Hence v ′ = α + ri=1 γi .

Claim 10. Let dT x ≥ 1 be a valid
for (1), and assume w.l.o.g. that d1 ≤
Pn pitch-t inequality
1 t−2
d2 ≤ · · · ≤ dn . Then inequality i=2 di xi ≥ max{ 2 , t−1 } is a valid inequality of pitch at most
t − 1 for (1).
P
Proof. The inequality ni=2 di xi ≥ 1 − d1 isP
a valid inequality for (1), and by construction it is
of pitch at most t − 1. If t ≥ 3, we obtain t−1
i=1 di < 1 and consequently d1 < 1/(t − 1), from
which we deduce
t−2
1
1
=
≥ .
1 − d1 > 1 −
t−1
t−1
2
If conversely t = 2, by Lemma 3 we can assume w.l.o.g. that d1 = 1/2, and we can conclude
1 − d1 = 12 > t−2
t−1 .
Now consider the conic combination with multipliers α, α1 , . . . , αn , γ1 , . . . , γn+1 given above,
where each inequality of pitch-t is replaced with the inequality of pitch at most t − 1 obtained
using Claim 10. We obtain an inequality (c′ )T x ≥ v ′′ , where one immediately checks that c′ ≤ c
and
n
o
n
o
P
Pn+1 
1 t−2
1 t−2
v ′′ ≥ α + n+1
γ
max
,
,
≥
max
α
+
i
i=1 γi
2 t−1
2 t−1
n i=1 o
′
= max 21 , t−2
t−1 v .
Hence the integrality gap of K t is

C
C
≥ ′′ max
′
v
v



1 t−2
,
2 t−1



and the thesis follows since the integrality gap of K t−1 is at most C/v ′′ .

9

Lemma 6. For a fixed ǫ > 0 and square integers n ≥ 4, consider the MinKnap instance K
defined as follows:
Pn
√
min
ǫy +
nz +
i=1 xi
st
Pn
√
n
(n − n)y +
i=1 xi ≥ n
2z +
y,

z,

√
For every fixed t ∈ N, the integrality gap of K t is Ω( n).

x ∈ {0, 1}.

√
Proof. Because of Lemma 5, it is enough to show that the integrality gap of K 1 is Ω( n).
√
Clearly, the value of the integral optimal solution of the instance is n + ǫ. We claim that the
fractional solution




1
2 
1


√
√
(ȳ, x̄, z̄) = 1,
,√ 
,...,
 n− n+1
n− n+1
n
|
{z
}
n times
P
√
is a feasible point of K 1 . Since ǫȳ + nz̄ + ni=1 x̄i = ǫ + 2 + n−√nn+1 , the thesis follows.
P
√
√
Observe that (n − n)ȳ + n2 z̄ + ni=1 x̄i = (n − n) + n2 √2n + n−√nn+1 > n, hence (ȳ, x̄, z̄)
satisfies the original knapsack inequality.
Now consider a valid pitch-1 inequality whose support contains y. Since ȳ = 1, (ȳ, x̄, z̄)
satisfies this inequality. Hence, the only pitch-1 inequalities of interest do not have y in the
support. Note that such inequalities must have z in the support, and some of the xi . Hence,
all those inequalities are dominated by the valid pitch-1 inequalities
X
√
xi ≥ 1 ∀I ⊆ [n], |I| = n − n + 1,
z+
i∈I

which are clearly satisfied by (ȳ, x̄, z̄).

CGq (K)

Theorem 7. For a fixed q ∈ N, let
be the q−th CG closure of the MinKnap instance
√
K as defined in Lemma 6. The integrality gap of CGq (K) is Ω( n).
Proof. We will use the following fact, proved (for a generic covering problem) in [3].
Let t, q ∈ N and suppose (ȳ, z̄, x̄) ∈ K t . Define point (y ′ , x′ , z ′ ), where each component is
q
the minimum between 1 and ( t+1
t ) times the corresponding component of (ȳ, z̄, x̄). Then
′
′
′
q
(y , x , z ) ∈ CG (K). Now fix t, q. We have therefore that
q
P
P
√
√
ǫy ′ + nz ′ + ni=1 x′i ≤ t+1
(ǫȳ
+ nz̄ + ni=1
t
 x̄i )


n
t+1 q
ǫ + 2 + n−√n+1
=
t

and the claim follows in a similar fashion to the proof of Lemma 6.

4.3



When all knapsack cover inequalities are added

In this section we consider the min-knapsack formulation with knapsack cover inequalities (we
use KC to denote this LP formulation). In [4] it is shown that the integrality gap of KC is 2.
In the following we provide a simpler proof.
Let x̄ be a feasible fractional solution for KC of cost C(x̄). Starting from x̄, we show a
simple and fast rounding procedure to obtain a feasible integral solution of cost at most 2C(x̄).
10

The rounding procedure: Let S = {i ∈ [n] : x̄i ≥ 1/2}. Set xi = 1 for any i ∈ S. Consider
the residual variables S̄ := [n] \ S. The problem is to assign integral values to the the residual
variables. We call this problem the residual problem (RP). By abusing notation, from now
on, let x̄ denote the fractional solution for KC restricted to residual variables. Consider the
following residual relaxation (RR):
X
min
Ci xi
(14)
i∈S̄

X

p′i xi ≥ b′

(15)

0 ≤ xi ≤ 1/2

(16)

s.t.

i∈S̄

where p′i = min{pi , b − p(S)} and b′ = b − p(S). Note that x̄ satisfies (RR). So if x∗ is the
optimal solution of (RR) than it follows that
X
X
Ci x∗i ≤
Ci x̄i
i∈S̄

i∈S̄

Therefore, if it exists an integral solution xint to (RP) of cost C(xint ) ≤ 2C(x∗ ) then C(xint ) ≤
2C(x̄) and we are done. We can rewrite the residual relaxation (RR) in the following equivalent
way:
min

X Ci

s.t.

X p′

i∈S̄

2

i

i∈S̄

2

yi

(17)

y i ≥ b′

(18)

0 ≤ yi ≤ 1

(19)

Clearly the optimal fractional solution to (RR) can be obtained by ordering the variables
C
according to their densities. W.l.o.g., assume that Cp′1 ≤ Cp′2 ≤ . . . ≤ p′|S̄| and let t + 1 ∈ [|S̄|] be
1
2
|S̄|
P
p′i
′ and therefore (recall p′ ≤ b′ ):
the smallest integer such that t+1
≥
b
i
i=1 2
t
X
i=1

p′i ≥ 2b′ − p′t+1 ≥ b′

(20)

Note that the optimal fractional solution to (RR) picks the first t variables integrally and the
last t + 1 potentially fractional (but it could be integral). It follows that:
t
X
Ci
i=1

2

≤

X

Ci x∗i

(21)

i∈S̄

It follows that the integral solution xint obtained by setting x1 = 1 for i ∈ [t] and zero
otherwise is feasible by (20) and of cost at most twice the optimal fractional of (RR) by (21).

11

4.4

When all bounded pitch and knapsack cover inequalities are added

Consider the following MinKnap instance with ǫn =

min
s.t.

√1 :
n

X

i∈[n]

1 X
zj
xi + √
n

X

1 X
zj ≥ 1 + ǫn
xi +
n

i∈[n]

j∈[n]

(22)

j∈[n]

x, z ∈ {0, 1}n .
Lemma 8. For any fixed k ∈ N and n ∈ N sufficiently large, point (x̄, z̄) ∈ R2n with x̄i =
1+ǫn
k
n , z̄i = n satisfies the natural linear relaxation, all KC and all inequalities of pitch at most
k valid for (22). Observing that the optimal integral solution is 2, this gives an IG of 1+2 k ≈ 2.
n

Proof. We prove the statement by induction. Fix k ∈ N. Note that (x̄, z̄) dominates
componentwise the point generated at step k−1, and the latter by induction hypothesis satisfies
all inequalities of pitch at most k − 1. Let
X
X
wi xi +
wj zj ≥ β
(23)
i∈I

j∈J

be a valid KC or pitch-k inequality with support I ∪ J, which gives that wi , wj ∈ R>0 , ∀i ∈
I, ∀j ∈ J and β > 0. Observe the following.
Claim 11. |I| ≥ n − 1. In addition, |I| = n − 1 or |J| ≤ n(1 − ǫn ) implies wi ≥ β, ∀i ∈ I.
Proof. Since all coefficients in (23) are strictly positive and β > 0, |I| ≤ n − 2 gives that the
feasible solution (χ[n]\I , ~0) for (22) is cut off by (23), a contradiction.
∗
Furthermore, if |I| = n − 1 and wi∗ < β for some i∗ ∈ I, then (χ([n]\I)∪{i } , ~0) is cut off,
again a contradiction. Finally, if |I| = n, |J| ≤ n(1 − ǫn ) and wi∗ < β for some i∗ ∈ I, then
∗
(χ{i } , χ{[n]\J} ) does not satisfy (23), but it is feasible in (22).
We first show the statement for (23) being a KC. By the definition of KC: β = 1 + ǫn −
|[n]\J|
1
|[n]
P \ I| − n , wi = min{1, β}, ∀i ∈ I and wj = min{ n , β}, ∀j ∈ J. If I = [n], then
i∈I wi x̄i = min{1, β} · (1 + ǫn ) ≥ β since β ≤ 1 + ǫn . Otherwise, |[n] \ I| = 1 so wi = β, ∀i ∈ I
P
n)
and i∈I wi x̄i = β (n−1)(1+ǫ
> β for sufficiently large n.
n
Conversely, let (23) be a valid pitch-k inequality. By Claim 11, if |I| = n−1 or |J| ≤ n(1−ǫn )
then wi ≥ β, ∀i ∈ I so the proof is analogous to the one for KC. Otherwise, |I| = n and
|J| > n(1 − ǫn ). Consider the LP (13) in Section 3 specialized for our case – that is, we want to
detect if (x̄, z̄) can be separated via an inequality with support I ∪ J. Since (χi,ı̄ , 0) is feasible
in (22) for i, ı̄ ∈ I, then
αi + αı̄ ≥ 1.
(24)
Furthermore, for n large enough one has |J| > n(1 − ǫn ) ≥ k so
X
αj ≥ 1
j∈K

12

(25)

for any k-subset K of J. We claim that the minimum in (13) is attained at ᾱi = 1/2, ∀i ∈ I
and ᾱj = 1/k, ∀j ∈ J. Indeed, the objective function of (13) computed in ᾱ is given by
|I| ·

1 1+ǫ
1 k
1 + ǫn |J|
·
+ |J| · · =
+
.
2
n
k n
2
n

1+ǫn
and (25) for
On the other hand, by summing (24) for all possible pairs with multipliers 2(n−1)

−1
· nk , simple linear algebra calculations lead to
all subsets of J of size k with multipliers |J|−1
k−1

X

x̄i αi +

i∈I

X
j∈J

z̄j αj ≥

1 + ǫn |J|
+
,
2
n

showing the optimality of ᾱ. Recalling |J| > n(1 − ǫn ), we conclude that
X
i∈I

x̄i ᾱi +

X
j∈J

z̄j ᾱj =

1 + ǫn |J|
1 + ǫn
+
>
+ 1 − ǫn > 1,
2
n
2

hence (x̄, z̄) satisfies all inequalities with support I ∪ J.



Acknowledgments. Some of the work was done when the second and the third author
visited the IEOR department of Columbia University, partially funded by a gift of the Swiss
National Science Foundation.

References
[1] Abbas Bazzi, Samuel Fiorini, Sangxia Huang, and Ola Svensson. Small extended formulation for knapsack cover inequalities from monotone circuits. In Proceedings of the
Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA ’17, pages
2326–2341, Philadelphia, PA, USA, 2017. Society for Industrial and Applied Mathematics.
[2] Daniel Bienstock. Approximate formulations for 0-1 knapsack sets. Oper. Res. Lett.,
36(3):317–320, May 2008.
[3] Daniel Bienstock and Mark Zuckerberg. Approximate fixed-rank closures of covering problems. Mathematical Programming, 105(1):9–27, Jan 2006.
[4] Robert D. Carr, Lisa K. Fleischer, Vitus J. Leung, and Cynthia A. Phillips. Strengthening
integrality gaps for capacitated network design and covering problems. In Proc. of SODA
’00, pages 106–115, 2000.
[5] Michele Conforti, Gerard Cornuejols, and Giacomo Zambelli.
Springer Publishing Company, Incorporated, 2014.

Integer Programming.

[6] Szymon Dudycz and Carsten Moldenhauer. Approximated extended formulations for the
knapsack cover problem. Technical report, EPFL, 2015.
[7] Samuel Fiorini, Tony Huynh, and Stefan Weltge. Strengthening convex relaxations of
0/1-sets using boolean formulas. arXiv preprint arXiv:1711.01358, 2017.
[8] Martin Grötschel, László Lovász, and Alexander Schrijver. Geometric Algorithms and
Combinatorial Optimization. Springer-Verlag, New York, 1988.
13

[9] Oscar H. Ibarra and Chul E. Kim. Fast approximation algorithms for the knapsack and
sum of subset problems. J. ACM, 22(4):463–468, October 1975.
[10] Richard M. Karp. Reducibility among combinatorial problems. In Complexity of Computer
Computations, pages 85–103. Springer US, 1972.
[11] Diego Klabjan, George L. Nemhauser, and Craig A. Tovey. The complexity of cover
inequality separation. Oper. Res. Lett., 23(1-2):35–40, August 1998.
[12] Adam Kurpisz, Samuli Leppänen, and Monaldo Mastrolilli. On the hardest problem formulations for the 0/1 lasserre hierarchy. Math. Oper. Res., 42(1):135–143, 2017.
[13] Eugene L. Lawler. Fast approximation algorithms for knapsack problems. Math. Oper.
Res., 4(4):339–356, November 1979.

14

