IDEAS home Printed from https://ideas.repec.org/a/spr/jglopt/v77y2020i1d10.1007_s10898-020-00888-x.html
   My bibliography  Save this article

The decomposition-based outer approximation algorithm for convex mixed-integer nonlinear programming

Author

Listed:
  • Pavlo Muts

    (Hamburg University of Applied Sciences)

  • Ivo Nowak

    (Hamburg University of Applied Sciences)

  • Eligius M. T. Hendrix

    (University of Málaga)

Abstract

This paper presents a new two-phase method for solving convex mixed-integer nonlinear programming (MINLP) problems, called Decomposition-based Outer Approximation Algorithm (DECOA). In the first phase, a sequence of linear integer relaxed sub-problems (LP phase) is solved in order to rapidly generate a good linear relaxation of the original MINLP problem. In the second phase, the algorithm solves a sequence of mixed integer linear programming sub-problems (MIP phase). In both phases the outer approximation is improved iteratively by adding new supporting hyperplanes by solving many easier sub-problems in parallel. DECOA is implemented as a part of Decogo (Decomposition-based Global Optimizer), a parallel decomposition-based MINLP solver implemented in Python and Pyomo. Preliminary numerical results based on 70 convex MINLP instances up to 2700 variables show that due to the generated cuts in the LP phase, on average only 2–3 MIP problems have to be solved in the MIP phase.

Suggested Citation

  • Pavlo Muts & Ivo Nowak & Eligius M. T. Hendrix, 2020. "The decomposition-based outer approximation algorithm for convex mixed-integer nonlinear programming," Journal of Global Optimization, Springer, vol. 77(1), pages 75-96, May.
    • Handle: RePEc:spr:jglopt:v:77:y:2020:i:1:d:10.1007_s10898-020-00888-x
    DOI: 10.1007/s10898-020-00888-x
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10898-020-00888-x
    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/s10898-020-00888-x?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. Marco E. Lübbecke & Jacques Desrosiers, 2005. "Selected Topics in Column Generation," Operations Research, INFORMS, vol. 53(6), pages 1007-1023, December.
    2. Ivo Nowak & Norman Breitfeld & Eligius M. T. Hendrix & Grégoire Njacheun-Njanzoua, 2018. "Decomposition-based Inner- and Outer-Refinement Algorithms for Global Optimization," Journal of Global Optimization, Springer, vol. 72(2), pages 305-321, October.
    3. Ruth Misener & Christodoulos Floudas, 2014. "ANTIGONE: Algorithms for coNTinuous / Integer Global Optimization of Nonlinear Equations," Journal of Global Optimization, Springer, vol. 59(2), pages 503-526, July.
    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. Chen, Zebin & D’Ariano, Andrea & Li, Shukai & Tessitore, Marta Leonina & Yang, Lixing, 2024. "Robust dynamic train regulation integrated with stop-skipping strategy in urban rail networks: An outer approximation based solution method," Omega, Elsevier, vol. 128(C).
    2. 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.
    3. 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.
    4. Alireza Olama & Eduardo Camponogara & Paulo R. C. Mendes, 2023. "Distributed primal outer approximation algorithm for sparse convex programming with separable structures," Journal of Global Optimization, Springer, vol. 86(3), pages 637-670, 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.

    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. Renaud Chicoisne, 2023. "Computational aspects of column generation for nonlinear and conic optimization: classical and linearized schemes," Computational Optimization and Applications, Springer, vol. 84(3), pages 789-831, April.
    2. Ivo Nowak & Norman Breitfeld & Eligius M. T. Hendrix & Grégoire Njacheun-Njanzoua, 2018. "Decomposition-based Inner- and Outer-Refinement Algorithms for Global Optimization," Journal of Global Optimization, Springer, vol. 72(2), pages 305-321, October.
    3. Andrew Allman & Qi Zhang, 2021. "Branch-and-price for a class of nonconvex mixed-integer nonlinear programs," Journal of Global Optimization, Springer, vol. 81(4), pages 861-880, December.
    4. Pu Huang & Dharmashankar Subramanian, 2012. "Iterative estimation maximization for stochastic linear programs with conditional value-at-risk constraints," Computational Management Science, Springer, vol. 9(4), pages 441-458, November.
    5. Lee, Chungmok & Han, Jinil, 2017. "Benders-and-Price approach for electric vehicle charging station location problem under probabilistic travel range," Transportation Research Part B: Methodological, Elsevier, vol. 106(C), pages 130-152.
    6. Stuart M. Harwood & Paul I. Barton, 2017. "How to solve a design centering problem," Mathematical Methods of Operations Research, Springer;Gesellschaft für Operations Research (GOR);Nederlands Genootschap voor Besliskunde (NGB), vol. 86(1), pages 215-254, August.
    7. Jaromił Najman & Alexander Mitsos, 2019. "On tightness and anchoring of McCormick and other relaxations," Journal of Global Optimization, Springer, vol. 74(4), pages 677-703, August.
    8. Veaceslav Ghilas & Jean-François Cordeau & Emrah Demir & Tom Van Woensel, 2018. "Branch-and-Price for the Pickup and Delivery Problem with Time Windows and Scheduled Lines," Transportation Science, INFORMS, vol. 52(5), pages 1191-1210, October.
    9. Isabel Martins & Filipe Alvelos & Miguel Constantino, 2012. "A branch-and-price approach for harvest scheduling subject to maximum area restrictions," Computational Optimization and Applications, Springer, vol. 51(1), pages 363-385, January.
    10. Christensen, Tue R.L. & Labbé, Martine, 2015. "A branch-cut-and-price algorithm for the piecewise linear transportation problem," European Journal of Operational Research, Elsevier, vol. 245(3), pages 645-655.
    11. Lingxun Kong & Christos T. Maravelias, 2020. "On the Derivation of Continuous Piecewise Linear Approximating Functions," INFORMS Journal on Computing, INFORMS, vol. 32(3), pages 531-546, July.
    12. Ogbe, Emmanuel & Li, Xiang, 2017. "A new cross decomposition method for stochastic mixed-integer linear programming," European Journal of Operational Research, Elsevier, vol. 256(2), pages 487-499.
    13. Rönnberg, Elina & Larsson, Torbjörn, 2014. "All-integer column generation for set partitioning: Basic principles and extensions," European Journal of Operational Research, Elsevier, vol. 233(3), pages 529-538.
    14. Eliashberg, Jehoshua & Hegie, Quintus & Ho, Jason & Huisman, Dennis & Miller, Steven J. & Swami, Sanjeev & Weinberg, Charles B. & Wierenga, Berend, 2009. "Demand-driven scheduling of movies in a multiplex," International Journal of Research in Marketing, Elsevier, vol. 26(2), pages 75-88.
    15. François Clautiaux & Cláudio Alves & José Valério de Carvalho & Jürgen Rietz, 2011. "New Stabilization Procedures for the Cutting Stock Problem," INFORMS Journal on Computing, INFORMS, vol. 23(4), pages 530-545, November.
    16. Markus Frey & Rainer Kolisch & Christian Artigues, 2017. "Column Generation for Outbound Baggage Handling at Airports," Transportation Science, INFORMS, vol. 51(4), pages 1226-1241, November.
    17. Arts, Joachim, 2017. "A multi-item approach to repairable stocking and expediting in a fluctuating demand environment," European Journal of Operational Research, Elsevier, vol. 256(1), pages 102-115.
    18. de Lima, Vinícius L. & Alves, Cláudio & Clautiaux, François & Iori, Manuel & Valério de Carvalho, José M., 2022. "Arc flow formulations based on dynamic programming: Theoretical foundations and applications," European Journal of Operational Research, Elsevier, vol. 296(1), pages 3-21.
    19. Stefano Gualandi & Federico Malucelli, 2012. "Exact Solution of Graph Coloring Problems via Constraint Programming and Column Generation," INFORMS Journal on Computing, INFORMS, vol. 24(1), pages 81-100, February.
    20. Timo Hintsch & Stefan Irnich, 2018. "Exact Solution of the Soft-Clustered Vehicle Routing Problem," Working Papers 1813, Gutenberg School of Management and Economics, Johannes Gutenberg-Universität Mainz.

    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:jglopt:v:77:y:2020:i:1:d:10.1007_s10898-020-00888-x. 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.