Approximate formulations for 0-1 knapsack sets

DOI10.1016/j.orl.2007.09.003zbMath1152.90535OpenAlexW2065139435MaRDI QIDQ943790

Bienstock, Daniel

Publication date: 10 September 2008

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

Full work available at URL: https://doi.org/10.1016/j.orl.2007.09.003

zbMATH Keywords

lift-and-project

Mathematics Subject Classification ID

Integer programming (90C10)

Related Items (17)

Knapsack polytopes: a survey ⋮ On the mixing set with a knapsack constraint ⋮ Approximation Limits of Linear Programs (Beyond Hierarchies) ⋮ On inequalities with bounded coefficients and pitch for the min knapsack polytope ⋮ Simple extensions of polytopes ⋮ Tightening simple mixed-integer sets with guaranteed bounds ⋮ Some \(0/1\) polytopes need exponential size extended formulations ⋮ A note on the extension complexity of the knapsack polytope ⋮ Integrality Gaps of Linear and Semi-Definite Programming Relaxations for Knapsack ⋮ Extended formulations in combinatorial optimization ⋮ Evolution of new algorithms for the binary knapsack problem ⋮ Extended formulations in combinatorial optimization ⋮ On the existence of compact $\varepsilon$-approximated formulations for knapsack in the original space ⋮ No Small Linear Program Approximates Vertex Cover Within a Factor 2 − ɛ ⋮ Semi-Infinite Relaxations for the Dynamic Knapsack Problem with Stochastic Item Sizes ⋮ Unnamed Item ⋮ Approximation algorithms for cost-robust discrete minimization problems based on their LP-relaxations

Cites Work

• Unnamed Item
• Unnamed Item
• A lift-and-project cutting plane algorithm for mixed 0-1 programs
• Tree-width and the Sherali-Adams operator
• Approximate extended formulations
• Approximate fixed-rank closures of covering problems
• On the Matrix-Cut Rank of Polyhedra
• A Hierarchy of Relaxations between the Continuous and Convex Hull Representations for Zero-One Programming Problems
• Cones of Matrices and Set-Functions and 0–1 Optimization
• Fast Approximation Algorithms for the Knapsack and Sum of Subset Problems
• Subset Algebra Lift Operators for 0-1 Integer Programming
• When Does the Positive Semidefiniteness Constraint Help in Lifting Procedures?
• A Comparison of the Sherali-Adams, Lovász-Schrijver, and Lasserre Relaxations for 0–1 Programming

This page was built for publication: Approximate formulations for 0-1 knapsack sets