Lifted cover facets of the 0-1 knapsack polytope with GUB constraints

DOI10.1016/0167-6377(94)90038-8zbMath0826.90093OpenAlexW2111606357MaRDI QIDQ1890949

Pamela H. Vance, Nemhauser, George I.

Publication date: 25 June 1995

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

Full work available at URL: https://doi.org/10.1016/0167-6377(94)90038-8

zbMATH Keywords

facet-defining inequalities0-1 knapsack polytopegeneralized upper bound constraintslifting coefficients

Mathematics Subject Classification ID

Special polytopes (linear programming, centrally symmetric, etc.) (52B12) Boolean programming (90C09)

Related Items

Knapsack polytopes: a survey, Locating median cycles in networks, A branch-cut-and-price algorithm for the piecewise linear transportation problem, \(O(n \log n)\) procedures for tightening cover inequalities, Cover by disjoint cliques cuts for the knapsack problem with conflicting items, A polyhedral study on \(0\)-\(1\) knapsack problems with disjoint cardinality constraints: strong valid inequalities by sequence-independent lifting, A polyhedral study on \(0\)-\(1\) knapsack problems with disjoint cardinality constraints: facet-defining inequalities by sequential lifting, Higher-order cover cuts from zero-one knapsack constraints augmented by two-sided bounding inequalities, Valid inequalities for the multi-dimensional multiple-choice 0-1 knapsack problem, A polyhedral study on 0-1 knapsack problems with set packing constraints, An \(O(n \log n)\) procedure for identifying facets of the knapsack polytope., Strong bounds for resource constrained project scheduling: preprocessing and cutting planes, Cover and pack inequalities for (mixed) integer programming

Uses Software

• MINTO
• OSL

Cites Work

• The complexity of lifted inequalities for the knapsack problem
• MINTO, a Mixed INTeger Optimizer
• Valid inequalities for 0-1 knapsacks and MIPs with generalised upper bound constraints
• Easily Computable Facets of the Knapsack Polytope
• Facets of the knapsack polytope
• Facets of the Knapsack Polytope From Minimal Covers