Lifting properties of maximal lattice-free polyhedra

Gennadiy Averkov, Amitabh Basu

Abstract: 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, Cornuéjols and Köppe 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 previous work 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.

Introduction

In Mixed-Integer Linear Programming (MILP), solvers use "cutting planes" (cuts) to prune the search space and find optimal integer solutions faster. A powerful way to generate these cuts is through cut-generating functions derived from maximal lattice-free polyhedra—shapes that contain no integer points in their interior and cannot be enlarged without capturing one.

A key step in this process is lifting, which extends a cut defined on a subset of variables to the entire problem. Ideally, we want a unique minimal lifting, as this provides a single, "best" valid inequality that is easy to compute. Previously, researchers only knew that this uniqueness was a stable property for a very specific class of shapes (simplices). This paper addresses two major gaps:

  1. Is the uniqueness of lifting a property of the polyhedron itself, or does it depend on the specific "base point" ($f$) chosen inside it?
  2. How can we construct new, complex polyhedra that are guaranteed to have this unique lifting property?
Illustration of a cut-generating function $\pi$ and its lifting $\psi$ for a maximal lattice-free set $B$ and point $f$.

Methodology

The authors employ a mix of convex analysis and discrete geometry. Key techniques include:

  • Lifting Region Analysis: They study the "lifting region" $R(B, f)$, a geometric structure associated with a polyhedron $B$ and a point $f$. They prove that the volume of this region modulo the integer lattice $\mathbb{Z}^n$ is an affine function of $f$.
  • The Coproduct Operation: They introduce a geometric operation called the "coproduct" (essentially a way to join two lower-dimensional polytopes into a higher-dimensional one). They prove that if the building blocks have the unique lifting property, the resulting higher-dimensional shape does too.
  • Discrete Geometry Theorems: To characterize these shapes, they utilize deep results like the Venkov-Alexandrov-McMullen theorem (which relates space-tiling shapes to central symmetry) and McMullen’s characterization of zonotopes.

Key Insights and Ideas

  • Intrinsic Invariance: The most significant "aha moment" is the proof that unique lifting is invariant. If a maximal lattice-free polyhedron has a unique minimal lifting for one interior point, it has it for all of them. This elevates the property from a situational occurrence to a fundamental classification of the polyhedron.
  • Tiling and Symmetry: The authors reveal a deep connection between unique lifting and the ability of a shape's "lifting region" to tile space. They show that unique lifting is intimately related to how facets of the polyhedron interact with the integer lattice.
  • The "Lego" Approach to Polyhedra: The coproduct construction acts like a set of rules for "Lego bricks." By showing that the unique lifting property is preserved under this operation, they provide a recursive recipe to generate infinitely many valid cut-generating polyhedra, moving far beyond the simple triangles and tetrahedra used in earlier literature.

Key Results

  • General Invariance Theorem: They successfully generalized the invariance of unique minimal liftings from simplicial polytopes to all maximal lattice-free polyhedra.
  • Volume Formula: They developed a significantly more elegant and shorter proof for calculating the volume of lifting regions modulo $\mathbb{Z}^n$ compared to previous inclusion-exclusion methods.
  • New Classes of Polyhedra: Using the coproduct method, they showed that all previously known unique-lifting polyhedra (like Type 1 triangles) are just special cases of their broader construction.
  • The Cube Exception: They demonstrated that while the coproduct is powerful, it doesn't capture everything. For example, they proved that $n$-dimensional cubes (in odd dimensions $\ge 3$) have the unique lifting property under certain lattices but cannot be formed via a coproduct.

Limitations and Future Work

The paper is primarily theoretical. While it provides the "blueprints" for unique-lifting polyhedra, it does not provide a computational library or an algorithmic framework for selecting the optimal polyhedron for a specific MILP instance.

The authors note that providing an explicit, exhaustive description of all $n$-dimensional maximal lattice-free polyhedra with unique lifting remains a "challenging problem" for dimensions $n \ge 3$. Future work could involve bridging these geometric insights with practical solver implementations to see which of these newly discovered shapes produce the most effective cuts in real-world optimization problems.

Summary updated

Abstract

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, Cornuéjols and Köppe~\cite{bcm} for {\em 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~\cite{bcm} 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.
BibTeX
@inproceedings{averkov2015lifting,
  author = {Gennadiy Averkov and Amitabh Basu},
  title = {{Lifting properties of maximal lattice-free polyhedra}},
  booktitle = {Math. Program},
  year = {2015},
  url = {https://openreview.net/forum?id=asZFZ5LmbF},
}
Figure