- Lattice closures of polyhedra Sanjeeb Dash (sanjeebdus.ibm.com) Oktay Gunluk (gunlukus.ibm.com) Diego Moran (diego.moranuai.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/2016Entry Accepted: 10/31/2016Entry Last Modified: 09/20/2018Modify/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 Optimization Online is supported by the Mathematical Optmization Society.