Cardinality Constrained Combinatorial Optimization
In this project we investigate polyhedra associated with cardinality constrained combinatorial optimization problems. Given any combinatorial optimization problem Π, one obtains a cardinality constrained version of Π by adding cardinality constraints on the set of feasible solutions. This is usually done by requiring that all feasible solutions have cardinality k, ≤ k, or ≥ k. However, we are interested in more complex cardinality constraints.
To be more specific, we denote a combinatorial optimization problem by the triple Π = (E, I, w), where E is a finite set, I is a subset of the power set of E, called feasible solutions, and w is the objective function. The goal is to find a feasible solution F maximizing (minimizing) w. Moreover, let c = (c_{1}, ..., c_{m}) be a finite sequence of integers 0 ≤ c_{1} < c_{2} < ... < c_{m} ≤  E  Then, the optimization problem Π_{c}: max w(F), F ∈ I,  F  = c_{p} for some p is a cardinality constrained version of Π. Denote by P^{c} the polytope associated with Π_{c}, that is, the convex hull of the incidence vectors of feasible solutions with respect to Π_{c}. The aim of this project is a better understanding of facet defining inequalities that are specific to these cardinality conditions.
IPformulations
If one has an integer programming formulation of Π = (E, I, w), say Ax ≤ b, x_{e} ∈ {0,1} for all e ∈ E, then one obtains an integer programming formulation for Π_{c} by adding the cardinality bounds x(E) ≥ c_{1} and x(E) ≤ c_{m} as well as the forbidden set inequalities
The Cardinality Constrained Matroid Polytope
A basic idea for strenghtening forbidden set inequalities is not to consider the cardinality of a set F itself but the maximum size of the intersection of a feasible solution and F. When (E,I) is a matroid, then this is exactly the rank of F. One can show that the rank induced forbidden set inequalities
Poster
 Polyhedral Investigation of Cardinality Constrained Combinatorial Optimization Problems (05/2008) [(pdf)]
Publications
2010 

Volker Kaibel, Rüdiger Stephan  On cardinality constrained cycle and path polytopes  Math. Program., 123(2 (A)), pp. 371394, 2010 (preprint available as ZIBReport 0725) 
PDF (ZIBReport)
BibTeX DOI 
2009 

Rüdiger Stephan  Facets of the (s,t)ppath polytope  Discrete Appl. Math., 157(14), pp. 31193132, 2009 (preprint available as ZIBReport 0638) 
PDF (ZIBReport)
BibTeX DOI 
Jean Maurras, Rüdiger Stephan  On the cardinality constrained matroid polytope  2009 (preprint available as ZIBReport 0808) 
PDF (ZIBReport)
BibTeX 
2005 

Rüdiger Stephan  Polytopes associated with length restricted directed circuits  diploma thesis, Technische Universität Berlin, 2005 
BibTeX

2004 

Martin Grötschel  Cardinality Homogeneous Set Systems, Cycles in Matroids, and Associated Polytopes  The Sharpest Cut, Martin Grötschel (Ed.), MPSSIAM, pp. 99120, 2004 (preprint available as ) 
BibTeX
