A note on clique-web facets for multicut polytopes. (English) Zbl 1082.90104
Summary: In this note we provide a previously undiscovered necessary condition for the facet-defining property of clique-web inequalities for the multicut polytope. This condition imposes a minimum cardinality requirement on the node set of the clique, thus implying, in general, that clique-web inequalities associated with relatively small cliques are not facet-defining for multicut polytopes.
MSC:
90C27 | Combinatorial optimization |
52A40 | Inequalities and extremum problems involving convexity in convex geometry |
90C35 | Programming involving graphs or networks |
90C57 | Polyhedral combinatorics, branch-and-bound, branch-and-cut |