The Worst Case Analysis of Strong Knapsack Facets

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.