On inequalities with bounded coefficients and pitch for the min knapsack polytope

摘要

The min knapsack problem appears as a major component in the structure of capacitated covering problems. Its polyhedral relaxations have been extensively studied, leading to strong relaxations for networking, scheduling and facility location problems. A valid inequality alpha(T) x >= alpha 0 with therefore alpha >= 0 for a min knapsack instance is said to have pitch <= pi (pi a positive integer) if the pi smallest strictly positive alpha(j) sum to at least alpha(0). An inequality with coefficients and right-hand side in {0, 1,...., pi} has pitch <= pi. The notion of pitch has been used for measuring the complexity of valid inequalities for the min knapsack polytope. Separating inequalities of pitch-1 is already NP-Hard. In this paper, we show an algorithm for efficiently separating inequalities with coefficients in {0, 1,..., pi} for any fixed pi up to an arbitrarily small additive error. As a special case, this allows for approximate separation of inequalities with pitch at most 2. We moreover investigate the integrality gap of minimum knapsack instances when bounded pitch inequalities (possibly in conjunction with other inequalities) are added. Among other results, we show that the CG closure of minimum knapsack has unbounded integrality gap even after a constant number of rounds. (C) 2020 Elsevier B.V. All rights reserved.