Lattice closures of polyhedra

• 成果类型: Article
• 署名作者: Dash, Sanjeeb; Gunluk, Oktay; Moran R, Diego A.
• 署名单位: International Business Machines (IBM); IBM USA; Universidad Adolfo Ibanez
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-019-01379-y
• 发表日期: 2020
• 页码: 119-147
• 关键词: sets

摘要

Given P. Rn, a mixed-integer set PI = P n (Zt x Rn-t), and a k-tuple of ndimensional integral vectors (p1,..., pk) 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 pT 1 x,..., pT k x 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.