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 = (c1, ..., cm) be a finite sequence of integers 0 ≤ c1 < c2 < ... < cm ≤ | E | Then, the optimization problem Πc: max w(F), F ∈ I, | F | = cp for some p is a cardinality constrained version of Π. Denote by Pc 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.
IP-formulations
If one has an integer programming formulation of Π = (E, I, w), say Ax ≤ b, xe ∈ {0,1} for all e ∈ E, then one obtains an integer programming formulation for Πc by adding the cardinality bounds x(E) ≥ c1 and x(E) ≤ cm 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. 371-394, 2010 (preprint available as ZIB-Report 07-25) |
PDF (ZIB-Report)
BibTeX DOI |
2009 |
|||
Rüdiger Stephan | Facets of the (s,t)-p-path polytope | Discrete Appl. Math., 157(14), pp. 3119-3132, 2009 (preprint available as ZIB-Report 06-38) |
PDF (ZIB-Report)
BibTeX DOI |
Jean Maurras, Rüdiger Stephan | On the cardinality constrained matroid polytope | 2009 (preprint available as ZIB-Report 08-08) |
PDF (ZIB-Report)
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.), MPS-SIAM, pp. 99-120, 2004 (preprint available as ) |
BibTeX
|