Knapsack polytopes – a survey

Christopher Hojny, Tristan Gally, Oliver Habeck, Hendrik Lüthen, Frederic Matter, Marc E. Pfetsch (Corresponding author), Andreas Schmitt

Research output: Contribution to journalArticleAcademicpeer-review

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.
Original languageEnglish
JournalAnnals of Operations Research
Early online date19 Sep 2019
DOIs
Publication statusE-pub ahead of print - 19 Sep 2019
Externally publishedYes

    Fingerprint

Keywords

  • Complete linear description
  • Cover inequality
  • Independence systems
  • Knapsack polytope
  • Lifting
  • Separation problem

Cite this

Hojny, C., Gally, T., Habeck, O., Lüthen, H., Matter, F., Pfetsch, M. E., & Schmitt, A. (2019). Knapsack polytopes – a survey. Annals of Operations Research. https://doi.org/10.1007/s10479-019-03380-2