About cookies on this site Our websites require some cookies to function properly (required). In addition, other cookies may be used with your consent to analyze site usage, improve the user experience and for advertising. For more information, please review your options. By visiting our website, you agree to our processing of information as described in IBM’sprivacy statement. To provide a smooth navigation, your cookie preferences will be shared across the IBM web domains listed here.
Publication
SIOPT
Paper
On the polyhedrality of closures of multibranch split sets and other polyhedra with bounded max-facet-width
Abstract
For a fixed integer t > 0, we say that a t-branch split set (the union of t split sets) is dominated by another one on a polyhedron P if all cuts for P obtained from the first t-branch split set are implied by cuts obtained from the second one. We prove that given a rational polyhedron P, any arbitrary family of t-branch split sets has a finite subfamily such that each element of the family is dominated on P by an element from the subfamily. The result for t = 1 (i.e., for split sets) was proved by Averkov [Discrete Optim., 9 (2012), pp. 209-215] extending results in Andersen, Cornuéjols, and Li [Math. Program, 102 (2005), pp. 457-493]. Our result implies that the closure of P with respect to any family of t-branch split sets is a polyhedron. We extend this result by replacing split sets with bounded max-facet-width polyhedra as building blocks, and show that any family of t-branch sets where each set is the union of t polyhedral sets that have bounded max-facet-width has a finite dominating subfamily with respect to P. This latter result generalizes a result of Averkov [Discrete Optim., 9 (2012), pp. 209-215] on bounded max-facet-width polyhedra (corresponding to the case t = 1).