On the complexity of separating cutting planes for the knapsack polytope

• 成果类型: Article
• 署名作者: Del Pia, Alberto; Linderoth, Jeff; Zhu, Haoran
• 署名单位: University of Wisconsin System; University of Wisconsin Madison
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-023-01963-3
• 发表日期: 2024
• 页码: 33-59
• 关键词: cover inequalities; facets

摘要

We close three open problems on the separation complexity of valid inequalities for the knapsack polytope. Specifically, we establish that the separation problems for extended cover inequalities, (1, k)-configuration inequalities, and weight inequalities are all NP-complete. We also show that, when the number of constraints of the LP relaxation is constant and its optimal solution is an extreme point, then the separation problems of both extended cover inequalities and weight inequalities can be solved in polynomial time. Moreover, we provide a natural generalization of (1, k)-configuration inequality which is easier to separate and contains the original (1, k)-configuration inequality as a strict sub-family.