Optimization Online


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

Diego Moran (diego.moran***at***uai.cl)
Oktay Gunluk (gunluk***at***us.ibm.com)
Sanjeeb Dash (sanjeebd***at***us.ibm.com )

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

Keywords: Integer Programming, Cutting planes, Closure, Polyhedrality

Category 1: Integer Programming ((Mixed) Integer Linear Programming )


Download: [PDF]

Entry Submitted: 08/02/2016
Entry Accepted: 08/02/2016
Entry Last Modified: 08/02/2016

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society