-

 

 

 




Optimization Online





 

Lattice closures of polyhedra

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

Abstract: Given $P\subset\R^n$, a mixed integer set $P^I=P\cap (\Z^{t}\times\R^{n-t}$), and a $k$-tuple of $n$-dimensional integral vectors $(\pi_1, \ldots, \pi_k)$ where the last $n-t$ entries of each vector is zero, we consider the relaxation of $P^I$ obtained by taking the convex hull of points $x$ in $P$ for which $ \pi_1^Tx,\ldots,\pi^T_kx$ are integral. We then define the $k$-dimensional lattice closure of $P^I$ to be the intersection of all such relaxations obtained from $k$-tuples of $n$-dimensional vectors. When $P$ is a rational polyhedron, we show that given any collection of such $k$-tuples, there is a finite subcollection that gives the same closure; more generally, we show that any $k$-tuple is dominated by another $k$-tuple coming from the finite subcollection. The $k$-dimensional lattice closure contains the convex hull of $P^I$ and is equal to the split closure when $k=1$. Therefore, a result of Cook, Kannan, and Schrijver (1990) implies that when $P$ is a rational polyhedron, the $k$-dimensional lattice closure is a polyhedron for $k=1$ and our finiteness result extends this to all $k\ge2$. We also construct a polyhedral mixed-integer set with $n$ integer variables and one continuous variable such that for any $k < n$, finitely many iterations of the $k$-dimensional lattice closure do not give the convex hull of the set. Our result implies that $t$-branch split cuts cannot give the convex hull of the set, nor can valid inequalities from unbounded, full-dimensional, convex lattice-free sets.

Keywords: integer programming, cutting planes, split cuts, split closure, lattice closure

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

Category 2: Integer Programming (Cutting Plane Approaches )

Citation:

Download: [PDF]

Entry Submitted: 10/30/2016
Entry Accepted: 10/31/2016
Entry Last Modified: 04/11/2017

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
Mathematical Optimization Society