Maximal lattice-free polyhedra: finiteness and an explicit description in dimension three

DOI10.48550/ARXIV.1010.1077zbMATH Open1246.90107arXiv1010.1077OpenAlexW2021567595MaRDI QIDQ161306FDOQ161306

Authors: Gennadiy Averkov, Christian Wagner, Robert Weismantel 

Publication date: 6 October 2010

Published in: Mathematics of Operations Research (Search for Journal in Brave)

Abstract: 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 $mathbb{R}^d$ is the smallest integer $s$ such that $sP$ is an integral polyhedron. In this paper we show that, up to affine mappings preserving $mathbb{Z}^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.

Full work available at URL: https://arxiv.org/abs/1010.1077

Recommendations

• Notions of Maximality for Integral Lattice-Free Polyhedra: The Case of Dimension Three
• Maximal lattice-free convex sets in linear subspaces
• An analysis of mixed integer linear sets based on lattice point free convex sets
• A proof of Lovász's theorem on maximal lattice-free sets
• Minimal inequalities for an infinite relaxation of integer programs

zbMATH Keywords

cutting plane integral polyhedron maximal lattice-free set mixed-integer programming

Mathematics Subject Classification ID

Integer programming (90C10) Lattice polytopes in convex geometry (including relations with commutative algebra and algebraic geometry) (52B20) Lattices and convex bodies in (n) dimensions (aspects of discrete geometry) (52C07) Mixed integer programming (90C11)

Cited In (36)

• Hollow polytopes of large width
• Difference between families of weakly and strongly maximal integral lattice-free polytopes
• On the fine interior of three-dimensional canonical Fano polytopes
• The triangle closure is a polyhedron
• Families of lattice polytopes of mixed degree one
• On base loci of higher fundamental forms of toric varieties
• Constructing lattice-free gradient polyhedra in dimension two
• Complexity of linear relaxations in integer programming
• Lattice-free sets, multi-branch split disjunctions, and mixed-integer programming
• Minimal inequalities for an infinite relaxation of integer programs
• Maximal lattice-free convex sets in linear subspaces
• Local optimality of Zaks-Perles-Wills simplices
• Largest integral simplices with one interior integral point: solution of Hensley's conjecture and related results
• Classification of triples of lattice polytopes with a given mixed volume
• Inequalities for the lattice width of lattice-free convex sets in the plane
• Lifting properties of maximal lattice-free polyhedra
• The finiteness threshold width of lattice polytopes
• Lattice zonotopes of degree 2
• A geometric approach to cut-generating functions
• On the polyhedrality of cross and quadrilateral closures
• Constructing Lattice-Free Gradient Polyhedra in Dimension Two
• Relaxations of mixed integer sets from lattice-free polyhedra
• Relaxations of mixed integer sets from lattice-free polyhedra
• Approximation of Corner Polyhedra with Families of Intersection Cuts
• On convergence in mixed integer programming
• Classification of empty lattice 4-simplices of width larger than 2
• Cracked polytopes and Fano toric complete intersections
• The complete classification of empty lattice 4-simplices
• Notions of Maximality for Integral Lattice-Free Polyhedra: The Case of Dimension Three
• Generating valid linear inequalities for nonlinear programs via sums of squares
• Classification of empty lattice 4-simplices of width larger than two
• Enumeration of lattice polytopes by their volume
• Lattice 3-polytopes with few lattice points
• Polytopes.Lattice.ExceptionalMaximalHollow
• An analysis of mixed integer linear sets based on lattice point free convex sets
• On finitely generated closures in the theory of cutting planes

This page was built for publication: Maximal lattice-free polyhedra: finiteness and an explicit description in dimension three

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q161306)