Lifting properties of maximal lattice-free polyhedra
From MaRDI portal
(Redirected from Publication:896280)
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'ejols and K"oppe~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.
Recommendations
Cites work
- scientific article; zbMATH DE number 3555734 (Why is no real title available?)
- scientific article; zbMATH DE number 1182906 (Why is no real title available?)
- scientific article; zbMATH DE number 4119933 (Why is no real title available?)
- scientific article; zbMATH DE number 236540 (Why is no real title available?)
- scientific article; zbMATH DE number 5209739 (Why is no real title available?)
- A \((k+1)\)-slope theorem for the \(k\)-dimensional infinite group relaxation
- A geometric perspective on lifting
- A proof of Lovász's theorem on maximal lattice-free sets
- An observation on the structure of production sets with indivisibilities
- Composite lifting of group inequalities and an application to two-row mixing inequalities
- Convex Analysis
- Convex and Discrete Geometry
- Convexity in cristallographical lattices
- Integer Programming with a Fixed Number of Variables
- Lectures on Polytopes
- Maximal lattice-free convex sets in linear subspaces
- Maximal lattice-free polyhedra: finiteness and an explicit description in dimension three
- On finitely generated closures in the theory of cutting planes
- Polytopes with centrally symmetric faces
- Polytopes with centrally symmetric facets
- Some continuous functions related to corner polyhedra
- Some continuous functions related to corner polyhedra, II
- Some polyhedra related to combinatorial problems
- Two row mixed-integer cuts via lifting
- Unique lifting of integer variables in minimal inequalities
- Unique minimal liftings for simplicial polytopes
Cited in
(18)- Computing the covering radius of a polytope with an application to lonely runners
- A geometric approach to cut-generating functions
- Tight bounds on discrete quantitative Helly numbers
- Lifting convex inequalities for bipartite bilinear programs
- Lifting convex inequalities for bipartite bilinear programs
- Maximal \(S\)-free convex sets and the Helly number
- Unique minimal liftings for simplicial polytopes
- Hollow polytopes of large width
- Notions of Maximality for Integral Lattice-Free Polyhedra: The Case of Dimension Three
- On the unique-lifting property
- Nonunique lifting of integer variables in minimal inequalities
- Can cut-generating functions be good and efficient?
- The covering radius and a discrete surface area for non-hollow simplices
- Theoretical challenges towards cutting-plane selection
- The strength of multi-row aggregation cuts for sign-pattern integer programs
- scientific article; zbMATH DE number 3885658 (Why is no real title available?)
- The (not so) trivial lifting in two dimensions
- Operations that preserve the covering property of the lifting region
This page was built for publication: Lifting properties of maximal lattice-free polyhedra
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q896280)
