On the complexity of separating cutting planes for the knapsack polytope

DOI10.1007/s10107-023-01963-3MaRDI QIDQ6589743

Haoran Zhu, Alberto Del Pia, Jeff Linderoth

Publication date: 20 August 2024

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

zbMATH Keywords

complexity theoryseparation problemknapsack polytope

Mathematics Subject Classification ID

Integer programming (90C10) Combinatorial optimization (90C27)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Cover and pack inequalities for (mixed) integer programming
• The complexity of cover inequality separation
• On the \(0/1\) knapsack polytope
• A scheme for exact separation of extended cover inequalities and application to multidimensional knapsack problems
• Multi-cover inequalities for totally-ordered multiple knapsack sets
• On the complexity of separation from the knapsack polytope
• On lifted cover inequalities: a new lifting procedure with unusual properties
• Separation algorithms for 0-1 knapsack polytopes
• The Multidimensional Knapsack Problem: Structure and Algorithms
• (1,k)-configurations and facets for packing problems
• Technical Note—A Note on Zero-One Programming
• Faces for a linear inequality in 0–1 variables
• Facets of the knapsack polytope
• Facets of the Knapsack Polytope From Minimal Covers
• Lifted Cover Inequalities for 0-1 Integer Programs: Complexity
• Solving Multiple Knapsack Problems by Cutting Planes
• Reducibility among Combinatorial Problems

This page was built for publication: On the complexity of separating cutting planes for the knapsack polytope