A polyhedral study of the cardinality constrained knapsack problem

Ismael R. De Farias, George L. Nemhauser

Research output: Chapter in Book/Report/Conference proceedingConference contribution

2 Scopus citations

Abstract

A cardinality constrained knapsack problem is a continuous knapsack problem in which no more than a specified number of nonnegative variables are allowed to be positive. This structure occurs, for example, in areas such as finance, location, and scheduling. Traditionally, cardinality constraints are modeled by introducing auxiliary 0-1 variables and additional constraints that relate the continuous and the 0-1 variables. We use an alternative approach, in which we keep in the model only the continuous variables, and we enforce the cardinality constraint through a specialized branching scheme and the use of strong inequalities valid for the convex hull of the feasible set in the space of the continuous variables. To derive the valid inequalities, we extend the concepts of cover and cover inequality, commonly used in 0-1 programming, to this class of problems, and we show how cover inequalities can be lifted to derive facet-defining inequalities. We present three families of non-trivial facet-defining inequalities that are lifted cover inequalities. Finally, we report computational results that demonstrate the effectiveness of lifted cover inequalities and the superiority of the approach of not introducing auxiliary 0-1 variables over the traditional MIP approach for this class of problems.

Original languageEnglish
Title of host publicationInteger Programming and Combinatorial Optimization - 9th International IPCO 2002 Conference, Proceedings
EditorsWilliam J. Cook, Andreas S. Schulz
PublisherSpringer-Verlag
Pages291-303
Number of pages13
ISBN (Print)9783540478676
DOIs
StatePublished - 2002
Event9th International Conference on Integer Programming and Combinatorial Optimization, IPCO 2002 - Cambridge, MA, United States
Duration: May 27 2002May 29 2002

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume2337 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference9th International Conference on Integer Programming and Combinatorial Optimization, IPCO 2002
CountryUnited States
CityCambridge, MA
Period05/27/0205/29/02

Fingerprint Dive into the research topics of 'A polyhedral study of the cardinality constrained knapsack problem'. Together they form a unique fingerprint.

  • Cite this

    De Farias, I. R., & Nemhauser, G. L. (2002). A polyhedral study of the cardinality constrained knapsack problem. In W. J. Cook, & A. S. Schulz (Eds.), Integer Programming and Combinatorial Optimization - 9th International IPCO 2002 Conference, Proceedings (pp. 291-303). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 2337 LNCS). Springer-Verlag. https://doi.org/10.1007/3-540-47867-1_21