@misc{PedersenLindnerRehfeldtetal.2025, author = {Pedersen, Jaap and Lindner, Niels and Rehfeldt, Daniel and Koch, Thorsten}, title = {Comparing Branching Rules for the Quota Steiner Tree Problem with Interference}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-101250}, year = {2025}, abstract = {Branching decisions play a crucial role in branch-and-bound algorithms for solving combinatorial optimization problems. In this paper, we investigate several branching rules applied to the Quota Steiner Tree Problem with Interference (QSTPI). The Quota Steiner Tree Problem (QSTP) generalizes the classical Steiner Tree Problem (STP) in graphs by seeking a minimum-cost tree that connects a subset of profit-associated vertices to meet a given quota. The extended version, QSTPI, introduces interference among vertices: Selecting certain vertices simultaneously reduces their individual contributions to the overall profit. This problem arises, for example, in positioning and connecting wind turbines, where turbines possibly shadow other turbines, reducing their energy yield. While exact solvers for standard STP-related problems often rely heavily on reduction techniques and cutting-plane methods - rarely generating large branch-and-bound trees - experiments reveal that large instances of QSTPI require significantly more branching to compute provably optimal solutions. In contrast to branching on variables, we utilize the combinatorial structure of the QSTPI by branching on the graph's vertices. We adapt classical and problem-specific branching rules and present a comprehensive computational study comparing the effectiveness of these branching strategies.}, language = {en} } @article{PedersenLeKochetal.2024, author = {Pedersen, Jaap and Le, Thi Thai and Koch, Thorsten and Zittel, Janina}, title = {Optimal discrete pipe sizing for tree-shaped CO2 networks}, volume = {46}, journal = {OR Spectrum}, doi = {10.1007/s00291-024-00773-z}, pages = {1163 -- 1187}, year = {2024}, abstract = {For industries like the cement industry, switching to a carbon-neutral production process is impossible. They must rely on carbon capture, utilization and storage (CCUS) technologies to reduce their production processes' inevitable carbon dioxide (CO2) emissions. For transporting continuously large amounts of CO2, utilizing a pipeline network is the most effective solution; however, building such a network is expensive. Therefore minimizing the cost of the pipelines to be built is extremely important to make the operation financially feasible. In this context, we investigate the problem of finding optimal pipeline diameters from a discrete set of diameters for a tree-shaped network transporting captured CO2 from multiple sources to a single sink. The general problem of optimizing arc capacities in potential-based fluid networks is already a challenging mixed-integer nonlinear optimization problem. The problem becomes even more complex when adding the highly sensitive nonlinear behavior of CO2 regarding temperature and pressure changes. We propose an iterative algorithm splitting the problem into two parts: a) the pipe-sizing problem under a fixed supply scenario and temperature distribution and b) the thermophysical modeling, including mixing effects, the Joule-Thomson effect, and heat exchange with the surrounding environment. We demonstrate the effectiveness of our approach by applying our algorithm to a real-world network planning problem for a CO2 network in Western Germany. Further, we show the robustness of the algorithm by solving a large artificially created set of network instances.}, language = {en} } @article{VanBulckGoossensClarneretal.2024, author = {Van Bulck, David and Goossens, Dries and Clarner, Jan-Patrick and Dimitsas, Angelos and Fonseca, Georg H. G. and Lamas-Fernandez, Carlos and Lester, Martin Mariusz and Pedersen, Jaap and Phillips, Antony E. and Rosati, Roberto Maria}, title = {Which algorithm to select in sports timetabling?}, volume = {318}, journal = {European Journal of Operational Research}, number = {2}, arxiv = {http://arxiv.org/abs/2309.03229}, doi = {10.1016/j.ejor.2024.06.005}, pages = {575 -- 591}, year = {2024}, abstract = {Any sports competition needs a timetable, specifying when and where teams meet each other. The recent International Timetabling Competition (ITC2021) on sports timetabling showed that, although it is possible to develop general algorithms, the performance of each algorithm varies considerably over the problem instances. This paper provides a problem type analysis for sports timetabling, resulting in powerful insights into the strengths and weaknesses of eight state-of-the-art algorithms. Based on machine learning techniques, we propose an algorithm selection system that predicts which algorithm is likely to perform best based on the type of competition and constraints being used (i.e., the problem type) in a given sports timetabling problem instance. Furthermore, we visualize how the problem type relates to algorithm performance, providing insights and possibilities to further enhance several algorithms. Finally, we assess the empirical hardness of the instances. Our results are based on large computational experiments involving about 50 years of CPU time on more than 500 newly generated problem instances.}, language = {en} } @article{PedersenWeinandSyranidouetal.2024, author = {Pedersen, Jaap and Weinand, Jann Michael and Syranidou, Chloi and Rehfeldt, Daniel}, title = {An efficient solver for large-scale onshore wind farm siting including cable routing}, volume = {317}, journal = {European Journal of Operational Research}, number = {2}, arxiv = {http://arxiv.org/abs/2304.09658}, doi = {10.1016/j.ejor.2024.04.026}, pages = {616 -- 630}, year = {2024}, abstract = {Existing planning approaches for onshore wind farm siting and grid integration often do not meet minimum cost solutions or social and environmental considerations. In this paper, we develop an exact approach for the integrated layout and cable routing problem of onshore wind farm planning using the Quota Steiner tree problem. Applying a novel transformation on a known directed cut formulation, reduction techniques, and heuristics, we design an exact solver that makes large problem instances solvable and outperforms generic MIP solvers. In selected regions of Germany, the trade-offs between minimizing costs and landscape impact of onshore wind farm siting are investigated. Although our case studies show large trade-offs between the objective criteria of cost and landscape impact, small burdens on one criterion can significantly improve the other criteria. In addition, we demonstrate that contrary to many approaches for exclusive turbine siting, grid integration must be simultaneously optimized to avoid excessive costs or landscape impacts in the course of a wind farm project. Our novel problem formulation and the developed solver can assist planners in decision-making and help optimize wind farms in large regions in the future.}, language = {en} } @inproceedings{PedersenHoppmannBaumZitteletal.2022, author = {Pedersen, Jaap and Hoppmann-Baum, Kai and Zittel, Janina and Koch, Thorsten}, title = {Blending hydrogen into natural gas: An assessment of the capacity of the German gas grid}, booktitle = {Operations Research Proceedings 2021}, doi = {https://doi.org/10.1007/978-3-031-08623-6_28}, pages = {182 -- 187}, year = {2022}, abstract = {In the transition towards a pure hydrogen infrastructure, repurposing the existing natural gas infrastructure is considered. In this study, the maximal technically feasible injection of hydrogen into the existing German natural gas transmission network is analysed with respect to regulatory limits regarding the gas quality. We propose a transient tracking model based on the general pooling problem including linepack. The analysis is conducted using real-world hourly gas flow data on a network of about 10,000 km length.}, language = {en} } @misc{KochBertholdPedersenetal.2022, author = {Koch, Thorsten and Berthold, Timo and Pedersen, Jaap and Vanaret, Charlie}, title = {Progress in Mathematical Programming Solvers from 2001 to 2020}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-82779}, year = {2022}, abstract = {This study investigates the progress made in LP and MILP solver performance during the last two decades by comparing the solver software from the beginning of the millennium with the codes available today. On average, we found out that for solving LP/MILP, computer hardware got about 20 times faster, and the algorithms improved by a factor of about nine for LP and around 50 for MILP, which gives a total speed-up of about 180 and 1,000 times, respectively. However, these numbers have a very high variance and they considerably underestimate the progress made on the algorithmic side: many problem instances can nowadays be solved within seconds, which the old codes are not able to solve within any reasonable time.}, language = {en} } @misc{PedersenHoppmannBaumZitteletal.2021, author = {Pedersen, Jaap and Hoppmann-Baum, Kai and Zittel, Janina and Koch, Thorsten}, title = {Blending hydrogen into natural gas: An assessment of the capacity of the German gas grid; Technical Report}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-82838}, year = {2021}, abstract = {In the transition towards a pure hydrogen infrastructure, utilizing the existing natural gas infrastructure is a necessity. In this study, the maximal technically feasible injection of hydrogen into the existing German natural gas transmission network is analysed with respect to regulatory limits regarding the gas quality. We propose a transient tracking model based on the general pooling problem including linepack. The analysis is conducted using real-world hourly gas flow data on a network of about 10,000 km length.}, language = {en} } @inproceedings{PedersenSchachlerHeideretal.2021, author = {Pedersen, Jaap and Schachler, Birgit and Heider, Anya and Pleßmann, Guido}, title = {Distribution System Planning with Battery Storage using Multiperiod Optimal Power Flow}, volume = {6}, booktitle = {14th International Renewable Energy Storage Conference 2020 (IRES 2020)}, doi = {https://doi.org/10.2991/ahe.k.210202.007}, pages = {41 -- 48}, year = {2021}, abstract = {The ongoing energy transition introduces new challenges for distribution networks and brings about the need to expand existing power grid capacities. In order to contain network expansion and with it economic costs, utilization of various flexibility options to reduce expansion needs is discussed. This paper proposes a multiperiod optimal power flow (MPOPF) approach with a new continuous network expansion formulation to optimize the deployment of flexibility options under the objective of minimizing network expansion costs. In a comparison of the newly proposed continuous network expansion formulation with an existing mixed integer formulation and a continuous interpretation of the latter the here proposed formulation is shown to be useful in order to obtain a solvable problem and contain computational efforts. The presented MPOPF including the flexibility options storage units and curtailment is then assessed on synthetic medium voltage grids and applied to evaluate the benefit of a combined vs. a stepwise optimization of these flexibility options. It is demonstrated that using a local solver the proposed approach is applicable and yields a solution in reasonable time. Furthermore, it is shown that the combined optimization generally leads to a more efficient utilization of the considered flexibility options and therefore lower grid expansion costs than the stepwise consideration.}, language = {en} } @article{PedersenSpreckelsenGotzesetal.2023, author = {Pedersen, Jaap and Spreckelsen, Klaus and Gotzes, Uwe and Zittel, Janina and Koch, Thorsten}, title = {Beimischung von Wasserstoff zum Erdgas: Eine Kapazit{\"a}tsstudie des deutschen Gasnetzes}, journal = {3R - Fachzeitschrift f{\"u}r Rohrleitungssystem}, number = {06/2023}, pages = {70 -- 75}, year = {2023}, abstract = {Die europ{\"a}ische Gasinfrastruktur wird disruptiv in ein zuk{\"u}nftiges dekarbonisiertes Energiesystem ver{\"a}ndert; ein Prozess, der angesichts der j{\"u}ngsten politischen Situation beschleunigt werden muss. Mit einem wachsenden Wasserstoffmarkt wird der pipelinebasierte Transport unter Nutzung der bestehenden Erdgasinfrastruktur wirtschaftlich sinnvoll, tr{\"a}gt zur Erh{\"o}hung der {\"o}ffentlichen Akzeptanz bei und beschleunigt den Umstellungsprozess. In diesem Fachbeitrag wird die maximal technisch machbare Einspeisung von Wasserstoff in das bestehende deutsche Erdgastransportnetz hinsichtlich regulatorischer Grenzwerte der Gasqualit{\"a}t analysiert. Die Analyse erfolgt auf Basis eines transienten Tracking-Modells, das auf dem allgemeinen Pooling-Problem einschließlich Linepack aufbaut. Es zeigt sich, dass das Gasnetz auch bei strengen Grenzwerten gen{\"u}gend Kapazit{\"a}t bietet, um f{\"u}r einen großen Teil der bis 2030 geplanten Erzeugungskapazit{\"a}t f{\"u}r gr{\"u}nen Wasserstoff als garantierter Abnehmer zu dienen.}, language = {de} } @article{PedersenSpreckelsenGotzesetal.2023, author = {Pedersen, Jaap and Spreckelsen, Klaus and Gotzes, Uwe and Zittel, Janina and Koch, Thorsten}, title = {Beimischung von Wasserstoff zum Erdgas: Eine Kapazit{\"a}tsstudie des deutschen Gasnetzes}, journal = {gwf Gas + Energie}, edition = {06/2023}, publisher = {Vulkan Verlag}, year = {2023}, abstract = {Die europaische Gasinfrastruktur wird disruptiv in ein zukunftiges dekarbonisiertes Energiesystem ver{\"a}ndert; ein Prozess, der angesichts der j{\"u}ngsten politischen Situation beschleunigt werden muss. Mit einem wachsenden Wasserstoffmarkt wird der pipelinebasierte Transport unter Nutzung der bestehenden Erdgasinfrastruktur wirtschaftlich sinnvoll, tr{\"a}gt zur Erh{\"o}hung der {\"o}ffentlichen Akzeptanz bei und beschleunigt den Umstellungsprozess. In diesem Beitrag wird die maximal technisch machbare Einspeisung von Wasserstoff in das bestehende deutsche Erdgastransportnetz hinsichtlich regulatorischer Grenzwerte der Gasqualit{\"a}t analysiert. Die Analyse erfolgt auf Basis eines transienten Tracking-Modells, das auf dem allgemeinen Pooling-Problem einschließlich Linepack aufbaut. Es zeigt sich, dass das Gasnetz auch bei strengen Grenzwerten gen ̈ugend Kapazit{\"a}t bietet, um f{\"u}r einen großen Teil der bis 2030 geplanten Erzeugungskapazit{\"a}t f{\"u}r gr{\"u}nen Wasserstoff als garantierter Abnehmer zu dienen.}, language = {de} }