On the polyhedrality of closures of multi-branch split sets and other polyhedra with bounded max-facet-width

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 (2012) extending results in Andersen, Cornu\’ejols and Li (2005). 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 polyhedral sets with bounded max-facet-width as building blocks and show that any family of such sets also has a finite dominating subfamily. This result generalizes a result of Averkov (2012) on bounded max-facet-width polyhedra.

Article

Download

View PDF