The worst case analysis of strong knapsack facets

Sangho Shim, Sunil Chopra*, Wenwei Cao

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

2 Scopus citations

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≤ 4) are strong facets for the knapsack polytope. We show that this finding is robust by proving that the removal of these facets from the master knapsack polytope significantly weakens the resulting relaxation in the worst case. We show that the 1 / k-facets for k= 1 are the strongest in that their removal from the master knapsack polytope weakens the 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 and that the 1 / k-facets with k even are stronger than the 1 / k-facets with k odd.

Original languageEnglish (US)
Pages (from-to)465-493
Number of pages29
JournalMathematical Programming
Volume162
Issue number1-2
DOIs
StatePublished - Mar 1 2017

Keywords

  • 90C10
  • 90C27

ASJC Scopus subject areas

  • Software
  • Mathematics(all)

Fingerprint Dive into the research topics of 'The worst case analysis of strong knapsack facets'. Together they form a unique fingerprint.

Cite this