Knapsack polytopes: a survey

Christopher Hojny; Tristan Gally; Oliver Habeck; Hendrik Lüthen; Frederic Matter; Marc E. Pfetsch; Andreas Schmitt

doi:10.1007/s10479-019-03380-2

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 journal › Article › Academic › peer-review

9 Citations (Scopus)

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 language	English
Pages (from-to)	469-517
Number of pages	49
Journal	Annals of Operations Research
Volume	292
Early online date	19 Sept 2019
DOIs	https://doi.org/10.1007/s10479-019-03380-2
Publication status	Published - 1 Sept 2020
Externally published	Yes

Keywords

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

Access to Document

10.1007/s10479-019-03380-2

Cite this

@article{93c88f5f91d44dc09f6564b8d7ad3089,

title = "Knapsack polytopes: a survey",

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.",

keywords = "Complete linear description, Cover inequality, Independence systems, Knapsack polytope, Lifting, Separation problem",

author = "Christopher Hojny and Tristan Gally and Oliver Habeck and Hendrik L{\"u}then and Frederic Matter and Pfetsch, {Marc E.} and Andreas Schmitt",

year = "2020",

month = sep,

day = "1",

doi = "10.1007/s10479-019-03380-2",

language = "English",

volume = "292",

pages = "469--517",

journal = "Annals of Operations Research",

issn = "0254-5330",

publisher = "Springer",

}

TY - JOUR

T1 - Knapsack polytopes: a survey

AU - Hojny, Christopher

AU - Gally, Tristan

AU - Habeck, Oliver

AU - Lüthen, Hendrik

AU - Matter, Frederic

AU - Pfetsch, Marc E.

AU - Schmitt, Andreas

PY - 2020/9/1

Y1 - 2020/9/1

N2 - 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.

AB - 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.

KW - Complete linear description

KW - Cover inequality

KW - Independence systems

KW - Knapsack polytope

KW - Lifting

KW - Separation problem

UR - http://www.scopus.com/inward/record.url?scp=85073995205&partnerID=8YFLogxK

U2 - 10.1007/s10479-019-03380-2

DO - 10.1007/s10479-019-03380-2

M3 - Article

SN - 0254-5330

VL - 292

SP - 469

EP - 517

JO - Annals of Operations Research

JF - Annals of Operations Research

ER -

Knapsack polytopes: a survey

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this