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

DOI10.1007/S10107-017-1192-XMaRDI QIDQ1785202zbMATH OpenOpenAlexFDO

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

Publication date 28 September 2018

Published in Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1606.08951

zbMATH Keywords

aggregationinteger programmingcutting planescoveringpacking

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Integer programming (90C10)

Abstract: In this paper, we study the strength of Chvatal-Gomory (CG) cuts and more generally aggregation cuts for packing and covering integer programs (IPs). Aggregation cuts are obtained as follows: Given an IP formulation, we first generate a single implied inequality using aggregation of the original constraints, then obtain the integer hull of the set defined by this single inequality with variable bounds, and finally use the inequalities describing the integer hull as cutting-planes. Our first main result is to show that for packing and covering IPs, the CG and aggregation closures can be 2-approximated by simply generating the respective closures for each of the original formulation constraints, without using any aggregations. On the other hand, we use computational experiments to show that aggregation cuts can be arbitrarily stronger than cuts from individual constraints for general IPs. The proof of the above stated results for the case of covering IPs with bounds require the development of some new structural results, which may be of independent interest. Finally, we examine the strength of cuts based on k different aggregation inequalities simultaneously, the so-called multi-row cuts, and show that every packing or covering IP with a large integrality gap also has a large k-aggregation closure rank. In particular, this rank is always at least of the order of the logarithm of the integrality gap.

Recommendations

• The aggregation closure is polyhedral for packing and covering integer programs
• The strength of multi-row aggregation cuts for sign-pattern integer programs
• Lower Bounds on the Lattice-Free Rank for Packing and Covering Integer Programs
• Chvatal--Gomory--tier cuts for general integer programs
• Iterated Chvátal-Gomory cuts and the geometry of numbers

Cites work

• scientific article; zbMATH DE number 193411 (Why is no real title available?)
• scientific article; zbMATH DE number 1266748 (Why is no real title available?)
• scientific article; zbMATH DE number 1070896 (Why is no real title available?)
• scientific article; zbMATH DE number 1445293 (Why is no real title available?)
• scientific article; zbMATH DE number 2196290 (Why is no real title available?)
• 0/1 polytopes with quadratic Chvátal rank
• 50 Years of Integer Programming 1958-2008
• A Class of Hard Small 0-1 Programs
• Approximate fixed-rank closures of covering problems
• Cutting planes in integer and mixed integer programming
• Faces for a linear inequality in 0–1 variables
• Improved Approximation Guarantees for Packing and Covering Integer Programs
• Improving integrality gaps via Chvátal-Gomory rounding
• Integer Programming
• Lifting the facets of zero–one polytopes
• Lower bounds for the Chvàtal-Gomory rank in the 0/1 cube
• Mixed integer programming computation
• On Cutting Planes
• On cutting-plane proofs in combinatorial optimization
• On the \(0/1\) knapsack polytope
• On the exact separation of mixed integer knapsack cuts
• On the rank of cutting-plane proof systems
• Optimizing over the first Chvátal closure
• Some properties of convex hulls of integer points contained in general convex sets
• The Malinvaud Eigenvalue Lemma: Correction and Amplification
• The group-theoretic approach in mixed integer programming
• Worst-case comparison of valid inequalities for the TSP

Cited in

(12)

• On a generalization of the Chvátal-Gomory closure
• Multi-cover inequalities for totally-ordered multiple knapsack sets: theory and computation
• Aggregations of Quadratic Inequalities and Hidden Hyperplane Convexity
• Lifting convex inequalities for bipartite bilinear programs
• On obtaining the convex hull of quadratic inequalities via aggregations
• Lower Bounds on the Lattice-Free Rank for Packing and Covering Integer Programs
• Multi-cover inequalities for totally-ordered multiple knapsack sets
• New SOCP relaxation and branching rule for bipartite bilinear programs
• The strength of multi-row aggregation cuts for sign-pattern integer programs
• Two-halfspace closure
• The aggregation closure is polyhedral for packing and covering integer programs
• Chvatal--Gomory--tier cuts for general integer programs

This page was built for publication: Aggregation-based cutting-planes for packing and covering integer programs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1785202)