Maximal Lattice‐Free Polyhedra: Finiteness and an Explicit Description in Dimension Three

A convex set with nonempty interior is maximal lattice‐free if it is inclusion maximal with respect to the property of not containing integer points in its interior. Maximal lattice‐free convex sets are known to be polyhedra. The precision of a rational polyhedron P in ℝ^d is the smallest natural number s such that sP is an integral polyhedron. In this paper we show that, up to affine mappings preserving ℤ^d, the number of maximal lattice‐free rational polyhedra of a given precision s is finite. Furthermore, we present the complete list of all maximal lattice‐free integral polyhedra in dimension three. Our results are motivated by recent research on cutting plane theory in mixed‐integer linear optimization.