Lifting properties of maximal lattice-free polyhedra
From MaRDI portal
Publication:896280
DOI10.1007/S10107-015-0865-6zbMATH Open1328.90084arXiv1404.7421OpenAlexW1977146361MaRDI QIDQ896280FDOQ896280
Authors: Gennadiy Averkov, Amitabh Basu 
Publication date: 9 December 2015
Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)
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.
Full work available at URL: https://arxiv.org/abs/1404.7421
Recommendations
Integer programming (90C10) Special polytopes (linear programming, centrally symmetric, etc.) (52B12) Lattices and convex bodies in (n) dimensions (aspects of discrete geometry) (52C07) Mixed integer programming (90C11) Tilings in (n) dimensions (aspects of discrete geometry) (52C22)
Cites Work
- Title not available (Why is that?)
- Title not available (Why is that?)
- Convex and Discrete Geometry
- Convex Analysis
- Maximal lattice-free polyhedra: finiteness and an explicit description in dimension three
- Lectures on Polytopes
- Some polyhedra related to combinatorial problems
- Two row mixed-integer cuts via lifting
- A \((k+1)\)-slope theorem for the \(k\)-dimensional infinite group relaxation
- Unique minimal liftings for simplicial polytopes
- Integer Programming with a Fixed Number of Variables
- A geometric perspective on lifting
- Maximal lattice-free convex sets in linear subspaces
- Unique lifting of integer variables in minimal inequalities
- Title not available (Why is that?)
- Some continuous functions related to corner polyhedra
- Some continuous functions related to corner polyhedra, II
- Title not available (Why is that?)
- Convexity in cristallographical lattices
- On finitely generated closures in the theory of cutting planes
- Title not available (Why is that?)
- Polytopes with centrally symmetric facets
- Polytopes with centrally symmetric faces
- An observation on the structure of production sets with indivisibilities
- Composite lifting of group inequalities and an application to two-row mixing inequalities
- A proof of Lovász's theorem on maximal lattice-free sets
Cited In (18)
- Hollow polytopes of large width
- The (not so) trivial lifting in two dimensions
- Nonunique lifting of integer variables in minimal inequalities
- Lifting convex inequalities for bipartite bilinear programs
- Lifting convex inequalities for bipartite bilinear programs
- Maximal \(S\)-free convex sets and the Helly number
- Can Cut-Generating Functions Be Good and Efficient?
- Theoretical challenges towards cutting-plane selection
- On the unique-lifting property
- Operations that preserve the covering property of the lifting region
- Tight bounds on discrete quantitative Helly numbers
- A geometric approach to cut-generating functions
- Unique minimal liftings for simplicial polytopes
- The covering radius and a discrete surface area for non-hollow simplices
- The strength of multi-row aggregation cuts for sign-pattern integer programs
- Notions of Maximality for Integral Lattice-Free Polyhedra: The Case of Dimension Three
- Computing the covering radius of a polytope with an application to lonely runners
- Title not available (Why is that?)
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)
