Notions of maximality for integral lattice-free polyhedra: the case of dimension three

preprint2015arXivOpen access

Abstract

Lattice-free sets (convex subsets of Rd\mathbb{R}^d without interior integer points) and their applications for cutting-plane methods in mixed-integer optimization have been studied in recent literature. Notably, the family of all integral lattice-free polyhedra which are not properly contained in another integral lattice-free polyhedron has been of particular interest. We call these polyhedra Zd\mathbb{Z}^d-maximal. It is known that, for fixed dd, the family Zd\mathbb{Z}^d-maximal integral lattice-free polyhedra is finite up to unimodular equivalence. In view of possible applications in cutting-plane theory, one would like to have a classification of this family. However, this turns out to be a challenging task already for small dimensions. In contrast, the subfamily of all integral lattice-free polyhedra which are not properly contained in any other lattice-free set, which we call Rd\mathbb{R}^d-maximal lattice-free polyhedra, allow a rather simple geometric characterization. Hence, the question was raised for which dimensions the notions of Zd\mathbb{Z}^d-maximality and Rd\mathbb{R}^d-maximality are equivalent. This was known to be the case for dimensions one and two. On the other hand, Nill and Ziegler (2011) showed that for dimension d≥4d \ge 4, there exist polyhedra which are Zd\mathbb{Z}^d-maximal but not Rd\mathbb{R}^d-maximal. In this article, we consider the remaining case d=3d = 3 and prove that for integral polyhedra the notions of R3\mathbb{R}^3-maximality and Z3\mathbb{Z}^3-maximality are equivalent. As a consequence, the classification of all R3\mathbb{R}^3-maximal integral polyhedra by Averkov, Wagner and Weismantel (2011) contains all Z3\mathbb{Z}^3-maximal integral polyhedra.

Explore this paper’s authors, topics and related work.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Reviews 0

Write a reviewWrite

No reviews yet.

Discussion 0

Add a commentWrite

No comments yet.