Simultaneously lifting sets of binary variables into cover inequalities for knapsack polytopes

DOI10.1016/j.disopt.2007.05.003zbMath1151.90026OpenAlexW2036861438MaRDI QIDQ951099

Kevin Hooker, Todd Easton

Publication date: 29 October 2008

Published in: Discrete Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.disopt.2007.05.003

zbMATH Keywords

polyhedral theory

Mathematics Subject Classification ID

Integer programming (90C10) Combinatorial optimization (90C27)

Related Items

Knapsack polytopes: a survey ⋮ Sequence independent lifting for mixed knapsack problems with GUB constraints ⋮ Approximate and exact merging of knapsack constraints with cover inequalities

Uses Software

• CPLEX

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Facets of the knapsack polytope derived from disjoint and overlapping index configurations
• An algorithm for the solution of the 0-1 knapsack problem
• The complexity of cover inequality separation
• On the \(0/1\) knapsack polytope
• Corner polyhedra and their connection with cutting planes
• Sequence independent lifting in mixed integer programming
• Some polyhedra related to combinatorial problems
• Simple lifted cover inequalities and hard knapsack problems
• Easily Computable Facets of the Knapsack Polytope
• A New Algorithm for the 0-1 Knapsack Problem
• Lifting the facets of zero–one polytopes
• Hard Knapsack Problems
• An Algorithm for Large Zero-One Knapsack Problems
• Faces for a linear inequality in 0–1 variables
• Facet of regular 0–1 polytopes
• 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
• On the facial structure of set packing polyhedra
• Discrete-Variable Extremum Problems