{'fraction_non_alphanumeric': 0.06413361169102297, 'fraction_numerical': 0.021419624217118998, 'mean_word_length': 3.455171130952381, 'pattern_counts': {'":': 0, '<': 24, '<?xml version=': 0, '>': 11, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 12, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Simpler derivation of bounded pitch inequalities for set covering, and minimum knapsack sets

A valid inequality \alpha^Tx \ge \alpha_0 for a set covering problem is said to have pitch<= k ( a positive integer) if the k smallest positive \alpha_j sum to at least alpha_0. This paper presents a new, simple derivation of a relaxation for set covering problems whose solutions satisfy all valid inequalities of pitch and is of polynomial size, for each fixed . We also consider the minimum knapsack problem, and show that for each fixed integer p>0 and 0<\epsilon<1 one can separate, within additive tolerance \epsilon, from the relaxation defined by the valid inequalities with coefficients in {0, 1, . . . , p} in time polynomial in the number of variables and 1/\epsilon.


Introduction
In this paper we first consider set-covering problems. Formally, given the m × n, 0/1 matrix A we write where e is the vector of m 1s. We assume, without loss of generality, that the supports of constraints in Ax ≥ e never contain one another and have cardinality greater than 1. Under these assumptions any undominated inequality α T x ≥ α 0 valid for Σ(A) satisfies α 0 ≥ 0 and α j ≥ 0 for 1 ≤ j ≤ n.
Given such an inequality, we write S(α) = {1 ≤ j ≤ n : α j > 0}. The set (1) can have extreme points with high fractionality that are difficult to cut-off by standard integer programming techniques. Balas and Ng [1] characterize the facets for (1) with coefficients in {0, 1, 2}. The work in [3] introduced a general class of combinatorial inequalities generalizing those consider in [1]. This work relies on the concept of pitch: Definition 1 [3]. Given an inequality α T x ≥ α 0 with α ≥ 0 and integer 0 ≥ π ≤ |S(α)|, we say that α T x ≥ α 0 is of pitch ≤ π if the π smallest positive entries in α sum to at least α 0 . When π > 0 the inequality is said to be of pitch = π if it is of pitch ≤ π and it is not of pitch ≤ π − 1.
As a result, an inequality with coefficients in {0, 1, . . . , π} has pitch ≤ π. Note that when π = 0 we must have α 0 ≤ 0. The main result in [3] is the following: Theorem 2 [3] Consider a set-covering problem given by a matrix A, and let π ≥ 2 be a fixed integer. There is a polynomial-sized extended formulation whose projection to x-space satisfies all valid inequalities for Σ(A) of pitch ≤ π.
Here, an extended formulation is of the form {(x, y) ∈ R n×N : Cx + Dy ≥ b} (for some N, C, D and b) whose projection to x-space contains Σ(A), and the theorem states that the size of this description (number of bits) is polynomial in n and m. The construction in [3] is admittedly complex. Also see [4]. Recent work [10], [6] has provided new constructions related to bounded pitch inequalities for set covering.
A first result in the paper provides a simpler construction for Theorem (2).
Theorem 3 Given a set-covering problem given by a matrix A, and integer π ≥ 2 there is a disjunctive formulation for (1) with O(mn 2 + π m π−1 n π ) variables and constraints.
In the second part of this paper we consider the so-called minimum-knapsack problem, i.e. a problem whose feasible region is of the form with w j ∈ Z + for 0 ≤ j ≤ n. Obviously by complementing the variables we obtain a standard ("maximum") knapsack problem; however from a polyhedral standpoint there are significant differences.
Here, a cover inequality is a valid inequality of the form x(S) ≥ 1 for some S ⊆ {1, . . . , n}. Given remark (4) one wonders if a result similar to Theorem 2 exists for the minimum-knapsack problem. This question has been taken up in recent work [5], where the following result is proved: Given a minimum-knapsack problem (2), 0 < ǫ < 1 and p = 1 or p = 2, there is an algorithm that, with input x * ∈ [0, 1] n either finds a valid inequality for (2) of pitch = p that is violated by x * or shows that x * satisfies all valid inequalities of pitch p within multiplicative error ǫ. The complexity of the algorithm is polynomial in n and 1/ǫ. This result does not guarantee strict separation; however one can show that an inequality of pitch = 1 is violated iff a cover inequality is violated, and separation of such inequalities is known to be NP-hard. In this sense Theorem 5 is best possible, for pitch ≤ 2.
In this paper we prove the following result: Theorem 6 Given a minimum-knapsack problem (2), 0 < ǫ < 1, and integer p ≥ 1, there is an algorithm that, with input x * ∈ [0, 1] n either finds a valid inequality for (2) with coefficients in {0, 1, . . . , p} that is violated by x * or shows that x * satisfies all such valid inequalities within additive error ǫ. The complexity of the algorithm is polynomial in n and 1/ǫ.
One can show that a valid inequality of pitch ≤ 2 is violated by a given vector x * iff x * violates a valid inequality with coefficients in {0, 1, 2}; thus Theorem 6 generalizes Theorem 5.

Set covering
In this section we provide a short construction leading to Theorem 3. First we will motivate our approach by introducing a branching technique for 0/1 integer programming that is of independent interest, and which we term vector branching.
is valid for a mixed-integer set F , where the x variables are assumed to be binary. Write S = {j 1 , j 2 , . . . , j |S| }, and for 1 ≤ h ≤ |S| define the set Then the disjunction is valid for F since (3) implies j∈S x j ≥ 1. This simple observation can be used to drive a branch-and-bound algorithm to solve optimization problems over F . When processing a node v of branch-and-bound, this scheme (a) identifies an inequality (3) that is valid for the relaxation to F used at v and (b) creates |S| new nodes, corresponding to each of the terms in the disjunction (4). The node corresponding to term h of (4) imposes the constraints defining F h in addition to all those present at v. We call this procedure vector branching 1 .
Here we are interested in the implications of this scheme toward set covering problems (1) when the inequalities (3) used to drive vector branching are rows of Ax ≥ e. Lemma 8 given below will be used to motivate our proof of Theorem 2, but first, for self-containment, we prove a basic result [1,3] which will be used in the sequel.
Proof. (1) Otherwise setting x j = 1 if j / ∈ T and x j = 0 otherwise yields a feasible binary solution to Ax ≥ e which violates j∈T α j x j ≥ α 0 . (2) Otherwise setting x j = 1 if j / ∈ T or j = k, and x j = 0 otherwise, yields a feasible binary solution to Ax ≥ e which violates j∈T α j x j ≥ α 0 .
Lemma 8 Suppose we apply vector branching to a set covering problem (1). Consider a node that arises when we vector-branch on one of the rows, j∈S x j ≥ 1, of Ax ≥ e. Let y ∈ R n be a feasible solution to the relaxation at that node. Then y satisfies every inequality with α j > 0 for all j ∈ T which is valid for (1), of pitch ≤ 2, and such that S ⊆ T .
Proof. By construction y k = 1 for some k ∈ T , so we may assume α k < α 0 . By Lemma 7 (2) there is some row This result epitomizes the techniques that we will use below to obtain a proof of Theorem 2 -the result relies on the explicit variable-fixing constraints defining the F h plus the structural properties of valid inequalities for set covering. Letchford [9] has used a similar idea.
Note that Lemma 8 does not yield a strategy for developing a polynomial-size branch-and-bound tree whose leaf nodes satisfy all valid inequalities of pitch ≤ 2. In order to prove Theorem 2 we instead rely on the well-known equivalence between branching and disjunctive formulations. Specifically, for each integer π ≥ 1 we will present a lifted formulation of the form where, for some integer N π , y π ∈ is a vector of additional variables and C π , D π , b π are of appropriate dimension, such that (a) (6) is a relaxation of (1), i.e. any feasible solution to (1) can be lifted so as to satisfy (6), The x-component of any vector (x, y π ) feasible for (6) satisfies every valid inequality for (1) of pitch ≤ π, and (c) The size of formulation (6) is polynomial in n and m (= number of rows in the matrix A defining the set-covering problem).
We term (6) the level-π formulation. We will first inductively describe the level-π formulation and then prove that it satisfies the desired properties. We start with the level-1 formulation, which is simply the original set-covering set of inequalities and variable bounds: Ax ≥ e, x ∈ [0, 1] n (so N 1 = 0). Now assume inductively that π ≥ 1 and we have constructed the level-π formulation.
To generate the level-(π + 1) formulation we proceed using steps (I) and (II) given below; however we first provide an intuitive interpretation of our approach, which is based on considering the projection to x-space of the level-k formulation (for any k) which we denote by M k .
Thus, given M π , for each row i of A we define a polytope which amounts to the disjunction that represents vector branching on the i th constraint of Ax ≥ e. To this end, let 1 ≤ i ≤ m, and suppose the support of the i th row of A is S i = {j 1 , . . . , j |Si| }. Then, for each 1 ≤ t ≤ |S i |, we define the polytope D π+1 (t) ⊆ [0, 1] n by the system x ∈ M π .
and then define Finally, let The intuition here is that for each 1 ≤ i ≤ m, the collection of all systems (7), (8), plus (9) indeed implements vector branching on the i th constraint of Ax ≥ e from a disjunctive perspective, while (10) enforces the simultaneous application of all such disjunctions. When π = 2, a simple rewording of Lemma 8 shows that every point in M 2 satisfies all pitch ≤ 2 valid inequalities. Now we will provide our formal description of the level-π formulation.
Next we prove the desired facts regarding this formulation.
Lemma 9 Letx be a feasible solution to the set covering problem (1), i.e.x ∈ {0, 1} n satisfies Ax ≥ e. Then for every integer π ≥ 1,x can be lifted to a vector feasible for the level-π formulation.
Proof. By induction on π with the case π = 1 valid by definition. Asssume that the assertion has been proved for π; we now show it is true for π + 1. It suffices to prove, for 1 ≤ i ≤ m, thatx can be lifted to a vector contained in D π+1 i . And in order to prove this fact we need to show thatx can be lifted to a vector contained in D π+1 i (t) for some t with 1 ≤ t ≤ |S i |. This fact follows by setting t = min{1 ≤ h ≤ |S i | :x h = 1}, and induction.
Proof. By induction on π. Let j∈T α j x j ≥ α 0 be a valid inequality for (1) with α ≥ 0 and α 0 > 0, α j ≤ α 0 for each j ∈ T , of pitch ≤ π. Since, for any π ≥ 1, M π+1 ⊆ M π , i.e. the set of feasible solutions for the level-(π + 1) formulation is contained in the set of feasible solutions for the level-π formulation, we may assume that j∈T α j x j ≥ α 0 has pitch = π. Further, since j∈T α j x j ≥ α 0 is valid for (1), by Lemma 7(1) Hence, if π = 1 the result clearly follows. Suppose now that we have proved the assertion for π and wish to prove it for π + 1. Since (x,ỹ) is contained in D π+1 i the result will follow if we can prove that, for every t with has pitch ≤ π − 1 and so by induction (and constraint (11b)) it is satisfied byx. The result now follows.

Lemma 11
For each fixed π, the level-π formulation has size polynomial in m and n.

Minimum-knapsack
In this section we consider minimum-knapsack problems (2) and prove Theorem 6. We will use Remark 4, together with a structural characterization of valid inequalities for (2), so as to obtain a polynomial-time algorithm for near-separation from the relaxation for the knapsack (2) defined by the valid inequalities with coefficients in {0, 1, . . . , p} for some fixed p > 0.
3.0.1 Motivation: the cases p = 2 and p = 3 We first illustrate our approach in the case p = 2 and outline a difficulty that arises when p = 3. Let p = 2; here we want to check if a vector y ∈ [0, 1] n violates any valid inequality (where S 1 ∩S 2 = ∅) that is not dominated by another inequality of the same kind. Here the situation is simple because by a result to be proven below (Theorem 16) when p = 2 we must have w h < w k for every h ∈ S 1 and k ∈ S 2 .
Example 12 Consider the minimum-knapsack set (2) given by inequality The inequality is valid. However this inequality is not monotone in that w 3 = 5 < 6 = w 4 and yet the coefficients of x 3 and x 4 are 2 and 1, respectively. However, the inequality is also valid, and dominates (14).
As a result, we next argue that checking if y violates any inequality (13) can be reduced to the solution of the following n minimum-knapsack problems, one for each index 1 ≤ k ≤ n, where the k th case checks for violations of those inequalities (13) where k = argmax{w j : j ∈ S 1 }, and is formulated as follows: To see that this approach works, supposeẑ is feasible for (15). Then constraint (15b) guarantees that for every index h withẑ h = 1 and w h ≤ w k we have i.e. {j :ẑ j = 1} \ {h} forms a cover for (2). Thus, by Remark 4, the inequality j : wj ≤w k ,ẑj=1 x j + 2 j : wj >w k ,ẑj =1 x j ≥ 2 is valid for (2) and if it is violated by y then j : wj ≤w k y jẑj + 2 j : wj >w k y jẑj < 2 and therefore V (k) < 2. The reverse construction is similar. In summary, V (k) < 2 if and only if y violates some inequality (13) where k = argmax{w j : j ∈ S 1 }, as desired. Note that this separation argument requires exact solution of a knapsack problem, however near-separation follows using the usual FPTAS argument. As a further example, suppose we want to check if there exists some violated valid inequality of the form with T 1 , T 2 nonempty and pairwise disjoint. [This is the p = 3 case but without a term of therm 3x(T 3 ) in the left-hand side.] Again we aim to reduce this task to a polynomially-large set of knapsack problems. To extend the approach used for p = 2 we need, to begin with, some way to summarize the structure of covers (for (16)) while guaranteeing that such covers are also covers for the original knapsack (2) (this will be done, in the general case, in Lemma 25 below). The salient point is that there are two critical cases that are needed to guarantee that any cover for (16) is also a cover for (2): first, the case where the indices of the two largest w j with j ∈ T 1 are excluded from T 1 ∪ T 2 and second, the case where the single largest largest w j with j ∈ T 2 is excluded from T 1 ∪ T 2 . Thus, we have two cases, rather than one, but we need to be able to represent both using a single constraint similar to (15b). Moreover, the approach used for p = 2 relied on the "monotonicity" property illustrated by Example 12. In the case p = 3 the monotonicity does not hold.
As the example shows, the technique outlined for the case p = 2 is not easily extended due to non-monotonicities in coefficients. However, Theorem 16 will show that for any fixed p the total number of such non-monotonicities is bounded (i.e. independent of n).
In our general approach we will handle both aspects outlined above while nevertheless relying on enumeration of a polynomial number of cases: the multiple types of cover inequalities that have to be considered, and the non-monotonicity illustrated by Example 13.

Near-monotonicity
In this section we describe an important, near-monotonicity property of valid inequalities for (2) that will be critical in developing our polynomial-time separation algorithm.
Definition 14 Let n j=1 α j x j ≥ α 0 be an inequality (valid or not) with α j ∈ Z + for 0 ≤ j ≤ n. Let k ∈ Z + be such that α j = k for some j. The drag of k is defined as If there is no j with α j = k then we set δ(k) = ∅.
Example 15 Consider the minimum knapsack set given by Then is valid for the knapsack. Applying Definition 14, some selected drag sets are as follows. Using this definition, we obtain a criterion for validity of an inequality for the knapsack set (2).
Theorem 16 Let P ∈ Z+, and suppose n j=1 α j x j ≥ α 0 is a valid inequality for (2) with α j ∈ {0, 1, . . . , P } for all j. Then either h∈δ(k) α h ≤ P − 2 for every k ≥ 2 or there is another valid inequality with coefficients in {0, 1, . . . , P } that strictly dominates n j=1 α j x j ≥ α 0 . Proof. Aiming for a contradiction suppose for some k ≥ 2 we have h∈δ(k) α h ≥ P − 1. Choose Let S = suppt(α) = suppt(α ′ ). To complete the proof we will show that the inequality which dominates n j=1 α j x j ≥ α 0 , is valid for (2). To do so we appeal to Remark 4. In other words, we need to prove that for any C ⊆ S if α ′ (S \ C) < α 0 then w(S \ C) < w 0 .
Let C ⊆ S be given. If i / ∈ S \ C then α ′ (S \ C) = α(S \ C) and we are done. In the remainder of the proof we assume i ∈ S \ C and α ′ (S \ C) < α 0 . Let δ = δ(k) be defined as in Definition 14. If But this is a contradiction since we assumed α ′ (S \ C) < α 0 . Hence ∃h ∈ δ ∩ C.
is a valid inequality for the minimumknapsack set defined by n j=1 α j x j ≥ α 0 and hence it is also valid for (2), i.e.

Separation
Given a fractional vector y ∈ [0, 1] n we consider separation of y from the relaxation for the knapsack (2) defined by all valid inequalities of the form (where the S h are assumed pairwise disjoint), in polynomial time. Enumeration of all q ∈ {2, . . . , p} will yield Thorem xyzp. As a first step in our procedure, we will present an efficient procedure that succinctly enumerates all possible inequalities (20) that are valid and undominated. The enumeration will be accomplished by first classifying all inequalities (20) using a compact scheme. Throughout, we will rely on Example 15 given above.
Example 17 (Example 15, continued.) In this example the knapsack set was given by the inequality 10x 1 + 10x 2 + 80x 3 + 100x 4 + 80x 5 + 20x 6 + 50x 7 + 25x 8 ≥ 280 and we consider the valid inequality Consider an inequality (20) (valid or not). In order to classify this inequality we define The following observation will be useful throughout: (t.2) For each k ∈ I, m k ∈ argmin{w j : j ∈ S k } with ties broken arbitrarily.
Remark 20 A given inequality can have more than one type. However, Lemma 21 given next narrows the choices, without loss of generality, and furthermore Lemma 24 will show a common attribute for all types. Proof. Considering requirements (t.1)(a,b) for a type τ , we see that for any i ∈ I, |L i | ≤ max{|D i |, q− 1}. But |D i | ≤ q 2 , by Theorem 16. We will next see how the type of an inequality encodes its validity. This will be done in Lemma 25 below after we introduce some notation.
Lemma 24 Suppose an inequality (20) is of type τ , and that for each i ∈ I we have a subset X i such that L i ⊆ X i ⊆ S i . Then we can rewrite As a corollary, all types for a given inequality (20) have the same signature.
Proof. Identity (23) follows because as noted in Remark 19 for all i ∈ I, L i contains the indices of the |L i |-largest w h with h ∈ S i , and by (t The corollary follows (for example) by setting X i = S i for all i ∈ I.
We now present the characterization of validity that we will useful below.
Lemma 25 An inequality (20) of type τ is valid for Proof. Remark (4) implies that inequality (20) is valid for (2) iff for each family of subsets from which the result follows.

Separation through type enumeration
Our separation procedure will enumerate a set of candidate triple (I, L, m) that includes all possible types τ arising from valid inequalities, and for each enumerated candidate perform a polynomial-time test, given in Section 3.3. In this section we describe the enumeration. Let us consider an arbitrary triple (I, L, m) where L is a collection of q subsets of {1, . . . , n} and each m i ∈ {0, 1, . . . , n}. In order for the triple to arise as the type of an inequality it must satisfy a number of conditions given next: (r.1) I ⊆ {1, . . . , q}. The sets {m i } ∪ L i (i ∈ I)are pairwise disjoint. For any i ∈ I, if |L i | < q − 1 then m i ∈ L i , and if m i / ∈ L i then w mi < w m k for all k > i with k ∈ I.
(r.2) We require that |L i | < q 2 for all i ∈ I. In terms of separation from undominated, valid inequalities requirement is valid in light of Theorem 16 and Lemma 21.
Stronger conditions can be imposed, however these assumptions suffice to prove: Lemma 27 For given q, the set of pairs satisfying (r.1)-(r.2) includes all types arising from undominated, valid inequalities (20). The total number of tuples that satisfy (r.1)-(r.4) is at most O(q 2 2 q n q 3 ).
Proof. Follows from the above discussion and the fact that there are at most 2 q choices for sets of indices i with m i > 0.

Separation using a given type
Assume again a given y ∈ [0, 1] n . Consider a fixed triple τ = (I, L, m) that has been enumerated as indicated above, i.e, it satisfies (r.1)-(r.2). Here we will first describe an optimization problem whose solution either:  (2) that is violated by y.
To construct the formulation, we write, each i ∈ I, Now we describe our formulation. Let σ(τ ) be the value of problem (22) (computed exactly as in that formulation). Then we solve the problem: z ∈ {0, 1} n Lemma 28 Suppose there is an inequality q i=1 i x(S i ) ≥ q of type τ valid for the knapsack (2). Then, settingẑ j = 1 iff j ∈ ∪ i S i yields a feasible solution to (26).
Proof. By definition of the type τẑ satisfies (26b). To show (26c) holds atẑ, we will show that S i ⊆ V i for all i ∈ I. Let j ∈ S i ; if j ∈ {m i }∪L i then by construction j ∈ V i , so assume j / ∈ {m i }∪L i . In this case we prove j ∈ R i . To do so, note that by definition of m i in (t.2), w mi ≤ w j . Moreover j ∈ S i \ L i and hence (Remark 19) w j ≤ M i . Finally, the S k are disjoint, and so j / ∈ ∪ k =i S k and hence j / ∈ F i . Thus indeed j ∈ R i as desired. To complete the proof we need to show thatẑ satisfies (26d), but this follows from Lemma 25. is valid for (2).
Proof. First note that for any i ∈ I, S i ⊇ L i (by (26b)). Moreover, for each i ∈ I, either (a) |L i | < q − 1 in which case S i = L i or (b) |L i | ≥ q − 1 and w j ≥ w h for each j ∈ L i and h ∈ S i \ L i . Thus it follows (Lemma 24) that if (27) has a certain type τ ′ , then σ(τ ′ ) = σ(τ ). As a result, constraint (26d) and Lemma 25 imply that (27) is valid for (2). We can now prove our key separation theorem.
Proof. Suppose first that i∈I i x(S i ) ≥ q is an inequality of type τ , valid for (20) and violated by y. By Lemma 28, by settingẑ j = 1 iff j ∈ ∪ q i=1 S e(i) we obtain a feasible solution for problem 26. But since the objective value attained byẑ in this problem equals i∈I i y(S i ) < q we conclude as desired.
Now assume Ω(y, τ ) < q. Letz be an optimal solution for (26). By Lemma 29 the inequality i∈I i x(S i ) ≥ q is valid for (2) where for i ∈ I we define S i . = V i ∩ {j :z j = 1}. But since q > Ω(y, τ ) = i∈I i y(S i ) we conclude y violates (28).

Near separation in polynomial time
In order to prove Theorem 6 there remains the issue of the complexity of solving problems of the form (26). These are min-knapsack problems, for which an FPTAS exists, based on that for the standard knapsack problem [8], [7]. Relying on such an FPTAS would yield a proof of Theorem 6 (though,technically, the complexity would depend polynomially on p/ǫ). However this route would yield an algorithm that relies on the traditional techniques: dynamic programming and coefficient scaling.
Here we indicate a simpler technique that applies in this case 3 . Consider, again, a given value of q and an inquality of type τ as in the sections above. For 1 ≤ j ≤ n defineŷ j . = 1 qn 2 ⌈qn 2 y j ⌉, i.e. the "round-up" of y j to the nearest integer multiple of 1 qn 2 . Then for any type τ V (y, τ ) ≤ V (ŷ, τ ) ≤ V (y, τ ) + 1 n and so V (ŷ, τ ) < q implies that y violates an inequality of type τ whereas if V (ŷ, τ ) ≥ q then y satisfies every inequality of type τ within additive error at most 1/n, which is less than ǫ for n large enough.
Moreover V (ŷ, τ ) can be computed in polynomial time, since it can be restated as a minknapsack problem with nonnegative, integral objective coefficients bounded above by qn 2 . Such a min-knapsack problem can be solved using dynamic-programming (no need for coefficient scaling) 4 . We have thus proved Theorem 6.