@misc{YuekselErguenKochZittel2024, author = {Yueksel-Erguen, Inci and Koch, Thorsten and Zittel, Janina}, title = {Mathematical optimization based flow scenario generation for operational analysis of European gas transport networks based on open data}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-95789}, year = {2024}, abstract = {The decarbonization of the European energy system demands a rapid and comprehensive transformation while securing energy supplies at all times. Still, natural gas plays a crucial role in this process. Recent unexpected events forced drastic changes in gas routes throughout Europe. Therefore, operational-level analysis of the gas transport networks and technical capacities to cope with these transitions using unconventional scenarios has become essential. Unfortunately, data limitations often hinder such analyses. To overcome this challenge, we propose a mathematical model-based scenario generator that enables operational analysis of the European gas network using open data. Our approach focuses on the consistent analysis of specific partitions of the gas transport network, whose network topology data is readily available. We generate reproducible and consistent node-based gas in/out-flow scenarios for these defined network partitions to enable feasibility analysis and data quality assessment. Our proposed method is demonstrated through several applications that address the feasibility analysis and data quality assessment of the German gas transport network. By using open data and a mathematical modeling approach, our method allows for a more comprehensive understanding of the gas transport network's behavior and assists in decision-making during the transition to decarbonization.}, language = {en} } @article{PetkovicChenGamrathetal.2022, author = {Petkovic, Milena and Chen, Ying and Gamrath, Inken and Gotzes, Uwe and Hadjidimitrou, Natalia Selini and Zittel, Janina and Xu, Xiaofei and Koch, Thorsten}, title = {A hybrid approach for high precision prediction of gas flows}, volume = {13}, journal = {Energy Systems}, doi = {10.1007/s12667-021-00466-4}, pages = {383 -- 408}, year = {2022}, abstract = {About 23\% of the German energy demand is supplied by natural gas. Additionally, for about the same amount Germany serves as a transit country. Thereby, the German network represents a central hub in the European natural gas transport network. The transport infrastructure is operated by transmissions system operators (TSOs). The number one priority of the TSOs is to ensure the security of supply. However, the TSOs have only very limited knowledge about the intentions and planned actions of the shippers (traders). Open Grid Europe (OGE), one of Germany's largest TSO, operates a high-pressure transport network of about 12,000 km length. With the introduction of peak-load gas power stations, it is of great importance to predict in- and out-flow of the network to ensure the necessary flexibility and security of supply for the German Energy Transition ("Energiewende"). In this paper, we introduce a novel hybrid forecast method applied to gas flows at the boundary nodes of a transport network. This method employs an optimized feature selection and minimization. We use a combination of a FAR, LSTM and mathematical programming to achieve robust high-quality forecasts on real-world data for different types of network nodes.}, 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} } @incollection{GroetschelKochHoang2010, author = {Gr{\"o}tschel, Martin and Koch, Thorsten and Hoang, Nam-Dung}, title = {Lagenwechsel minimieren - oder das Bohren von L{\"o}chern in Leiterplatten}, booktitle = {Besser als Mathe}, editor = {Biermann, Katja and Gr{\"o}tschel, Martin and Lutz-Westphal, Brigitte}, publisher = {Vieweg+Teubner}, doi = {10.1007/978-3-658-01004-1_19}, pages = {161 -- 174}, year = {2010}, language = {en} } @article{BertholdKochShinano2021, author = {Berthold, Timo and Koch, Thorsten and Shinano, Yuji}, title = {MILP. Try. Repeat.}, volume = {2}, journal = {Proceedings of the 13th International Conference on the Practice and Theory of Automated Timetabling - PATAT 2021}, year = {2021}, language = {en} } @article{PetkovicKochZittel2021, author = {Petkovic, Milena and Koch, Thorsten and Zittel, Janina}, title = {Deep learning for spatio-temporal supply anddemand forecasting in natural gas transmission networks}, journal = {Energy Science and Engineering}, doi = {https://doi.org/10.1002/ese3.932}, year = {2021}, abstract = {Germany is the largest market for natural gas in the European Union, with an annual consumption of approx. 95 billion cubic meters. Germany's high-pressure gas pipeline network is roughly 40,000 km long, which enables highly fluctuating quantities of gas to be transported safely over long distances. Considering that similar amounts of gas are also transshipped through Germany to other EU states, it is clear that Germany's gas transport system is essential to the European energy supply. Since the average velocity of gas in a pipeline is only 25km/h, an adequate high-precision, high-frequency forecasting of supply and demand is crucial for efficient control and operation of such a transmission network. We propose a deep learning model based on spatio-temporal convolutional neural networks (DLST) to tackle the problem of gas flow forecasting in a complex high-pressure transmission network. Experiments show that our model effectively captures comprehensive spatio-temporal correlations through modeling gas networks and consistently outperforms state-of-the-art benchmarks on real-world data sets by at least 21\%. The results demonstrate that the proposed model can deal with complex nonlinear gas network flow forecasting with high accuracy and effectiveness.}, 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} } @article{LeKoch2021, author = {Le, Thi Thai and Koch, Thorsten}, title = {Interface stability of compressible fluids in porous media}, volume = {33}, journal = {Physics of Fluids}, number = {8}, publisher = {AIP Publishing}, doi = {10.1063/5.0059336}, pages = {084102}, year = {2021}, abstract = {The stability of flows in porous media plays a vital role in transiting energy supply from natural gas to hydrogen, especially for estimating the usability of existing underground gas storage infrastructures. Thus, this research aims to analyze the interface stability of the tangential-velocity discontinuity between two compressible gases by using Darcy's model to include the porosity effect. The results shown in this research will be a basis for considering whether underground gas storages in porous material can be used to store hydrogen. We show the relation between the Mach number M, the viscosity \mu, and the porosity \epsilon on the stability of the interface. This interface stability affects gases' withdrawal and injection processes, thus will help us to determine the velocity which with gas can be extracted and injected into the storage effectively. By imposing solid walls along the flow direction, the critical values of these parameters regarding the stability of the interface are smaller than when considering no walls. The consideration of bounded flows approaches the problem more realistically. In particular, this analysis plays a vital role when considering two-dimensional gas flows in storages and pipes.}, 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{AndersonTurnerKoch2022, author = {Anderson, Lovis and Turner, Mark and Koch, Thorsten}, title = {Generative deep learning for decision making in gas networks}, volume = {95}, journal = {Mathematical Methods of Operations Research}, publisher = {Springer Nature}, doi = {10.1007/s00186-022-00777-x}, pages = {503 -- 532}, year = {2022}, abstract = {A decision support system relies on frequent re-solving of similar problem instances. While the general structure remains the same in corresponding applications, the input parameters are updated on a regular basis. We propose a generative neural network design for learning integer decision variables of mixed-integer linear programming (MILP) formulations of these problems. We utilise a deep neural network discriminator and a MILP solver as our oracle to train our generative neural network. In this article, we present the results of our design applied to the transient gas optimisation problem. With the trained network we produce a feasible solution in 2.5s, use it as a warm-start solution, and thereby decrease global optimal solution solve time by 60.5\%.}, 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} } @misc{ChenKochXu2019, author = {Chen, Ying and Koch, Thorsten and Xu, Xiaofei}, title = {Regularized partially functional autoregressive model with application to high-resolution natural gas forecasting in Germany}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-74880}, year = {2019}, abstract = {We propose a partially functional autoregressive model with exogenous variables (pFAR) to describe the dynamic evolution of the serially correlated functional data. It provides a unit� ed framework to model both the temporal dependence on multiple lagged functional covariates and the causal relation with ultrahigh-dimensional exogenous scalar covariates. Estimation is conducted under a two-layer sparsity assumption, where only a few groups and elements are supposed to be active, yet without knowing their number and location in advance. We establish asymptotic properties of the estimator and investigate its unite sample performance along with simulation studies. We demonstrate the application of pFAR with the high-resolution natural gas flows in Germany, where the pFAR model provides insightful interpretation as well as good out-of-sample forecast accuracy.}, language = {en} } @article{HenningsAndersonHoppmannBaumetal.2021, author = {Hennings, Felix and Anderson, Lovis and Hoppmann-Baum, Kai and Turner, Mark and Koch, Thorsten}, title = {Controlling transient gas flow in real-world pipeline intersection areas}, volume = {22}, journal = {Optimization and Engineering}, edition = {2}, publisher = {Springer Nature}, doi = {https://doi.org/10.1007/s11081-020-09559-y}, pages = {687 -- 734}, year = {2021}, abstract = {Compressor stations are the heart of every high-pressure gas transport network. Located at intersection areas of the network they are contained in huge complex plants, where they are in combination with valves and regulators responsible for routing and pushing the gas through the network. Due to their complexity and lack of data compressor stations are usually dealt with in the scientific literature in a highly simplified and idealized manner. As part of an ongoing project with one of Germany's largest Transmission System Operators to develop a decision support system for their dispatching center, we investigated how to automatize control of compressor stations. Each station has to be in a particular configuration, leading in combination with the other nearby elements to a discrete set of up to 2000 possible feasible operation modes in the intersection area. Since the desired performance of the station changes over time, the configuration of the station has to adapt. Our goal is to minimize the necessary changes in the overall operation modes and related elements over time, while fulfilling a preset performance envelope or demand scenario. This article describes the chosen model and the implemented mixed integer programming based algorithms to tackle this challenge. By presenting extensive computational results on real world data we demonstrate the performance of our approach.}, language = {en} } @misc{HoangKoch2012, author = {Hoang, Nam-Dung and Koch, Thorsten}, title = {Steiner Tree Packing Revisited}, issn = {1438-0064}, doi = {10.1007/s00186-012-0391-8}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-14625}, number = {12-02}, year = {2012}, abstract = {The Steiner tree packing problem (STPP) in graphs is a long studied problem in combinatorial optimization. In contrast to many other problems, where there have been tremendous advances in practical problem solving, STPP remains very difficult. Most heuristics schemes are ineffective and even finding feasible solutions is already NP-hard. What makes this problem special is that in order to reach the overall optimal solution non-optimal solutions to the underlying NP-hard Steiner tree problems must be used. Any non-global approach to the STPP is likely to fail. Integer programming is currently the best approach for computing optimal solutions. In this paper we review some "classical" STPP instances which model the underlying real world application only in a reduced form. Through improved modelling, including some new cutting planes, and by emplyoing recent advances in solver technology we are for the first time able to solve those instances in the original 3D grid graphs to optimimality.}, language = {en} } @article{BreuerBussieckFiandetal.2019, author = {Breuer, Thomas and Bussieck, Michael and Fiand, Frederik and Cao, Karl-Ki{\^e}n and Gils, Hans Christian and Wetzel, Manuel and Gleixner, Ambros and Koch, Thorsten and Rehfeldt, Daniel and Khabi, Dmitry}, title = {BEAM-ME: Ein interdisziplin{\"a}rer Beitrag zur Erreichung der Klimaziele}, journal = {OR-News : das Magazin der GOR}, number = {66}, pages = {6 -- 8}, year = {2019}, language = {de} } @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{ShinanoRehfeldtKoch2019, author = {Shinano, Yuji and Rehfeldt, Daniel and Koch, Thorsten}, title = {Building Optimal Steiner Trees on Supercomputers by Using up to 43,000 Cores}, volume = {11494}, booktitle = {Integration of Constraint Programming, Artificial Intelligence, and Operations Research. CPAIOR 2019}, publisher = {Springer}, doi = {10.1007/978-3-030-19212-9_35}, pages = {529 -- 539}, year = {2019}, abstract = {SCIP-JACK is a customized, branch-and-cut based solver for Steiner tree and related problems. ug [SCIP-JACK, MPI] extends SCIP-JACK to a massively parallel solver by using the Ubiquity Generator (UG) framework. ug [SCIP-JACK, MPI] was the only solver that could run on a distributed environment at the (latest) 11th DIMACS Challenge in 2014. Furthermore, it could solve three well-known open instances and updated 14 best-known solutions to instances from the benchmark libary STEINLIB. After the DIMACS Challenge, SCIP-JACK has been considerably improved. However, the improvements were not reflected on ug [SCIP- JACK, MPI]. This paper describes an updated version of ug [SCIP-JACK, MPI], especially branching on constrains and a customized racing ramp-up. Furthermore, the different stages of the solution process on a supercomputer are described in detail. We also show the latest results on open instances from the STEINLIB.}, language = {en} } @misc{HoppmannHenningsLenzetal.2019, author = {Hoppmann, Kai and Hennings, Felix and Lenz, Ralf and Gotzes, Uwe and Heinecke, Nina and Spreckelsen, Klaus and Koch, Thorsten}, title = {Optimal Operation of Transient Gas Transport Networks}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-73639}, year = {2019}, language = {en} } @misc{HenningsAndersonHoppmannetal.2019, author = {Hennings, Felix and Anderson, Lovis and Hoppmann, Kai and Turner, Mark and Koch, Thorsten}, title = {Controlling transient gas flow in real-world pipeline intersection areas}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-73645}, year = {2019}, abstract = {Compressor stations are the heart of every high-pressure gas transport network. Located at intersection areas of the network they are contained in huge complex plants, where they are in combination with valves and regulators responsible for routing and pushing the gas through the network. Due to their complexity and lack of data compressor stations are usually dealt with in the scientific literature in a highly simplified and idealized manner. As part of an ongoing project with one of Germany's largest Transmission System Operators to develop a decision support system for their dispatching center, we investigated how to automatize control of compressor stations. Each station has to be in a particular configuration, leading in combination with the other nearby elements to a discrete set of up to 2000 possible feasible operation modes in the intersection area. Since the desired performance of the station changes over time, the configuration of the station has to adapt. Our goal is to minimize the necessary changes in the overall operation modes and related elements over time, while fulfilling a preset performance envelope or demand scenario. This article describes the chosen model and the implemented mixed integer programming based algorithms to tackle this challenge. By presenting extensive computational results on real world data we demonstrate the performance of our approach.}, language = {en} } @misc{PetkovicChenGamrathetal.2019, author = {Petkovic, Milena and Chen, Ying and Gamrath, Inken and Gotzes, Uwe and Hadjidimitriou, Natalia Selini and Zittel, Janina and Xu, Xiaofei and Koch, Thorsten}, title = {A Hybrid Approach for High Precision Prediction of Gas Flows}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-73525}, year = {2019}, abstract = {About 20\% of the German energy demand is supplied by natural gas. Ad- ditionally, for about twice the amount Germany serves as a transit country. Thereby, the German network represents a central hub in the European natural gas transport network. The transport infrastructure is operated by so-called transmissions system operators or TSOs. The number one priority of the TSOs is to ensure security of supply. However, the TSOs have no knowledge of the intentions and planned actions of the shippers (traders). Open Grid Europe (OGE), one of Germany's largest TSO, operates a high- pressure transport network of about 12.000 km length. Since flexibility and security of supply is of utmost importance to the German Energy Transition ("Energiewende") especially with the introduction of peak-load gas power stations, being able to predict in- and out-flow of the network is of great importance. In this paper we introduce a new hybrid forecast method applied to gas flows at the boundary nodes of a transport network. The new method employs optimized feature minimization and selection. We use a combination of an FAR, LSTM DNN and mathematical programming to achieve robust high quality forecasts on real world data for different types of network nodes. Keywords: Gas Forecast, Time series, Hybrid Method, FAR, LSTM, Mathematical Optimisation}, language = {en} } @article{ChenChuaKoch2018, author = {Chen, Ying and Chua, Wee Song and Koch, Thorsten}, title = {Forecasting day-ahead high-resolution natural-gas demand and supply in Germany}, journal = {Applied Energy}, number = {Volume 228}, doi = {https://doi.org/10.1016/j.apenergy.2018.06.137}, pages = {1091 -- 1110}, year = {2018}, abstract = {Forecasting natural gas demand and supply is essential for an efficient operation of the German gas distribution system and a basis for the operational decisions of the transmission system operators. The German gas market is moving towards more short-term planning, in particular, day-ahead contracts. This increases the difficulty that the operators in the dispatching centre are facing, as well as the necessity of accurate forecasts. This paper presents a novel predictive model that provides day-ahead forecasts of the high resolution gas flow by developing a Functional AutoRegressive model with eXogenous variables (FARX). The predictive model allows the dynamic patterns of hourly gas flows to be described in a wide range of historical profiles, while also taking the relevant determinants data into account. By taking into account a richer set of information, FARX provides stronger performance in real data analysis, with both accuracy and high computational efficiency. Compared to several alternative models in out-of-sample forecasts, the proposed model can improve forecast accuracy by at least 12\% and up to 5-fold for one node, 3\% to 2-fold and 2-fold to 4-fold for the other two nodes. The results show that lagged 1-day gas flow and nominations are important predictors, and with their presence in the forecast model, temperature becomes insignificant for short-term predictions.}, language = {en} } @inproceedings{RehfeldtShinanoKoch2021, author = {Rehfeldt, Daniel and Shinano, Yuji and Koch, Thorsten}, title = {SCIP-Jack: 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}, doi = {10.1007/978-3-030-55240-4_10}, year = {2021}, abstract = {The Steiner tree problem in graphs is one of the classic combinatorial optimization problems. Furthermore, many related problems, such as the rectilinear Steiner tree problem or the maximum-weight connected subgraph problem, have been described in the literature—with a wide range of practical applications. To embrace this wealth of problem classes, the solver SCIP-JACK has been developed as an exact framework for classic Steiner tree and 11 related problems. Moreover, the solver comes with both shared- and distributed memory extensions by means of the UG framework. Besides its versatility, SCIP-JACK is highly competitive for most of the 12 problem classes it can solve, as for instance demonstrated by its top ranking in the recent PACE 2018 Challenge. This article describes the current state of SCIP-JACK and provides up-to-date computational results, including several instances that can now be solved for the first time to optimality.}, language = {en} } @inproceedings{YuekselErguenKochZittel2025, author = {Yueksel-Erguen, Inci and Koch, Thorsten and Zittel, Janina}, title = {Consistent flow scenario generation based on open data for operational analysis of European gas transport networks}, booktitle = {Operations Research Proceedings 2023. OR 2023}, publisher = {Springer}, doi = {10.1007/978-3-031-58405-3_63}, pages = {493 -- 499}, year = {2025}, abstract = {In recent years, European gas transport has been affected by major disruptive events like political issues such as, most recently, the Russian war on Ukraine. To incorporate the impacts of such events into decision-making during the energy transition, more complex models for gas network analysis are required. However, the limited availability of consistent data presents a significant obstacle in this endeavor. We use a mathematical-modeling-based scenario generator to deal with this obstacle. The scenario generator consists of capacitated network flow models representing the gas network at different aggregation levels. In this study, we present the coarse-to-fine approach utilized in this scenario generator.}, 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} } @misc{RehfeldtHobbieSchoenheitetal.2019, author = {Rehfeldt, Daniel and Hobbie, Hannes and Sch{\"o}nheit, David and Gleixner, Ambros and Koch, Thorsten and M{\"o}st, Dominik}, title = {A massively parallel interior-point solver for linear energy system models with block structure}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-74321}, year = {2019}, abstract = {Linear energy system models are often a crucial component of system design and operations, as well as energy policy consulting. Such models can lead to large-scale linear programs, which can be intractable even for state-of-the-art commercial solvers|already the available memory on a desktop machine might not be sufficient. Against this backdrop, this article introduces an interior-point solver that exploits common structures of linear 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. Special effort has been put into handling large numbers of linking constraints and variables as commonly observed in energy system models. In order to handle this strong linkage, a distributed preconditioning of the Schur complement 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 existing parallel interior-point solver PIPS-IPM. We evaluate the computational performance on energy system models with up to 700 million non-zero entries in the constraint matrix, and with more than 200 million columns and 250 million 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 during the recent years. However, it will be demonstrated that the new solver is also applicable to other energy system models.}, language = {en} } @misc{GleixnerKempkeKochetal.2019, 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}, issn = {1438-0064}, doi = {10.1007/978-3-030-48439-2_13}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-74084}, year = {2019}, 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} } @article{XuChenZhangetal.2021, author = {Xu, Xiaofei and Chen, Ying and Zhang, Ge and Koch, Thorsten}, title = {Modeling functional time series and mixed-type predictors with partially functional autoregressions*}, journal = {Journal of Business and Economic Statistics}, doi = {10.1080/07350015.2021.2011299}, pages = {1 -- 43}, year = {2021}, abstract = {In many business and economics studies, researchers have sought to measure the dynamic dependence of curves with high-dimensional mixed-type predictors. We propose a partially functional autoregressive model (pFAR) where the serial dependence of curves is controlled by coefficient operators that are defined on a two-dimensional surface, and the individual and group effects of mixed-type predictors are estimated with a two-layer regularization. We develop an efficient estimation with the proven asymptotic properties of consistency and sparsity. We show how to choose the sieve and tuning parameters in regularization based on a forward-looking criterion. In addition to the asymptotic properties, numerical validation suggests that the dependence structure is accurately detected. The implementation of the pFAR within a real-world analysis of dependence in German daily natural gas flow curves, with seven lagged curves and 85 scalar predictors, produces superior forecast accuracy and an insightful understanding of the dynamics of natural gas supply and demand for the municipal, industry, and border nodes, respectively.}, 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} } @misc{GleixnerEiflerGallyetal.2017, author = {Gleixner, Ambros and Eifler, Leon and Gally, Tristan and Gamrath, Gerald and Gemander, Patrick and Gottwald, Robert Lion and Hendel, Gregor and Hojny, Christopher and Koch, Thorsten and Miltenberger, Matthias and M{\"u}ller, Benjamin and Pfetsch, Marc and Puchert, Christian and Rehfeldt, Daniel and Schl{\"o}sser, Franziska and Serrano, Felipe and Shinano, Yuji and Viernickel, Jan Merlin and Vigerske, Stefan and Weninger, Dieter and Witt, Jonas T. and Witzig, Jakob}, title = {The SCIP Optimization Suite 5.0}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-66297}, year = {2017}, abstract = {This article describes new features and enhanced algorithms made available in version 5.0 of the SCIP Optimization Suite. In its central component, the constraint integer programming solver SCIP, remarkable performance improvements have been achieved for solving mixed-integer linear and nonlinear programs. On MIPs, SCIP 5.0 is about 41 \% faster than SCIP 4.0 and over twice as fast on instances that take at least 100 seconds to solve. For MINLP, SCIP 5.0 is about 17 \% faster overall and 23 \% faster on instances that take at least 100 seconds to solve. This boost is due to algorithmic advances in several parts of the solver such as cutting plane generation and management, a new adaptive coordination of large neighborhood search heuristics, symmetry handling, and strengthened McCormick relaxations for bilinear terms in MINLPs. Besides discussing the theoretical background and the implementational aspects of these developments, the report describes recent additions for the other software packages connected to SCIP, in particular for the LP solver SoPlex, the Steiner tree solver SCIP-Jack, the MISDP solver SCIP-SDP, and the parallelization framework UG.}, language = {en} } @misc{ShinanoAchterbergBertholdetal.2015, author = {Shinano, Yuji and Achterberg, Tobias and Berthold, Timo and Heinz, Stefan and Koch, Thorsten and Winkler, Michael}, title = {Solving Open MIP Instances with ParaSCIP on Supercomputers using up to 80,000 Cores}, issn = {1438-0064}, doi = {10.1109/IPDPS.2016.56}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-56404}, year = {2015}, abstract = {This paper describes how we solved 12 previously unsolved mixed-integer program- ming (MIP) instances from the MIPLIB benchmark sets. To achieve these results we used an enhanced version of ParaSCIP, setting a new record for the largest scale MIP computation: up to 80,000 cores in parallel on the Titan supercomputer. In this paper we describe the basic parallelization mechanism of ParaSCIP, improvements of the dynamic load balancing and novel techniques to exploit the power of parallelization for MIP solving. We give a detailed overview of computing times and statistics for solving open MIPLIB instances.}, language = {en} } @misc{RehfeldtKoch2018, author = {Rehfeldt, Daniel and Koch, Thorsten}, title = {Reduction-based exact solution of prize-collecting Steiner tree problems}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-70958}, year = {2018}, language = {en} } @misc{ShinanoRehfeldtKoch2018, author = {Shinano, Yuji and Rehfeldt, Daniel and Koch, Thorsten}, title = {Building Optimal Steiner Trees on Supercomputers by using up to 43,000 Cores}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-71118}, year = {2018}, abstract = {SCIP-JACK is a customized, branch-and-cut based solver for Steiner tree and related problems. ug [SCIP-JACK, MPI] extends SCIP-JACK to a massively par- allel solver by using the Ubiquity Generator (UG) framework. ug [SCIP-JACK, MPI] was the only solver that could run on a distributed environment at the (latest) 11th DIMACS Challenge in 2014. Furthermore, it could solve three well-known open instances and updated 14 best known solutions to instances from the bench- mark libary STEINLIB. After the DIMACS Challenge, SCIP-JACK has been con- siderably improved. However, the improvements were not reflected on ug [SCIP- JACK, MPI]. This paper describes an updated version of ug [SCIP-JACK, MPI], especially branching on constrains and a customized racing ramp-up. Furthermore, the different stages of the solution process on a supercomputer are described in detail. We also show the latest results on open instances from the STEINLIB.}, language = {en} } @article{VuLitzelKoch2026, author = {Vu, Thi Huong and Litzel, Ida and Koch, Thorsten}, title = {Similarity-based fuzzy clustering scientific articles: potentials and challenges from mathematical and computational perspectives}, volume = {10}, journal = {Journal of Nonlinear and Variational Analysis}, number = {2}, publisher = {Biemdas}, arxiv = {http://arxiv.org/abs/2506.04045}, doi = {https://doi.org/10.23952/jnva.10.2026.2.8}, pages = {381 -- 401}, year = {2026}, abstract = {Fuzzy clustering, which allows an article to belong to multiple clusters with soft membership degrees, plays a vital role in analyzing publication data. This problem can be formulated as a constrained optimization model, where the goal is to minimize the discrepancy between the similarity observed from data and the similarity derived from a predicted distribution. While this approach benefits from leveraging state-of-the-art optimization algorithms, tailoring them to work with real, massive databases like OpenAlex or Web of Science - containing about 70 million articles and a billion citations - poses significant challenges. We analyze potentials and challenges of the approach from both mathematical and computational perspectives. Among other things, second-order optimality conditions are established, providing new theoretical insights, and practical solution methods are proposed by exploiting the structure of the problem. Specifically, we accelerate the gradient projection method using GPU-based parallel computing to efficiently handle large-scale data.}, language = {en} } @article{GleixnerHendelGamrathetal.2021, author = {Gleixner, Ambros and Hendel, Gregor and Gamrath, Gerald and Achterberg, Tobias and Bastubbe, Michael and Berthold, Timo and Christophel, Philipp M. and Jarck, Kati and Koch, Thorsten and Linderoth, Jeff and L{\"u}bbecke, Marco and Mittelmann, Hans and Ozyurt, Derya and Ralphs, Ted and Salvagnin, Domenico and Shinano, Yuji}, title = {MIPLIB 2017: Data-Driven Compilation of the 6th Mixed-Integer Programming Library}, volume = {13}, journal = {Mathematical Programming Computation}, number = {3}, doi = {10.1007/s12532-020-00194-3}, pages = {443 -- 490}, year = {2021}, abstract = {We report on the selection process leading to the sixth version of the Mixed Integer Programming Library. Selected from an initial pool of over 5,000 instances, the new MIPLIB 2017 collection consists of 1,065 instances. A subset of 240 instances was specially selected for benchmarking solver performance. For the first time, the compilation of these sets was done using a data-driven selection process supported by the solution of a sequence of mixed integer optimization problems, which encoded requirements on diversity and balancedness with respect to instance features and performance data.}, language = {en} } @inproceedings{BleyGleixnerKochetal.2012, author = {Bley, Andreas and Gleixner, Ambros and Koch, Thorsten and Vigerske, Stefan}, title = {Comparing MIQCP Solvers to a Specialised Algorithm for Mine Production Scheduling}, booktitle = {Modeling, Simulation and Optimization of Complex Processes. Proceedings of the Fourth International Conference on High Performance Scientific Computing, March 2-6, 2009, Hanoi, Vietnam}, doi = {10.1007/978-3-642-25707-0_3}, pages = {25 -- 39}, year = {2012}, abstract = {In this paper we investigate the performance of several out-of-the box solvers for mixed-integer quadratically constrained programmes (MIQCPs) on an open pit mine production scheduling problem with mixing constraints. We compare the solvers BARON, Couenne, SBB, and SCIP to a problem-specific algorithm on two different MIQCP formulations. The computational results presented show that general-purpose solvers with no particular knowledge of problem structure are able to nearly match the performance of a hand-crafted algorithm.}, 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} } @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} } @article{LeKoch2023, author = {Le, Thi Thai and Koch, Thorsten}, title = {Effect of inertia force on the interface stability of a tangential-velocity discontinuity in porous media}, volume = {169}, journal = {International Journal of Multiphase Flow}, doi = {10.1016/j.ijmultiphaseflow.2023.104612}, year = {2023}, abstract = {The present study investigates the stability of a tangential-velocity discontinuity in porous media during the withdrawing and injecting processes of natural gases from and into an underground gas storage. The focus is placed on analyzing the impact of inertia forces on the interface stability using the Forchheimer equations. Other publications have relied primarily on Darcy's law to describe flow stability in porous media. However, Darcy's law only adequately describes flows in which viscous forces dominate over inertia forces. As the flow rate increases, the significance of inertia forces becomes more pronounced, and Darcy's law becomes insufficient for considering such flows. Our findings indicate that even a slight consideration of the inertia effect leads to permanent destabilization of the discontinuity interface, regardless of the fluid viscosity or the Mach number. In contrast, when the inertia effect is neglected, the interface is stabilized across the entire Mach number range if the fluid viscosity is strong enough.}, language = {en} } @article{ChenKochZakiyevaetal.2023, author = {Chen, Ying and Koch, Thorsten and Zakiyeva, Nazgul and Liu, Kailiang and Xu, Zhitong and Chen, Chun-houh and Nakano, Junji and Honda, Keisuke}, title = {Article's scientific prestige: Measuring the impact of individual articles in the web of science}, volume = {17}, journal = {Journal of Informetrics}, number = {1}, doi = {10.1016/j.joi.2023.101379}, pages = {101379}, year = {2023}, abstract = {We performed a citation analysis on the Web of Science publications consisting of more than 63 million articles and 1.45 billion citations on 254 subjects from 1981 to 2020. We proposed the Article's Scientific Prestige (ASP) metric and compared this metric to number of citations (\#Cit) and journal grade in measuring the scientific impact of individual articles in the large-scale hierarchical and multi-disciplined citation network. In contrast to \#Cit, ASP, that is computed based on the eigenvector centrality, considers both direct and indirect citations, and provides steady-state evaluation cross different disciplines. We found that ASP and \#Cit are not aligned for most articles, with a growing mismatch amongst the less cited articles. While both metrics are reliable for evaluating the prestige of articles such as Nobel Prize winning articles, ASP tends to provide more persuasive rankings than \#Cit when the articles are not highly cited. The journal grade, that is eventually determined by a few highly cited articles, is unable to properly reflect the scientific impact of individual articles. The number of references and coauthors are less relevant to scientific impact, but subjects do make a difference.}, language = {en} } @inproceedings{TurnerBertholdBesanconetal.2023, author = {Turner, Mark and Berthold, Timo and Besan{\c{c}}on, Mathieu and Koch, Thorsten}, title = {Cutting Plane Selection with Analytic Centers and Multiregression}, volume = {13884}, booktitle = {Integration of Constraint Programming, Artificial Intelligence, and Operations Research. CPAIOR 2023.}, publisher = {Springer}, doi = {10.1007/978-3-031-33271-5_4}, pages = {52 -- 68}, year = {2023}, abstract = {Cutting planes are a crucial component of state-of-the-art mixed-integer programming solvers, with the choice of which subset of cuts to add being vital for solver performance. We propose new distance-based measures to qualify the value of a cut by quantifying the extent to which it separates relevant parts of the relaxed feasible set. For this purpose, we use the analytic centers of the relaxation polytope or of its optimal face, as well as alternative optimal solutions of the linear programming relaxation. We assess the impact of the choice of distance measure on root node performance and throughout the whole branch-and-bound tree, comparing our measures against those prevalent in the literature. Finally, by a multi-output regression, we predict the relative performance of each measure, using static features readily available before the separation process. Our results indicate that analytic center-based methods help to significantly reduce the number of branch-and-bound nodes needed to explore the search space and that our multiregression approach can further improve on any individual method.}, language = {en} } @misc{TurnerBertholdBesanconetal.2022, author = {Turner, Mark and Berthold, Timo and Besan{\c{c}}on, Mathieu and Koch, Thorsten}, title = {Cutting Plane Selection with Analytic Centers and Multiregression}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-89065}, year = {2022}, abstract = {Cutting planes are a crucial component of state-of-the-art mixed-integer programming solvers, with the choice of which subset of cuts to add being vital for solver performance. We propose new distance-based measures to qualify the value of a cut by quantifying the extent to which it separates relevant parts of the relaxed feasible set. For this purpose, we use the analytic centers of the relaxation polytope or of its optimal face, as well as alternative optimal solutions of the linear programming relaxation. We assess the impact of the choice of distance measure on root node performance and throughout the whole branch-and-bound tree, comparing our measures against those prevalent in the literature. Finally, by a multi-output regression, we predict the relative performance of each measure, using static features readily available before the separation process. Our results indicate that analytic center-based methods help to significantly reduce the number of branch-and-bound nodes needed to explore the search space and that our multiregression approach can further improve on any individual method.}, language = {en} } @article{KochBertholdPedersenetal.2022, author = {Koch, Thorsten and Berthold, Timo and Pedersen, Jaap and Vanaret, Charlie}, title = {Progress in mathematical programming solvers from 2001 to 2020}, volume = {10}, journal = {EURO Journal on Computational Optimization}, doi = {10.1016/j.ejco.2022.100031}, pages = {100031}, 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{BleyGleixnerKochetal.2009, author = {Bley, Andreas and Gleixner, Ambros and Koch, Thorsten and Vigerske, Stefan}, title = {Comparing MIQCP solvers to a specialised algorithm for mine production scheduling}, organization = {ZIB}, issn = {1438-0064}, doi = {10.1007/978-3-642-25707-0}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-11507}, number = {09-32}, year = {2009}, abstract = {In this paper we investigate the performance of several out-of-the box solvers for mixed-integer quadratically constrained programmes (MIQCPs) on an open pit mine production scheduling problem with mixing constraints. We compare the solvers BARON, Couenne, SBB, and SCIP to a problem-specific algorithm on two different MIQCP formulations. The computational results presented show that general-purpose solvers with no particular knowledge of problem structure are able to nearly match the performance of a hand-crafted algorithm.}, 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} } @misc{VuLitzelKoch2025, author = {Vu, Thi Huong and Litzel, Ida and Koch, Thorsten}, title = {Similarity-based fuzzy clustering scientific articles: potentials and challenges from mathematical and computational perspectives}, arxiv = {http://arxiv.org/abs/2506.04045}, year = {2025}, abstract = {Fuzzy clustering, which allows an article to belong to multiple clusters with soft membership degrees, plays a vital role in analyzing publication data. This problem can be formulated as a constrained optimization model, where the goal is to minimize the discrepancy between the similarity observed from data and the similarity derived from a predicted distribution. While this approach benefits from leveraging state-of-the-art optimization algorithms, tailoring them to work with real, massive databases like OpenAlex or Web of Science -- containing about 70 million articles and a billion citations -- poses significant challenges. We analyze potentials and challenges of the approach from both mathematical and computational perspectives. Among other things, second-order optimality conditions are established, providing new theoretical insights, and practical solution methods are proposed by exploiting the problem's structure. Specifically, we accelerate the gradient projection method using GPU-based parallel computing to efficiently handle large-scale data.}, language = {en} } @misc{VuKoch2025, author = {Vu, Thi Huong and Koch, Thorsten}, title = {Clustering scientific publications: lessons learned through experiments with a real citation network}, arxiv = {http://arxiv.org/abs/2505.18180}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-100418}, year = {2025}, abstract = {Clustering scientific publications helps uncover research structures within bibliographic databases. Graph-based methods such as spectral, Louvain, and Leiden clustering are commonly used due to their ability to model citation networks. However, their effectiveness can diminish when applied to real-world data. This study evaluates these clustering algorithms on a citation graph of about 700,000 articles and 4.6 million citations from the Web of Science. The results show that while scalable methods like Louvain and Leiden perform efficiently, their default settings often yield poor partitioning. Meaningful outcomes require careful parameter tuning, especially for large networks with uneven structures, including a dense core and loosely connected papers. These findings highlight practical lessons about the challenges of large-scale data, method selection and tuning based on specific structures of bibliometric clustering tasks.}, 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} } @article{RongChenMaetal.2025, author = {Rong, Guoyang and Chen, Ying and Ma, Feicheng and Koch, Thorsten}, title = {Exploring Interdisciplinary Research Trends through Critical Years for Interdisciplinary Citation}, volume = {19}, journal = {Journal of Informetrics}, number = {4}, doi = {10.1016/j.joi.2025.101726}, 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} }