The Worst Case Analysis of Strong Knapsack Facets

Sangho Shim, Wenwei Cao, Sunil Chopra

Research output: Working paper

Abstract

In this paper we identify strong facet defining inequalities for the master knapsack polytope. Our computational experiments for small master knapsack problems show that $1/k$-facets for small values of $k$ ($k\leq 4$) are strong facets for the knapsack polytope. We then show that these facets are strong in the sense that their removal from the master knapsack polytope significantly weakens the resulting LP-relaxation in the worst case. We show that the $1/k$-facets for $k = 1$ or $2$ are the strongest in that their removal from the master knapsack polytope weakens the LP-relaxation by a factor of $3/2$ in the worst case. We then show that the $1/k$-facets with $k = 3$ or $4$ are the next strongest. We also show that the strength of the $1/k$-facets weakens as $k$ grows. In general we are able to show that the $1/k$-facets with $k$ even are stronger than the $1/k$-facets with $k$ odd.
Original languageEnglish (US)
PublisherResearchGate
StatePublished - Aug 2014

Fingerprint Dive into the research topics of 'The Worst Case Analysis of Strong Knapsack Facets'. Together they form a unique fingerprint.

  • Cite this