On the complexity of separation from the knapsack polytope

DOI10.1007/978-3-031-06901-7_13zbMath1497.90130arXiv2111.06556OpenAlexW3213324146MaRDI QIDQ2164691

Jeff Linderoth, Haoran Zhu, Alberto Del Pia

Publication date: 16 August 2022

Full work available at URL: https://arxiv.org/abs/2111.06556

zbMATH Keywords

complexity theoryseparation problemknapsack polytope

Mathematics Subject Classification ID

Integer programming (90C10) Abstract computational complexity for mathematical programming problems (90C60) Combinatorial optimization (90C27)

Related Items

New classes of facets for complementarity knapsack problems

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 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