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

DOI10.48550/ARXIV.1010.1077MaRDI QIDQ161306zbMATH OpenOpenAlexFDO

Authors Gennadiy Averkov, Christian Wagner, Robert Weismantel

Publication date 6 October 2010

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

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

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)

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.

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

Cited in

(38)

• On finitely generated closures in the theory of cutting planes
• 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
• On maximal \(S\)-free convex sets
• 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
• 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
• Approximation of corner polyhedra with families of intersection cuts
• 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
• Inequalities for the lattice width of lattice-free convex sets in the plane
• Classification of triples of lattice polytopes with a given mixed volume
• Polytopes.Lattice.ExceptionalMaximalHollow
• Lifting properties of maximal lattice-free polyhedra
• Size bounds and classification results for integral polyhedra with at most one interior integral point
• The finiteness threshold width of lattice polytopes
• On the polyhedrality of cross and quadrilateral closures
• A geometric approach to cut-generating functions
• Lattice zonotopes of degree 2
• A proof of Lovász's theorem on maximal lattice-free sets
• Relaxations of mixed integer sets from lattice-free polyhedra
• Relaxations of mixed integer sets from lattice-free polyhedra
• On convergence in mixed integer programming
• Cracked polytopes and Fano toric complete intersections
• Classification of empty lattice 4-simplices of width larger than 2
• 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
• An analysis of mixed integer linear sets based on lattice point free convex sets

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)