Notions of Maximality for Integral Lattice-Free Polyhedra: The Case of Dimension Three

Lattice-free sets and their applications for cutting-plane methods in mixed-integer optimization have been studied in recent literature. The family of all integral lattice-free polyhedra that are not properly contained in another integral lattice-free polyhedron has been of particular interest. We call these polyhedra ℤ^d-maximal.

For fixed d, the family of ℤ^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. This is a challenging task already for small dimensions.

In contrast, the subfamily of all integral lattice-free polyhedra that are not properly contained in any other lattice-free set, which we call ℝ^d-maximal lattice-free polyhedra, allow a rather simple geometric characterization. Hence, the question was raised for which dimensions the notions of ℤ^d-maximality and ℝ^d-maximality are equivalent. This was known to be the case for dimensions one and two. On the other hand, for d ≥ 4 there exist integral lattice-free polyhedra that are ℤ^d-maximal but not ℝ^d-maximal. We consider the remaining case d = 3 and prove that for integral lattice-free polyhedra the notions of ℝ³-maximality and ℤ³-maximality are equivalent. This allows to complete the classification of all ℤ³-maximal integral lattice-free polyhedra.