The complexity of lifted inequalities for the knapsack problem

DOI10.1016/0166-218X(92)90162-4zbMath0767.90071MaRDI QIDQ1201098

Eitan Zemel, David B. Hartvigsen

Publication date: 17 January 1993

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

zbMATH Keywords

valid inequalitiesfacetsminimal coversknapsack polytopecomplexity of lifting

Mathematics Subject Classification ID

Special polytopes (linear programming, centrally symmetric, etc.) (52B12) Abstract computational complexity for mathematical programming problems (90C60) Combinatorial optimization (90C27)

Related Items

Knapsack polytopes: a survey, On the complexity of sequentially lifting cover inequalities for the knapsack polytope, Lifted cover facets of the 0-1 knapsack polytope with GUB constraints, Lifting the knapsack cover inequalities for the knapsack polytope, Sequence independent lifting for mixed knapsack problems with GUB constraints, Integrality Gaps of Linear and Semi-Definite Programming Relaxations for Knapsack, Adjacency of the 0-1 knapsack problem, Polyhedral results for the precedence-constrained knapsack problem, On lifted cover inequalities: a new lifting procedure with unusual properties

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The complexity of facets (and some facets of complexity)
• Optimization of a 532-city symmetric traveling salesman problem by branch and cut
• The ellipsoid method and its consequences in combinatorial optimization
• Easily Computable Facets of the Knapsack Polytope
• Covers and packings in a family of sets
• Solving Large-Scale Zero-One Linear Programming Problems
• Lifting the facets of zero–one polytopes
• Solving Large-Scale Symmetric Travelling Salesman Problems to Optimality
• Technical Note—A Note on Zero-One Programming
• Faces for a linear inequality in 0–1 variables
• Facet of regular 0–1 polytopes
• Facets of the knapsack polytope
• Facets of the Knapsack Polytope From Minimal Covers
• On Linear Characterizations of Combinatorial Optimization Problems
• Properties of vertex packing and independence system polyhedra
• Maximum matching and a polyhedron with 0,1-vertices