On the Complexity of Separating Cutting Planes for the Knapsack Polytope

2021/11/12 by Alberto Del Pia, Del Pia, Alberto, Jeff Linderoth +3
Computer Science · Engineering · Mathematics · #Combinatorics #Computational Geometry and Mesh Generation #Continuous knapsack problem #Cover (algebra) #Discrete mathematics #FOS: Mathematics #Inequality #Knapsack problem #Material Properties and Processing #Mathematical analysis #Mathematical optimization #Mathematics #Optimization and Control (math.OC) #Optimization and Packing Problems #Polytope #Separation (statistics) #Time complexity

paper · pdf · doi:10.48550/arxiv.2111.06556

openalex publication_date 2021/11/12 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/08

Abstract

We close three open problems in 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 give a number of special cases where the separation problem can be solved in polynomial time.

Related

• New Classes of Facets for Complementarity Knapsack Problems
• Computational Aspects of Lifted Cover Inequalities for Knapsacks with Few Different Weights
• On the complexity of sequentially lifting cover inequalities for the knapsack polytope
• Multi-cover Inequalities for Totally-Ordered Multiple Knapsack Sets: Theory and Computation
• Combinatorial separation algorithms for the continuous knapsack polyhedra with divisible capacities