Lattice closures of polyhedra

• Published in: Mathematical programming 2020-05, Vol.181 (1), p.119-147
• Main Authors: Dash, Sanjeeb, Günlük, Oktay, Morán R., Diego A.
• Format: Article
• Language: English
• Subjects: Calculus of Variations and Optimal Control; Optimization; Closures; Combinatorics; Continuity (mathematics); Convexity; Full Length Paper; Game theory; Hulls; Integers; Integrals; Mathematical and Computational Physics; Mathematical Methods in Physics; Mathematics; Mathematics and Statistics; Mathematics of Computing; Numerical Analysis; Polyhedra; Theoretical
• ISSN: 0025-5610; 1436-4646
• DOI: 10.1007/s10107-019-01379-y

Given P ⊂ R n , a mixed-integer set P I = P ∩ ( Z t × R n - t ), and a k -tuple of n -dimensional integral vectors ( π 1 , … , π 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 π 1 T x , … , π k T x 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 et al. (Math Program 47:155–174, 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 ≥ 2 . 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.