Cardinality constrained combinatorial optimization: Complexity and polyhedra

AbstractGiven a combinatorial optimization problem and a subset N of nonnegative integer numbers, we obtain a cardinality constrained version of this problem by permitting only those feasible solutions whose cardinalities are elements of N. In this paper we briefly touch on questions that address common grounds and differences of the complexity of a combinatorial optimization problem and its cardinality constrained version. Afterwards we focus on the polyhedral aspects of the cardinality constrained combinatorial optimization problems. Maurras (1977) [5] introduced a class of inequalities, called forbidden cardinality inequalities in this paper, that can be added to a given integer programming formulation for a combinatorial optimization problem to obtain one for the cardinality restricted versions of this problem. Since the forbidden cardinality inequalities in their original form are mostly not facet defining for the associated polyhedron, we discuss some possibilities to strengthen them, based on the experiments made in Kaibel and Stephan (2007) and Maurras and Stephan (2009) [2,3]