IDEAS home Printed from https://ideas.repec.org/a/eee/ejores/v218y2012i1p38-47.html
   My bibliography  Save this article

A hierarchy of relaxations for nonlinear convex generalized disjunctive programming

Author

Listed:
  • Ruiz, Juan P.
  • Grossmann, Ignacio E.

Abstract

We propose a framework to generate alternative mixed-integer nonlinear programming formulations for disjunctive convex programs that lead to stronger relaxations. We extend the concept of “basic steps” defined for disjunctive linear programs to the nonlinear case. A basic step is an operation that takes a disjunctive set to another with fewer number of conjuncts. We show that the strength of the relaxations increases as the number of conjuncts decreases, leading to a hierarchy of relaxations. We prove that the tightest of these relaxations, allows in theory the solution of the disjunctive convex program as a nonlinear programming problem. We present a methodology to guide the generation of strong relaxations without incurring an exponential increase of the size of the reformulated mixed-integer program. Finally, we apply the theory developed to improve the computational efficiency of solution methods for nonlinear convex generalized disjunctive programs (GDP). This methodology is validated through a set of numerical examples.

Suggested Citation

  • 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.
    • Handle: RePEc:eee:ejores:v:218:y:2012:i:1:p:38-47
    DOI: 10.1016/j.ejor.2011.10.002
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S037722171100899X
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.ejor.2011.10.002?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. Omprakash K. Gupta & A. Ravindran, 1985. "Branch and Bound Experiments in Convex Nonlinear Integer Programming," Management Science, INFORMS, vol. 31(12), pages 1533-1546, December.
    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. 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.
    2. 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.
    3. Peter Kirst & Fabian Rigterink & Oliver Stein, 2017. "Global optimization of disjunctive programs," Journal of Global Optimization, Springer, vol. 69(2), pages 283-307, October.
    4. 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.
    5. 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.
    6. 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).
    7. 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.
    8. 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.

    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. Terzi, Mourad & Ouazene, Yassine & Yalaoui, Alice & Yalaoui, Farouk, 2023. "Lot-sizing and pricing decisions under attraction demand models and multi-channel environment: New efficient formulations," Operations Research Perspectives, Elsevier, vol. 10(C).
    2. 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.
    3. Kumar Abhishek & Sven Leyffer & Jeff Linderoth, 2010. "FilMINT: An Outer Approximation-Based Solver for Convex Mixed-Integer Nonlinear Programs," INFORMS Journal on Computing, INFORMS, vol. 22(4), pages 555-567, November.
    4. Shyamal Gondkar & Sivakumar Sreeramagiri & Edwin Zondervan, 2012. "Methodology for Assessment and Optimization of Industrial Eco-Systems," Challenges, MDPI, vol. 3(1), pages 1-21, June.
    5. 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.
    6. Corazza, Marco & Favaretto, Daniela, 2007. "On the existence of solutions to the quadratic mixed-integer mean-variance portfolio selection problem," European Journal of Operational Research, Elsevier, vol. 176(3), pages 1947-1960, February.
    7. Jin, Tongdan & Tian, Yu, 2012. "Optimizing reliability and service parts logistics for a time-varying installed base," European Journal of Operational Research, Elsevier, vol. 218(1), pages 152-162.
    8. Sönke Behrends & Ruth Hübner & Anita Schöbel, 2018. "Norm bounds and underestimators for unconstrained polynomial integer minimization," Mathematical Methods of Operations Research, Springer;Gesellschaft für Operations Research (GOR);Nederlands Genootschap voor Besliskunde (NGB), vol. 87(1), pages 73-107, February.
    9. 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.
    10. Zhou Wei & M. Montaz Ali & Liang Xu & Bo Zeng & Jen-Chih Yao, 2019. "On Solving Nonsmooth Mixed-Integer Nonlinear Programming Problems by Outer Approximation and Generalized Benders Decomposition," Journal of Optimization Theory and Applications, Springer, vol. 181(3), pages 840-863, June.
    11. Xiaoling Sun & Duan Li, 2000. "Asymptotic Strong Duality for Bounded Integer Programming: A Logarithmic-Exponential Dual Formulation," Mathematics of Operations Research, INFORMS, vol. 25(4), pages 625-644, November.
    12. Qin, Ruwen & Cudney, Elizabeth A. & Hamzic, Zlatan, 2015. "An optimal plan of zero-defect single-sampling by attributes for incoming inspections in assembly lines," European Journal of Operational Research, Elsevier, vol. 246(3), pages 907-915.
    13. Mostafa Parsa & Ali Shahandeh Nookabadi & Zümbül Atan & Yaser Malekian, 2022. "An optimal inventory policy for a multi-echelon closed-loop supply chain of postconsumer recycled content products," Operational Research, Springer, vol. 22(3), pages 1887-1938, July.
    14. 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.
    15. 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.
    16. Birolini, Sebastian & Jacquillat, Alexandre & Cattaneo, Mattia & Antunes, António Pais, 2021. "Airline Network Planning: Mixed-integer non-convex optimization with demand–supply interactions," Transportation Research Part B: Methodological, Elsevier, vol. 154(C), pages 100-124.
    17. Fukasawa, Ricardo & He, Qie & Song, Yongjia, 2016. "A disjunctive convex programming approach to the pollution-routing problem," Transportation Research Part B: Methodological, Elsevier, vol. 94(C), pages 61-79.
    18. Hübner, Ruth & Schöbel, Anita, 2014. "When is rounding allowed in integer nonlinear optimization?," European Journal of Operational Research, Elsevier, vol. 237(2), pages 404-410.
    19. Maimon, Oded & Dayagi, Arie, 1995. "Nesting planning based on production priorities and technological efficiency," European Journal of Operational Research, Elsevier, vol. 80(1), pages 121-129, January.
    20. Miguel A. Lejeune & Francois Margot, 2018. "Aeromedical Battlefield Evacuation Under Endogenous Uncertainty in Casualty Delivery Times," Management Science, INFORMS, vol. 64(12), pages 5481-5496, 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:eee:ejores:v:218:y:2012:i:1:p:38-47. 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: Catherine Liu (email available below). General contact details of provider: http://www.elsevier.com/locate/eor .

    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.