Affordable Access

Publisher Website

A polyhedral study on [formula omitted]knapsack problems with disjoint cardinality constraints: Facet-defining inequalities by sequential lifting

Authors
Journal
Discrete Optimization
1572-5286
Publisher
Elsevier
Publication Date
Volume
8
Issue
2
Identifiers
DOI: 10.1016/j.disopt.2010.09.005
Keywords
  • Knapsack
  • Cardinality Constraint
  • Facet
  • Lifting
  • Maximal Set
Disciplines
  • Computer Science

Abstract

Abstract In this paper, we study the polyhedral structure of the set of 0 – 1 integer solutions to a single knapsack constraint and multiple disjoint cardinality constraints (MCKP). This set is a generalization of the classical 0 – 1 knapsack polytope (KP) and the 0 – 1 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.

There are no comments yet on this publication. Be the first to share your thoughts.