@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} } @misc{RehfeldtKoch2020, author = {Rehfeldt, Daniel and Koch, Thorsten}, title = {On the exact solution of prize-collecting Steiner tree problems}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-78174}, year = {2020}, language = {en} } @article{RehfeldtKoch2023, author = {Rehfeldt, Daniel and Koch, Thorsten}, title = {Implications, Conflicts, and Reductions for Steiner Trees}, volume = {197}, journal = {Mathematical Programming}, publisher = {Springer}, doi = {10.1007/s10107-021-01757-5}, pages = {903 -- 966}, year = {2023}, language = {en} } @misc{KempkeRehfeldtKoch2024, author = {Kempke, Nils-Christian and Rehfeldt, Daniel and Koch, Thorsten}, title = {A Massively Parallel Interior-Point-Method for Arrowhead Linear Programs}, issn = {1438-0064}, arxiv = {http://arxiv.org/abs/2412.07731}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-98829}, year = {2024}, abstract = {In practice, non-specialized interior point algorithms often cannot utilize the massively parallel compute resources offered by modern many- and multi-core compute platforms. However, efficient distributed solution techniques are required, especially for large-scale linear programs. This article describes a new decomposition technique for systems of linear equations implemented in the parallel interior-point solver PIPS-IPM++. The algorithm exploits a matrix structure commonly found in optimization problems: a doubly-bordered block-diagonal or arrowhead structure. This structure is preserved in the linear KKT systems solved during each iteration of the interior-point method. We present a hierarchical Schur complement decomposition that distributes and solves the linear optimization problem; it is designed for high-performance architectures and scales well with the availability of additional computing resources. The decomposition approach uses the border constraints' locality to decouple the factorization process. Our approach is motivated by large-scale unit-commitment problems. We demonstrate the performance of our method on a set of mid-to large-scale instances, some of which have more than 10^9 nonzeros in their constraint matrix.}, 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} } @article{RehfeldtHobbieSchoenheitetal.2022, author = {Rehfeldt, Daniel and Hobbie, Hannes and Sch{\"o}nheit, David and Koch, Thorsten and M{\"o}st, Dominik and Gleixner, Ambros}, title = {A massively parallel interior-point solver for LPs with generalized arrowhead structure, and applications to energy system models}, volume = {296}, journal = {European Journal of Operational Research}, number = {1}, doi = {10.1016/j.ejor.2021.06.063}, pages = {60 -- 71}, year = {2022}, abstract = {Linear energy system models are a crucial component of energy system design and operations, as well as energy policy consulting. If detailed enough, such models lead to large-scale linear programs, which can be intractable even for the best state-of-the-art solvers. This article introduces an interior-point solver that exploits common structures of energy system models to efficiently run in parallel on distributed-memory systems. The solver is designed for linear programs with doubly-bordered block-diagonal constraint matrix and makes use of a Schur complement based decomposition. In order to handle the large number of linking constraints and variables commonly observed in energy system models, a distributed Schur complement preconditioner is used. In addition, the solver features a number of more generic techniques such as parallel matrix scaling and structure-preserving presolving. The implementation is based on the solver PIPS-IPM. We evaluate the computational performance on energy system models with up to four billion nonzero entries in the constraint matrix—and up to one billion columns and one billion rows. This article mainly concentrates on the energy system model ELMOD, which is a linear optimization model representing the European electricity markets by the use of a nodal pricing market-clearing. It has been widely applied in the literature on energy system analyses in recent years. However, it will be demonstrated that the new solver is also applicable to other energy system models.}, language = {en} } @inproceedings{RehfeldtKoch2021, author = {Rehfeldt, Daniel and Koch, Thorsten}, title = {Implications, conflicts, and reductions for Steiner trees}, booktitle = {Integer Programming and Combinatorial Optimization: 22th International Conference, IPCO 2021}, doi = {10.1007/978-3-030-73879-2_33}, pages = {473 -- 487}, year = {2021}, language = {en} } @article{RehfeldtKoch2021, author = {Rehfeldt, Daniel and Koch, Thorsten}, title = {On the exact solution of prize-collecting Steiner tree problems}, journal = {INFORMS Journal on Computing}, doi = {10.1287/ijoc.2021.1087}, year = {2021}, language = {en} } @inproceedings{GleixnerKempkeKochetal.2020, author = {Gleixner, Ambros and Kempke, Nils-Christian and Koch, Thorsten and Rehfeldt, Daniel and Uslu, Svenja}, title = {First Experiments with Structure-Aware Presolving for a Parallel Interior-Point Method}, booktitle = {Operations Research Proceedings 2019}, edition = {1}, publisher = {Springer International Publishing}, doi = {10.1007/978-3-030-48439-2_13}, pages = {105 -- 111}, year = {2020}, abstract = {In linear optimization, matrix structure can often be exploited algorithmically. However, beneficial presolving reductions sometimes destroy the special structure of a given problem. In this article, we discuss structure-aware implementations of presolving as part of a parallel interior-point method to solve linear programs with block-diagonal structure, including both linking variables and linking constraints. While presolving reductions are often mathematically simple, their implementation in a high-performance computing environment is a complex endeavor. We report results on impact, performance, and scalability of the resulting presolving routines on real-world energy system models with up to 700 million nonzero entries in the constraint matrix.}, language = {en} } @inproceedings{KochRehfeldtShinano2025, author = {Koch, Thorsten and Rehfeldt, Daniel and Shinano, Yuji}, title = {On the state of QUBO solving}, booktitle = {Operations Research Proceedings 2023. OR 2023}, publisher = {Springer}, doi = {10.1007/978-3-031-58405-3_46}, pages = {357 -- 365}, year = {2025}, abstract = {It is regularly claimed that quantum computers will bring breakthrough progress in solving challenging combinatorial optimization problems relevant in practice. In particular, Quadratic Unconstrained Binary Optimization (QUBO) problems are said to be the model of choice for use in (adiabatic) quantum systems during the noisy intermediate- scale quantum (NISQ) era. Even the first commercial quantum-based systems are advertised to solve such problems. Theoretically, any Integer Program can be converted into a QUBO. In practice, however, there are some caveats, as even for problems that can be nicely modeled as a QUBO, this might not be the most effective way to solve them. We review the state of QUBO solving on digital and quantum computers and provide insights regarding current benchmark instances and modeling.}, language = {en} } @article{RehfeldtFranzKoch2022, author = {Rehfeldt, Daniel and Franz, Henriette and Koch, Thorsten}, title = {Optimal Connected Subgraphs: Integer Programming Formulations and Polyhedra}, volume = {80}, journal = {Networks}, number = {3}, publisher = {Wiley}, doi = {10.1002/net.22101}, pages = {314 -- 332}, year = {2022}, language = {en} } @article{RehfeldtKochShinano2023, author = {Rehfeldt, Daniel and Koch, Thorsten and Shinano, Yuji}, title = {Faster exact solution of sparse MaxCut and QUBO problems}, volume = {15}, journal = {Mathematical Programming Computation}, doi = {10.1007/s12532-023-00236-6}, pages = {445 -- 470}, year = {2023}, abstract = {The maximum-cut problem is one of the fundamental problems in combinatorial optimization. With the advent of quantum computers, both the maximum-cut and the equivalent quadratic unconstrained binary optimization problem have experienced much interest in recent years. This article aims to advance the state of the art in the exact solution of both problems—by using mathematical programming techniques. The main focus lies on sparse problem instances, although also dense ones can be solved. We enhance several algorithmic components such as reduction techniques and cutting-plane separation algorithms, and combine them in an exact branch-and-cut solver. Furthermore, we provide a parallel implementation. The new solver is shown to significantly outperform existing state-of-the-art software for sparse maximum-cut and quadratic unconstrained binary optimization instances. Furthermore, we improve the best known bounds for several instances from the 7th DIMACS Challenge and the QPLIB, and solve some of them (for the first time) to optimality.}, language = {en} } @inproceedings{Rehfeldt2022, author = {Rehfeldt, Daniel}, title = {Faster Algorithms for Steiner Tree and related Problems: From Theory to Practice}, booktitle = {Operations Research Proceedings 2022}, year = {2022}, language = {en} } @misc{RehfeldtFujisawaKochetal.2022, author = {Rehfeldt, Daniel and Fujisawa, Katsuki and Koch, Thorsten and Nakao, Masahiro and Shinano, Yuji}, title = {Computing single-source shortest paths on graphs with over 8 trillion edges}, issn = {1438-0064}, doi = {10.12752/8818}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-88180}, year = {2022}, abstract = {This paper introduces an implementation for solving the single-source shortest path problem on distributed-memory machines. It is tailored to power-law graphs and scales to trillions of edges. The new implementation reached 2nd and 10th place in the latest Graph500 benchmark in June 2022 and handled the largest and second-largest graphs among all participants.}, language = {en} } @article{KempkeRehfeldtKoch2025, author = {Kempke, Nils-Christian and Rehfeldt, Daniel and Koch, Thorsten}, title = {A Massively Parallel Interior-Point-Method for Arrowhead Linear Programs}, journal = {SIAM Journal on Scientific Computing}, arxiv = {http://arxiv.org/abs/2412.07731}, year = {2025}, language = {en} } @misc{PedersenLindnerRehfeldtetal.2025, author = {Pedersen, Jaap and Lindner, Niels and Rehfeldt, Daniel and Koch, Thorsten}, title = {Integrated Wind Farm Design: Optimizing Turbine Placement and Cable Routing with Wake Effects}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-99218}, year = {2025}, abstract = {An accelerated deployment of renewable energy sources is crucial for a successful transformation of the current energy system, with wind energy playing a key role in this transition. This study addresses the integrated wind farm layout and cable routing problem, a challenging nonlinear optimization problem. We model this problem as an extended version of the Quota Steiner Tree Problem (QSTP), optimizing turbine placement and network connectivity simultaneously to meet specified expansion targets. Our proposed approach accounts for the wake effect - a region of reduced wind speed induced by each installed turbine - and enforces minimum spacing between turbines. We introduce an exact solution framework in terms of the novel Quota Steiner Tree Problem with interference (QSTPI). By leveraging an interference-based splitting strategy, we develop an advanced solver capable of tackling large-scale problem instances. The presented approach outperforms generic state-of-the-art mixed integer programming solvers on our dataset by up to two orders of magnitude. Moreover, we demonstrate that our integrated method significantly reduces the costs in contrast to a sequential approach. Thus, we provide a planning tool that enhances existing planning methodologies for supporting a faster and cost-efficient expansion of wind energy.}, language = {en} } @misc{PedersenWeinandSyranidouetal.2023, author = {Pedersen, Jaap and Weinand, Jann Michael and Syranidou, Chloi and Rehfeldt, Daniel}, title = {An efficient solver for multi-objective onshore wind farm siting and network integration}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-90590}, year = {2023}, abstract = {Existing planning approaches for onshore wind farm siting and network integration often do not meet minimum cost solutions or social and environmental considerations. In this paper, we develop an approach for the multi-objective optimization of turbine locations and their network connection using a 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. Although our case studies in selected regions of Germany 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, network integration must be simultaneously optimized in order 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} } @incollection{KochRehfeldtShinano2020, author = {Koch, Thorsten and Rehfeldt, Daniel and Shinano, Yuji}, title = {An exact high performance solver for Steiner tree problems in graphs and related problems}, booktitle = {Modeling, Simulation and Optimization of Complex Processes HPSC 2018}, publisher = {Springer}, year = {2020}, language = {en} } @misc{RehfeldtKoch2020, author = {Rehfeldt, Daniel and Koch, Thorsten}, title = {Implications, conflicts, and reductions for Steiner trees}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-80039}, year = {2020}, language = {en} } @misc{RehfeldtFranzKoch2020, author = {Rehfeldt, Daniel and Franz, Henriette and Koch, Thorsten}, title = {Optimal Connected Subgraphs: Formulations and Algorithms}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-79094}, year = {2020}, language = {en} } @misc{RehfeldtKochShinano2022, author = {Rehfeldt, Daniel and Koch, Thorsten and Shinano, Yuji}, title = {Faster exact solution of sparse MaxCut and QUBO problems}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-85715}, year = {2022}, language = {en} } @misc{BestuzhevaBesanconChenetal.2021, author = {Bestuzheva, Ksenia and Besan{\c{c}}on, Mathieu and Chen, Wei-Kun and Chmiela, Antonia and Donkiewicz, Tim and van Doornmalen, Jasper and Eifler, Leon and Gaul, Oliver and Gamrath, Gerald and Gleixner, Ambros and Gottwald, Leona and Graczyk, Christoph and Halbig, Katrin and Hoen, Alexander and Hojny, Christopher and van der Hulst, Rolf and Koch, Thorsten and L{\"u}bbecke, Marco and Maher, Stephen J. and Matter, Frederic and M{\"u}hmer, Erik and M{\"u}ller, Benjamin and Pfetsch, Marc E. and Rehfeldt, Daniel and Schlein, Steffan and Schl{\"o}sser, Franziska and Serrano, Felipe and Shinano, Yuji and Sofranac, Boro and Turner, Mark and Vigerske, Stefan and Wegscheider, Fabian and Wellner, Philipp and Weninger, Dieter and Witzig, Jakob}, title = {The SCIP Optimization Suite 8.0}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-85309}, year = {2021}, abstract = {The SCIP Optimization Suite provides a collection of software packages for mathematical optimization centered around the constraint integer programming framework SCIP. This paper discusses enhancements and extensions contained in version 8.0 of the SCIP Optimization Suite. Major updates in SCIP include improvements in symmetry handling and decomposition algorithms, new cutting planes, a new plugin type for cut selection, and a complete rework of the way nonlinear constraints are handled. Additionally, SCIP 8.0 now supports interfaces for Julia as well as Matlab. Further, UG now includes a unified framework to parallelize all solvers, a utility to analyze computational experiments has been added to GCG, dual solutions can be postsolved by PaPILO, new heuristics and presolving methods were added to SCIP-SDP, and additional problem classes and major performance improvements are available in SCIP-Jack.}, language = {en} }