Simpler derivation of bounded pitch inequalities for set covering, and minimum knapsack sets

2018/06/19 by Daniel Bienstock, Bienstock, Daniel, Mark Zuckerberg +1
Computer Science · Engineering · Mathematics · #Computational Geometry and Mesh Generation #FOS: Mathematics #Metal Forming Simulation Techniques #Optimization and Control (math.OC) #Optimization and Packing Problems #math.OC

paper · pdf · doi:10.48550/arxiv.1806.07435

arxiv created 2018/06/19 · openalex publication_date 2018/06/19 · arxiv updated 2018/06/21 · openalex created_date 2018/06/29 · openalex updated_date 2026/07/28

Abstract

A valid inequality α^Tx ≥ α₀ for a set covering problem is said to have pitch <= k ( a positive integer) if the k smallest positive α_j sum to at least alpha₀. This paper presents a new, simple derivation of a relaxation for set covering problems whose solutions satisfy all valid inequalities of pitch and is of polynomial size, for each fixed . We also consider the minimum knapsack problem, and show that for each fixed integer p > 0 and 0 < ε< 1 one can separate, within additive tolerance ε, from the relaxation defined by the valid inequalities with coefficients in 0, 1, . . . , p in time polynomial in the number of variables and 1/ε.

Related

• On bounded pitch inequalities for the min-knapsack polytope
• On the complexity of sequentially lifting cover inequalities for the knapsack polytope
• Small Extended Formulation for Knapsack Cover Inequalities from Monotone Circuits
• Computational Aspects of Lifted Cover Inequalities for Knapsacks with Few Different Weights
• Understanding Set Cover: Sub-exponential Time Approximations and Lift-and-Project Methods