Aggregation-based cutting-planes for packing and covering integer programs
From MaRDI portal
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
- 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
- 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?)
- 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 group-theoretic approach in mixed integer programming
- The Malinvaud Eigenvalue Lemma: Correction and Amplification
- Worst-case comparison of valid inequalities for the TSP
Cited in
(18)- Chvatal--Gomory--tier cuts for general integer programs
- Multi-cover inequalities for totally-ordered multiple knapsack sets
- The aggregation closure is polyhedral for packing and covering integer programs
- On a generalization of the Chvátal-Gomory closure
- The strength of multi-row aggregation cuts for sign-pattern integer programs
- New SOCP relaxation and branching rule for bipartite bilinear programs
- Two-halfspace closure
- Multi-cover inequalities for totally-ordered multiple knapsack sets: theory and computation
- Lower Bounds on the Lattice-Free Rank for Packing and Covering Integer Programs
- On obtaining the convex hull of quadratic inequalities via aggregations
- Lifting convex inequalities for bipartite bilinear programs
- Aggregations of Quadratic Inequalities and Hidden Hyperplane Convexity
- On a geometric graph-covering problem related to optimal safety-landing-site location
- The k-aggregation closure for covering sets
- A topological approach to simple descriptions of convex hulls of sets defined by three quadrics
- Aggregation of bilinear bipartite equality constraints and its application to structural model updating problem
- Strengthening dual bounds for multicommodity capacitated network design with unsplittable flow constraints
- On the power and limitations of branch and cut
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)
