IDEAS home Printed from https://ideas.repec.org/a/spr/annopr/v295y2020i1d10.1007_s10479-020-03709-2.html
   My bibliography  Save this article

Reformulating the disjunctive cut generating linear program

Author

Listed:
  • Thiago Serra

    (Bucknell University)

Abstract

Lift-and-project cuts can be obtained by defining an elegant optimization problem over the space of valid inequalities, the cut generating linear program (CGLP). A CGLP has two main ingredients: (i) an objective function, which invariably maximizes the violation with respect to a fractional solution $${\bar{x}}$$ x ¯ to be separated; and (ii) a normalization constraint, which limits the scale in which cuts are represented. One would expect that CGLP optima entail the best cuts, but the normalization may distort how cuts are compared, and the cutting plane may not be a supporting hyperplane with respect to the closure of valid inequalities from the CGLP. This work proposes the reverse polar CGLP (RP-CGLP), which switches the roles conventionally played by objective and normalization: violation with respect to $${\bar{x}}$$ x ¯ is fixed to a positive constant, whereas we minimize the slack for a point p that cannot be separated by the valid inequalities. Cuts from RP-CGLP optima define supporting hyperplanes of the immediate closure. When that closure is full-dimensional, the face defined by the cut lays on facets first intersected by a ray from $${\bar{x}}$$ x ¯ to p, all of which corresponding to cutting planes from RP-CGLP optima if p is an interior point. In fact, these are the cuts minimizing a ratio between the slack for p and the violation for $${\bar{x}}$$ x ¯ . We show how to derive such cuts directly from the simplex tableau in the case of split disjunctions and report experiments on adapting the CglLandP cut generator library for the RP-CGLP formulation.

Suggested Citation

  • Thiago Serra, 2020. "Reformulating the disjunctive cut generating linear program," Annals of Operations Research, Springer, vol. 295(1), pages 363-384, December.
  • Handle: RePEc:spr:annopr:v:295:y:2020:i:1:d:10.1007_s10479-020-03709-2
    DOI: 10.1007/s10479-020-03709-2
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10479-020-03709-2
    File Function: Abstract
    Download Restriction: Access to the full text of the articles in this series is restricted.

    File URL: https://libkey.io/10.1007/s10479-020-03709-2?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
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. CONFORTI, Michele & WOLSEY, Laurence A., 2016. "“Facet” Separation with One Linear Program," LIDAM Discussion Papers CORE 2016021, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    2. Arthur F. Veinott, 1967. "The Supporting Hyperplane Method for Unimodal Programming," Operations Research, INFORMS, vol. 15(1), pages 147-152, February.
    3. Mohan Bala & Kipp Martin, 1997. "A Mathematical Programming Approach to Data Base Normalization," INFORMS Journal on Computing, INFORMS, vol. 9(1), pages 1-14, February.
    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. Ville-Pekka Eronen & Jan Kronqvist & Tapio Westerlund & Marko M. Mäkelä & Napsu Karmitsa, 2017. "Method for solving generalized convex nonsmooth mixed-integer nonlinear programming problems," Journal of Global Optimization, Springer, vol. 69(2), pages 443-459, October.
    2. Daniel Dörfler, 2022. "On the Approximation of Unbounded Convex Sets by Polyhedra," Journal of Optimization Theory and Applications, Springer, vol. 194(1), pages 265-287, July.
    3. Frederic H. Murphy, 1972. "Row Dropping Procedures for Cutting Plane Algorithms," Discussion Papers 16, Northwestern University, Center for Mathematical Studies in Economics and Management Science.
    4. Wim Ackooij & Welington Oliveira, 2014. "Level bundle methods for constrained convex optimization with various oracles," Computational Optimization and Applications, Springer, vol. 57(3), pages 555-597, April.
    5. Pey-Chun Chen & Pierre Hansen & Brigitte Jaumard & Hoang Tuy, 1998. "Solution of the Multisource Weber and Conditional Weber Problems by D.-C. Programming," Operations Research, INFORMS, vol. 46(4), pages 548-562, August.
    6. Wendel Melo & Marcia Fampa & Fernanda Raupp, 2020. "An overview of MINLP algorithms and their implementation in Muriqui Optimizer," Annals of Operations Research, Springer, vol. 286(1), pages 217-241, March.
    7. Wim Ackooij, 2014. "Decomposition approaches for block-structured chance-constrained programs with application to hydro-thermal unit commitment," Mathematical Methods of Operations Research, Springer;Gesellschaft für Operations Research (GOR);Nederlands Genootschap voor Besliskunde (NGB), vol. 80(3), pages 227-253, December.
    8. Felipe Serrano & Robert Schwarz & Ambros Gleixner, 2020. "On the relation between the extended supporting hyperplane algorithm and Kelley’s cutting plane algorithm," Journal of Global Optimization, Springer, vol. 78(1), pages 161-179, September.
    9. Alfred Auslender & Miguel A. Goberna & Marco A. López, 2009. "Penalty and Smoothing Methods for Convex Semi-Infinite Programming," Mathematics of Operations Research, INFORMS, vol. 34(2), pages 303-319, May.
    10. Tapio Westerlund & Ville-Pekka Eronen & Marko M. Mäkelä, 2018. "On solving generalized convex MINLP problems using supporting hyperplane techniques," Journal of Global Optimization, Springer, vol. 71(4), pages 987-1011, August.
    11. Valerian Bulatov, 2010. "Methods of embedding-cutting off in problems of mathematical programming," Journal of Global Optimization, Springer, vol. 48(1), pages 3-15, September.
    12. H. P. Benson, 2010. "Branch-and-Bound Outer Approximation Algorithm for Sum-of-Ratios Fractional Programs," Journal of Optimization Theory and Applications, Springer, vol. 146(1), pages 1-18, July.
    13. Chunming Tang & Bo He & Zhenzhen Wang, 2020. "Modified Accelerated Bundle-Level Methods and Their Application in Two-Stage Stochastic Programming," Mathematics, MDPI, vol. 8(2), pages 1-26, February.

    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:spr:annopr:v:295:y:2020:i:1:d:10.1007_s10479-020-03709-2. 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: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    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.