Lattice Closures of Polyhedra

We define the k-dimensional lattice closure of a polyhedral mixed-integer set to be the intersection of the convex hulls of all possible relaxations of the set obtained by choosing up to k integer vectors and requiring to be integral. We show that given any collection of such relaxations, finitely many of them dominate the rest. The k-dimensional lattice closure is equal to the split closure when k = 1. Therefore the k-dimensional lattice closure of a rational polyhedral mixed-integer set is a polyhedron when k = 1 and our domination result extends this to all k 2. We also construct a polyhedral mixed-integer set with n > k integer variables such that finitely many iterations of the k-dimensional lattice closure do not give the integer hull. In addition, we use this result to show that t-branch split cuts cannot give the integer hull, nor can valid inequalities from unbounded, full-dimensional, convex lattice-free sets.

By: Sanjeeb Dash, Oktay Günlük, Diego A. Morán

Published in: RC25634 in 2016


This Research Report is available. This report has been submitted for publication outside of IBM and will probably be copyrighted if accepted for publication. It has been issued as a Research Report for early dissemination of its contents. In view of the transfer of copyright to the outside publisher, its distribution outside of IBM prior to publication should be limited to peer communications and specific requests. After outside publication, requests should be filled only by reprints or legally obtained copies of the article (e.g., payment of royalties). I have read and understand this notice and am a member of the scientific community outside or inside of IBM seeking a single copy only.


Questions about this service can be mailed to .