Lower Bounds on the Lattice-Free Rank for Packing and Covering Integer Programs

DOI10.1137/17M1149985MaRDI QIDQ4646443zbMATH OpenOpenAlexWikidataFDO

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

Publication date 14 January 2019

Published in SIAM Journal on Optimization (Search for Journal in Brave)

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

zbMATH Keywords

coveringinteger programminglattice-free rankmulti-branch split rankpackingsplit rank

Mathematics Subject Classification ID

Integer programming (90C10) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57)

Abstract: In this paper, we present lower bounds on the rank of the split closure, the multi-branch closure and the lattice-free closure for packing sets as a function of the integrality gap. We also provide a similar lower bound on the split rank of covering polyhedra. These results indicate that whenever the integrality gap is high, these classes of cutting planes must necessarily be applied for many rounds in order to obtain the integer hull.

Recommendations

• Ranking lower bounds for the bin-packing problem
• Improved Approximation Guarantees for Packing and Covering Integer Programs
• Approximation algorithms for covering/packing integer programs
• Approximation of optima of integer programs of the packing—covering type
• Cover and pack inequalities for (mixed) integer programming
• Exact Semidefinite Programming Bounds for Packing Problems
• _1-sparsity approximation bounds for packing integer programs
• \(\ell_1\)-sparsity approximation bounds for packing integer programs
• Lower bounds for covering problems
• Packing and covering k-chain free subsets in Boolean lattices

Cites work

• A geometric approach to cut-generating functions
• A note on the split rank of intersection cuts
• Aggregation-based cutting-planes for packing and covering integer programs
• Approximation of corner polyhedra with families of intersection cuts
• Chvátal closures for mixed integer programming problems
• Convex Analysis
• Cook, Kannan and Schrijver's example revisited
• Cutting planes from extended LP formulations
• Disjunctive Programming
• Inequalities from Two Rows of a Simplex Tableau
• Integer Programming
• Intersection cuts with infinite Split rank
• Lattice-free sets, multi-branch split disjunctions, and mixed-integer programming
• Lower bounds for the Chvàtal-Gomory rank in the 0/1 cube
• Minimal valid inequalities for integer constraints
• On t-branch split cuts for mixed-integer programs
• On Cutting Planes
• On finitely generated closures in the theory of cutting planes
• Optimizing over the split closure
• Reverse split rank
• Split rank of triangle and quadrilateral inequalities
• The group-theoretic approach in mixed integer programming
• Two dimensional lattice-free cuts and asymmetric disjunctions for mixed-integer polyhedra

Cited in

(6)

• Aggregation-based cutting-planes for packing and covering integer programs
• The aggregation closure is polyhedral for packing and covering integer programs
• Approximate fixed-rank closures of covering problems
• Intersection cuts with infinite Split rank
• On the rank of disjunctive cuts
• On polytopes with linear rank with respect to generalizations of the split closure

This page was built for publication: Lower Bounds on the Lattice-Free Rank 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 Q4646443)