IDEAS home Printed from https://ideas.repec.org/a/inm/oropre/v59y2011i3p569-577.html
   My bibliography  Save this article

A Geometric Perspective on Lifting

Author

Listed:
  • Michele Conforti

    (Dipartimento di Matematica Pura ed Applicata, Università di Padova, 35121 Padova, Italy)

  • Gérard Cornuéjols

    (Tepper School of Business, Carnegie Mellon University, Pittsburgh, Pennsylvania 15213)

  • Giacomo Zambelli

    (London School of Economics and Political Sciences, London WC2A 2AE, United Kingdom)

Abstract

Recently it has been shown that minimal inequalities for a continuous relaxation of mixed-integer linear programs are associated with maximal lattice-free convex sets. In this paper, we show how to lift these inequalities for integral nonbasic variables by considering maximal lattice-free convex sets in a higher dimensional space. We apply this approach to several examples. In particular, we identify cases in which the lifting is unique.

Suggested Citation

  • Michele Conforti & Gérard Cornuéjols & Giacomo Zambelli, 2011. "A Geometric Perspective on Lifting," Operations Research, INFORMS, vol. 59(3), pages 569-577, June.
    • Handle: RePEc:inm:oropre:v:59:y:2011:i:3:p:569-577
    DOI: 10.1287/opre.1110.0916
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/opre.1110.0916
    Download Restriction: no
    File URL: https://libkey.io/10.1287/opre.1110.0916?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. L. A. Wolsey, 1977. "Valid Inequalities and Superadditivity for 0--1 Integer Programs," Mathematics of Operations Research, INFORMS, vol. 2(1), pages 66-77, February.
    2. Valentin Borozan & Gérard Cornuéjols, 2009. "Minimal Valid Inequalities for Integer Constraints," Mathematics of Operations Research, INFORMS, vol. 34(3), pages 538-546, August.
    3. Balas, Egon & Jeroslow, Robert G., 1980. "Strengthening cuts for mixed integer programs," European Journal of Operational Research, Elsevier, vol. 4(4), pages 224-234, April.
    4. Zonghao Gu & George L. Nemhauser & Martin W.P. Savelsbergh, 2000. "Sequence Independent Lifting in Mixed Integer Programming," Journal of Combinatorial Optimization, Springer, vol. 4(1), pages 109-129, March.
    5. DEY, Santanu S. & WOLSEY, Laurence A., 2010. "Constrained infinite group relaxations of MIPS," LIDAM Reprints CORE 2314, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    6. WOLSEY, Laurence A., 1977. "Valid inequalities and superadditivity for 0-1 integer programs," LIDAM Reprints CORE 328, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Amitabh Basu & Gérard Cornuéjols & Matthias Köppe, 2012. "Unique Minimal Liftings for Simplicial Polytopes," Mathematics of Operations Research, INFORMS, vol. 37(2), pages 346-355, May.
    2. 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.
    3. Santanu S. Dey & Andrea Lodi & Andrea Tramontani & Laurence A. Wolsey, 2014. "On the Practical Strength of Two-Row Tableau Cuts," INFORMS Journal on Computing, INFORMS, vol. 26(2), pages 222-237, May.
    4. 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.
    5. 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.

    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. Xiaoyi Gu & Santanu S. Dey & Jean-Philippe P. Richard, 2024. "Solving Sparse Separable Bilinear Programs Using Lifted Bilinear Cover Inequalities," INFORMS Journal on Computing, INFORMS, vol. 36(3), pages 884-899, May.
    2. Amar K. Narisetty & Jean-Philippe P. Richard & George L. Nemhauser, 2011. "Lifted Tableaux Inequalities for 0--1 Mixed-Integer Programs: A Computational Study," INFORMS Journal on Computing, INFORMS, vol. 23(3), pages 416-424, August.
    3. Absi, Nabil & Kedad-Sidhoum, Safia, 2008. "The multi-item capacitated lot-sizing problem with setup times and shortage costs," European Journal of Operational Research, Elsevier, vol. 185(3), pages 1351-1374, March.
    4. Santanu S. Dey & Andrea Lodi & Andrea Tramontani & Laurence A. Wolsey, 2014. "On the Practical Strength of Two-Row Tableau Cuts," INFORMS Journal on Computing, INFORMS, vol. 26(2), pages 222-237, May.
    5. Alper Atamtürk, 2004. "Sequence Independent Lifting for Mixed-Integer Programming," Operations Research, INFORMS, vol. 52(3), pages 487-490, June.
    6. Santanu S. Dey & Jean-Philippe Richard, 2009. "Linear-Programming-Based Lifting and Its Application to Primal Cutting-Plane Algorithms," INFORMS Journal on Computing, INFORMS, vol. 21(1), pages 137-150, February.
    7. 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.
    8. Quentin Louveaux & Laurence Wolsey, 2007. "Lifting, superadditivity, mixed integer rounding and single node flow sets revisited," Annals of Operations Research, Springer, vol. 153(1), pages 47-77, September.
    9. Egon Balas & Thiago Serra, 2020. "When Lift-and-Project Cuts Are Different," INFORMS Journal on Computing, INFORMS, vol. 32(3), pages 822-834, July.
    10. 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.
    11. Amitabh Basu & Robert Hildebrand & Matthias Köppe, 2016. "Light on the infinite group relaxation I: foundations and taxonomy," 4OR, Springer, vol. 14(1), pages 1-40, March.
    12. Amitabh Basu & Robert Hildebrand & Matthias Köppe, 2016. "Light on the infinite group relaxation II: sufficient conditions for extremality, sequences, and algorithms," 4OR, Springer, vol. 14(2), pages 107-131, June.
    13. Shlyk, Vladimir A., 2013. "Master corner polyhedron: Vertices," European Journal of Operational Research, Elsevier, vol. 226(2), pages 203-210.
    14. Zonghao Gu & George L. Nemhauser & Martin W.P. Savelsbergh, 2000. "Sequence Independent Lifting in Mixed Integer Programming," Journal of Combinatorial Optimization, Springer, vol. 4(1), pages 109-129, March.
    15. Michele Conforti & Gérard Cornuéjols & Aris Daniilidis & Claude Lemaréchal & Jérôme Malick, 2015. "Cut-Generating Functions and S -Free Sets," Mathematics of Operations Research, INFORMS, vol. 40(2), pages 276-391, February.
    16. Kaparis, Konstantinos & Letchford, Adam N., 2008. "Local and global lifted cover inequalities for the 0-1 multidimensional knapsack problem," European Journal of Operational Research, Elsevier, vol. 186(1), pages 91-103, April.
    17. Amitabh Basu & Gérard Cornuéjols & François Margot, 2012. "Intersection Cuts with Infinite Split Rank," Mathematics of Operations Research, INFORMS, vol. 37(1), pages 21-40, February.
    18. Atamturk, Alper & Munoz, Juan Carlos, 2002. "A Study of the Lot-Sizing Polytope," University of California Transportation Center, Working Papers qt6zz2g0z4, University of California Transportation Center.
    19. Fatma Kılınç-Karzan, 2016. "On Minimal Valid Inequalities for Mixed Integer Conic Programs," Mathematics of Operations Research, INFORMS, vol. 41(2), pages 477-510, May.
    20. Amitabh Basu & Gérard Cornuéjols & Matthias Köppe, 2012. "Unique Minimal Liftings for Simplicial Polytopes," Mathematics of Operations Research, INFORMS, vol. 37(2), pages 346-355, May.

    More about this item

    Keywords

    programming/integer/cutting plane;

    Statistics

    Access and download statistics

    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:oropre:v:59:y:2011:i:3:p:569-577. 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.