  


Lattice closures of polyhedra
Sanjeeb Dash (sanjeebdus.ibm.com) Abstract: Given $P\subset\R^n$, a mixedinteger set $P^I=P\cap (\Z^{t}\times\R^{nt}$), and a $k$tuple of $n$dimensional integral vectors $(\pi_1, \ldots, \pi_k)$ where the last $nt$ 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 mixedinteger 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, fulldimensional, convex latticefree 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 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  