A polyhedral study on 0-1 knapsack problems with disjoint cardinality constraints: Facet-defining inequalities by sequential lifting

Research output: Contribution to journalArticlepeer-review

9 Scopus citations

Abstract

In this paper, we study the polyhedral structure of the set of 01 integer solutions to a single knapsack constraint and multiple disjoint cardinality constraints (MCKP). This set is a generalization of the classical 01 knapsack polytope (KP) and the 01 knapsack polytope with generalized upper bounds (GUBKP). For MCKP, we extend the traditional concept of a cover to that of a generalized cover. We then introduce generalized cover inequalities and present a polynomial algorithm that can lift them into facet-defining inequalities of the convex hull of MCKP. For the case where the knapsack coefficients are non-negative, we derive strong bounds on the lifting coefficients and describe the maximal set of generalized cover inequalities. Finally, we show that the bound estimates we obtained strengthen or generalize the known results for KP and GUBKP.

Original languageEnglish (US)
Pages (from-to)277-301
Number of pages25
JournalDiscrete Optimization
Volume8
Issue number2
DOIs
StatePublished - May 2011
Externally publishedYes

Bibliographical note

Funding Information:
Supported by NSF Grant DMI-03-48611 .

Copyright:
Copyright 2011 Elsevier B.V., All rights reserved.

Keywords

  • Cardinality constraint
  • Facet
  • Knapsack
  • Lifting
  • Maximal set

Fingerprint Dive into the research topics of 'A polyhedral study on 0-1 knapsack problems with disjoint cardinality constraints: Facet-defining inequalities by sequential lifting'. Together they form a unique fingerprint.

Cite this