TY - JOUR

T1 - Lattice closures of polyhedra

AU - Dash, Sanjeeb

AU - Günlük, Oktay

AU - Morán R, Diego A.

N1 - Publisher Copyright:
© 2019, Springer-Verlag GmbH Germany, part of Springer Nature and Mathematical Optimization Society.

PY - 2020/5/1

Y1 - 2020/5/1

N2 - Given P⊂ Rn, a mixed-integer set PI= P∩ (Zt× Rn - 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 PI obtained by taking the convex hull of points x in P for which π1Tx,…,πkTx are integral. We then define the k-dimensional lattice closure of PI 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 PI 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.

AB - Given P⊂ Rn, a mixed-integer set PI= P∩ (Zt× Rn - 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 PI obtained by taking the convex hull of points x in P for which π1Tx,…,πkTx are integral. We then define the k-dimensional lattice closure of PI 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 PI 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.

UR - http://www.scopus.com/inward/record.url?scp=85063209316&partnerID=8YFLogxK

U2 - 10.1007/s10107-019-01379-y

DO - 10.1007/s10107-019-01379-y

M3 - Article

AN - SCOPUS:85063209316

VL - 181

SP - 119

EP - 147

JO - Mathematical Programming

JF - Mathematical Programming

SN - 0025-5610

IS - 1

ER -