Lattice closures of polyhedra

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.

Article

Download

View PDF