We study the uniqueness of minimal liftings of cut-generating functions obtained from maximal lattice-free polyhedra. We prove a basic invariance property of unique minimal liftings for general maximal lattice-free polyhedra. This generalizes a previous result by Basu et al. (Math Oper Res 37(2):346–355, 2012) for simplicial maximal lattice-free polytopes, thus completely settling this fundamental question about lifting for maximal lattice-free polyhedra. We further give a very general iterative construction to get maximal lattice-free polyhedra with the unique-lifting property in arbitrary dimensions. This single construction not only obtains all previously known polyhedra with the unique-lifting property, but goes further and vastly expands the known list of such polyhedra. Finally, we extend characterizations from Basu et al. (2012) about lifting with respect to maximal lattice-free simplices to more general polytopes. These nontrivial generalizations rely on a number of results from discrete geometry, including the Venkov-Alexandrov-McMullen theorem on translative tilings and characterizations of zonotopes in terms of central symmetry of their faces.
We study the problem of approximating the corner polyhedron using intersection cuts derived from families of lattice-free sets. In particular, we look at the problem of characterizing families that approximate the corner polyhedron up to a constant factor in fixed dimension n (the constant depends on n). The literature already contains several results in this direction. In this paper, we use the maximum number of facets of a lattice-free set in a family as a measure of its complexity and precisely characterize the level of complexity of a family required for constant factor approximations. As one of the main results, we show that for each natural number n, a corner polyhedron for n integer variables is approximated by intersection cuts from lattice-free sets with at most i facets up to a constant factor (depending only on n) if i>2n−1 and that no such approximation is possible if i≤2n−1. When the approximation factor is allowed to depend on the denominator of the underlying fractional point of the corner polyhedron, we show that the threshold is i>n versus i≤n. The tools introduced for proving such results are of independent interest for studying intersection cuts.
We study the uniqueness of minimal liftings of cut generating functions obtained from maximal lattice-free polytopes. We prove a basic invariance property of unique minimal liftings for general maximal lattice-free polytopes. This generalizes a previous result by Basu, Cornuéjols and Köppe [3] for simplicial maximal lattice-free polytopes, thus completely settling this fundamental question about lifting. We also extend results from [3] for minimal liftings in maximal lattice-free simplices to more general polytopes. These nontrivial generalizations require the use of deep theorems from discrete geometry and geometry of numbers, such as the Venkov-Alexandrov-McMullen theorem on translative tilings, and McMullen’s characterization of zonotopes.