IDEAS home Printed from https://ideas.repec.org/a/inm/orijoc/v32y3i2020p822-834.html
   My bibliography  Save this article

When Lift-and-Project Cuts Are Different

Author

Listed:
  • Egon Balas

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

  • Thiago Serra

    (Freeman College of Management, Bucknell University, Lewisburg, Pennsylvania 17837)

Abstract

In this paper, we present a method to determine if a lift-and-project cut for a mixed-integer linear program is irregular, in which case the cut is not equivalent to any intersection cut from the bases of the linear relaxation. This is an important question due to the intense research activity for the past decade on cuts from multiple rows of simplex tableau as well as on lift-and-project cuts from nonsplit disjunctions. Although it has been known for a while that lift-and-project cuts from split disjunctions are always equivalent to intersection cuts and consequently to such multirow cuts, it has been recently shown that there is a necessary and sufficient condition in the case of arbitrary disjunctions: a lift-and-project cut is regular if, and only if, it corresponds to a regular basic solution of the Cut Generating Linear Program (CGLP). This paper has four contributions. First, we state a result that simplifies the verification of regularity for basic CGLP solutions. Second, we provide a mixed-integer formulation that checks whether there is a regular CGLP solution for a given cut that is regular in a broader sense, which also encompasses irregular cuts that are implied by the regular cut closure. Third, we describe a numerical procedure based on such formulation that identifies irregular lift-and-project cuts. Finally, we use this method to evaluate how often lift-and-project cuts from simple t -branch split disjunctions are irregular, and thus not equivalent to multirow cuts, on 74 instances of the Mixed Integer Programming Library (MIPLIB) benchmarks.

Suggested Citation

  • Egon Balas & Thiago Serra, 2020. "When Lift-and-Project Cuts Are Different," INFORMS Journal on Computing, INFORMS, vol. 32(3), pages 822-834, July.
  • Handle: RePEc:inm:orijoc:v:32:y:3:i:2020:p:822-834
    DOI: 10.1287/ijoc.2019.0943
    as

    Download full text from publisher

    File URL: https://doi.org/10.1287/ijoc.2019.0943
    Download Restriction: no

    File URL: https://libkey.io/10.1287/ijoc.2019.0943?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. 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.
    2. Egon Balas, 1971. "Intersection Cuts—A New Type of Cutting Planes for Integer Programming," Operations Research, INFORMS, vol. 19(1), pages 19-39, February.
    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. 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.
    5. 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).
    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. 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.
    2. 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.
    3. 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.
    4. 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.
    5. 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.
    6. 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.
    7. 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.
    8. 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.
    9. Michele Conforti & Gérard Cornuéjols & Giacomo Zambelli, 2011. "A Geometric Perspective on Lifting," Operations Research, INFORMS, vol. 59(3), pages 569-577, June.
    10. Kent Andersen & Gérard Cornuéjols & Yanjun Li, 2005. "Reduce-and-Split Cuts: Improving the Performance of Mixed-Integer Gomory Cuts," Management Science, INFORMS, vol. 51(11), pages 1720-1732, November.
    11. Matteo Fischetti & Domenico Salvagnin, 2013. "Approximating the Split Closure," INFORMS Journal on Computing, INFORMS, vol. 25(4), pages 808-819, November.
    12. Matteo Fischetti & Ivana Ljubić & Michele Monaci & Markus Sinnl, 2017. "A New General-Purpose Algorithm for Mixed-Integer Bilevel Linear Programs," Operations Research, INFORMS, vol. 65(6), pages 1615-1637, December.
    13. Amitabh Basu & Robert Hildebrand & Matthias Köppe, 2015. "Equivariant Perturbation in Gomory and Johnson's Infinite Group Problem. I. The One-Dimensional Case," Mathematics of Operations Research, INFORMS, vol. 40(1), pages 105-129, February.
    14. 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.
    15. Álinson S. Xavier & Ricardo Fukasawa & Laurent Poirrier, 2021. "Multirow Intersection Cuts Based on the Infinity Norm," INFORMS Journal on Computing, INFORMS, vol. 33(4), pages 1624-1643, October.
    16. Amitabh Basu & Michele Conforti & Gérard Cornuéjols & Giacomo Zambelli, 2010. "Maximal Lattice-Free Convex Sets in Linear Subspaces," Mathematics of Operations Research, INFORMS, vol. 35(3), pages 704-720, August.
    17. Egon Balas & Gérard Cornuéjols & Tamás Kis & Giacomo Nannicini, 2013. "Combining Lift-and-Project and Reduce-and-Split," INFORMS Journal on Computing, INFORMS, vol. 25(3), pages 475-487, August.
    18. 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.
    19. Sebastián Ceria, 2007. "A brief history of lift-and-project," Annals of Operations Research, Springer, vol. 149(1), pages 57-61, February.
    20. 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.

    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:orijoc:v:32:y:3:i:2020:p:822-834. 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.