An \(O(n \log n)\) procedure for identifying facets of the knapsack polytope.

DOI10.1016/S0167-6377(02)00221-3zbMath1042.90035MaRDI QIDQ1811629

Gloria Pérez, Laureano Fernando Escudero Bueno, María Araceli Garín

Publication date: 17 June 2003

Published in: Operations Research Letters (Search for Journal in Brave)

zbMATH Keywords

Knapsack polytopeFacet-defining inequalitiesStrong minimal coversTightening procedures

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Combinatorial optimization (90C27)

Related Items

Integrality Gaps of Linear and Semi-Definite Programming Relaxations for Knapsack, A polyhedral study on 0-1 knapsack problems with set packing constraints, Construction de facettes pour le polytope du sac-à-dos quadratique en 0-1, Cover and pack inequalities for (mixed) integer programming

Cites Work

• \(O(n \log n)\) procedures for tightening cover inequalities
• On the \(0/1\) knapsack polytope
• \(O(n)\) procedures for identifying maximal cliques and non-dominated extensions of consecutive minimal covers and alternates
• Lifted cover facets of the 0-1 knapsack polytope with GUB constraints
• Easily Computable Facets of the Knapsack Polytope
• Maximizing Submodular Set Functions: Formulations and Analysis of Algorithms
• 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
• Properties of vertex packing and independence system polyhedra
• Sequence independent lifting of cover inequalities
• On the facial structure of set packing polyhedra
• Canonical Cuts on the Unit Hypercube