TY - GEN A1 - Stephan, Rüdiger T1 - On the cardinality constrained matroid polytope N2 - 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. T3 - ZIB-Report - 08-08 KW - Matroid-Polytop KW - Kardinalitätsbeschränkung KW - Separationsalgorithmus KW - Matroid Polytope KW - Cardinality constraints KW - Separation algorithm Y1 - 2008 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-10614 SN - 1438-0064 ER - TY - GEN A1 - Stephan, Rüdiger T1 - Facets of the (s,t)-p-path polytope N2 - \noindent We give a partial description of the $(s,t)-p$-path polytope of a directed graph $D$ which is the convex hull of the incidence vectors of simple directed $(s,t)$-paths in $D$ of length $p$. First, we point out how the $(s,t)-p$-path polytope is located in the family of path and cycle polyhedra. Next, we give some classes of valid inequalities which are very similar to inequalities which are valid for the $p$-cycle polytope, that is, the convex hull of the incidence vectors of simple cycles of length $p$ in $D$. We give necessary and sufficient conditions for these inequalities to be facet defining. Furthermore, we consider a class of inequalities that has been identifie d to be valid for $(s,t)$-paths of cardinality at most $p$. Finally, we transfer the results to related polytopes, in particular, the undirected counterpart of the $(s,t)-p$-path polytope. T3 - ZIB-Report - 06-38 Y1 - 2006 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-9328 ER - TY - GEN A1 - Kaibel, Volker A1 - Stephan, Rüdiger T1 - On cardinality constrained cycle and path polytopes N2 - We consider polytopes associated with cardinality constrained path and cycle problems defined on a directed or undirected graph. We present integer characterizations of these polytopes by facet defining linear inequalities for which the separation problem can be solved in polynomial time. Moreover, we give further facet defining inequalities, in particular those that are specific to odd/even paths and cycles. T3 - ZIB-Report - 07-25 KW - path KW - cycles KW - integer characterizations KW - facets Y1 - 2007 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-10093 SN - 1438-0064 ER - TY - CHAP A1 - Grötschel, Martin ED - Grötschel, Martin T1 - Cardinality Homogeneous Set Systems, Cycles in Matroids, and Associated Polytopes T2 - The Sharpest Cut Y1 - 2004 SP - 99 EP - 120 PB - MPS-SIAM ER - TY - JOUR A1 - Kaibel, Volker A1 - Stephan, Rüdiger T1 - On cardinality constrained cycle and path polytopes JF - Math. Program. Y1 - 2010 U6 - https://doi.org/10.1007/s10107-008-0257-2 VL - 123 IS - 2 (A) SP - 371 EP - 394 ER - TY - GEN A1 - Maurras, Jean A1 - Stephan, Rüdiger T1 - On the cardinality constrained matroid polytope Y1 - 2009 ER - TY - BOOK A1 - Stephan, Rüdiger T1 - Polytopes associated with length restricted directed circuits Y1 - 2005 PB - diploma thesis, Technische Universität Berlin ER - TY - JOUR A1 - Stephan, Rüdiger T1 - Facets of the (s,t)-p-path polytope JF - Discrete Appl. Math. Y1 - 2009 U6 - https://doi.org/10.1016/j.dam.2009.06.003 VL - 157 IS - 14 SP - 3119 EP - 3132 ER -