On the cardinality constrained matroid polytope
Please always quote using this URN: urn:nbn:de:0297-zib-10614
- Edmonds showed that the so-called rank inequalities and the nonnegativity constraints provide a complete linear description of the matroid polytope. By essentially adding Grötschel's cardinality forcing inequalities, 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 cardinality forcing inequalities can be reduced to that for the rank inequalities. We also give necessary and sufficient conditions for a cardinality forcing inequality to be facet defining.
Download full text files
Additional Services
| Author: | Rüdiger Stephan |
|---|---|
| Document Type: | ZIB-Report |
| Tag: | Kardinalitätsbeschränkung; Matroid-Polytop; Separationsalgorithmus Cardinality constraints; Matroid Polytope; Separation algorithm |
| MSC-Classification: | 05-XX COMBINATORICS (For finite fields, see 11Txx) / 05Bxx Designs and configurations (For applications of design theory, see 94C30) / 05B35 Matroids, geometric lattices [See also 52B40, 90C27] |
| 52-XX CONVEX AND DISCRETE GEOMETRY / 52Bxx Polytopes and polyhedra / 52B40 Matroids (realizations in the context of convex polytopes, convexity in combinatorial structures, etc.) [See also 05B35, 52Cxx] | |
| 90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING / 90Cxx Mathematical programming [See also 49Mxx, 65Kxx] / 90C27 Combinatorial optimization | |
| Date of first Publication: | 2008/02/20 |
| Series (Serial Number): | ZIB-Report (08-08) |
| ISSN: | 1438-0064 |
| ZIB-Reportnumber: | 08-08 |
