IDEAS home Printed from https://ideas.repec.org/a/spr/coopap/v88y2024i1d10.1007_s10589-024-00557-9.html
   My bibliography  Save this article

Convex mixed-integer nonlinear programs derived from generalized disjunctive programming using cones

Author

Listed:
  • David E. Bernal Neira

    (Purdue University
    Universities Space Research Association
    NASA Ames Research Center)

  • Ignacio E. Grossmann

    (Carnegie Mellon University)

Abstract

We propose the formulation of convex Generalized Disjunctive Programming (GDP) problems using conic inequalities leading to conic GDP problems. We then show the reformulation of conic GDPs into Mixed-Integer Conic Programming (MICP) problems through both the big-M and hull reformulations. These reformulations have the advantage that they are representable using the same cones as the original conic GDP. In the case of the hull reformulation, they require no approximation of the perspective function. Moreover, the MICP problems derived can be solved by specialized conic solvers and offer a natural extended formulation amenable to both conic and gradient-based solvers. We present the closed form of several convex functions and their respective perspectives in conic sets, allowing users to formulate their conic GDP problems easily. We finally implement a large set of conic GDP examples and solve them via the scalar nonlinear and conic mixed-integer reformulations. These examples include applications from Process Systems Engineering, Machine learning, and randomly generated instances. Our results show that the conic structure can be exploited to solve these challenging MICP problems more efficiently. Our main contribution is providing the reformulations, examples, and computational results that support the claim that taking advantage of conic formulations of convex GDP instead of their nonlinear algebraic descriptions can lead to a more efficient solution to these problems.

Suggested Citation

  • David E. Bernal Neira & Ignacio E. Grossmann, 2024. "Convex mixed-integer nonlinear programs derived from generalized disjunctive programming using cones," Computational Optimization and Applications, Springer, vol. 88(1), pages 251-312, May.
    • Handle: RePEc:spr:coopap:v:88:y:2024:i:1:d:10.1007_s10589-024-00557-9
    DOI: 10.1007/s10589-024-00557-9
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10589-024-00557-9
    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/s10589-024-00557-9?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. Jan Kronqvist & Andreas Lundell & Tapio Westerlund, 2018. "Reformulations for utilizing separability when solving convex MINLP problems," Journal of Global Optimization, Springer, vol. 71(3), pages 571-592, July.
    2. Ruiz, Juan P. & Grossmann, Ignacio E., 2012. "A hierarchy of relaxations for nonlinear convex generalized disjunctive programming," European Journal of Operational Research, Elsevier, vol. 218(1), pages 38-47.
    3. Sawaya, Nicolas & Grossmann, Ignacio, 2012. "A hierarchy of relaxations for linear generalized disjunctive programming," European Journal of Operational Research, Elsevier, vol. 216(1), pages 70-82.
    4. Kevin C. Furman & Nicolas W. Sawaya & Ignacio E. Grossmann, 2020. "A computationally useful algebraic representation of nonlinear disjunctive convex sets using the perspective function," Computational Optimization and Applications, Springer, vol. 76(2), pages 589-614, June.
    5. Dimitri J. Papageorgiou & Francisco Trespalacios, 2018. "Pseudo basic steps: bound improvement guarantees from Lagrangian decomposition in convex disjunctive programming," EURO Journal on Computational Optimization, Springer;EURO - The Association of European Operational Research Societies, vol. 6(1), pages 55-83, March.
    6. Hassan Hijazi & Pierre Bonami & Adam Ouorou, 2014. "An Outer-Inner Approximation for Separable Mixed-Integer Nonlinear Programs," INFORMS Journal on Computing, INFORMS, vol. 26(1), pages 31-44, February.
    7. Chris Coey & Lea Kapelevich & Juan Pablo Vielma, 2022. "Solving Natural Conic Formulations with Hypatia.jl," INFORMS Journal on Computing, INFORMS, vol. 34(5), pages 2686-2699, September.
    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. Novas, Juan M. & Ramello, Juan Ignacio & Rodríguez, María Analía, 2020. "Generalized disjunctive programming models for the truck loading problem: A case study from the non-alcoholic beverages industry," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 140(C).
    2. Dimitri J. Papageorgiou & Francisco Trespalacios, 2018. "Pseudo basic steps: bound improvement guarantees from Lagrangian decomposition in convex disjunctive programming," EURO Journal on Computational Optimization, Springer;EURO - The Association of European Operational Research Societies, vol. 6(1), pages 55-83, March.
    3. Francisco Trespalacios & Ignacio E. Grossmann, 2016. "Cutting Plane Algorithm for Convex Generalized Disjunctive Programs," INFORMS Journal on Computing, INFORMS, vol. 28(2), pages 209-222, May.
    4. Alexander Murray & Timm Faulwasser & Veit Hagenmeyer & Mario E. Villanueva & Boris Houska, 2021. "Partially distributed outer approximation," Journal of Global Optimization, Springer, vol. 80(3), pages 523-550, July.
    5. Andreas Lundell & Jan Kronqvist & Tapio Westerlund, 2022. "The supporting hyperplane optimization toolkit for convex MINLP," Journal of Global Optimization, Springer, vol. 84(1), pages 1-41, September.
    6. Peter Kirst & Fabian Rigterink & Oliver Stein, 2017. "Global optimization of disjunctive programs," Journal of Global Optimization, Springer, vol. 69(2), pages 283-307, October.
    7. Francisco Trespalacios & Ignacio E. Grossmann, 2015. "Algorithmic Approach for Improved Mixed-Integer Reformulations of Convex Generalized Disjunctive Programs," INFORMS Journal on Computing, INFORMS, vol. 27(1), pages 59-74, February.
    8. Yinrun Lyu & Li Chen & Changyou Zhang & Dacheng Qu & Nasro Min-Allah & Yongji Wang, 2018. "An interleaved depth-first search method for the linear optimization problem with disjunctive constraints," Journal of Global Optimization, Springer, vol. 70(4), pages 737-756, April.
    9. Jon Lee & Daphne Skipper & Emily Speakman & Luze Xu, 2023. "Gaining or Losing Perspective for Piecewise-Linear Under-Estimators of Convex Univariate Functions," Journal of Optimization Theory and Applications, Springer, vol. 196(1), pages 1-35, January.
    10. Ying Lin & Scott B. Lindstrom & Bruno F. Lourenço & Ting Kei Pong, 2025. "Tight Error Bounds for Log-Determinant Cones Without Constraint Qualifications," Journal of Optimization Theory and Applications, Springer, vol. 205(3), pages 1-42, June.
    11. David E. Bernal & Zedong Peng & Jan Kronqvist & Ignacio E. Grossmann, 2022. "Alternative regularizations for Outer-Approximation algorithms for convex MINLP," Journal of Global Optimization, Springer, vol. 84(4), pages 807-842, December.
    12. Can Li & Ignacio E. Grossmann, 2019. "A finite $$\epsilon $$ϵ-convergence algorithm for two-stage stochastic convex nonlinear programs with mixed-binary first and second-stage variables," Journal of Global Optimization, Springer, vol. 75(4), pages 921-947, December.
    13. Juan P. Ruiz & Ignacio E. Grossmann, 2017. "Global optimization of non-convex generalized disjunctive programs: a review on reformulations and relaxation techniques," Journal of Global Optimization, Springer, vol. 67(1), pages 43-58, January.
    14. Ngan Ha Duong & Tien Thanh Dam & Thuy Anh Ta & Tien Mai, 2022. "Joint Location and Cost Planning in Maximum Capture Facility Location under Multiplicative Random Utility Maximization," Papers 2205.07345, arXiv.org, revised Feb 2023.
    15. Ana Maria A. C. Rocha & M. Fernanda P. Costa & Edite M. G. P. Fernandes, 2018. "Preface to the Special Issue “GOW’16”," Journal of Global Optimization, Springer, vol. 71(3), pages 441-442, July.
    16. Li Chen & Yinrun Lyu & Chong Wang & Jingzheng Wu & Changyou Zhang & Nasro Min-Allah & Jamal Alhiyafi & Yongji Wang, 2017. "Solving linear optimization over arithmetic constraint formula," Journal of Global Optimization, Springer, vol. 69(1), pages 69-102, September.
    17. Andreas Lundell & Jan Kronqvist, 2022. "Polyhedral approximation strategies for nonconvex mixed-integer nonlinear programming in SHOT," Journal of Global Optimization, Springer, vol. 82(4), pages 863-896, April.
    18. Liu, Weiwei & Kong, Nan & Wang, Mingzheng & Zhang, Lingling, 2021. "Sustainable multi-commodity capacitated facility location problem with complementarity demand functions," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 145(C).
    19. Mathieu Besançon & Joaquim Dias Garcia & Benoît Legat & Akshay Sharma, 2024. "Flexible Differentiable Optimization via Model Transformations," INFORMS Journal on Computing, INFORMS, vol. 36(2), pages 456-478, March.
    20. Massimo De Mauri & Joris Gillis & Jan Swevers & Goele Pipeleers, 2020. "A proximal-point outer approximation algorithm," Computational Optimization and Applications, Springer, vol. 77(3), pages 755-777, December.

    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:coopap:v:88:y:2024:i:1:d:10.1007_s10589-024-00557-9. 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.