IDEAS home Printed from https://ideas.repec.org/a/inm/orijoc/v36y2024i2p397-416.html
   My bibliography  Save this article

A Consensus-Based Alternating Direction Method for Mixed-Integer and PDE-Constrained Gas Transport Problems

Author

Listed:
  • Richard Krug

    (Department of Data Science, Friedrich-Alexander-Universität Erlangen-Nürnberg, 91058 Erlangen, Germany)

  • Günter Leugering

    (Department of Data Science, Friedrich-Alexander-Universität Erlangen-Nürnberg, 91058 Erlangen, Germany)

  • Alexander Martin

    (Department of Liberal Arts and Sciences, University of Technology Nuremberg, D-90443 Nürnberg, Germany)

  • Martin Schmidt

    (Department of Mathematics, Trier University, 54296 Trier, Germany)

  • Dieter Weninger

    (Department of Data Science, Friedrich-Alexander-Universität Erlangen-Nürnberg, 91058 Erlangen, Germany)

Abstract

We consider dynamic gas transport optimization problems, which lead to large-scale and nonconvex mixed-integer nonlinear optimization problems (MINLPs) on graphs. Usually, the resulting instances are too challenging to be solved by state-of-the-art MINLP solvers. In this paper, we use graph decompositions to obtain multiple optimization problems on smaller blocks, which can be solved in parallel and may result in simpler classes of optimization problems because not every block necessarily contains mixed-integer or nonlinear aspects. For achieving feasibility at the interfaces of the several blocks, we employ a tailored consensus-based penalty alternating direction method. Our numerical results show that such decomposition techniques can outperform the baseline approach of just solving the overall MINLP from scratch. However, a complete answer to the question of how to decompose MINLPs on graphs in dependence of the given model is still an open topic for future research.

Suggested Citation

  • Richard Krug & Günter Leugering & Alexander Martin & Martin Schmidt & Dieter Weninger, 2024. "A Consensus-Based Alternating Direction Method for Mixed-Integer and PDE-Constrained Gas Transport Problems," INFORMS Journal on Computing, INFORMS, vol. 36(2), pages 397-416, March.
    • Handle: RePEc:inm:orijoc:v:36:y:2024:i:2:p:397-416
    DOI: 10.1287/ijoc.2022.0319
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/ijoc.2022.0319
    Download Restriction: no
    File URL: https://libkey.io/10.1287/ijoc.2022.0319?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
    ---><---

    References listed on IDEAS

    as
    1. Björn Geißler & Antonio Morsi & Lars Schewe & Martin Schmidt, 2018. "Solving Highly Detailed Gas Transport MINLPs: Block Separability and Penalty Alternating Direction Methods," INFORMS Journal on Computing, INFORMS, vol. 30(2), pages 309-323, May.
    2. Daniel Rose & Martin Schmidt & Marc C. Steinbach & Bernhard M. Willert, 2016. "Computational optimization of gas compressor stations: MINLP models versus continuous reformulations," Mathematical Methods of Operations Research, Springer;Gesellschaft für Operations Research (GOR);Nederlands Genootschap voor Besliskunde (NGB), vol. 83(3), pages 409-444, June.
    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. Johannes Thürauf, 2022. "Deciding the feasibility of a booking in the European gas market is coNP-hard," Annals of Operations Research, Springer, vol. 318(1), pages 591-618, November.
    2. Falk M. Hante & Martin Schmidt, 2019. "Complementarity-based nonlinear programming techniques for optimal mixing in gas networks," EURO Journal on Computational Optimization, Springer;EURO - The Association of European Operational Research Societies, vol. 7(3), pages 299-323, September.
    3. Benjamin Hiller & René Saitenmacher & Tom Walther, 2021. "Improved models for operation modes of complex compressor stations," Mathematical Methods of Operations Research, Springer;Gesellschaft für Operations Research (GOR);Nederlands Genootschap voor Besliskunde (NGB), vol. 94(2), pages 171-195, October.
    4. Mengying Xue & Tianhu Deng & Zuo‐Jun Max Shen, 2019. "Optimizing natural gas pipeline transmission with nonuniform elevation: A new initialization approach," Naval Research Logistics (NRL), John Wiley & Sons, vol. 66(7), pages 547-564, October.
    5. Lars Schewe & Martin Schmidt & Johannes Thürauf, 2020. "Structural properties of feasible bookings in the European entry–exit gas market system," 4OR, Springer, vol. 18(2), pages 197-218, June.
    6. Milosavljevic, Predrag & Marchetti, Alejandro G. & Cortinovis, Andrea & Faulwasser, Timm & Mercangöz, Mehmet & Bonvin, Dominique, 2020. "Real-time optimization of load sharing for gas compressors in the presence of uncertainty," Applied Energy, Elsevier, vol. 272(C).
    7. Thomas Kleinert & Martin Schmidt, 2021. "Computing Feasible Points of Bilevel Problems with a Penalty Alternating Direction Method," INFORMS Journal on Computing, INFORMS, vol. 33(1), pages 198-215, January.
    8. Wen, Kai & Qiao, Dan & Nie, Chaofei & Lu, Yangfan & Wen, Feng & Zhang, Jing & Miao, Qing & Gong, Jing & Li, Cuicui & Hong, Bingyuan, 2023. "Multi-period supply and demand balance of large-scale and complex natural gas pipeline network: Economy and environment," Energy, Elsevier, vol. 264(C).
    9. Lars Schewe & Martin Schmidt & Johannes Thürauf, 2020. "Computing technical capacities in the European entry-exit gas market is NP-hard," Annals of Operations Research, Springer, vol. 295(1), pages 337-362, December.
    10. Veronika Grimm & Lars Schewe & Martin Schmidt & Gregor Zöttl, 2019. "A multilevel model of the European entry-exit gas market," Mathematical Methods of Operations Research, Springer;Gesellschaft für Operations Research (GOR);Nederlands Genootschap voor Besliskunde (NGB), vol. 89(2), pages 223-255, April.
    11. Jan Pablo Burgard & Carina Moreira Costa & Martin Schmidt, 2024. "Robustification of the k-means clustering problem and tailored decomposition methods: when more conservative means more accurate," Annals of Operations Research, Springer, vol. 339(3), pages 1525-1568, August.
    12. Carina Moreira Costa & Dennis Kreber & Martin Schmidt, 2022. "An Alternating Method for Cardinality-Constrained Optimization: A Computational Study for the Best Subset Selection and Sparse Portfolio Problems," INFORMS Journal on Computing, INFORMS, vol. 34(6), pages 2968-2988, November.
    13. Björn Geißler & Antonio Morsi & Lars Schewe & Martin Schmidt, 2018. "Solving Highly Detailed Gas Transport MINLPs: Block Separability and Penalty Alternating Direction Methods," INFORMS Journal on Computing, INFORMS, vol. 30(2), pages 309-323, May.
    14. Pia Domschke & Oliver Kolb & Jens Lang, 2022. "Fast and reliable transient simulation and continuous optimization of large-scale gas networks," Mathematical Methods of Operations Research, Springer;Gesellschaft für Operations Research (GOR);Nederlands Genootschap voor Besliskunde (NGB), vol. 95(3), pages 475-501, June.
    15. Wang, Guotao & Zhao, Wei & Qiu, Rui & Liao, Qi & Lin, Zhenjia & Wang, Chang & Zhang, Haoran, 2023. "Operational optimization of large-scale thermal constrained natural gas pipeline networks: A novel iterative decomposition approach," Energy, Elsevier, vol. 282(C).
    16. Groissböck, Markus, 2019. "Are open source energy system optimization tools mature enough for serious use?," Renewable and Sustainable Energy Reviews, Elsevier, vol. 102(C), pages 234-248.
    17. Martin Schmidt & Denis Aßmann & Robert Burlacu & Jesco Humpola & Imke Joormann & Nikolaos Kanelakis & Thorsten Koch & Djamal Oucherif & Marc E. Pfetsch & Lars Schewe & Robert Schwarz & Mathias Sirvent, 2017. "GasLib—A Library of Gas Network Instances," Data, MDPI, vol. 2(4), pages 1-18, 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:inm:orijoc:v:36:y:2024:i:2:p:397-416. 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: Chris Asher (email available below). General contact details of provider: https://edirc.repec.org/data/inforea.html .

    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.