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

(cp+1 - |F|) x(F) - (|F| - cp)x(E \ F) ≤ cp(cp+1 - |F|) for all F ⊆ E with cp < |F| < cp+1 and all p=1,...,m-1.
However, in general the forbidden set inequalities are quite weak in this form. In order to obtain stronger inequalities, we study some easy optimization problems under cardinality restrictions.

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

(cp+1 - r(F)) x(F) - (r(F) - cp)x(E \ F) ≤ cp(cp+1 - r(F)) for all F ⊆ E with cp < r(F) < cp+1 and all p=1,...,m-1
are not only valid for the cardinality constrained matroid polytope but much stronger than in the original form. Moreover, the rank induced forbidden set inequalities together with the rank inequalities introduced by Edmonds as well as the cardinality bounds and the nonnegativity constraints provide a complete linear description of the cardinality constrained matroid polytope. The rank induced forbidden set inequality associated with F is in general facet defining if F is closed.

Poster

  • Polyhedral Investigation of Cardinality Constrained Combinatorial Optimization Problems (05/2008) [(pdf)]
 
Research focus area: 
Combinatorics and MINLP
Research group: 
Mathematical Optimization Methods
Heads: 
Stephan, Dr. Rüdiger
Members: 
Stephan, Dr. Rüdiger
Partners: 
Volker Kaibel (U Magdeburg)
Jean François Maurras (U de la Méditerranée)