IDEAS home Printed from https://ideas.repec.org/a/inm/ormoor/v42y2017i4p1035-1062.html
   My bibliography  Save this article

Notions of Maximality for Integral Lattice-Free Polyhedra: The Case of Dimension Three

Author

Listed:
  • Gennadiy Averkov

    (Otto-von-Guericke-Universität Magdeburg, 39106 Magdeburg, Germany)

  • Jan Krümpelmann

    (Otto-von-Guericke-Universität Magdeburg, 39106 Magdeburg, Germany)

  • Stefan Weltge

    (ETH Zürich, 8092 Zürich, Switzerland)

Abstract

Lattice-free sets and their applications for cutting-plane methods in mixed-integer optimization have been studied in recent literature. The family of all integral lattice-free polyhedra that are not properly contained in another integral lattice-free polyhedron has been of particular interest. We call these polyhedra ℤ d -maximal. For fixed d , the family of ℤ d -maximal integral lattice-free polyhedra is finite up to unimodular equivalence. In view of possible applications in cutting-plane theory, one would like to have a classification of this family. This is a challenging task already for small dimensions. In contrast, the subfamily of all integral lattice-free polyhedra that are not properly contained in any other lattice-free set, which we call ℝ d -maximal lattice-free polyhedra, allow a rather simple geometric characterization. Hence, the question was raised for which dimensions the notions of ℤ d -maximality and ℝ d -maximality are equivalent. This was known to be the case for dimensions one and two. On the other hand, for d ≥ 4 there exist integral lattice-free polyhedra that are ℤ d -maximal but not ℝ d -maximal. We consider the remaining case d = 3 and prove that for integral lattice-free polyhedra the notions of ℝ 3 -maximality and ℤ 3 -maximality are equivalent. This allows to complete the classification of all ℤ 3 -maximal integral lattice-free polyhedra.

Suggested Citation

  • Gennadiy Averkov & Jan Krümpelmann & Stefan Weltge, 2017. "Notions of Maximality for Integral Lattice-Free Polyhedra: The Case of Dimension Three," Mathematics of Operations Research, INFORMS, vol. 42(4), pages 1035-1062, November.
    • Handle: RePEc:inm:ormoor:v:42:y:2017:i:4:p:1035-1062
    DOI: 10.1287/moor.2016.0836
    as

    Download full text from publisher

    File URL: https://doi.org/10.1287/moor.2016.0836
    Download Restriction: no
    File URL: https://libkey.io/10.1287/moor.2016.0836?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    References listed on IDEAS

    as
    1. Benjamin Nill & Günter M. Ziegler, 2011. "Projecting Lattice Polytopes Without Interior Lattice Points," Mathematics of Operations Research, INFORMS, vol. 36(3), pages 462-467, August.
    2. Gennadiy Averkov & Christian Wagner & Robert Weismantel, 2011. "Maximal Lattice-Free Polyhedra: Finiteness and an Explicit Description in Dimension Three," Mathematics of Operations Research, INFORMS, vol. 36(4), pages 721-742, November.
    3. DEY, Santanu S. & WOLSEY, Laurence A., 2010. "Two row mixed-integer cuts via lifting," LIDAM Reprints CORE 2254, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    4. Herbert E. Scarf, 2008. "Integral Polyhedra in Three Space," Palgrave Macmillan Books, in: Zaifu Yang (ed.), Herbert Scarf’s Contributions to Economics, Game Theory and Operations Research, chapter 4, pages 69-104, Palgrave Macmillan.
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Alberto Del Pia & Robert Weismantel, 2016. "Relaxations of mixed integer sets from lattice-free polyhedra," Annals of Operations Research, Springer, vol. 240(1), pages 95-117, May.
    2. Gennadiy Averkov & Christian Wagner & Robert Weismantel, 2011. "Maximal Lattice-Free Polyhedra: Finiteness and an Explicit Description in Dimension Three," Mathematics of Operations Research, INFORMS, vol. 36(4), pages 721-742, November.
    3. Amitabh Basu & Pierre Bonami & Gérard Cornuéjols & François Margot, 2011. "Experiments with Two-Row Cuts from Degenerate Tableaux," INFORMS Journal on Computing, INFORMS, vol. 23(4), pages 578-590, November.
    4. Sercan Yıldız & Gérard Cornuéjols, 2016. "Cut-Generating Functions for Integer Variables," Mathematics of Operations Research, INFORMS, vol. 41(4), pages 1381-1403, November.
    5. Egon Balas & Thiago Serra, 2020. "When Lift-and-Project Cuts Are Different," INFORMS Journal on Computing, INFORMS, vol. 32(3), pages 822-834, July.
    6. Santanu S. Dey & Quentin Louveaux, 2011. "Split Rank of Triangle and Quadrilateral Inequalities," Mathematics of Operations Research, INFORMS, vol. 36(3), pages 432-461, August.
    7. Sönke Behrends & Anita Schöbel, 2020. "Generating Valid Linear Inequalities for Nonlinear Programs via Sums of Squares," Journal of Optimization Theory and Applications, Springer, vol. 186(3), pages 911-935, September.
    8. Benjamin Nill & Günter M. Ziegler, 2011. "Projecting Lattice Polytopes Without Interior Lattice Points," Mathematics of Operations Research, INFORMS, vol. 36(3), pages 462-467, August.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:inm:ormoor:v:42:y:2017:i:4:p:1035-1062. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Chris Asher (email available below). General contact details of provider: https://edirc.repec.org/data/inforea.html .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.