  


On the polyhedrality of closures of multibranch split sets and other polyhedra with bounded maxfacetwidth
Diego Moran (diego.moranuai.cl) 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 (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 maxfacetwidth 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 maxfacetwidth polyhedra. Keywords: Integer Programming, Cutting planes, Closure, Polyhedrality Category 1: Integer Programming ((Mixed) Integer Linear Programming ) Citation: Download: [PDF] Entry Submitted: 08/02/2016 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  