A polyhedral study on 01 knapsack problems with disjoint cardinality constraints: Strong valid inequalities by sequence-independent lifting

Research output: Contribution to journalArticlepeer-review

7 Scopus citations

Abstract

We study the set of 01 integer solutions to a single knapsack constraint and a set of non-overlapping cardinality constraints (MCKP), which generalizes the classical 01 knapsack polytope and the 01 knapsack polytope with generalized upper bounds. We derive strong valid inequalities for the convex hull of its feasible solutions using sequence-independent lifting. For problems with a single cardinality constraint, we derive two-dimensional superadditive lifting functions and prove that they are maximal and non-dominated under some mild conditions. We then show that these functions can be used to build strong valid inequalities for problems with multiple disjoint cardinality constraints. Finally, we present preliminary computational results aimed at evaluating the strength of the cuts obtained from sequence-independent lifting with respect to those obtained from sequential lifting.

Original languageEnglish (US)
Pages (from-to)259-276
Number of pages18
JournalDiscrete Optimization
Volume8
Issue number2
DOIs
StatePublished - May 2011
Externally publishedYes

Keywords

  • Cardinality constraint
  • Cutting plane
  • Knapsack
  • Sequence-independent lifting

Fingerprint Dive into the research topics of 'A polyhedral study on 01 knapsack problems with disjoint cardinality constraints: Strong valid inequalities by sequence-independent lifting'. Together they form a unique fingerprint.

Cite this