Lifting the knapsack cover inequalities for the knapsack polytope

DOI10.1016/j.orl.2020.07.010zbMath1479.90140OpenAlexW3045412348MaRDI QIDQ2661529

Georgia Souli, Adam N. Letchford

Publication date: 7 April 2021

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

Full work available at URL: https://eprints.lancs.ac.uk/id/eprint/145667/1/knapsack_cover.pdf

zbMATH Keywords

mixed-integer linear programmingpolyhedral combinatoricsknapsack problemslifted cover inequalities

Mathematics Subject Classification ID

Mixed integer programming (90C11) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57)

Related Items

Knapsack problems -- an overview of recent advances. I: Single knapsack problems

Uses Software

• PORTA

Cites Work

• Unnamed Item
• Cover and pack inequalities for (mixed) integer programming
• The complexity of lifted inequalities for the knapsack problem
• On the \(0/1\) knapsack polytope
• A recursive procedure to generate all cuts for 0-1 mixed integer programs
• Sequence independent lifting in mixed integer programming
• On lifted cover inequalities: a new lifting procedure with unusual properties
• Edmonds polytopes and a hierarchy of combinatorial problems
• Separation algorithms for 0-1 knapsack polytopes
• Easily Computable Facets of the Knapsack Polytope
• Outline of an algorithm for integer solutions to linear programs
• Aggregation and Mixed Integer Rounding to Solve MIPs
• Solving Large-Scale Zero-One Linear Programming Problems
• Improving LP-Representations of Zero-One Linear Programs for Branch-and-Cut
• Technical Note—A Note on Zero-One Programming
• Faces for a linear inequality in 0–1 variables
• Facets of the knapsack polytope
• Technical Note—Facets and Strong Valid Inequalities for Integer Programs
• Facets of the Knapsack Polytope From Minimal Covers
• Valid Inequalities and Superadditivity for 0–1 Integer Programs
• Generating Fenchel Cutting Planes for Knapsack Polyhedra