On bounded pitch inequalities for the MIN-knapsack polytope

DOI10.1007/978-3-319-96151-4_15zbMATH Open1401.90185arXiv1801.08850OpenAlexW2964086864MaRDI QIDQ1661877FDOQ1661877

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

Publication date: 17 August 2018

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.

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

Mathematics Subject Classification ID

Combinatorial optimization (90C27)

Cited In (1)

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

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)