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).