On the Robustness of Potential-Based Flow Networks (Max Klimm, Marc E. Pfetsch, Rico Raber, and Martin Skutella)
Mathematical Programming, 197:337–374, 2023.
@article{KlimmPfetschRaber+2022a,
author = {Max Klimm and Marc E. Pfetsch and Rico Raber and Martin Skutella},
doi = {10.1007/s10107-021-01760-w},
journal = {Mathematical Programming},
title = {On the Robustness of Potential-Based Flow Networks},
year = {2023},
volume = {197},
pages = {337--374},
}
Potential-based flows provide a simple yet realistic mathematical model of transport in many real-world infrastructure networks such as, e.g., gas or water networks, where the flow along each edge depends on the difference of the potentials at its end nodes. We call a network topology robust if the maximal node potential needed to satisfy a set of demands never increases when demands are decreased. This notion of robustness is motivated by infrastructure networks where users first make reservations for certain demands that may be larger than the actual flows sent later on. In these networks, node potentials correspond to physical quantities such as pressures or hydraulic heads and must be guaranteed to lie within a fixed range, even if the actual amounts are smaller than the previously reserved demands. Our main results are a precise characterization of robust network topologies for the case of point-to-point demands via forbidden node-labeled graph minors, as well as an efficient algorithm for testing robustness.
Reduction of Potential-Based Flow Networks (Max Klimm, Marc Pfetsch, Rico Raber, and Martin Skutella)
Mathematics of Operations Research, 48:2287–2303, 2023.
@article{KlimmPfetschRaber+2023,
author = {Max Klimm and Marc Pfetsch and Rico Raber and Martin Skutella},
title = {Reduction of Potential-Based Flow Networks},
journal = {Mathematics of Operations Research},
volume = {48},
issue = {4},
year = {2023},
pages = {2287--2303},
doi = {10.1287/moor.2022.1338},
}
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.
