New Sequence-Independent Lifting Techniques for Cover Inequalities and When They Induce Facets

1 Introduction

Lifting is a technique for strengthening cutting planes for integer programs by increasing the coefficients of variables that are not in the cut. We study lifting methods for valid cuts of knapsack polytopes, which have the form conv(P ) where

for a1, . . . , an, b ∈ N with 0 < a1, . . . , an ≤ b. We interpret P as the set of feasible packings of n items with weights a1, . . . , an into a knapsack of capacity b. Such knapsack constraints arise in binary integer programs from various industrial applications such as resource allocation, auctions, and container packing. They are a very general and expressive modeling tool, as any linear constraint involving binary variables admits an equivalent knapsack constraint by replacing negative-coefficient variables with their complements. A minimal cover is a set C ⊆ {1, . . . , n} such that

∑j∈C aj > b and ∑j∈C\{i} aj ≤ b for all i ∈ C. That is, the items in C cannot all fit in the knapsack, but any proper subset of C can. The minimal cover inequality/cut corresponding to C is the inequality∑

which enforces that the items in C cannot all be selected. A lifting of the minimal cover inequality is any valid inequality of the form

The lifting coefficients αj are often computed one-by-onea process called sequential lifting that depends on the lifting order. Sequential lifting can be expensive since one must solve an optimization problem for each coefficient. Furthermore, one must reckon with the question of what lifting order to use. To lessen this computational burden, the lifting coefficients can be computed simultaneously. This method is called sequence-independent lifting and is the focus of this work. Our contributions include: (i) a generalization of the seminal sequence-independent lifting method developed by Gu et al. [2000] and a correction of their proposed generalization; (ii) the first broad conditions under which sequenceindependent liftings that are efficiently computable from the underlying cover-via our new techniques-define facets of conv(P) (facet-defining cuts are the gold standard for cutting planes since they are in a formal sense the strongest kind of cutting plane); and (iii) new cover inequality generation methods that, together with our new lifting techniques, display promising practical performance in experiments.

1.1 Preliminaries on Cutting Planes and Sequence-Independent Lifting

A (valid) cutting plane for P is any constraint a⊤x ≤ b that is satisfied by all x ∈ P . Cutting planes are one of the most critical components of all modern state-of-the-art branch-and-cut integer programming solvers like Gurobi, CPLEX, Xpress, etc. They yield better dual bounds, thereby speeding up branch-and-cut tree search, by cutting off portions of the feasible region of the linear-programming relaxation (including the optimal fractional solution) while preserving all integer feasible solutions. Lifted cover inequalities (1) are a specific family of cuts that are used by all the aforementioned solvers.

A cut a⊤x ≤ b is a facet of conv(P) if it defines a dimension-(dim(P) - 1) face of conv(P). Facet-defining cuts are thus the strongest kind of cutting plane and provide the best dual bounds for use within branch-and-cut.

Lifting. We begin with an overview of the lifting function f : [0, b] → R associated with a minimal cover C, defined by f(z) = |C|-1-max{∑j∈C xj : ∑j∈C ajxj ≤ b-z, xj ∈ {0, 1}}. For i /∈ C, the value f(ai) is the maximum possible coefficient αi such that ∑j∈C xj + αixi ≤ |C| - 1 is valid for conv(P). The lifting function has a more convenient closed form due to Balas [1975]. First, relabel the items so C = {1, . . . , t} and a1 ≥ · · · ≥ at. Let µ0 = 0 and for h = 1, . . . , t let µh = a1+· · ·+ah. Let λ = µt-b > 0 be the cover's excess weight. Then, f(z) = 0 if 0 ≤ z ≤ µ1-λ and f(z) = h if µh -λ < z ≤ µh+1 -λ. The lifting function has an intuitive interpretation: f(z) is the maximum h such that an item of weight z cannot be brought into in C and fit in the knapsack, even if we are allowed to discard any h items from C. The lifting function f may be used to maximally lift a single variable not in the cover. To lift a second variable, a new lifting function must be computed. This (order-dependent) process can be continued to lift all remaining variables, and is known as sequential lifting. Conforti et al. [2014] and Hojny et al. [2020] contain further details.

Superadditivity and Sequence-Independent Lifting. A function g : D → R is superadditive if g(u + v) ≥ g(u) + g(v) for all u, v, u + v ∈ D. If g ≤ f is superadditive, ∑j∈C xj + ∑j/∈C g(aj)xj ≤ |C| - 1 is a valid sequence-independent lifting for conv(P). This result is due to Wolsey [1977]; Gu et al. [2000] generalize to mixed 0-1 integer programs. The lifting function f is generally not superadditive. Gu et al. [2000] construct a superadditive function g ≤ f as follows. Let ρh = max{0, ah+1 - (a1 - λ)} be the excess weight of the cover if the heaviest item is replaced with a copy of the (h+1)-st heaviest item. For h ∈ {0, . . . , t-1}, let Fh = (µh -λ+ρh, µh+1 -λ] and for h ∈ {1, . . . , t-1}, let Sh = (µh - λ, µh - λ + ρh]. Sh is nonempty if and only if ρh > 0. For w : [0, ρ1] → [0, 1], Gu et al. define gw(z) =

Gu et al. prove that for w(x) = x/ρ1, gw is superadditive. We call this particular lifting function the Gu-NemhauserSavelsbergh (GNS) lifting function. Furthermore, gw is undominated, that is, there is no superadditive g′ with f ≥ g′ ≥ gw and g′ (z′ ) > gw(z′ ) for some z′ ∈ [0, b].

1.2 Our Contributions

In Section 2, we prove that under a certain condition, gw is superadditive for any linear symmetric function w. This generalizes Gu et al.'s [2000] result for w(x) = x/ρ1 and furthermore corrects an error in their proposed generalization, which incorrectly claims w can be any symmetric function.

Of particular interest is the constant function w = 1/2; we call the resulting lifting piecewise-constant (PC) lifting. In Section 2.1 we give a thorough comparison of PC and GNS lifting. We show that GNS lifting can be arbitrarily worse than PC lifting, and characterize the full domination criteria between the two methods. In Section 2.2, we provide a broad set of conditions under which PC lifting defines facets of conv(P). To our knowledge, these are the first conditions for facet-defining sequence-independent liftings that are efficiently computable from the underlying cover. 1 Furthermore, PC-lifted cuts only have integral and half-integral coefficients making them practically relevant for solvers. In Section 2.2 we give an example that shows PC lifting can be significantly stronger than another half-integral sequence-independent lifting procedure due to Letchford and Souli [2019] that is currently implemented in the FICO Xpress solver [Perregard, 2024].

In Section 3, we experimentally evaluate our lifting techniques in conjunction with a number of novel cover cut generation techniques. Our cut generation techniques do not solve expensive NP-hard separation problems (which has been the norm in prior research [Kaparis and Letchford, 2010]). Instead, we cheaply generate many candidate cover cuts based on qualitative criteria, lift them, and check for separation only before adding the cut. This approach is effective in experiments with CPLEX.

1.3 RelatedWork

Cover cuts and their associated separation routines were first shown to be useful in a branch-and-cut framework by Crowder et al. [1983]. Since then, there has been a large body of work studying various computational aspects, both theoretical and practical, of cover cuts, separation routines, and lifting. The seminal work of Gu et al. [2000] showed how sequence-independent lifting can be performed efficiently using gw for w(x) = x/ρ1. Gu et al. [1998] perform a computational study of sequential lifting, and Wolter [2006] presents some computational results on the interaction between the sequence-independent lifting technique of Gu et al. [2000] and different separation techniques. To our knowledge, this is the only computational study of sequence-independent lifting published to date. Our computational study takes a different approach than prior work. Rather than solving separation problems exactly, which involves expensive optimization, we generate large pools of candidate cover cuts, lift them, and check for separation before adding cuts to the formulation. This approach proves to be effective in our experiments. (The separation problem is NP-hard [Klabjan et al., 1998; Gu et al., 1999], but checking violation is a trivial linear time operation. More on separation can be found in Kaparis and Letchford [2010].) Marchand et al. [2002] and Letchford and Souli [2019; 2020] present other sequence-independent lifting functions based on superadditivity.

1 Balas [1975] proved that lifting coefficients are sometimes fully determined independent of the lifting order, in which case sequential and sequence-independent lifting are the same and yield a facet. When sequence-independent lifting can be non-trivially performed, ours is the first such result.

2 New Sequence-Independent Lifting Functions: Structure and Properties

We generalize the result of Gu et al. [2000] and also point out an error in their suggested generalization. Gu et al. claim that if µ1-λ ≥ ρ1, then gw is superadditive for any nondecreasing w : [0, ρ1] → [0, 1] such that w(x) + w(ρ1 - x) = 1. This claim is incorrect (we provide counterexamples in App. A). We show that this claim is correct when restricted to linear w.

The GNS lifting function is given by g1/ρ1 . The proof of Theorem 1 follows the proof that g1/ρ1 is superadditive [Gu et al., 2000] with a few key modifications; we defer it to App. B. Of particular interest is the superadditive lifting function g0, which we refer to as the piecewise-constant (PC) lifting function. The condition µ1 - λ ≥ ρ1 is necessary for superadditivity of g0 (proven in App. B). The following result shows that the lifting obtained via gk is dominated by the union of the liftings obtained via g0 (PC lifting) and g1/ρ1 (GNS lifting). Thus, in order to get as close to conv(P) as possible, it suffices to study these two lifting functions.

Proof. We have gk(z) = kρ1g1/ρ1 (z) + (1 - kρ1)g0(z) by direct computation, so gk lifting is a convex combination of GNS and PC lifting.

Example 1. Let C = {1, 2, 3, 4} and consider a knapsack constraint of the form 16x1 + 14x2 + 13x3 + 9x4 + ∑j/∈C ajxj ≤ 44. C is a minimal cover with µ1 = 16, µ2 = 30, µ3 = 43, µ4 = 52, λ = 8, ρ1 = 6, ρ2 = 5, ρ3 = 1, and µ1 -λ ≥ ρ1. Fig. 1 depicts g0 and g1/ρ1 truncated to the domain [µ1 - λ, µ3 - λ] = [8, 35].

2.1 Comparisons Between PC and GNS Lifting

The following result shows GNS lifting can be arbitrarily worse than PC lifting.

Proposition 2. For any ε > 0, t ∈ N there exists a knapsack constraint with a minimal cover C of size t such that PC lifting yields ∑j∈C xj + ∑j /∈C 1 2 xj ≤ |C| - 1 and GNS lifting is dominated by ∑j∈C xj + ∑j /∈C εxj ≤ |C| - 1.

The proof is in Appendix C. At a high level, we construct an instance where the length of S1, which is ρ1, is large, and consider coefficients that are at the leftmost part S1. GNS barely lifts such coefficients, while PC yields lifting coefficients of 1/2. The next proposition fully characterizes the domination criteria between PC and GNS lifting. Its proof is immediate from the plots in Fig. 1.

Proposition 3. Assume µ1 -λ ≥ ρ1. Furthermore, suppose {j /∈ C : ∃h s.t. aj ∈ Sh} ̸= ∅ (else, GNS and PC trivially produce the same cut). If, for all j /∈ C,

1. aj ∈ Sh =⇒ ρh > ρ1 2 and aj ≤ µh - λ + ρh - ρ1 2 with at least one such aj ∈ Sh satisfying aj < µh -λ+ ρh - ρ1 2 , PC strictly dominates GNS.
2. aj ∈ Sh =⇒ ρh > ρ1 2 and aj = µh - λ + ρh - ρ1 2 , PC and GNS yield the same cut.
3. aj ∈ Sh =⇒ (ρh ≤ ρ1 2 ) or (ρh > ρ1 2 and aj > µh - λ + ρh - ρ1 2 ), GNS strictly dominates PC.
4. Otherwise, neither PC nor GNS dominates the other.

Example 2. Consider the constraint 16x1 + 14x2 + 13x3 + 9x4 + a5x5 + a6x6 + a7x7 ≤ 44 with minimal cover C = {1, 2, 3, 4}.

1. Let a5 = 9, a6 = 10, a7 = 23. GNS yields x1 + x2 + x3+x4+ 16 x5+ 13 x6+ 43 x7 ≤ 3. PC yields the dominant cut x1 + x2 + x3 + x4 + 1 2 x5 + 1 2 x6 + 32 x7 ≤ 3.
2. Let a5 = 11, a6 = 17, a7 = 24. GNS and PC both yield the cut x1 + x2 + x3 + x4 + 1 2 x5 + x6 + 3 2 x7 ≤ 3.
3. Let a5 = 12, a6 = 13, a7 = 26. GNS yields x1 + x2 + x3 + x4 + 23 x5 + 56 x6 + 11 6 x7 ≤ 3. PC yields the weaker cut x1 + x2 + x3 + x4 + 1 2 x5 + 1 2 x6 + 32 x7 ≤ 3.
4. Let a5 = 9, a6 = 13, a7 = 24. GNS yields x1 + x2 + x3+x4+ 16 x5+ 56 x6+ 32 x7 ≤ 3. PC yields x1+x2+x3+ x4 + 1 2 x5 + 12 x6 + 32 x7 ≤ 3. Neither cut is dominating.

Open question: Gu et al. [1999] and Hunsaker and Tovey [2005] construct knapsack problems where branchand-cut requires a tree of exponential size, even when all lifted cover inequalities (all inequalities of the form (1)) are added to the formulation. Do there exist knapsack problems where branch-and-cut requires exponential-size trees when all GNS-lifted cover inequalities are added, but does not when PC-lifted cover inequalities are added (or vice versa)?

2.2 Facet Defining Inequalities From Sequence-Independent Lifting

We now provide a broad set of sufficient conditions under which PC lifting yields facet-defining inequalities. Our result relies on the following complete characterization of the facets of the knapsack polytope obtained from lifting minimal cover cuts, due to Balas and Zemel [1978; 2020], which we restate using the notation and terminology of Gu et al. [2000] and Conforti et al. [2014, sec. 7.2]. Given a minimal cover C and j /∈ C, let h(j) be the index such that µh(j) ≤ aj < µh(j)+1. Theorem 2 (Balas and Zemel [1978]). Let C be a minimal cover. Let J = {j /∈ C : aj > µh(j)+1 - λ} and let I = ({1, . . . , n} \ C) \ J. Let Q(J) = {Q ⊆ J : ∑j∈Q aj ≤ b, Q ̸= ∅}. The inequality ∑j∈C xj + ∑j /∈C αjxj ≤ |C|-1 is a facet of conv(P) if and only if αj = h(j)+δj · 1(j ∈ J) where each δj ∈ [0, 1] and δ = (δj)j∈J is a vertex of the polyhedron T =

The characterization of facets based on T in Theorem 2 does not translate to a tractable method of deriving facetdefining inequalities, since one would need to enumerate the vertices of T . In fact, Hartvigsen and Zemel [1992] show the question of determining whether or not a cutting plane is a valid lifted cover cut is co-NP-complete. Deciding whether or not a cutting plane is a facet-defining lifted cover cut is in D P (D P is a complexity class introduced by Papadimitriou and Yannakakis [1982] to characterize the complexity of facet recognition). Critically, these complexity results hold when the underlying cover is given as input.

Our result, to the best of our knowledge, provides the first broad set of sufficient conditions under which sequenceindependent liftings that can be efficiently computed from the underlying minimal cover-via PC lifting-are facet defining. We now state and prove our result.

Theorem 3. Let C = {1, . . . , t}, a1 ≥ · · · ≥ at, be a minimal cover such that µ1 - λ ≥ ρ1 > 0. Suppose |{j /∈ C : aj ∈ S1}| ≥ 3 and for all j /∈ C:

Then, the cut∑

obtained via PC lifting, defines a facet of conv(P).

Proof. First we show that J = ∪h≥1{j /∈ C : aj ∈ Sh} and I = ∪h≥0{j /∈ C : aj ∈ Fh}. Let j /∈ C be such that aj ∈ Sh. We have aj > µh - λ > µh-1 (as λ ≤ ai for any i ∈ C) and aj ≤ µh -λ+ρh - ρ1 2 < µh-λ+ρh < µh (the final inequality follows directly from expanding out µh and ρh). So h(j) = h - 1, and as aj > µh - λ = µh(j)+1 - λ, j ∈ J. Next, let j /∈ C be such that aj ∈ Fh. Then, aj ≤ µh+1 -λ < µh+1, and by assumption aj ≥ µh, so h(j) = h. Therefore aj ≤ µh(j)+1 - λ, and so j ∈ I. The facts that aj ∈ Sh =⇒ h(j) = h - 1 and aj ∈ Fh =⇒ h(j) = h will be used repeatedly in the remainder of the proof.

We now determine the constraints defining the polyhedron T ⊂ R|J| in Theorem 2. (For j ∈ I, PC lifting produces a coefficient of h(j), as required by Theorem 2.) Partition J into two sets J = J1 ∪ J>1 where J1 = {j /∈ C : aj ∈

S1} and J>1 = ∪h>1{j /∈ C : aj ∈ Sh}. Each singleton Q = {j} ∈ Q(J) yields the constraint δj ≤ 1. Consider now Q = {j1, j2} ∈ Q(J). We consider two cases, one where j1 ∈ J1 and the other where j1 ∈ J>1. First, let j1 ∈ J1. Let h be such that aj2 ∈ Sh. We have aj1 +aj2 > aj2 > µh -λ, so f(aj1 + aj2 ) ≥ h, and aj1 + aj2 ≤ µ1 - λ + ρ1 2 +µh - λ + ρh - ρ1 2 = a1 - λ + µh - λ + (ah+1 - a1 + λ) = µh + ah+1 - λ = µh+1 - λ, so f (aj1 + aj2 ) ≤ h. Therefore f(aj1 + aj2 ) = h, and we get the constraint δj1 + δj2 ≤ f(aj1 + aj2 ) - h(j1) - h(j2) = h - 0 - (h - 1) = 1. Suppose now that j1, j2 ∈ J>1 (if j2 ∈ J1 that is handled by the first case). Let h1, h2 be the integers such that aj1 ∈ Sh1 and aj2 ∈ Sh2 . We have aj1 + aj2 > µh1 - λ + µh2 - λ = (a1+· · ·+ah1 )+(a1+· · ·+ah2 )-2λ > (a1+· · ·+ah1-1)+ (a1 + · · · + ah2 ) - λ > µh1+h2-1 - λ so f(aj1 + aj2 ) ≥ h1 + h2 - 1, and f(aj1 + aj2 ) - h(j1) - h(j2) ≥ 1. So for such pairs, we obtain a constraint δj1 + δj2 ≤ H(j1, j2), where H(j1, j2) ≥ 1. Finally, we consider Q ∈ Q(J) with |Q| ≥ 3. For j ∈ Q let hj be the integer such that aj ∈ Shj . We claim that∑

This claim is succinctly proven using the quantities used to prove Theorem 1 (defined by Gu et al. [2000] to prove superadditivity of g1/ρ1 ). To avoid notational clutter, we defer its proof to App. D. The claim implies f(∑j∈Q aj) ≥ ∑j∈Q hj - ⌊|Q|/2⌋, so the constraint induced by Q is of the form ∑j∈Q δj ≤ H(Q), where

We can now write down a complete description of T as

where H(i, j) ≥ 1 for all (i, j) ∈ J>1 × J>1 and H(Q) ≥ ⌈|Q|/2⌉ for all Q ∈ Q(J), |Q| ≥ 3. We argue that δ = (1/2, . . . , 1/2) is a vertex of T. Constraints of type (1), (3), and (4) are satisfied, and type (2) constraints are tight. Fix distinct j1, j2, j3 ∈ J1. The set of |J| type (2) constraints {δj + δj1 ≤ 1 ∀ j ∈ J \ {j1}} ∪ {δj2 + δj3 ≤ 1} is linearly independent, and hence δ = (1/2, . . . , 1/2) is a vertex of T . PC lifting produces precisely the coefficients prescribed by Theorem 2: g0(aj) = h(j) for j ∈ I and g0(aj) = h(j) + 12 for j ∈ J, so we are done.

Fig. 1 illustrates the sufficient conditions of Theorem 3. While a facet-defining PC lifting can be efficiently obtained given a minimal cover satisfying the sufficient conditions of Theorem 3, we do not show how to find a minimal cover satisfying these conditions. We conjecture that finding such a cover is NP-hard.

Example 3. Consider the constraint 16x1 + 14x2 + 13x3 + 9x4 + 9x5 + 10x6 + 11x7 + 23x8 ≤ 44 with minimal cover C = {1, 2, 3, 4}. GNS lifting yields the cut x1 + x2 + x3 + x4 + 1 6 x5 + 1 3 x6 + 12 x7 + 43 x8 ≤ 3 and PC lifting yields the strictly dominant facet-defining cut x1 + x2 + x3 + x4 + 12 (x5 + x6 + x7) + 3 2 x8 ≤ 3.

Other Half-Integral Liftings. There exist facet-defining lifted cover inequalities with half-integral coefficients that cannot be obtained via PC lifting. Balas and Zemel [1978] provide an example of a knapsack constraint and minimal cover for which δ = (1/2, . . . , 1/2) is a vertex of T, but µ1 - λ ≥ ρ1 does not hold. It is an interesting open question to investigate when such facets arise and how to (efficiently) find them. The lifting procedure of Letchford and Souli [2019] also produces half-integral coefficients, but it is unclear when it can yield facets (it produces cuts that in general are incomparable with ours as their lifting function is also undominated). In Example 3, Letchford and Souli's lifting technique (which is implemented in version 9.5 of the FICO Xpress solver [Perregard, 2024]) yields the cut x1 + x2 + x3 + x4 + x8 ≤ 3, a significantly weaker cut than the facet-defining PC cut. The numerical properties of halfintegral cuts make them desirable for implementation within a solver, and the computational overhead of PC lifting (sorting the cover elements) is the same as Letchford and Souli's lifting.

It would be interesting to derive similar conditions under which GNS lifting defines facets. The following sufficient conditions are immediate, but it is likely that a stronger result could be derived. We leave this as an open question.

Proposition 4. If for all j /∈ C, aj ∈ Sh =⇒ aj = µh - λ + ρh, GNS lifting strictly dominates PC lifting and defines a facet of conv(P).

Proof. The condition implies g1/ρ1 coincides with the lifting function f on all aj , j /∈ C, which (e.g., Prop. 7.2 in Conforti et al. [2014]) means GNS lifting is facet defining.

3 Experimental Evaluation

We evaluate our new sequence-independent lifting techniques in conjunction with a number of methods for generating the minimal cover cuts that are to be lifted. We describe each component of the experimental setup below.

Cover Cut Generation. Let ∑nj=1 ajxj ≤ b be a knapsack constraint, let xLP be the LP optimal solution at a given node of the branch-and-cut tree, and let I = {i : xLP i > 0}. Enumerate I as I = {1, . . . , s} (relabeling variables if necessary). We do not include variables not in I in any of the minimal covers, since these do not contribute to the violation of xLP (though such variables may be assigned a nonzero coefficient in the lifted cover cut). Next, we present the five cover cut generation techniques that we use in experiments. Contiguous covers. First, sort the variables in I in descending order of weight; without loss of generality relabel them so that a1 ≥ a2 ≥ · · · ≥ as. For each i ∈ {1, . . . , s}, let j ∈ {i + 1, . . . , s} be such that C = {i, i + 1, . . . , j} is a minimal cover (if such a j exists). This is the contiguous cover starting at i. We generate all such contiguous cover cuts for each i. (Balcan et al. [2022a] introduced these cover cuts, though they did not lift them nor did they restrict to xLP i > 0.) Spread covers. As before, sort the variables in I in descending order of weight; a1 ≥ · · · ≥ as. For each i, let j ∈ {i + 1, . . . , s} be maximal (if such a j exists) such that there exists k ∈ {j+1, . . . , s} such that C = {i}∪{j, . . . , k} is a minimal cover. Intuitively, i can be thought of as a heavy "head", and the "tail" from j to k is as light as possible. We coin this the spread cover with head i. We generate all such spread cover cuts for each i.

Heaviest contiguous cover. We define this as the contiguous cover starting at 1.

Default cover. Sort (and relabel) the variables in I in descending order of LP value so that xLP 1 ≥ · · · ≥ xLP s . Let j be minimal so that {1, . . . , j} is a cover. Then, evict items, lightest first, until the cover is minimal. We coin this the default cover. These cover cuts are loosely based on the "default" separation routine implemented by Gu et al. [1998]. (Their routine was for sequential lifting and does not directly carry

over to our setting.) Wolter [2006] tested similar routines. Bang-for-buck cover. Sort (and relabel) the variables in I in descending order of "bang-for-buck" so that c1 a1 ≥ · · · cs as , where ci is variable i's objective coefficient. Let j be minimal so that {1, . . . , j} is a cover. Then, evict items, lightest first, until the cover is minimal. We coin this the bang-for-buck cover.

Example 4. Consider the knapsack constraint 10x1 +9x2 + 8x3 + 7x4 + 6x5 + 6x6 + 5x7 + 4x8 ≤ 26, suppose the LP optimal solution at the current branch-and-cut node is xLP = (0.1, 0.8, 0.7, 0.4, 0, 1, 0.2, 0.8), and suppose c = (5, 7, 9, 1, 2, 6, 6, 5). We have I = {1, 2, 3, 4, 6, 7, 8}. The contiguous minimal covers are {1, 2, 3}, {2, 3, 4, 6}, {3, 4, 6, 7, 8}. The spread minimal covers are {1, 4, 6, 7}, {2, 4, 6, 7}, {3, 4, 6, 7, 8}. The heaviest contiguous cover is {1, 2, 3}. The default cover is {2, 3, 6, 8}. The bang-for-buck cover is {2, 3, 6, 7}.

Lifting. We evaluate three lifting methods. (1) GNS: The cover cut is lifted using g1/ρ1 . (2) PC: If µ1 - λ ≥ ρ1 the cover cut is lifted using g0, and otherwise it is lifted using g1/ρ1 . (3) Smart: If µ1 -λ ≥ ρ1, two liftings are generated: one with g0 and one with g1/ρ1 . If either lifting dominates Algorithm 1 Lifted cover cut generation at a node of branchand-cut

Input: IP data c,A, b, LP optimumat current node xLP , pernode cut limit ℓ 1: Initialize cuts = ∅. 2: for each knapsack constraint a⊤x ≤ b do 3: for each cut ∈ CoverCuts(a, b, c, xLP ) do 4: for each liftedcut ∈ Lift(cut) do 5: if liftedcut separates xLP then 6: cuts ← cuts ∪ {liftedcut}. 7: Add the top min{ℓ, |cuts|} cuts in cuts with respect to efficacy.

the other, the weaker lifting is discarded. If µ1 -λ < ρ1, the cover cut is only lifted using g1/ρ1 .

Integration with Branch-and-Cut. Alg. 1 is the pseudocode for adding lifted cover cuts at a node of the branchand-cut tree and is called once at every node of the tree. It uses the prescribed lifting method Lift atop the prescribed cover cut generation method CoverCuts for each constraint, and adds the resulting lifted cut to a set of candidate cuts if it separates the current LP optimum xLP . It adds the ℓ deepest cuts among the candidate cuts to the formulation. (The depth or efficacy of a cut α⊤x ≤ β is the quantity α⊤xLP-β ∥α2∥ and measures the distance between the cut and xLP .) The ℓ cuts are added in a single round at the current node, and no further cuts are generated at that node. Alg. 1 does not solve NP-hard separation problems and instead relies on fast ways of generating candidate cuts through CoverCuts, and only adds those that separate xLP .

Experimental Results. We evaluated our techniques on five problem distributions: two distributions over winnerdetermination problems in multi-unit combinatorial auctions (decay-decay [Sandholm et al., 2002] and multipaths from CATS version 1.0 [Leyton-Brown et al., 2000]) and three distributions over multiple knapsack problems (uncorrelated and weakly correlated benchmark distributions from Fukunaga [2011] and Chv´atal from Balcan et al. [2022a]). We ran experiments in C++ using the callable library of CPLEX version 20.1 on a 64-core machine, and implemented Alg. 1 with ℓ = 10 within a cut callback. We generated 100 integer programs from each distribution. We set a 1 hour time limit, allocated 16GB of RAM, and used one thread for each integer program.

We present illustrative results in Fig. 2, focusing on settings where PC lifting had significant impact. The full set of experiments are in App. E. We focus on tree size as the performance measure, but we provide full run-time results in App. E. Each curve is labeled setting/lifting/covers or setting/CPLEX. The setting label is either empty, np, or d. Empty corresponds to all cuts, all heuristics, and presolve off. A setting of np denotes presolve off and all other settings untouched. A setting of d denotes the default settings (this setting is incompatible with our lifting implementations since presolve is incompatible with cut callbacks). If an underscore follows the label, CPLEX's internal cover cut generation is turned off; otherwise it is on. To ensure fair comparisons, in all CPLEX runs not involving our new techniques (those labeled setting/CPLEX), we register a dummy cut callback that does nothing. This disables proprietary techniques such as "dynamic search" which do not support callbacks and thus do not support experiments of the type required in this paper.

We now describe the performance plots (Fig. 2), which display how many instances each method was able to solve using trees smaller than the prescribed size on the x-axis within the 1 hour time limit. Weakly correlated, contiguous covers (top left): GNS solves 81 instances, Smart solves 83 instances, and PC solves 88 instances. These all outperform default CPLEX which solves 80 instances and builds trees an order of magnitude larger. Uncorrelated, contiguous covers (top right): GNS solves 43 instances, Smart solves 48 instances, and PC solves 55 instances, while default CPLEX solves 78 instances. Chv´atal, heaviest covers (middle left): PC lifting dramatically outperforms the other methods. Here, all CPLEX parameters are turned off, so we are directly comparing our lifted cover cut implementations with CPLEX's own cover cut generation routines. PC and Smart strictly outperform GNS and CPLEX (GNS is the only one unable to solve all 100 problems), and the largest tree size required by PC is an order of magnitude smaller than any of the other methods. This translates into a run-time improvement as well due to PC lifting (Fig. 6 in the appendix). On the auction instances, there is little discernible performance difference between the lifting methods. Decay-decay, spread covers (middle right): our lifting implementations with all other CPLEX parameters off dramatically outperform default CPLEX on problems requiring trees of size > 104 (though default CPLEX solves all 100 problems while our methods do not.) Multipaths, spread covers (bottom left): we once again directly compare our lifted cover cut implementations with CPLEX's internal cover cut generation. Here, spread covers yield over an order of magnitude reduction in tree size relative to CPLEX, while default covers perform extremely poorly. We observed that contiguous and spread covers generally resulted in the best performance (with heaviest contiguous covers on par), and default and bang-for-buck covers performed much worse.

While our techniques often led to significantly smaller trees than CPLEX, this did not translate to significant runtime improvements. However, in most settings our techniques were not too much slower than CPLEX and sometimes they were faster. Full run-time performance plots are in App. E. A possibility for this is that we did not limit the total number of cuts added throughout the tree, causing the formulation to grow very large. We ran an experiment to investigate the runtime impact of varying the number of cuts allowed (i) at each node (ℓ in Alg. 1) and (ii) throughout the entire search tree. We plot the average run-time (time limit of 1 hour) over the first 10 weakly-correlated instances using pc/contiguous, visualized as a heatmap (Fig. 2; bottom right). The best settings (limiting the overall number of cuts to 800) yield an average run-time of around 300 seconds and solved all 10 instances. Default CPLEX (d/CPLEX) averaged roughly 900 seconds and only solved 9 instances to optimality.

4 Conclusions and Future Research

In this paper we showed that PC lifting can be a useful alternative to GNS lifting. We proved that under some sufficient conditions, PC lifting is facet-defining. To our knowledge, these are the first broad conditions for facet-defining sequence-independent liftings that can be efficiently computed from the underlying cover. We invented new cover cut generation routines, which in conjunction with our new lifting techniques, displayed promising practical performance.

There are a number of important future research directions that stem from our findings. First, a much more extensive experimental evaluation of PC lifting is needed. We have made several simplifying design choices, including (i) adding only one wave of lifted cover cuts at each node; (ii) ranking cuts solely based on efficacy (efficacy is not always the best quality to prioritize [Balcan et al., 2022a; Balcan et al., 2022b; Turner et al., 2023]); (iii) keeping ℓ constant across nodes while it could be a tuned hyperparameter, or even adjusted dynamically during search. Our experiments show promise even with these fixed choices, but a more thorough suite of tests could find how to best exploit the potential of our new techniques. Another direction here is to use machine learning (which has already been used to tune cutting plane selection policies [Balcan et al., 2021; Li et al., 2023]) to decide when to use PC or GNS lifting. There might also be additional ways of determining what lifting method to use based on problem structure, and detecting that automatically. Finally, PC lifting possesses strong numerical properties since it always involves half-integral coefficients. That, along with its ability to yield facets, makes PC lifting practically relevant for solvers.

Acknowledgments

This material is based on work supported by the Vannevar Bush Faculty Fellowship ONR N00014-23-1-2876, NSF grants RI-2312342 and RI-1901403, ARO award W911NF2210266, NIH award A240108S001 and Defense Advanced Research Projects Agency under cooperative agreement HR00112020003.