×

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
Full Text: DOI