A polyhedral study of the cardinality constrained knapsack problem |
| |
Authors: | IR de Farias Jr GL Nemhauser |
| |
Institution: | (1) CORE, 34 Voie du Roman Pays, 1348 Louvain-la-Neuve, Belgium, e-mail: defarias@core.ucl.ac.be, BE;(2) School of Industrial and Systems Engineering, Georgia Institute of Technology, Atlanta, GA 30332-0205, USA, e-mail: george.nemhauser@isye.gatech.edu Partially supported by NSF grants DMI-0100020 and DMI-0121495., US |
| |
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.
Received: March 13, 2003
Published online: April 10, 2003
Key Words. mixed-integer programming – knapsack problem – cardinality constrained programming – branch-and-cut |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|