On the cardinality constrained matroid polytope

Details On the cardinality constrained matroid polytope On the cardinality constrained matroid polytope

2009-02-11

arxiv.org/abs/0902.1932v1

Mathematics

Combinatorics

17 pages

Scientific paper

Given a combinatorial optimization problem $\Pi$ and an increasing finite sequence $c$ of natural numbers, we obtain a cardinality constrained version $\Pi_c$ of $\Pi$ by permitting only those feasible solutions of $\Pi$ whose cardinalities are members of $c$. We are interested in polyhedra associated with those problems, in particular in inequalities that cut off solutions of forbidden cardinality. Maurras (1977) and Camion and Maurras (1982) introduced a family of inequalities, that we call forbidden set inequalities, which can be used to cut off those solutions. However, these inequalities are in general not facet defining for the polyhedron associated with $\Pi_c$. Kaibel and Stephan (2007) showed how one can combine integer characterizations for cycle and path polytopes and a modified form of forbidden set inequalities to give facet defining integer representations for the cardinality restricted versions of these polytopes. Motivated by this work, we apply the same approach on the matroid polytope. It is well known that the so-called rank inequalities together with the nonnegativity constraints provide a complete linear description of the matroid polytope (see Edmonds (1971). By essentially adding the forbidden set inequalities in an appropriate form, we obtain a complete linear description of the cardinality constrained matroid polytope which is the convex hull of the incidence vectors of those independent sets that have a feasible cardinality. Moreover, we show how the separation problem for the forbidden set inequalities can be reduced to that for the rank inequalities. We also give necessary and sufficient conditions for a forbidden set inequality to be facet defining.

Affiliated with

Also associated with

No associations

Rating

On the cardinality constrained matroid polytope does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with On the cardinality constrained matroid polytope, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On the cardinality constrained matroid polytope will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-488261