Lower bounds on the lattice-free rank for packing and covering integer\n programs

2017/09/29 by Merve Bodur, Bodur, Merve, Alberto Del Pia +5
Engineering · #Advanced Manufacturing and Logistics Optimization #FOS: Mathematics #Optimization and Control (math.OC) #Optimization and Packing Problems #Scheduling and Optimization Algorithms

paper · pdf · doi:10.48550/arxiv.1710.00031

openalex publication_date 2017/09/29 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

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

Related

• Aggregation-based cutting-planes for packing and covering integer\n programs
• Two-halfspace closure
• On Polytopes with Linear Rank with respect to Generalizations of the Split Closure
• An LP with Integrality Gap 1+epsilon for Multidimensional Knapsack
• Lower Bounds on the Sizes of Integer Programs Without Additional Variables