On bounded pitch inequalities for the MIN-knapsack polytope

DOI10.1007/978-3-319-96151-4_15MaRDI QIDQ1661877zbMATH OpenOpenAlexFDO

Authors Yuri Faenza, Monaldo Mastrolilli, Ola Svensson, Igor Malinović

Publication date 17 August 2018

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

Mathematics Subject Classification ID

Combinatorial optimization (90C27)

Abstract: In the min-knapsack problem one aims at choosing a set of objects with minimum total cost and total profit above a given threshold. In this paper, we study a class of valid inequalities for min-knapsack known as bounded pitch inequalities, which generalize the well-known unweighted cover inequalities. While separating over pitch-1 inequalities is NP-hard, we show that approximate separation over the set of pitch-1 and pitch-2 inequalities can be done in polynomial time. We also investigate integrality gaps of linear relaxations for min-knapsack when these inequalities are added. Among other results, we show that, for any fixed $t$, the $t$-th CG closure of the natural linear relaxation has the unbounded integrality gap.

Recommendations

• On inequalities with bounded coefficients and pitch for the min knapsack polytope
• On the complexity of separation from the knapsack polytope
• The Integer Knapsack Cover Polyhedron
• On the \(0/1\) knapsack polytope
• Valid inequalities, cutting planes and integrality of the knapsack polytope

Cited in

(2)

• On inequalities with bounded coefficients and pitch for the min knapsack polytope
• Pitch, extension complexity, and covering problems

This page was built for publication: On bounded pitch inequalities for the MIN-knapsack polytope

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1661877)