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

A proximal-point outer approximation algorithm

Author

Listed:
  • Massimo De Mauri

    (KU Leuven and Flanders Make - DMMS_M)

  • Joris Gillis

    (KU Leuven and Flanders Make - DMMS_M)

  • Jan Swevers

    (KU Leuven and Flanders Make - DMMS_M)

  • Goele Pipeleers

    (KU Leuven and Flanders Make - DMMS_M)

Abstract

Many engineering and scientific applications, e.g. resource allocation, control of hybrid systems, scheduling, etc., require the solution of mixed-integer non-linear problems (MINLPs). Problems of such class combine the high computational burden arising from considering discrete variables with the complexity of non-linear functions. As a consequence, the development of algorithms able to efficiently solve medium-large MINLPs is still an interesting field of research. In the last decades, several approaches to tackle MINLPs have been developed. Some of such approaches, usually defined as exact methods, aim at finding a globally optimal solution for a given MINLP at expense of a long execution time, while others, generally defined as heuristics, aim at discovering suboptimal feasible solutions in the shortest time possible. Among the various proposed paradigms, outer approximation (OA) and feasibility pump (FP), respectively as exact method and as heuristic, deserve a special mention for the number of relevant publications and successful implementations related to them. In this paper we present a new exact method for convex mixed-integer non-linear programming called proximal outer approximation (POA). POA blends the fundamental ideas behind FP into the general OA scheme that attepts to yield faster and more robust convergence with respect to OA while retaining the good performances in terms of fast generation of feasible solutions of FP.

Suggested Citation

  • 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.
    • Handle: RePEc:spr:coopap:v:77:y:2020:i:3:d:10.1007_s10589-020-00216-9
    DOI: 10.1007/s10589-020-00216-9
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10589-020-00216-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-020-00216-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. Marianna De Santis & Stefano Lucidi & Francesco Rinaldi, 2013. "A new class of functions for measuring solution integrality in the Feasibility Pump approach: Complete Results," DIAG Technical Reports 2013-05, Department of Computer, Control and Management Engineering, Universita' degli Studi di Roma "La Sapienza".
    2. Shaurya Sharma & Brage Knudsen & Bjarne Grimstad, 2016. "Towards an objective feasibility pump for convex MINLPs," Computational Optimization and Applications, Springer, vol. 63(3), pages 737-753, April.
    3. 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.
    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. 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.
    2. Shaurya Sharma & Brage Knudsen & Bjarne Grimstad, 2016. "Towards an objective feasibility pump for convex MINLPs," Computational Optimization and Applications, Springer, vol. 63(3), pages 737-753, April.
    3. 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.
    4. 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).
    5. 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.
    6. 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.
    7. Matteo Fischetti & Ivana Ljubić & Markus Sinnl, 2017. "Redesigning Benders Decomposition for Large-Scale Facility Location," Management Science, INFORMS, vol. 63(7), pages 2146-2162, July.
    8. Guastaroba, G. & Savelsbergh, M. & Speranza, M.G., 2017. "Adaptive Kernel Search: A heuristic for solving Mixed Integer linear Programs," European Journal of Operational Research, Elsevier, vol. 263(3), pages 789-804.
    9. Ma, Cheng & Zhang, Liansheng, 2015. "On an exact penalty function method for nonlinear mixed discrete programming problems and its applications in search engine advertising problems," Applied Mathematics and Computation, Elsevier, vol. 271(C), pages 642-656.
    10. Meenarli Sharma & Prashant Palkar & Ashutosh Mahajan, 2022. "Linearization and parallelization schemes for convex mixed-integer nonlinear optimization," Computational Optimization and Applications, Springer, vol. 81(2), pages 423-478, March.
    11. Timo Berthold & Andrea Lodi & Domenico Salvagnin, 2019. "Ten years of feasibility pump, and counting," EURO Journal on Computational Optimization, Springer;EURO - The Association of European Operational Research Societies, vol. 7(1), pages 1-14, March.
    12. Marianna De Santis & Sven de Vries & Martin Schmidt & Lukas Winkel, 2022. "A Penalty Branch-and-Bound Method for Mixed Binary Linear Complementarity Problems," INFORMS Journal on Computing, INFORMS, vol. 34(6), pages 3117-3133, November.
    13. M. N. Yarahmadi & S. A. MirHassani & F. Hooshmand, 2023. "A heuristic method to find a quick feasible solution based on the ratio programming," Operational Research, Springer, vol. 23(3), pages 1-19, September.

    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:77:y:2020:i:3:d:10.1007_s10589-020-00216-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.