Combinatorial Network Flow Methods for Instationary Gas Flows and Gas Market Problems
Project Goal
This project develops combinatorial and algorithmic methods for planning and
transforming gas and hydrogen infrastructures under potential-based flow
laws. It links strategic network expansion with staged modernization,
aiming to keep service quality high while infrastructure is being migrated.
The work combines two complementary viewpoints: mixed-integer nonlinear
optimization for cost-minimal physical network design, and competitive
analysis for transformation orders that maintain high utility in all
intermediate states.
Main Results
For physical network design, the project studies a MINLP with binary build
variables and potential-flow coupling,
\[
\pi_u-\pi_v = \beta_a\,\mathrm{sign}(f_a)\,|f_a|^r.
\]
A key contribution is a new class of strong valid inequalities for fractional
relaxations, together with a polynomial-time separation routine. This enables
direct integration into branch-and-cut.
The computational study on path and GasLib instances confirms substantial
practical gains: for example, Path52 is solved at the root node with cuts,
while the cut-free version hits the time limit; on GasLib134, the final gap
within the same time limit decreases from 114.7\% to 41.5\%.
In parallel, the project introduces incremental-decremental maximization for
staged renewal, where an order \(\pi=(e_1,\dots,e_n)\) of transformed
elements must preserve high utility throughout the rollout.
For monotone functions with curvature \(c\in(0,1]\) and generic
submodularity ratio \(\gamma\in(0,1]\), the proposed double-greedy
algorithm achieves
\[
\rho \le \frac{1}{\gamma}\left(1+\frac{c e^c}{e^c-1}\right).
\]
This yields \(1+\tfrac{e}{e-1}\)-competitiveness for submodular functions
and factor \(2\) for gross substitutes.
The analysis also establishes inherent limits: nontrivial lower bounds remain
even in structured settings (including \(5/4\) for gross substitutes and
bounds parameterized by curvature and submodularity ratio).
Overall, the project contributes methods that are both mathematically
rigorous and operationally relevant for transition planning in future gas and
hydrogen networks.
References
- Valid Cuts for the Design of Potential-based Flow Networks (Pascal Börner, Max Klimm, Annette Lutz, Marc Pfetsch, Martin Skutella, and Lea Strubberg)
IPCO 2025 – Proc. 26th Conference on Integer Programming and Combinatorial Optimization, pp. 142–156.
@inproceedings{BoernerKlimmLutz+2025,
author = {Pascal Börner and Max Klimm and Annette Lutz and Marc Pfetsch and Martin Skutella and Lea Strubberg},
title = {Valid Cuts for the Design of Potential-based Flow Networks},
booktitle = {IPCO 2025 – Proc. 26th Conference on Integer Programming and Combinatorial Optimization},
pages = {142--156},
doi = {10.1007/978-3-031-93112-3_11},
year = {2025},
}
The construction of a cost minimal network for flows obeying physical laws is an important problem for the design of electricity, water, hydrogen, and natural gas infrastructures. We formulate this problem as a mixed-integer non-linear program. Its non-convexity, due to the potential flow, together with the binary variables, indicating the decision to build a connection, make these problems challenging to solve. We develop a novel class of valid inequalities on the fractional relaxations of the binary variables. Further, we show that this class of inequalities can be separated in polynomial for solutions to a fractional relaxation. This makes it possible to incorporate these inequalities into a branch-and-bound algorithm. The advantage of these inequalities is lastly demonstrated in a computational study on the design of real-world gas transport networks.
- Incremental–Decremental Maximization (Yann Disser, Max Klimm, Annette Lutz, and Lea Strubberg)
WAOA 2025 – Proc. 23th Workshop on Approximation and Online Algorithms, pp. 97–110.
@inproceedings{DisserKlimmLutz+2025,
author = {Yann Disser and Max Klimm and Annette Lutz and Lea Strubberg},
title = {Incremental–Decremental Maximization},
booktitle = {WAOA 2025 – Proc. 23th Workshop on Approximation and Online Algorithms},
year = {2025},
doi = {10.1007/978-3-032-06706-7_7},
pages = {97--110},
}
We introduce a framework for incremental–decremental maximization that captures the gradual transformation or renewal of infrastructures. In our model, an initial solution is transformed one element at a time and the utility of an intermediate solution is given by the sum of the utilities of the transformed and untransformed parts. We propose a simple randomized and a deterministic algorithm that both find an order in which to transform the elements while maintaining a large utility during all stages of transformation, relative to an optimum solution for the current stage. More specifically, our algorithms yield competitive solutions for utility functions of bounded curvature and/or generic submodularity ratio, and, in particular, for submodular functions, and gross substitute functions. Our results exhibit that incremental–decremental maximization is substantially more difficult than incremental maximization.
