IDEAS home Printed from https://ideas.repec.org/a/spr/joptap/v198y2023i3d10.1007_s10957-023-02254-9.html
   My bibliography  Save this article

A Successive Linear Relaxation Method for MINLPs with Multivariate Lipschitz Continuous Nonlinearities

Author

Listed:
  • Julia Grübel

    (Friedrich-Alexander-Universität Erlangen-Nürnberg (FAU)
    Energie Campus Nürnberg)

  • Richard Krug

    (Friedrich-Alexander-Universität Erlangen-Nürnberg (FAU))

  • Martin Schmidt

    (Trier University)

  • Winnifried Wollner

    (Universität Hamburg)

Abstract

We present a novel method for mixed-integer optimization problems with multivariate and Lipschitz continuous nonlinearities. In particular, we do not assume that the nonlinear constraints are explicitly given but that we can only evaluate them and that we know their global Lipschitz constants. The algorithm is a successive linear relaxation method in which we alternate between solving a master problem, which is a mixed-integer linear relaxation of the original problem, and a subproblem, which is designed to tighten the linear relaxation of the next master problem by using the Lipschitz information about the respective functions. By doing so, we follow the ideas of Schmidt, Sirvent, and Wollner (Math Program 178(1):449–483 (2019) and Optim Lett 16(5):1355-1372 (2022)) and improve the tackling of multivariate constraints. Although multivariate nonlinearities obviously increase modeling capabilities, their incorporation also significantly increases the computational burden of the proposed algorithm. We prove the correctness of our method and also derive a worst-case iteration bound. Finally, we show the generality of the addressed problem class and the proposed method by illustrating that both bilevel optimization problems with nonconvex and quadratic lower levels as well as nonlinear and mixed-integer models of gas transport can be tackled by our method. We provide the necessary theory for both applications and briefly illustrate the outcomes of the new method when applied to these two problems.

Suggested Citation

  • Julia Grübel & Richard Krug & Martin Schmidt & Winnifried Wollner, 2023. "A Successive Linear Relaxation Method for MINLPs with Multivariate Lipschitz Continuous Nonlinearities," Journal of Optimization Theory and Applications, Springer, vol. 198(3), pages 1077-1117, September.
    • Handle: RePEc:spr:joptap:v:198:y:2023:i:3:d:10.1007_s10957-023-02254-9
    DOI: 10.1007/s10957-023-02254-9
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10957-023-02254-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/s10957-023-02254-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. Christoph Buchheim & Renke Kuhlmann & Christian Meyer, 2018. "Combinatorial optimal control of semilinear elliptic PDEs," Computational Optimization and Applications, Springer, vol. 70(3), pages 641-675, July.
    2. Beck, Yasmine & Ljubić, Ivana & Schmidt, Martin, 2023. "A survey on bilevel optimization under uncertainty," European Journal of Operational Research, Elsevier, vol. 311(2), pages 401-426.
    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. Yasmine Beck & Daniel Bienstock & Martin Schmidt & Johannes Thürauf, 2023. "On a Computationally Ill-Behaved Bilevel Problem with a Continuous and Nonconvex Lower Level," Journal of Optimization Theory and Applications, Springer, vol. 198(1), pages 428-447, July.
    2. Blom, Danny & Smeulders, Bart & Spieksma, Frits, 2024. "Rejection-proof mechanisms for multi-agent kidney exchange," Games and Economic Behavior, Elsevier, vol. 143(C), pages 25-50.
    3. Puming Wang & Liqin Zheng & Tianyi Diao & Shengquan Huang & Xiaoqing Bai, 2023. "Robust Bilevel Optimal Dispatch of Park Integrated Energy System Considering Renewable Energy Uncertainty," Energies, MDPI, vol. 16(21), pages 1-23, October.
    4. Jacquet, Quentin & van Ackooij, Wim & Alasseur, Clémence & Gaubert, Stéphane, 2024. "Quadratic regularization of bilevel pricing problems and application to electricity retail markets," European Journal of Operational Research, Elsevier, vol. 313(3), pages 841-857.
    5. Jiayi Xu & Mario Di Nardo & Shi Yin, 2024. "Improved Swarm Intelligence-Based Logistics Distribution Optimizer: Decision Support for Multimodal Transportation of Cross-Border E-Commerce," Mathematics, MDPI, vol. 12(5), pages 1-20, March.
    6. Carolin Natemeyer & Daniel Wachsmuth, 2021. "A proximal gradient method for control problems with non-smooth and non-convex control cost," Computational Optimization and Applications, Springer, vol. 80(2), pages 639-677, November.
    7. Jeffrey Larson & Sven Leyffer & Prashant Palkar & Stefan M. Wild, 2021. "A method for convex black-box integer global optimization," Journal of Global Optimization, Springer, vol. 80(2), pages 439-477, June.

    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:joptap:v:198:y:2023:i:3:d:10.1007_s10957-023-02254-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.