TY - CHAP A1 - Averkov, Gennadiy A1 - Basu, Amitabh ED - Lee, John ED - Vygen, Jens T1 - On the unique-lifting property T2 - Integer Programming and Combinatorial Optimization N2 - We study the uniqueness of minimal liftings of cut generating functions obtained from maximal lattice-free polytopes. We prove a basic invariance property of unique minimal liftings for general maximal lattice-free polytopes. This generalizes a previous result by Basu, Cornuéjols and Köppe [3] for simplicial maximal lattice-free polytopes, thus completely settling this fundamental question about lifting. We also extend results from [3] for minimal liftings in maximal lattice-free simplices to more general polytopes. These nontrivial generalizations require the use of deep theorems from discrete geometry and geometry of numbers, such as the Venkov-Alexandrov-McMullen theorem on translative tilings, and McMullen’s characterization of zonotopes. KW - Integer Point, Relative Interior, Tile Space, Unimodular Transformation, Nontrivial Generalization Y1 - 2014 SN - 978-3-319-07557-0 SN - 978-3-319-07556-3 U6 - https://doi.org/10.1007/978-3-319-07557-0_7 VL - 2014 SP - 76 EP - 87 PB - Springer ER - TY - GEN A1 - Averkov, Gennadiy A1 - Basu, Amitabh T1 - Lifting properties of maximal lattice-free polyhedra T2 - Mathematical Programming N2 - 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 et al. (Math Oper Res 37(2):346–355, 2012) 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 Basu et al. (2012) 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. Y1 - 2015 UR - https://link.springer.com/article/10.1007/s10107-015-0865-6 U6 - https://doi.org/10.1007/s10107-015-0865-6 SN - 0025-5610 VL - 154 IS - 1-2 SP - 81 EP - 111 ER - TY - CHAP A1 - Averkov, Gennadiy A1 - Basu, Amitabh A1 - Paat, Joseph T1 - Approximation of Corner Polyhedra with Families of Intersection Cuts T2 - Integer Programming and Combinatorial Optimization N2 - We study the problem of approximating the corner polyhedron using intersection cuts derived from families of lattice-free sets. In particular, we look at the problem of characterizing families that approximate the corner polyhedron up to a constant factor in fixed dimension n (the constant depends on n). The literature already contains several results in this direction. In this paper, we use the maximum number of facets of a lattice-free set in a family as a measure of its complexity and precisely characterize the level of complexity of a family required for constant factor approximations. As one of the main results, we show that for each natural number n, a corner polyhedron for n integer variables is approximated by intersection cuts from lattice-free sets with at most i facets up to a constant factor (depending only on n) if i>2n−1 and that no such approximation is possible if i≤2n−1. When the approximation factor is allowed to depend on the denominator of the underlying fractional point of the corner polyhedron, we show that the threshold is i>n versus i≤n. The tools introduced for proving such results are of independent interest for studying intersection cuts. KW - Relative Strength Gauge Function Constant Factor Approximation Recession Cone Standard Basis Vector Y1 - 2017 UR - https://link.springer.com/chapter/10.1007%2F978-3-319-59250-3_5 SN - 978-3-319-59249-7 SN - 978-3-319-59250-3 U6 - https://doi.org/10.1007/978-3-319-59250-3_5 SP - 51 EP - 62 PB - Springer Nature Switzerland AG. Part of Springer Nature. CY - Schweiz ER -