The worst case analysis of strong knapsack facets

• 成果类型: Article
• 署名作者: Shim, Sangho; Chopra, Sunil; Cao, Wenwei
• 署名单位: Robert Morris University; Northwestern University; University System of Georgia; Georgia Institute of Technology
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-016-1050-2
• 发表日期: 2017
• 页码: 465-493
• 关键词: cutting planes; cyclic group; relaxation; polyhedra; THEOREM

摘要

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 () 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 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 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.