@article{RiedmuellerKoch2025, author = {Riedm{\"u}ller, Stephanie and Koch, Thorsten}, title = {Exact Objective Space Contraction for the Preprocessing of Multi-objective Integer Programs}, arxiv = {http://arxiv.org/abs/2512.01535}, year = {2025}, abstract = {Solving integer optimization problems with large or widely ranged objective coefficients can lead to numerical instability and increased runtimes. When the problem also involves multiple objectives, the impact of the objective coefficients on runtimes and numerical issues multiplies. We address this issue by transforming the coefficients of linear objective functions into smaller integer coefficients. To the best of our knowledge, this problem has not been defined before. Next to a straightforward scaling heuristic, we introduce a novel exact transformation approach for the preprocessing of multi-objective binary problems. In this exact approach, the large or widely ranged integer objective coefficients are transformed into the minimal integer objective coefficients that preserve the dominance relation of the points in the objective space. The transformation problem is solved with an integer programming formulation with an exponential number of constraints. We present a cutting-plane algorithm that can efficiently handle the problem size. In a first computational study, we analyze how often and in which settings the transformation actually leads to smaller coefficients. In a second study, we evaluate how the exact transformation and a typical scaling heuristic, when used as preprocessing, affect the runtime and numerical stability of the Defining Point Algorithm.}, language = {en} } @article{ChenKochPengetal.2025, author = {Chen, Ying and Koch, Thorsten and Peng, Hanqui and Zhang, Hongrui}, title = {Benchmarking of Quantum and Classical Computing in Large-Scale Dynamic Portfolio Optimization Under Market Frictions}, arxiv = {http://arxiv.org/abs/2502.05226}, year = {2025}, abstract = {Quantum computing is poised to transform the financial industry, yet its advantages over traditional methods have not been evidenced. As this technology rapidly evolves, benchmarking is essential to fairly evaluate and compare different computational strategies. This study presents a challenging yet solvable problem of large-scale dynamic portfolio optimization under realistic market conditions with frictions. We frame this issue as a Quadratic Unconstrained Binary Optimization (QUBO) problem, compatible with digital computing and ready for quantum computing, to establish a reliable benchmark. By applying the latest solvers to real data, we release benchmarks that help verify true advancements in dynamic trading strategies, either quantum or digital computing, ensuring that reported improvements in portfolio optimization are based on robust, transparent, and comparable metrics.}, language = {en} } @misc{GamrathAndersonBestuzhevaetal.2020, author = {Gamrath, Gerald and Anderson, Daniel and Bestuzheva, Ksenia and Chen, Wei-Kun and Eifler, Leon and Gasse, Maxime and Gemander, Patrick and Gleixner, Ambros and Gottwald, Leona and Halbig, Katrin and Hendel, Gregor and Hojny, Christopher and Koch, Thorsten and Le Bodic, Pierre and Maher, Stephen J. and Matter, Frederic and Miltenberger, Matthias and M{\"u}hmer, Erik and M{\"u}ller, Benjamin and Pfetsch, Marc and Schl{\"o}sser, Franziska and Serrano, Felipe and Shinano, Yuji and Tawfik, Christine and Vigerske, Stefan and Wegscheider, Fabian and Weninger, Dieter and Witzig, Jakob}, title = {The SCIP Optimization Suite 7.0}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-78023}, year = {2020}, abstract = {The SCIP Optimization Suite provides a collection of software packages for mathematical optimization centered around the constraint integer programming frame- work SCIP. This paper discusses enhancements and extensions contained in version 7.0 of the SCIP Optimization Suite. The new version features the parallel presolving library PaPILO as a new addition to the suite. PaPILO 1.0 simplifies mixed-integer linear op- timization problems and can be used stand-alone or integrated into SCIP via a presolver plugin. SCIP 7.0 provides additional support for decomposition algorithms. Besides im- provements in the Benders' decomposition solver of SCIP, user-defined decomposition structures can be read, which are used by the automated Benders' decomposition solver and two primal heuristics. Additionally, SCIP 7.0 comes with a tree size estimation that is used to predict the completion of the overall solving process and potentially trigger restarts. Moreover, substantial performance improvements of the MIP core were achieved by new developments in presolving, primal heuristics, branching rules, conflict analysis, and symmetry handling. Last, not least, the report presents updates to other components and extensions of the SCIP Optimization Suite, in particular, the LP solver SoPlex and the mixed-integer semidefinite programming solver SCIP-SDP.}, 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{GamrathGleixnerKochetal.2019, author = {Gamrath, Gerald and Gleixner, Ambros and Koch, Thorsten and Miltenberger, Matthias and Kniasew, Dimitri and Schl{\"o}gel, Dominik and Martin, Alexander and Weninger, Dieter}, title = {Tackling Industrial-Scale Supply Chain Problems by Mixed-Integer Programming}, volume = {37}, journal = {Journal of Computational Mathematics}, doi = {10.4208/jcm.1905-m2019-0055}, pages = {866 -- 888}, year = {2019}, abstract = {The modeling flexibility and the optimality guarantees provided by mixed-integer programming greatly aid the design of robust and future-proof decision support systems. The complexity of industrial-scale supply chain optimization, however, often poses limits to the application of general mixed-integer programming solvers. In this paper we describe algorithmic innovations that help to ensure that MIP solver performance matches the complexity of the large supply chain problems and tight time limits encountered in practice. Our computational evaluation is based on a diverse set, modeling real-world scenarios supplied by our industry partner SAP.}, language = {en} } @article{XuChenZhangetal.2022, 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}, volume = {42}, journal = {Journal of Business \& Economic Statistics}, number = {2}, publisher = {Informa UK Limited}, issn = {0735-0015}, doi = {https://doi.org/10.1080/07350015.2021.2011299}, pages = {349 -- 366}, year = {2022}, language = {en} } @inproceedings{HadjidimitriouLippiNastroetal.2024, author = {Hadjidimitriou, Natalia Selini and Lippi, Marco and Nastro, Raffaele and Koch, Thorsten and Mamei, Marco}, title = {Short-Term Forecasting of Energy Consumption and Production in Local Energy Communities}, booktitle = {2024 32nd International Conference on Enabling Technologies: Infrastructure for Collaborative Enterprises (WETICE)}, publisher = {IEEE}, doi = {10.1109/WETICE64632.2024.00022}, pages = {74 -- 79}, year = {2024}, 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{AbbasAmbainisAugustinoetal.2024, author = {Abbas, Amira and Ambainis, Andris and Augustino, Brandon and B{\"a}rtschi, Andreas and Buhrman, Harry and Coffrin, Carleton and Cortiana, Giorgio and Dunjko, Vedran and Egger, Daniel J. and Elmegreen, Bruce G. and Franco, Nicola and Fratini, Filippo and Fuller, Bryce and Gacon, Julien and Gonciulea, Constantin and Gribling, Sander and Gupta, Swati and Hadfield, Stuart and Heese, Raoul and Kircher, Gerhard and Kleinert, Thomas and Koch, Thorsten and Korpas, Georgios and Lenk, Steve and Marecek, Jakub and Markov, Vanio and Mazzola, Guglielmo and Mensa, Stefano and Mohseni, Naeimeh and Nannicini, Giacomo and O'Meara, Corey and Tapia, Elena Pe{\~n}a and Pokutta, Sebastian and Proissl, Manuel and Rebentrost, Patrick and Sahin, Emre and Symons, Benjamin C. B. and Tornow, Sabine and Valls, V{\´i}ctor and Woerner, Stefan and Wolf-Bauwens, Mira L. and Yard, Jon and Yarkoni, Sheir and Zechiel, Dirk and Zhuk, Sergiy and Zoufal, Christa}, title = {Challenges and opportunities in quantum optimization}, volume = {6}, journal = {Nature Reviews Physics}, publisher = {Springer Science and Business Media LLC}, issn = {2522-5820}, arxiv = {http://arxiv.org/abs/2312.02279}, doi = {10.1038/s42254-024-00770-9}, pages = {718 -- 735}, year = {2024}, language = {en} } @misc{VuKochXu2024, author = {Vu, Thi Huong and Koch, Thorsten and Xu, Hong-Kun}, title = {The gradient projection method: Is the Polyak adaptive stepsize rule optimal?}, year = {2024}, abstract = {Not always! This is our answer to the question of whether the Polyak adaptive stepsize rule in the gradient projection method is optimal. The answer is based on revisiting the subgradient projection method by Polyak [USSR Computational Mathematics and Mathematical Physics 9 (1969)] for smooth and convex minimization problems where the objective function possesses a geometric property called flatness. Our results show that the method can be more flexible (the effective range for the parameter controlling the stepsize can be wider) and have sharper convergence rates. Applications to split feasibility/equality problems are presented, deriving for the first time the O(1/k) rate of convergence for the adaptive CQ method. A theoretical guarantee of the linear convergence of the gradient descent method with adaptive stepsizes for Google PageRank is provided. At the same time, numerical experiments are designed to spot the ``optimal" stepsize and to compare with other basic gradient methods.}, language = {en} } @inproceedings{HadjidimitriouKochLippietal.2024, author = {Hadjidimitriou, Natalia Selini and Koch, Thorsten and Lippi, Marco and Petkovic, Milena and Mamei, Marco}, title = {Analysis of the Impact of COVID-19 and Russo-Ukraine War on Natural Gas Flow Using Time Series Forecasting}, booktitle = {Preceedings of the 16th International Conference on Management of Digital Ecosystems}, year = {2024}, 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} } @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} }