Knapsack Polytopes - A Survey

Christopher Hojny(hojnymathematik.tu-darmstadt.de)
Tristan Gally(gallymathematik.tu-darmstadt.de)
Oliver Habeck(habeckmathematik.tu-darmstadt.de)
Hendrik Lüthen(luethenmathematik.tu-darmstadt.de)
Frederic Matter(mattermathematik.tu-darmstadt.de)
Marc E. Pfetsch(pfetschmathematik.tu-darmstadt.de)
Andreas Schmitt(aschmittmathematik.tu-darmstadt.de)

Abstract: The 0/1 knapsack polytope is the convex hull of all 0/1 vectors that satisfy a given single linear inequality with non-negative coefficients. This paper provides a comprehensive overview of knapsack polytopes. We discuss basic polyhedral properties, (lifted) cover and other valid inequalities, cases for which complete linear descriptions are known, geometric properties for small dimensions, and connections to independence systems. We also discuss the generalization to (mixed-)integer knapsack polytopes and variants. The results from the literature are complemented by some new results, examples, and open questions.

Keywords: knapsack polytope, cover inequality, lifting, separation problem, complete linear description, independence systems

Category 1: Combinatorial Optimization (Polyhedra )

Category 2: Integer Programming (0-1 Programming )

Citation:

Download: [PDF]

Entry Submitted: 04/15/2019
Entry Accepted: 04/15/2019
Entry Last Modified: 04/15/2019

Modify/Update this entry