Dual consistent systems of linear inequalities and cardinality constrained polytopes

作者：Fujishige Satoru; Mas**erg Jens^*

来源：Mathematical Programming, 2015, 150(1): 35-48.

DOI：10.1007/s10107-014-0748-2

• Dual consistency
• Linear inequalities
• Cardinality constrained polytopes
• Matroids

We introduce a concept of dual consistency of systems of linear inequalities with full generality. We show that a cardinality constrained polytope is represented by a certain system of linear inequalities if and only if the systems of linear inequalities associated with the cardinalities are dual consistent. Typical dual consistent systems of inequalities are those which describe polymatroids, generalized polymatroids, and dual greedy polyhedra with certain choice functions. We show that the systems of inequalities for cardinality-constrained ordinary bipartite matching polytopes are not dual consistent in general, and give additional inequalities to make them dual consistent. Moreover, we show that ordinary systems of inequalities for the cardinality-constrained (poly)matroid intersection are not dual consistent, which disproves a conjecture of Maurras, Spiegelberg, and Stephan about a linear representation of the cardinality-constrained polymatroid intersection.

• 出版日期2015-4