On the cardinality constrained matroid polytope
On the cardinality constrained matroid polytope
复制标题
关于基数约束拟阵多胞形
DOI：
10.1002/net.20430
复制
发表时间：
2009
期刊：
影响因子：
2.1
通讯作者：
Rüdiger Stephan
中科院分区：
文献类型：
--
作者：
J. Maurras;Rüdiger Stephan
考虑到组合优化问题π和自然数的有限序列C，我们通过仅允许那些与CAD -CASERITIS的可行解决方案获得π的基数约束πc。尤其是在不平等的情况下切断了不平等基数的解决方案。我们称之为禁止的不等式，可用于切断这些解决方案。路径多型和修改形式的禁忌套装不等式，以定义由这些工作动机的基数限制版本的整数表示。众所周知，所谓的等级不等式以及非阴性约束提供了完整的线性描述（请参阅Edmonds [3]）。限制基质性的基质多层的描述是那些具有可行基数的独立集合的入射向量的凸壳。此外，我们如何将禁止集的分离问题减少到等级的不等式。
Given a combinatorial optimization problem Π and an increasing finite sequence c of natural numbers, we obtain a cardinality constrained version Πc of Π by permitting only those feasible solutions of Π 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 [ 9 ] and Camion and Maurras [ 1 ] 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 Πc. In [ 7 ] it was shown 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 to 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 [ 3 ]). 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. © 2011 Wiley Periodicals, Inc. NETWORKS, 2011