On bounded pitch inequalities for the min-knapsack polytope
Yuri Faenza Igor Malinović Monaldo Mastrolilli Ola Svensson
cs.DS

Gate-controlled quantum dots and superconductivity in planar germanium
    M. Veldhorst
    December 30, 2023
======================================================================


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 NP-hard, 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   




§ INTRODUCTION



The min-knapsack problem ()

    min c^T x    s.t.    p^T x ≥ 1,   x ∈{0,1}^n

is the variant of the max knapsack problem () 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.  is known to be NP-Complete, even when p=c. Moreover, it is easy to see that the classical FPTAS for  <cit.> can be adapted to work for , thus completely settling the complexity of .

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.

Surprisingly, if we aim at obtaining linear relaxations with few inequalities and bounded integrality gap,  and  seem to be very different. Indeed, the standard linear relaxation for  has integrality gap 2, and this can be boosted to (1+ϵ) by an extended formulation with n^O̅(1/ ϵ) many variables and constraints, for ϵ>0 <cit.>. Conversely, the standard linear relaxation for   has unbounded integrality gap, and this remains true even after Θ(n) rounds of the Lasserre hierarchy <cit.>. No linear relaxation for   with polynomially many constraints and constant integrality gap can be obtained in the original space <cit.>. It is an open problem whether an extended relaxation with this properties exists. Recent results showed the existence <cit.> and gave an explicit construction <cit.> of a linear relaxation for   of quasi-polynomial size with integrality gap 2+ϵ. This is obtained by giving an approximate formulation for Knapsack Cover inequalities (KC) (see <cit.> and the references therein). Adding those (exponentially many) inequalities gives an integrality gap of 2, and can be approximately separated <cit.>. 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 <cit.> defined in Section <ref>. 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. <cit.>).

 

In this paper, we study structural properties and separability of bounded pitch inequalities for , and the strength of linear relaxations for  when they are added. Let F be the set given by pitch-1, pitch-2, and inequalities from the linear relaxation of (<ref>).  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 <ref>; see Section <ref> 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 (<ref>) pitch-1 and pitch-2 inequalities, the integrality gap is bounded by 3/2; see Section <ref>. 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 <ref>. 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 Chvátal-Gomory (CG) closures established in <cit.>, this implies that, for each fixed t, the integrality gap of the t-th CG closure can be unbounded; see Section <ref>. For an alternative proof that having all KC inequalities bounds the integrality gap to 2 see Section <ref>. 




§ BASICS


A  instance is a binary optimization problem of the form (<ref>),
where p, c ∈^n and we assume 0≤ p_1 ≤ p_2 ≤…≤ p_n ≤ 1, 0 < c_i ≤ 1,  ∀ i ∈ [n]. We will often deal with its natural linear relaxation

    min c^T x    s.t.    p^T x ≥ 1,   x ∈ [0,1]^n.

The NP-Hardness of  immediately follows from the fact that  is NP-Hard <cit.>, and that a  instance

    max v^T x    s.t.    w^T x ≤ 1,   x ∈{0,1}^n.

can be reduced into a  instance (<ref>) as follows: each x ∈{0,1}^n is mapped via π: ^n →^n with π(x) = 1-x; p_i = w_i/∑_i=1^n w_i - 1 and c_i=v_i for i ∈ [n]. Note that the reduction is not approximation-preserving.

We say that an inequality w^T 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. w^T x ≥β is undominated if any set of valid inequalities dominating w^T x ≥β contains a positive multiple of it.

Consider a family F of inequalities valid for (<ref>). We refer to <cit.> 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 of (<ref>), 0≤y̅≤ 1. 

Let ∑_i ∈ T w_i x_i ≥β be a valid inequality for (<ref>), with w_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 w_i ≥β. Undominated pitch-1 inequalities are of the form ∑_i ∈ T x_i ≥ 1. Note that the map from  to  instances defined above gives a bijection between minimal cover inequalities

    ∑_i ∈ I x_i ≤ |I|-1

for  and undominated pitch-1 inequalities for the corresponding  instance. Since, given a  instance, it is NP-Hard to separate minimal cover inequalities <cit.>, we conclude the following.


It is NP-Hard to decide whether a given point satisfies all valid pitch-1 inequalities for a given  instance.


Given a set S⊆ [n], such that β:= 1-∑_i ∈ Sp_i > 0, the Knapsack cover inequality associated to S is given by

    ∑_i ∈ [n]∖ Smin{p_i,β} x_i ≥β

and it is valid for (<ref>).

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 ∈^n: Ax ≥ b } with A∈^m × n and b∈^m, the first Chvátal-Gomory (CG) closure <cit.> of P is defined as follows:


    P^(1)={x ∈^n:  ⌈λ^⊤ A ⌉ x ≥⌈λ^⊤ b⌉,  ∀λ∈^m }.


Equivalently, one can consider all λ∈ [0,1]^m such that λ^⊤ A∈^n. For t ∈_≥ 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 <cit.>.









§ SUMMARY



	
  *  Consider an  instance. Let x^* ∈ [0,1]^n. For each fixed ϵ>0 and x^*, there exists a polynomial-time algorithm that: either certifies that x^* satisfies all pitch-1 and pitch-2 inequalities up to ϵ-tolerance; or it finds a pitch-1 or pitch-2 inequality violated by x^*.
	
  *  When c=p, the integrality gap of the linear relaxation obtained by adding pitch-1 and pitch-2 is at most 3/2.
	
  *  For any fixed k there exists an instance such that, even when all pitch-k inequalities are added, the IG (integrality gap) is Θ(√(n)). Using known facts on the relation between the CG closure and pitch inequality, this implies that the IG of any fixed CG closure for   can be of order √(n) after any fixed number of rounds.
	
  *  If (x̅=0, y̅=1) is an optimal solution to the problem 
    min∑_i=1^3 c_i x_i + y ≥ 1    s.t.   ∑_i=1^3 p_i x_i + y ≥ 1,   x_i,y ∈{0,1},
 then the integrality gap obtained by adding all pitch-1 and pitch-2 inequality is 1.
	
  *  If we fix the support S, a pitch k and a point x^*, we can find the pitch-k inequality with support S that is most violated by x^* solving an LP.
	
  *  Ola's instance shows that adding all valid inequalities of pitch at most k to the relaxation of  with KC does not improve the IG of 2 in general.
	
	







§ A (1+Ε)-ORACLE FOR PITCH-1 AND PITCH-2 INEQUALITIES



In this section, we show the following:


	Given a  instance (<ref>), 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 (<ref>).
	

We start with a characterization of inequalities of interest for Theorem <ref>.


	Let K be the set of feasible solutions of a  instance (<ref>). All pitch-2 inequalities valid for K are implied by the set composed of:
	
		
  * Non-negativity constraints x_i ≥ 0 for i ∈ [n];
		
  * All valid pitch-1 inequalities;
		
  * 
		All inequalities of the form
		
    ∑_i ∈ I_1 x_i + 2 ∑_i ∈ I_2 x_i ≥ 2

		where I⊆ [n], |I| ≥ 2, β(I):=1-∑_i ∈ [n]∖ I p_i, I_1 :={ i ∈ I: p_i < β(I)}≠∅ and I_2 := I∖ I_1.
	
	The inequalities in <ref>) are pitch-2 and valid.


Proofs of Lemma <ref> and Theorem <ref> are given in Section <ref> and Section <ref>, respectively.























 §.§ Restricting the set of valid pitch-2 inequalities



We will build on two auxiliary statements in order to prove Lemma <ref>.


	If w^T x ≥β and u^T x ≥β are distinct inequalities valid for and u ≥ w, then the latter inequality is dominated by the former.



	u^T x ≥β can be obtained summing nonnegative multiples of w^T x ≥β and x_i ≥ 0 for i ∈ [n], which are all valid inequalities.
	
	
	



	
	Let 
    ∑_i ∈ T_1 x_i + 2 ∑_i ∈ T_2 x_i ≥ 2
 be a valid inequality for , with T_1 ∩ T_2 = ∅ and T_1, T_2 ⊆ [n]. Then, (<ref>) is dominated by the inequality in <ref>) with I=T_1 ∪ T_2.



	One readily verifies that Inequality (<ref>) with I as above is valid. Suppose now that i ∈ T_1 ∖ I_1. Then the integer solution that takes all elements in ([n]∖ I)∪{i} is feasible for , but it does not satisfy (<ref>), a contradiction. Hence T_1⊆ I_1. Since T_2=I∖ T_i ⊇ I ∖ I_1=I_2, (<ref>) dominates (<ref>) componentwise, and the thesis follows by Claim <ref>.
	


Proof of Lemma <ref>. The fact that an inequality of the form (<ref>) is pitch-2 and valid is immediate. Because of Claim <ref>, it is enough to show the thesis with (<ref>) replaced by (<ref>). Consider a pitch-2 inequality valid for K:


    ∑_i ∈ T w_i x_i ≥ 1,


where T ⊆ [n] is the support of the inequality, w ∈^|T|_+. Without loss of generality one can assume that T=[h] for some h ≤ n and w_1 ≤ w_2 ≤…≤ w_h. Since (<ref>) is pitch-2 we have that w_1 + w_i ≥ 1 for all i ∈ [h] ∖{ 1 }. We can also assume w_h ≤ 1, since otherwise ∑_i ∈ [h-1] w_i x_i + x_h ≥ 1 is valid and dominates (<ref>) by Claim <ref>.

Let j ∈ [h] be the maximum index such that w_j < 1. Note that such j exists, since, if w_1 ≥ 1, then (<ref>) is a pitch-1 inequality. If 1 - w_1 ≤ 1/2, then, by Claim <ref>, (<ref>) is dominated by the valid pitch-2 inequality

    ∑_i ∈ [j] x_i + 2 ∑_i=j+1^h x_i ≥ 2,

which again is of the type (<ref>). Hence 1- w_1 >  1/2 and again via Claim <ref>, (<ref>) is dominated by

    w_1 x_1 + ∑_i = 2^j (1- w_1) x_i + ∑_i=j+1^h x_i ≥ 1,
 since w_i + w_1 ≥ 1 for all i ≠ 1, so one has w_i ≥ 1-w_1 > 1/2.  Thus, we can assume that (<ref>) has the form (<ref>). Note that inequality 
    ∑_i=2^h x_i ≥ 1

is a valid pitch-1 inequality, since we observed w_1< 1. Therefore, (<ref>) is implied by
(<ref>) and (<ref>),  taken with the coefficients w_1 and 1- 2 w_1 respectively. Recalling that (<ref>) is a valid pitch-2 inequality of the form (<ref>) concludes the proof. 
























 §.§ A (1+ϵ)-oracle



We will prove Theorem <ref> in a sequence of intermediate steps. Our argument extends the weak separation of KC inequalities in <cit.>.

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 <ref>. Separating over i) is trivial. We first show how to separate over iii).


	
	For α∈ ]0,1], let z^α be the optimal solution to the following IP P_α, and v(z^α) its value:
	
    min∑_i ∈ [n]:  p_i < αx̅_i z_i + 2 ∑_i ∈ [n]:  p_i ≥αx̅_i z_i    s.t.   ∑_i ∈ [n] p_i (1 - z_i) ≤ 1-α,   z ∈{0,1}^n.

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



	Fix a feasible solution z̅ to (<ref>), and let I:={i ∈ [n]: z̅_i=1}. Then:
	
    β:=β(I)=1- ∑_i ∈ [n]∖ I p_i  =1  - ∑_i ∈ [n] p_i (1 - z̅_i) ≥α.

	Hence:
	
    [                      ∑_i ∈ I:  p_i < βx̅_i + 2 ∑_i ∈ I:  p_i ≥βx̅_i                                                                   =           ∑_i ∈ [n] :  p_i < βx̅_i z̅_i + 2 ∑_i ∈ [n] :  p_i ≥βx̅_i;                                                                                                                                       ≤ ∑_i ∈ [n]:  p_i < αx̅_i z̅_i + 2 ∑_i ∈ [n]:  p_i ≥αx̅_i z̅_i=v(z̅), ]

	where the central inequality holds at equality if α= β. Hence, if v(z^α)<2, the inequality with I:={i ∈ [n]: z_i^α=1} from (<ref>) is violated by x̅. Else, all inequalities from (<ref>) with β(I)=α are satisfied.
	


Note that
P_α is a  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 ∈ such that, for each i ∈ [n], p_i=r_i/q for some r_i ∈.


	Let r ∈{r_i + 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 (<ref>) with I={ i ∈ [n]: z̅^α = 1}. Else, (1+ϵ) x̅ satisfies all inequalities in Lemma <ref>.<ref>).  	



	Let r = r_i + 1 for some i ∈ [n]. If v̅^α < 2 then by Claim <ref> x̅ violates the corresponding inequality (<ref>). Otherwise, v^α≥ 2/(1+ϵ), and (1+ϵ)x̅ is feasible for any pitch-2 Inequality (<ref>) induced by I with β(I)=α.
	
	Now let I^* ⊆ [n] with β(I^*)=r^*/q < 1. There exists i^* ∈ [n] such that r_i^* < r^* ≤ r_i^*+1≤ q (with r_n+1 = q). Let α:=r_i^* + 1/q≤α^*:=β(I^*). The set of feasible solutions of P_α contains that of P_α^*, and {i ∈ [n] : p_i < α}= {i ∈ [n] : p_i < α^*}. Hence, v^α^*≥ v^α and consequently v^α^*<2 implies v^α<2.
	Thus, for separating all inequalities in Lemma <ref>.<ref>), it suffices to check (<ref>) for all α=r/q as in the statement of the claim.
	
	
	


The following claim follows in a similar fashion to the previous one by observing that, for β(I^*)=1/q, (<ref>) separates over undominated pitch-1 inequalities.


	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.


	Let x̅∈ [0,1]^n be such that (1+ϵ)x̅ satisfies all inequalities from Lemma <ref>, and define y̅∈^n as follows: y̅_i = min{1, 1+ϵ/1-ϵx̅_i} for i ∈ [n]. Then y̅∈ [0,1]^n and y̅ satisfies all inequalities from Lemma <ref>.



	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 ≠∅. Consider a pitch-2 inequality of the form (<ref>), and note that the left-hand side of the inequality computed in y̅ is lower bounded by ∑_i ∈ Jα_i, where α_i is the coefficient of x_i. First assume there exists j ∈ J ∩ I_2. 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}⊆ I_1. Then:
	
    ∑_i ∈ Iα_i x̅_i  ≥2/1+ϵ, from which we deduce
 
    ∑_i ∈ I∖{j}α_i x̅_i ≥2/1+ϵ-x̅_j ≥2/1+ϵ- 1 = 1-ϵ/1+ϵ and

	
    ∑_i ∈ Iα_i y̅_i  =  ∑_i ∈ I∖{j}α_i y̅_i + 1 = 1+ϵ/1-ϵ∑_i ∈ I∖{j}α_i x̅_i + 1 ≥ 2,

	as required. A similar (simpler) argument shows that y̅ also satisfies all pitch-1 inequalities ∑_i ∈ I x_i ≥ 1.
	
	
	


Proof of Theorem <ref>. We can now sum up our (1+ϵ)-oracle, see Algorithm <ref>. Correctness and polynomiality follow from the discussion above. 




































Since each p_i for i ∈ [n] is rational, we let q be the least common multiple for all p_i, i ∈ [n]. Then, fix β to be r/q where r ∈ [q].

We can iterate over all r ∈ [q] with β=r/q and check if an optimal solution z^* of (<ref>) has the objective value strictly smaller then 2. If there is such a case, then a violated inequality is induced by S:={i ∈ [n]:  z_i^* = 0 }. More  specifically, β':= β(S) = 1 - ∑_i ∈ [n] p_i (1 - z_i^*) ≥β and thus:


    ∑_i ∈ [n] ∖ S:  p_i < β'x̅_i + 2 ∑_i ∈ [n] ∖ S:  p_i ≥β'x̅_i ≤∑_i ∈ [n]:  p_i < βx̅_i z_i^* + 2 ∑_i ∈ [n]:  p_i ≥βx̅_i z_i^* < 2.


The IP in (<ref>) is a  problem and it can be solved up to the ϵ-tolerance with an FPTAS. Additionally, in order to consider only polynomially many IPs in the input size we can restrict r to the set {(1 + ϵ)^j:  j ∈ J } with J = { 0, 1, …, log_1 + ϵq }.


Observe that the pitch-1 inequalities can be ϵ-approximately separated with a single call of an FPTAS for the following :

    min∑_i ∈ [n]x̅_i z_i    s.t.   ∑_i ∈ [n] p_i (1 - z_i) ≤q-1/q,   z ∈{0,1}^n,

where x̅ and q are given as in the proof above. Here we just need to check whether the minimum is strictly smaller then 1, since (<ref>) is just a special case of (<ref>) where the objective function is scaled by 2 and β = 1/q, i.e. r=1.






 §.§ 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: 5 x_1 + 6 x_2 + 11 x_3 + 16 x_4 + 17 x_5 + 18 x_6 + 21 x_7 ≥ 41 }.

Inequality x_1 + x_3 + x_4 + 2 x_5 + x_6 + 2 x_7 ≥ 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 x_5 is higher than x_6 in this pitch-3, while it is the opposite in (<ref>). Such situations we call inversions and they do not occur in (relevant) pitch-2 inequalities. Inequality x_1 + x_2 + 2 x_3 + 3 x_4 + 4 x_5 + 3 x_6 + 4 x_7 ≥ 8 is an inverted facet of both the integer hull and the first CG closure.

For later use (in Section <ref>), 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.
Let β=1-p([n]∖ I). We can assume β>0, otherwise there is no valid inequality as above with support I.  Call J ⊆ I  massive if ∑_i ∈ Jp_i ≥β. Consider the following LP:

    [                  min     ∑_i ∈ Iα_i x^*_i;                 s.t.;                                ∑_i ∈ Jα_i                    ≥                    1 for all massive J⊆ I;                                         α                    ≥                    0 ]

Note that, for each feasible solution α̅ to the previous LP, we have that α̅^T x ≥ 1 is a valid inequality for the original  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.



However, when I ⊆ [n] is fixed, we can solve the separation problem over inequalities with support I just by solving an LP. Clearly, we are only interested in inequalities α^T x ≥ 1 with α≥ 0 and points 0≤ x^*≤ 1.


Let β=1-p([n]∖ I). We can assume β>0, otherwise there is no valid inequality as above with support I.  Call J ⊆ I  massive if p(J) ≥β. Call the unordered pair i≠ j ∈ I large if p_i + p_j ≥β. Consider the following LP:

    [                     min        ∑_i ∈ Iα_i x^*_i;                    s.t.;                                             α_i                       ≥                       1       for all massive i;                                       α_i + α_j                       ≥                       1 for all large pairs i,j;                                 α_i + α_j + α_k                       ≥                       1    for all i≠ j ≠ k ∈ I;                                               α                       ≥                       0 ]

Note that, for each feasible solution α̅ to the previous LP, we have that α̅^T x ≥ 1 is a valid inequality for the original  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.





§ INTEGRALITY GAP FOR  WITH BOUNDED PITCH INEQUALITIES




 §.§ When p=c



	
	Consider an instance of  (<ref>) with p=c. Denote by K the linear relaxation of (<ref>) 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 (<ref>). We can assume p^T x̅ > 1.5, else we are done.


	The support of x̅ has size 2.


	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
	
    p^T x' ≥( 1-1/k )p^T x̅ > 2/3· 1.5 = 1,

	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<p_i≤ p_j≤ 1. Since p_i + p_j >1.5, we deduce p_j > .75. Since p_j≤ 1, we deduce p_i>.5.


	Let ℓ < j and ℓ≠ i. Then p_ℓ <.25.


	Recall that for S ⊆ [n] we denote its characteristic vector with χ^S. If 0.25 ≤ p_ℓ < p_i, then χ^{ℓ,j} is a feasible integral solution of cost strictly less than x̅. Else if 0.5<p_i≤ p_ℓ<p_j, 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_n+∑_ℓ=1^i-1p_ℓ<1.



	Suppose p_n+∑_ℓ=1^i-1p_ℓ≥ 1. Since p_ℓ<.25 for all ℓ=1,…,i-1, there exists k≤ i-1 such that x_n+∑_ℓ=1^kp_k ∈ [1,1.25[. Hence x^{1,…,k,n} is a feasible integer solution of cost at most 1.25, a contradiction.	
	


Because of the previous claim, the pitch-2 inequality ∑_k=i^n x_k ≥ 2 is valid. The fractional solution of minimum cost that satisfies this inequality is the one that sets x_i=x_j=1 (since j=i+1) and all other variables to 0. This is exactly x̅.






 §.§ CG closures of bounded rank of the natural  relaxation


For t ∈, let K^t be the linear relaxation of the (<ref>) given by: the original knapsack inequality; non-negativity constraints; all pitch-k inequalities, for k≤ t.


	For t ≥ 2, the integrality gap of K^t is at least max{1/2,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 (<ref>). 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 c^T 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,…,γ_n+1). By scaling, we can assume that the rhs of the latter inequalities is 1. Hence v'=α + ∑_i=1^r γ_i. 


	Let d^Tx ≥ 1 be a valid pitch-t inequality for (<ref>), and assume w.l.o.g. that d_1≤ d_2 ≤…≤ d_n. Then inequality ∑_i=2^n d_i x_i ≥max{1/2,t-2/t-1} is a valid inequality of pitch at most t-1 for (<ref>).





	The inequality ∑_i=2^n d_i x_i ≥ 1 - d_1 is a valid inequality for (<ref>), and by construction it is of pitch at most t-1. If t≥ 3, we obtain ∑_i=1^t-1 d_i < 1 and consequently d_1 < 1 / (t-1), from which we deduce
	
    1 - d_1 > 1 - 1/t-1 =  t-2/t-1≥1/2.

	If conversely t=2, by Lemma <ref> we can assume w.l.o.g. that d_1=1/2, and we can conclude 1 -d_1=1/2> 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 <ref>. We obtain an inequality (c')^Tx ≥ v”, where one immediately checks that c'≤ c and

    [                                                                    v”                                                                     ≥ α + ∑_i=1^n+1γ_i  max{1/2,t-2/t-1}≥max{1/2,t-2/t-1}(α + ∑_i=1^n+1γ_i);                                                                                                                                           =                                                  max{1/2,t-2/t-1} v'. ]

Hence the integrality gap of K^t is

    C/v'≥C/v”max{1/2,t-2/t-1}

and the thesis follows since the integrality gap of K^t-1 is at most C/v”.




	
	For a fixed ϵ>0 and square integers n≥ 4, consider the   instance K defined as follows:
	
    [         min                     ϵ y           +      √(n) z           + ∑_i=1^n x_i;                      st;              (n-√(n)) y           +       n/2 z           + ∑_i=1^n x_i         ≥ n;            ;                      y,                      z,                       x     ∈{0,1}. ]

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


Proof.
Because of Lemma <ref>, 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

    (y̅,x̅,z̅)=(1,1/n-√(n)+1,…,1/n-√(n)+1_n  times,2/√(n))

is a feasible point of K^1. Since ϵy̅  + √(n)z̅ + ∑_i=1^n x̅_i =ϵ + 2 + n/n-√(n)+1, the thesis follows.

Observe that (n-√(n)) y̅ +  n/2z̅ +∑_i=1^n x̅_i=(n-√(n)) + n/22/√(n) + n/n-√(n)+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 x_i. Hence, all those inequalities are dominated by the valid pitch-1 inequalities

    z + ∑_i ∈ Ix_i ≥ 1  ∀ I ⊆ [n], |I|=n - √(n) +1,
 which are clearly satisfied by (y̅,x̅,z̅).




	For a fixed q ∈, let CG^q(K) be the q-th CG closure of the   instance K as defined in Lemma <ref>. The integrality gap of CG^q(K) is Ω(√(n)).


Proof.
We will use the following fact, proved (for a generic covering problem) in <cit.>. Let t,q ∈ and suppose (y̅,z̅, x̅) ∈  K^t. Define point
(y',x',z'), where each component is the minimum between 1 and (t+1/t)^q times the corresponding component of (y̅,z̅, x̅). Then (y',x',z') ∈ CG^q(K). Now fix t,q. We have therefore that

    [           ϵ y'   + √(n) z' + ∑_i=1^n x'_i                                         ≤ (t+1/t)^q (ϵy̅   + √(n)z̅+  ∑_i=1^n x̅_i);                                                                                   =            (t+1/t)^q (ϵ + 2 + n/n-√(n)+1) ]

and the claim follows in a similar fashion to the proof of Lemma <ref>.



 §.§ 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 <cit.> 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̅).



  
The rounding procedure:

Let S={i∈ [n]:x̅_i≥ 1/2}. Set x_i=1 for any i∈ S. Consider the residual variables :=[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):

    min   ∑_i∈ C_i x_i
    
    s.t.    ∑_i∈p_i' x_i ≥ b'
        0≤ x_i≤ 1/2

where p'_i=min{p_i, 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


    ∑_i∈ C_i x_i^* ≤∑_i∈ C_i x̅_i


Therefore, if it exists an integral solution x^int to (RP) of cost C(x^int)≤ 2C(x^*) then C(x^int)≤ 2C(x̅) and we are done.

We can rewrite the residual relaxation (RR) in the following equivalent way:

    min   ∑_i∈C_i/2 y_i
    
    s.t.    ∑_i∈p_i'/2 y_i ≥ b'
        0≤ y_i≤ 1


Clearly the optimal fractional solution to (RR) can be obtained by ordering the variables according to their densities. W.l.o.g., assume that C_1/p_1'≤C_2/p_2'≤…≤C_||/p_||' and let t+1∈[||] be the smallest integer such that
∑_i= 1^t+1p_i'/2≥ b' and therefore (recall p'_i≤ b'):


    ∑_i= 1^tp_i' ≥ 2b'-p'_t+1≥ b'


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:


    ∑_i=1^t C_i/2≤∑_i∈ C_i x_i^*


It follows that the integral solution x^int obtained by setting x_1=1 for i∈ [t] and zero otherwise is feasible by (<ref>) and of cost at most twice the optimal fractional of (RR) by (<ref>).



 §.§ When all bounded pitch and knapsack cover inequalities are added


Consider the following  instance with ϵ_n = 1/√(n):



    min     ∑_i ∈ [n] x_i + 1/√(n)∑_j ∈ [n] z_j  
    s.t.     ∑_i ∈ [n] x_i + 1/n∑_j ∈ [n] z_j ≥ 1 + ϵ_n 
         x, z ∈{0,1}^n.



	For any fixed k ∈ and n ∈ sufficiently large, point (x̅ ,z̅) ∈^2n with x̅_i = 1+ϵ_n/n, z̅_i = k/n satisfies the natural linear relaxation, all KC and all inequalities of pitch at most k valid for (<ref>). Observing that the optimal integral solution is 2, this gives an IG of 2/1 + k/n≈ 2.


Proof.
We prove the statement by induction. Fix k ∈. 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

    ∑_i ∈ I w_i x_i + ∑_j ∈ J w_j z_j ≥β

be a valid KC or pitch-k inequality with support I ∪ J, which gives that w_i, w_j ∈_>0,  ∀ i ∈ I,  ∀ j ∈ J and β > 0. Observe the following.


	
	
	|I| ≥ n-1. In addition, |I| = n-1 or |J| ≤ n (1-ϵ_n) implies w_i ≥β,  ∀ i ∈ I.



	Since all coefficients in (<ref>) are strictly positive and β > 0, |I| ≤ n-2 gives that the feasible solution (χ^[n] ∖ I, 0⃗) for (<ref>) is cut off by (<ref>), a contradiction.
	
	Furthermore, if |I| = n-1 and w_i^* < β for some i^* ∈ I, then (χ^([n] ∖ I) ∪{i^* }, 0⃗) is cut off, again a contradiction.
	
	Finally, if |I| = n, |J| ≤ n (1-ϵ_n) and w_i^* < β for some i^* ∈ I, then (χ^{i^* }, χ^{[n] ∖ J }) does not satisfy (<ref>), but it is feasible in (<ref>).
	
	


We first show the statement for (<ref>) being a KC. By the definition of KC:
β = 1 + ϵ_n - |[n] ∖ I|-|[n] ∖J|/n, w_i=min{1, β},  ∀ i ∈ I and w_j=min{1/n, β},  ∀ j ∈ J. If I=[n], then ∑_i ∈ I w_i x̅_i = min{1, β}· (1+ϵ_n) ≥β since β≤ 1 + ϵ_n. Otherwise, |[n] ∖ I|=1 so w_i=β,  ∀ i ∈ I and ∑_i ∈ I w_i x̅_i= β(n-1)(1+ϵ_n)/n > β for sufficiently large n.

Conversely, let (<ref>) be a valid pitch-k inequality. By Claim <ref>, if |I| = n-1 or |J| ≤ n (1-ϵ_n) then w_i ≥β,  ∀ i ∈ I so the proof is analogous to the one for KC. Otherwise, |I|=n and |J| > n (1-ϵ_n).
Consider the LP (<ref>) in Section <ref> 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 (<ref>) for i, ∈ I, then 
    α_i + α_≥ 1.
 Furthermore, for n large enough one has |J| > n (1-ϵ_n) ≥ k so

    ∑_j ∈ Kα_j ≥ 1
 for any k-subset K of J. We claim that the minimum in (<ref>) is attained at α̅_i=1/2,  ∀ i ∈ I and α̅_j=1/k,  ∀ j ∈ J. Indeed, the objective function of (<ref>) computed in α̅ is given by

    |I| ·1/2·1+ϵ/n + |J| ·1/k·k/n = 1+ϵ_n/2 + |J|/n.

On the other hand, by summing (<ref>) for all possible pairs with multipliers 1+ϵ_n/2(n-1) and (<ref>) for all subsets of J of size k with multipliers |J|-1 k-1^-1·k/n, simple linear algebra calculations lead to

    ∑_i ∈ Ix̅_i α_i + ∑_j ∈ Jz̅_j α_j ≥1+ϵ_n/2 + |J|/n,

showing the optimality of α̅. Recalling |J|>n(1-ϵ_n), we conclude that

    ∑_i ∈ Ix̅_i α̅_i + ∑_j ∈ Jz̅_j α̅_j = 1+ϵ_n/2 + |J|/n > 1+ϵ_n/2 + 1 -ϵ_n>1,

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.








































plain













