Aggregation-based cutting-planes for packing and covering integer programs

Merve Bodur, Alberto Del Pia, Santanu S. Dey, Marco Molinaro, Sebastian Pokutta

Abstract

In integer programming (IP), cutting-planes derived from aggregated constraints are a powerful tool for strengthening linear programming relaxations. This paper examines the necessity of such aggregation for specific problem classes. The authors demonstrate that for packing and covering IPs, simply generating cuts from individual constraints—ignoring any combinations—achieves a 2-approximation of the best possible aggregation-based cuts. However, for general IPs, aggregation remains essential, as 1-row closures can be arbitrarily weak compared to full aggregation closures.

Introduction: The Role of Aggregation

Cutting-planes are fundamental to modern IP solvers, allowing them to prune search trees by "cutting off" non-integer solutions. Many powerful cuts are found by linearly combining (aggregating) the original constraints of a problem to find a new, implied inequality. This paper asks a critical question: How much does this aggregation actually help? For common problem types like packing and covering, is the computational overhead of combining constraints justified, or can we obtain most of the benefit by considering constraints individually?

Methods and Theoretical Framework

The strength of cutting-planes is formalized through the concept of a closure—the set of points satisfying a specific family of cuts. The authors compare:

  1. Aggregation Closures: Derived by combining any number of constraints before generating cuts.
  2. 1-row Closures: Derived by generating cuts from each original constraint individually.

To establish their results, the authors introduce a theoretical "pre-processed LP" for packing problems and utilize Knapsack-Cover (KC) inequalities for covering problems. Rigorous mathematical proofs are used to determine approximation bounds, which are then tested against general IP instances.

Key Insights

  • The "Power of One": For packing and covering problems, the 1-row closure is a 2-approximation of the full aggregation closure. This implies that at most half the "strength" of the cuts is lost when aggregation is omitted.
  • Problem-Specific Utility: The 2-approximation rule is specific to packing and covering. In general IPs with mixed-sign constraints, 1-row approaches can be "arbitrarily bad," making aggregation mandatory for solver viability.
  • Integrality Gap and Rank: A fundamental link exists between a problem's integrality gap and its rank (the number of aggregation rounds needed). Large gaps necessitate many rounds of cuts, regardless of aggregation level.

Key Results

The paper's primary theoretical contribution is the proof that for any packing or covering polyhedron, the 1-row version of Chvátal-Gomory (CG) or aggregation cuts is a 2-approximation of the full version. This bound is shown to be tight.

Diagram illustrating the theoretical bounds between 1-row and aggregation closures for packing problems.

In contrast, for general polyhedra, the 1-row closure can be an infinitely bad approximation. Empirical tests on random general IPs support this, showing the ratio between 1-row CG and full CG closures frequently exceeding 10, and reaching as high as 50.

Ratio of 1-row CG closure to full CG closure for general IP instances.

Datasets and Empirical Evidence

The theoretical findings were supplemented by experiments on:

  • Randomly Generated General IPs: Small-scale problems (10–16 variables) with random integer coefficients.
  • Market Split Instances: Difficult 0-1 integer programs used to test the limits of cutting-plane methods.

The experiments confirmed that while aggregation is optional for packing, it is vital for general integer programming to close the integrality gap effectively.

Limitations and Future Work

Several open questions remain:

  1. Polyhedrality: It is unconfirmed if aggregation closures are polyhedral for all packing/covering problems, though it holds for "dense" cases.
  2. Heuristics: Can sign patterns in constraints guide better aggregation rules for general IPs?
  3. Multi-row Cuts: The practical trade-offs of combining $k$ rows (where $1 < k < m$) in real-world solvers require further investigation.

Summary updated

BibTeX
@inproceedings{bodur2018aggregation,
  author = {Merve Bodur and Alberto Del Pia and Santanu S. Dey and Marco Molinaro and Sebastian Pokutta},
  title = {{Aggregation-based cutting-planes for packing and covering integer programs}},
  booktitle = {Math. Program},
  year = {2018},
  url = {https://openreview.net/forum?id=TAjTXcb4mgj},
}

Loading related content...

Figure