IDEAS home Printed from https://ideas.repec.org/a/inm/ormoor/v48y2023i4p2287-2303.html

Reduction of Potential-Based Flow Networks

Author

Listed:
  • Max Klimm

    (Institut für Mathematik, Technische Universität Berlin, 10623 Berlin, Germany)

  • Marc E. Pfetsch

    (Department of Mathematics, Technische Universität Darmstadt, 64293 Darmstadt, Germany)

  • Rico Raber

    (Institut für Mathematik, Technische Universität Berlin, 10623 Berlin, Germany)

  • Martin Skutella

    (Institut für Mathematik, Technische Universität Berlin, 10623 Berlin, Germany)

Abstract

We consider potential-based flow networks with terminal nodes at which flow can enter or leave the network and physical properties, such as voltages or pressures, are measured and controlled. We study conditions under which such a network can be reduced to a smaller, equivalent network with the same behavior at the terminal nodes. Potential-based flow networks are widely used to model infrastructure networks, such as electricity, gas, or water networks. In contrast to Kron’s reduction for electrical networks, we prove that, in general, potential-based flow networks with at least three terminals cannot be reduced to smaller networks whose size only depends on the number of terminals. On the other hand, we show that it is possible to represent a special class of potential-based flow networks by a complete graph on the terminals, and we establish a characterization of networks that can be reduced to a path network. Our results build on fundamental properties of effective resistances proved in this paper, including explicit formulae for their dependence on edge resistances of the network and their metric properties.

Suggested Citation

  • Max Klimm & Marc E. Pfetsch & Rico Raber & Martin Skutella, 2023. "Reduction of Potential-Based Flow Networks," Mathematics of Operations Research, INFORMS, vol. 48(4), pages 2287-2303, November.
    • Handle: RePEc:inm:ormoor:v:48:y:2023:i:4:p:2287-2303
    DOI: 10.1287/moor.2022.1338
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/moor.2022.1338
    Download Restriction: no
    File URL: https://libkey.io/10.1287/moor.2022.1338?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. M. Collins & L. Cooper & R. Helgason & J. Kennington & L. LeBlanc, 1978. "Solving the Pipe Network Analysis Problem Using Optimization Techniques," Management Science, INFORMS, vol. 24(7), pages 747-760, March.
    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. 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.
    2. Brkic, Dejan, 2009. "An improvement of Hardy Cross method applied on looped spatial natural gas distribution networks," Applied Energy, Elsevier, vol. 86(7-8), pages 1290-1300, July.
    3. Hong, Sung-Pil & Kim, Taegyoon & Lee, Subin, 2019. "A precision pump schedule optimization for the water supply networks with small buffers," Omega, Elsevier, vol. 82(C), pages 24-37.
    4. J. David Allen & Richard V. Helgason & Jeffery L. Kennington, 1987. "The frequency assignment problem: A solution via nonlinear programming," Naval Research Logistics (NRL), John Wiley & Sons, vol. 34(1), pages 133-139, February.
    5. Fränk Plein & Johannes Thürauf & Martine Labbé & Martin Schmidt, 2022. "A bilevel optimization approach to decide the feasibility of bookings in the European gas market," Mathematical Methods of Operations Research, Springer;Gesellschaft für Operations Research (GOR);Nederlands Genootschap voor Besliskunde (NGB), vol. 95(3), pages 409-449, June.
    6. Lars Schewe & Martin Schmidt & Johannes Thürauf, 2022. "Global optimization for the multilevel European gas market system with nonlinear flow models on trees," Journal of Global Optimization, Springer, vol. 82(3), pages 627-653, March.
    7. Ralf Lenz & Kai Helge Becker, 2022. "Optimization of capacity expansion in potential-driven networks including multiple looping: a comparison of modelling approaches," OR Spectrum: Quantitative Approaches in Management, Springer;Gesellschaft für Operations Research e.V., vol. 44(1), pages 179-224, March.
    8. Marins, Fernando A. S. & Senne, Edson L. F. & Darby-Dowman, Ken & Machado, Arlene F. & Perin, Clovis, 1997. "Algorithms for network piecewise-linear programs: A comparative study," European Journal of Operational Research, Elsevier, vol. 97(1), pages 183-199, February.
    9. Spyros Kontogiorgis, 2000. "Practical Piecewise-Linear Approximation for Monotropic Optimization," INFORMS Journal on Computing, INFORMS, vol. 12(4), pages 324-340, November.
    10. Chidozie Charles Nnaji & Oloche Robert Ekwule & Cyrus Nnaji, 2025. "An extended period modeling of water supply systems using hydraulic simulators," Environment, Development and Sustainability: A Multidisciplinary Approach to the Theory and Practice of Sustainable Development, Springer, vol. 27(6), pages 12797-12825, June.
    11. Jesco Humpola & Armin Fügenschuh, 2015. "Convex reformulations for solving a nonlinear network design problem," Computational Optimization and Applications, Springer, vol. 62(3), pages 717-759, December.
    12. Syed Abbas Hussain Rizvi & Rabee Rustum & Luigi Berardi & Grant Wright & Scott Arthur & Daniele Laucelli, 2025. "Studying the Effects of Private Water Storage Tanks on Pump Scheduling Optimization and Leakage Control," Sustainability, MDPI, vol. 17(5), pages 1-19, February.
    13. Antoine Gautier & Frieda Granot, 1996. "Ripples, complements, and substitutes in generalized networks," Naval Research Logistics (NRL), John Wiley & Sons, vol. 43(1), pages 1-21, February.
    14. Lonnie Turpin & Barron Brown, 2021. "On Reworks in a Serial Process with Flexible Windows of Time," SN Operations Research Forum, Springer, vol. 2(2), pages 1-13, June.
    15. Byron Tasseff & Russell Bent & Carleton Coffrin & Clayton Barrows & Devon Sigler & Jonathan Stickel & Ahmed S. Zamzam & Yang Liu & Pascal Van Hentenryck, 2024. "Polyhedral Relaxations for Optimal Pump Scheduling of Potable Water Distribution Networks," INFORMS Journal on Computing, INFORMS, vol. 36(4), pages 1040-1063, July.
    16. Martin Robinius & Lars Schewe & Martin Schmidt & Detlef Stolten & Johannes Thürauf & Lara Welder, 2019. "Robust optimal discrete arc sizing for tree-shaped potential networks," Computational Optimization and Applications, Springer, vol. 73(3), pages 791-819, July.
    17. Babonneau, F. & Gilbert, D. & Piller, O. & Vial, J.P., 2024. "Robust optimal design of a tree-based water distribution network with intermittent demand," European Journal of Operational Research, Elsevier, vol. 319(3), pages 834-844.
    18. D’Ambrosio, Claudia & Lodi, Andrea & Wiese, Sven & Bragalli, Cristiana, 2015. "Mathematical programming techniques in water network optimization," European Journal of Operational Research, Elsevier, vol. 243(3), pages 774-788.

    More about this item

    Keywords

    ;
    ;
    ;
    ;
    ;

    JEL classification:

    Statistics

    Access and download statistics

    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:ormoor:v:48:y:2023:i:4:p:2287-2303. 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.