PaperlayerView exact revision on arXiv

Source-linked AI summary

Approximating the Chv\'atal--Gomory Closure of Capacity-Bounded Min-Closed Systems

Stefano Huber, Monaldo Mastrolilli

arXiv:2609.35915v1cs.DS

TL;DR

For binary programs with 0/1 constraint matrices, optimizing a linear objective over the rank-1 CG closure using multipliers {0, 1/2} is NP-hard [9]. A constant-degree SoS relaxation is used to approximate optimization over the first CG closure generated by multipliers in Λf. The algorithm outputs a rational point in P^(1)_Λf with objective value at least OPT(I)/(1 + ε).

  • Problem

    For binary programs with 0/1 constraint matrices, optimizing a linear objective over the rank-1 CG closure using multipliers {0, 1/2} is NP-hard [9].

    Source: §1 · p. 2

  • Method

    A constant-degree SoS relaxation is used to approximate optimization over the first CG closure generated by multipliers in Λf.

    Source: §2.2 · pp. 6–7

  • Results

    The algorithm outputs a rational point in P^(1)_Λf with objective value at least OPT(I)/(1 + ε).

    Source: §2.2 · p. 6

  • Takeaways & Limitations

    The paper establishes approximation for the first Λf-CG closure, while unitary implications and unconditional assertions are outside the algorithm's handled class.

    Source: §2.1 · p. 4, §5 · p. 13

    The algorithm does not handle unitary implications or unconditional assertions.

    Source: §2.1 · p. 4

Abstract

from arXiv · show

Optimizing over the {0, 1/2} rank-1 Chv\`atal-Gomory (CG) closure of a binary integer linear program is NP-hard. While polynomial-time approximation schemes (PTAS) are established for monotone packing and covering formulations, extending these guarantees to mixed-sign variants remains an open challenge. In this paper, we study the approximability of the CG closure for k-slack bounded (capacity-bounded) min-closed systems, a generalized packing formulation with mixed-sign constraints that extends weighted Boolean Horn logic. In these systems, a constant upper bound $k \ge 1$ bounds the ratio between the negative penalty coefficient $q$ and the right-hand side capacity $b$ of every constraint, enforcing $q \le k \cdot b$. We prove that a constant-degree sum-of-squares relaxation yields a PTAS for maximizing linear objectives over the first CG closure generated by multipliers in $\{0\}\cup[\tfrac1f,1]$, for any constant integer $f \ge 2$. This closure is contained in the {0, 1/2} rank-1 CG closure.Optimizing over the {0, 1/2} rank-1 CG closure of a binary integer linear program is NP-hard. While PTASes are established for monotone packing and covering formulations, extending these guarantees to mixed-sign variants remains an open challenge. In this paper, we study the approximability of the CG closure for \emph{$k$-slack bounded (capacity-bounded) min-closed systems}, a generalized packing formulation with mixed-sign constraints that extends weighted Boolean Horn logic. In these systems, a constant upper bound $k \ge 1$ bounds the ratio between the negative penalty coefficient $q$ and the right-hand side capacity $b$ of every constraint, enforcing $q \le k \cdot b$. We prove that a constant-degree sum-of-squares relaxation yields a PTAS for maximizing linear objectives over the first CG closure generated by multipliers in $\{0\}\cup[\tfrac1f,1]$, for any constant integer $f \ge 2$.

1 Introduction

The introduction frames CG cuts as a way to strengthen binary ILP relaxations, but optimization over the {0, 1/2} rank-1 closure is NP-hard. Existing approximation guarantees cover monotone packing and covering, leaving mixed-sign systems as an open challenge.

1 Introduction

  • A rank-1 CG cut combines valid inequalities so the aggregate left-hand side is integral, then rounds down the right-hand side.The first CG closure intersects the continuous relaxation with all rank-1 CG cuts; repeated application defines higher closures.Source: §1 · pp. 1–2
  • Many effective low-rank inequalities, including odd-cycle and blossom inequalities, can be derived using multipliers in {0, 1/2}.CG cuts can capture strong linear relaxations that bounded-degree SoS may not, though this expressive power comes at substantial computational cost.Source: §1 · p. 2
  • For monotone covering and packing formulations, prior work established PTAS guarantees for optimizing over any constant-rank CG closure.The covering result uses inclusion-minimal infeasible subsets, while the packing result uses constant-degree SoS; both rely on monotone structure.Source: §1 · p. 3
  • Mixed-sign integer programs lack a general approximation framework in the stated setting because their constraints lose the monotonicity used by packing and covering techniques.The introduction identifies characterizing mixed-sign classes that still admit polynomial-time guarantees as an open problem.Source: §1 · p. 3

2 Problem Setting and Overview of Results

The paper studies Chvátal–Gomory approximation for mixed-sign min-closed systems, focusing on a capacity-bounded subclass. For that subclass, a constant-degree sum-of-squares relaxation gives a PTAS for the first Λf-CG closure.

2.1 Min-Closed Systems and Valid Inequalities

  • Generalized Horn constraints are min-closed: the coordinate-wise minimum of any two satisfying assignments also satisfies the constraint.They act as soft packing constraints, with the negative variable serving as a slack term when positive variables exceed capacity.Source: §2.1 · pp. 4–5
  • Expanding a min-closed system into Horn clauses may require exponentially many clauses, so the algorithm works directly with generalized Horn constraints.Source: §2.1 · p. 5
  • The open question asks whether arbitrary min-closed linear constraints admit a PTAS over the first CG closure; this paper treats a structured subclass and restricts nonzero multipliers to [1/f, 1].Source: §2.1 · p. 5

2.2 Our Results

  • The k-slack condition bounds each constraint's negative penalty coefficient by its capacity: q ≤ k · b for a universal constant k.Source: §2.2 · p. 5
  • A constant-degree SoS relaxation gives a (1 + ε)-approximation for the first Λf-CG closure of k-slack bounded generalized Horn systems, for fixed k and integer f ≥ 2.The theorem assumes a nonnegative linear objective and applies for every fixed ε > 0.Source: §2.2 · p. 6
  • Under these assumptions, a polynomial-time algorithm returns a rational point feasible for the closure and a rational upper bound on the integer optimum.The point's objective value is at least OPT(I)/(1 + ε); the upper bound need not equal the point's objective value.Source: §2.2 · p. 6

2.3 Paper Organization

  • The proof roadmap combines exact SoS certification for bounded-capacity cuts with a structural bound on negative weights and uniform geometric scaling.Source: §2.3 · p. 7

3 The Violation Threshold and SoS Exactness

The violation threshold τ organizes the proof’s cut-by-cut analysis: bounded thresholds admit exact SoS certificates for CG rounding, while large thresholds allow scaling to absorb rounding error.

3 The Violation Threshold and SoS Exactness

  • The violation threshold τ is the largest number of positive variables that can be set to 1 before the cut is violated.The proof uses bounded thresholds for exact rounding certificates and handles large thresholds by scaling.Source: §3 · pp. 7–8
  • When τ = O(1), minimal violating subsets have constant size, enabling a constant-level SoS certificate for the CG rounding step.The cited packing result [10], derived from the Decomposition Theorem [7], also supplies constant-level certificates for bounded-threshold packing inequalities.Source: §3 · p. 8
  • A cut with violation threshold at most τ admits a (τ + |K| + 1)-SoS certificate for its Chvátal–Gomory rounding.The result applies when τ + |K| ≥ 1.Source: §3 · p. 8

4 Proof of Theorem 9

Theorem 9 is proved by analyzing non-dominated CG cuts and showing that a geometrically scaled constant-level SoS solution satisfies them. The proof bounds negative weight, treats low- and high-capacity cuts separately, and derives a (1 + ε)-approximation guarantee.

4 Proof of Theorem 9

  • The proof assumes k-slack-bounded structural constraints and handles lower bounds separately from upper box bounds.The objective is a nonnegative linear maximization objective, and the analysis establishes the approximation by combining structural cut analysis with geometric scaling.Source: §4 · pp. 8–9

4.1 Structural Analysis of CG Cuts

  • Non-minimal integer multipliers on non-negativity bounds produce dominated cuts, so the analysis can restrict to tight cuts; their total negative weight is at most (k + f)β + (k + f) − 1.The negative-weight bound is linear in the rounded capacity β.Source: §4.1 · pp. 9–10

4.2 Satisfiability Under Geometric Scaling

  • For low-capacity cuts, the violation threshold and negative support are bounded, giving a D-SoS certificate that satisfies the cut.Lemma 19 applies when the fractional capacity ˜b ≤ d.Source: §4.2 · pp. 10–11
  • For high-capacity cuts, scaling a point satisfying the fractional inequality by 1 − 1/d satisfies the rounded cut when ˜b > d.The geometric scaling handles these cuts irrespective of their violation threshold.Source: §4.2 · pp. 10–11

4.3 Approximation Guarantee

  • For maximization problems with generalized Horn constraints satisfying Assumption 8 for constant k, the scaled D-SoS solution lies in the first Λf-CG closure and yields a (1 + ε)-approximation ratio.Source: §4 · p. 8, §4.3 · p. 12

5 Discussion and Future Work

The paper proves a PTAS for the rank-1 Λ_f-CG closure, but its algorithm covers only generalized Horn systems satisfying Assumption 8. Zero-capacity formulations and broader algorithmic and complexity questions remain unresolved.

5 Discussion and Future Work

  • The SoS hierarchy approximates the rank-1 Λ_f-CG closure to any fixed precision ε for every constant f ≥ 2.The discussion identifies this as the paper’s main result.Source: §5 · p. 13
  • The algorithm handles only generalized Horn constraints satisfying Assumption 8, leaving other min-closed systems outside its stated scope.Composite clauses satisfy the assumption, whereas zero-capacity unitary implications do not in that formulation.Source: §5 · p. 13
  • Whether zero-capacity min-closed systems admit a PTAS for their first CG closure, with or without SoS, remains open.The question specifically concerns formulations containing zero-capacity implications x_i − y ≤ 0.Source: §5 · p. 13
  • It remains open whether non-SoS methods can match the guarantees or complexity lower bounds prevent extending them to larger subclasses.Source: §5 · p. 13

A Background: Sum of Squares Over the Boolean Hypercube

The appendix sets out Boolean-domain SoS derivations and their relation to semidefinite relaxations. It also explains the Boolean ideal, degree conventions, and how multilinear indicators yield exact certificates for nonnegative Boolean functions.

A Background: Sum of Squares Over the Boolean Hypercube

  • The Boolean ideal I2 is generated by x_i^2 − x_i, and congruence modulo I2 identifies polynomials differing by an element of that ideal.Reducing modulo I2 gives every polynomial a unique multilinear representative.Source: A Background: Sum of Squares Over the… · p. 14
  • A degree-d SoS derivation represents a target inequality using sums of squares times system constraints, arbitrary ideal multipliers, and terms of degree at most d.A refutation is a derivation of the constant −1.Source: A Background: Sum of Squares Over the… · p. 14
  • A t-SoS certificate bounds the degrees of squared polynomials by t; in the optimization convention, the t-SoS moment matrix is indexed by multilinear monomials of degree at most t.The paper notes that proof complexity instead indexes derivation degree by the total degree of the identity.Source: A Background: Sum of Squares Over the… · pp. 14–15
  • Every nonnegative Boolean function has an exact SoS representation, and the standard variable bounds have degree-2 certificates.Point indicators are idempotent modulo the Boolean ideal.Source: A Background: Sum of Squares Over the… · p. 14
  • The t-SoS relaxation optimizes over pseudo-expectations, and every solution satisfies inequalities that admit a t-SoS certificate from the system.The relaxation uses normalized linear functionals that are nonnegative on specified squares and constraint-weighted squares.Source: A Background: Sum of Squares Over the… · p. 15

B The Exponential Expressivity Gap

A single weighted generalized Horn constraint can encode a threshold condition on prerequisites. Representing the same feasible region using ordinary Horn clauses can require exponentially many clauses, even when the weighted constraint satisfies Assumption 8 for a threshold near half the variables.

B The Exponential Expressivity Gap

  • A single weighted generalized Horn constraint represents the condition that if any θ of n prerequisites are true, then target y must be true.The example uses one target variable and n prerequisite variables.Source: B The Exponential Expressivity Gap · p. 15
  • Without auxiliary variables, ordinary Horn CNF must forbid every possible subset of θ prerequisites when y = 0, requiring all minimal clauses of premise width θ.Source: B The Exponential Expressivity Gap · p. 15
  • For θ = ⌊n/2⌋, the weighted constraint satisfies Assumption 8 for a small constant of approximately 2, illustrating why dense weights must be handled natively.Source: B The Exponential Expressivity Gap · p. 15

C Proof of Lemma 12

The proof converts a CG cut into a single-row packing inequality and bounds its violation threshold. A packing SoS certificate is then transferred back through an affine substitution, giving the claimed certificate degree.

C Proof of Lemma 12

  • The proof forms a single-row packing instance P′ with integer weights w and capacity C, for which ⌊C⌋ − w⊤z ≥ 0 is valid.The construction identifies the cut expression through C − w⊤z.Source: C Proof of Lemma 12 · pp. 15–16
  • The violation threshold of w⊤z ≤ C is at most τ + |K|, because any larger prefix of the smallest weights includes more than τ entries from block a.The threshold is unchanged when C is replaced by ⌊C⌋ because the weights are integral.Source: C Proof of Lemma 12 · p. 16
  • Applying Lemma 13 yields sums of squares of degree at most π + 1, with π := τ + |K|, for the packing instance.Source: C Proof of Lemma 12 · p. 16
  • Substituting z = (x_S, 1 − y_K) preserves degrees and sums of squares, producing a (τ + |K| + 1)-SoS certificate for the CG rounding.The affine substitution also keeps the ideal terms in the Boolean ideal.Source: C Proof of Lemma 12 · p. 16

D Proof of Theorem 15

The proof compares generic rank-1 Λf-cuts with tight cuts, which use minimal fractional absorbers. Their right-hand sides agree, and every point satisfying a tight cut also satisfies its corresponding generic cut.

D Proof of Theorem 15

  • The tight cut uses the minimal fractional absorber µtight_i, setting each integer offset d_i to zero.A valid multiplier decomposes into a fractional absorber in [0, 1) and a nonnegative integer offset.Source: D Proof of Theorem 15 · p. 17
  • Every point satisfying Ctight satisfies Cgeneric.The two cuts have the same right-hand side, while the generic cut's left-hand side subtracts a nonnegative term from the tight cut's left-hand side.Source: D Proof of Theorem 15 · p. 17
  • Generic rank-1 Λf-cuts incorporate the nonnegativity bounds −x_i ≤ 0 with integer weights beyond the minimal fractional absorber.Those bounds contribute nothing to the cuts' right-hand sides.Source: D Proof of Theorem 15 · p. 17

E Proof of Theorem 16

The proof bounds the magnitude of negative coefficients in non-dominated rank-1 Λf-cuts. With fixed k, that magnitude is O(β), where β is the rounded capacity.

E Proof of Theorem 16

  • Nonnegative packing coefficients and structural multipliers provide a lower bound on each pre-absorption coefficient.The proof also uses the floor-rounded capacity β.Source: E Proof of Theorem 16 · p. 17
  • For a non-dominated cut, the non-negativity multipliers are minimal; their fractional parts lie in [0, 1) for every i in [n].Source: E Proof of Theorem 16 · p. 18
  • O(β) bounds the magnitude of any negative coefficient in a non-dominated rank-1 Λf-cut when k is fixed.The proof uses the rounded capacity β and the constraint that each negative coefficient is bounded by k times its right-hand-side capacity.Source: E Proof of Theorem 16 · p. 18

F Proof of Theorem 17

The proof bounds the total negative weight ∆cut in a non-dominated cut by a function of the rounded capacity β, k, and f. Only active constraints with nonzero negative coefficients affect this quantity.

F Proof of Theorem 17

  • Only active constraints with nonzero negative coefficients affect ∆cut; if there are none, ∆cut is zero.The active set consists of constraints with λℓ > 0 and cℓ ≥ 1.Source: F Proof of Theorem 17 · p. 18
  • The bound uses minimal non-negativity multipliers for non-dominated cuts and the assumption cℓ ≤ kbℓ.For active constraints, λℓ ≥ 1/f; the proof also uses bℓ ≥ 1.Source: F Proof of Theorem 17 · pp. 18–19
  • ∆cut ≤ β(k + f) + k + f − 1.The proof first obtains the strict bound ∆cut < k(β + 1) + f(β + 1), then uses that ∆cut is an integer.Source: F Proof of Theorem 17 · p. 19
Loading 2609.35915v1…