TY - GEN A1 - Riedmüller, Stephanie A1 - Buchholz, Annika A1 - Zittel, Janina T1 - Enhancing Multi-Energy Modeling: The Role of Mixed-Integer Optimization Decisions N2 - The goal to decarbonize the energy sector has led to increased research in modeling and optimizing multi-energy systems. One of the most promising and popular techniques for modeling and solving (multi-)energy optimization problems is (multi-objective) mixed-integer programming, valued for its ability to represent the complexities of integrated energy systems. While the literature often focuses on deriving mathematical formulations and parameter settings, less attention is given to critical post-formulation decisions. Modeling multi-energy systems as mixed-integer linear optimization programs demands decisions across multiple degrees of freedom. Key steps include reducing a real-world multi energy network into an abstract topology, defining variables, formulating the relevant (in-)equalities to represent technical requirements, setting (multiple) objectives, and integrating these elements into a mixed-integer program (MIP). However, with these elements fixed, the specific transformation of the abstract topology into a graph structure and the construction of the MIP remain non-uniquely. These choices can significantly impact user-friendliness, problem size, and computational efficiency, thus affecting the feasibility and efficiency of modeling efforts. In this work, we identify and analyze the additional degrees of freedom and describe two distinct approaches to address them. The approaches are compared regarding mathematical equivalence, suitability for solution algorithms, and clarity of the underlying topology. A case study on a realistic subarea of Berlin’s district heating network involving tri-objective optimization for a unit commitment problem demonstrates the practical significance of these decisions. By highlighting these critical yet often overlooked aspects, our work equips energy system modelers with insights to improve computational efficiency, scalability, and interpretability in their optimization efforts, ultimately enhancing the practicality and effectiveness of multi-energy system models. T3 - ZIB-Report - 25-08 Y1 - 2025 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-100329 SN - 1438-0064 ER - TY - GEN A1 - Pedersen, Jaap A1 - Lindner, Niels A1 - Rehfeldt, Daniel A1 - Koch, Thorsten T1 - Comparing Branching Rules for the Quota Steiner Tree Problem with Interference N2 - 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. T3 - ZIB-Report - 25-16 Y1 - 2025 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-101250 SN - 1438-0064 ER - TY - GEN A1 - Kempke, Nils-Christian A1 - Koch, Thorsten T1 - A GPU accelerated variant of Schroeppel-Shamir's algorithm for solving the market split problem N2 - The market split problem (MSP), introduced by Cornuéjols and Dawande (1998), is a challenging binary optimization problem that performs poorly on state-of-the-art linear programming-based branch-and-cut solvers. We present a novel algorithm for solving the feasibility version of this problem, derived from Schroeppel–Shamir's algorithm for the one-dimensional subset sum problem. Our approach is based on exhaustively enumerating one-dimensional solutions of MSP and utilizing GPUs to evaluate candidate solutions across the entire problem. The resulting hybrid CPU-GPU implementation efficiently solves instances with up to 10 constraints and 90 variables. We demonstrate the algorithm's performance on benchmark problems, solving instances of size (9, 80) in less than fifteen minutes and (10, 90) in up to one day. T3 - ZIB-Report - 25-10 Y1 - 2025 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-100554 SN - 1438-0064 ER - TY - JOUR A1 - Koch, Thorsten A1 - Bernal Neira, David E. A1 - Chen, Ying A1 - Cortiana, Giorgio A1 - Egger, Daniel J. A1 - Heese, Raoul A1 - Hegade, Narendra N. A1 - Gomez Cadavid, Alejandro A1 - Huang, Rhea A1 - Itoko, Toshinari A1 - Kleinert, Thomas A1 - Maciel Xavier, Pedro A1 - Mohseni, Naeimeh A1 - Montanez-Barrera, Jhon A. A1 - Nakano, Koji A1 - Nannicini, Giacomo A1 - O'Meara, Corey A1 - Pauckert, Justin A1 - Proissl, Manuel A1 - Ramesh, Anurag A1 - Schicker, Maximilian A1 - Shimada, Noriaki A1 - Takeori, Mitsuharu A1 - Valls, Victor A1 - Van Bulck, David A1 - Woerner, Stefan A1 - Zoufal, Christa T1 - Quantum Optimization Benchmark Library -- The Intractable Decathlon N2 - Through recent progress in hardware development, quantum computers have advanced to the point where benchmarking of (heuristic) quantum algorithms at scale is within reach. Particularly in combinatorial optimization -- where most algorithms are heuristics -- it is key to empirically analyze their performance on hardware and track progress towards quantum advantage. To this extent, we present ten optimization problem classes that are difficult for existing classical algorithms and can (mostly) be linked to practically-relevant applications, with the goal to enable systematic, fair, and comparable benchmarks for quantum optimization methods. Further, we introduce the Quantum Optimization Benchmark Library (QOBLIB) where the problem instances and solution track records can be found. The individual properties of the problem classes vary in terms of objective and variable type, coefficient ranges, and density. Crucially, they all become challenging for established classical methods already at system sizes ranging from less than 100 to, at most, an order of 100,000 decision variables, allowing to approach them with today's quantum computers. We reference the results from state-of-the-art solvers for instances from all problem classes and demonstrate exemplary baseline results obtained with quantum solvers for selected problems. The baseline results illustrate a standardized form to present benchmarking solutions, which has been designed to ensure comparability of the used methods, reproducibility of the respective results, and trackability of algorithmic and hardware improvements over time. We encourage the optimization community to explore the performance of available classical or quantum algorithms and hardware platforms with the benchmarking problem instances presented in this work toward demonstrating quantum advantage in optimization. Y1 - 2025 ER - TY - CHAP A1 - Riedmüller, Stephanie A1 - Buchholz, Annika A1 - Zittel, Janina T1 - Enhancing Multi-Energy Modeling: The Role of Mixed-Integer Optimization Decisions T2 - The 38th International Conference on Efficiency, Cost, Optimization, Simulation and Environmental Impact of Energy Systems – ECOS 2025 N2 - The goal to decarbonize the energy sector has led to increased research in modeling and optimizing multi-energy systems. One of the most promising and popular techniques for modeling and solving (multi-)energy optimization problems is (multi-objective) mixed-integer programming, valued for its ability to represent the complexities of integrated energy systems. While the literature often focuses on deriving mathematical formulations and parameter settings, less attention is given to critical post-formulation decisions. Modeling multi-energy systems as mixed-integer linear optimization programs demands decisions across multiple degrees of freedom. Key steps include reducing a real-world multi energy network into an abstract topology, defining variables, formulating the relevant (in-)equalities to represent technical requirements, setting (multiple) objectives, and integrating these elements into a mixed-integer program (MIP). However, with these elements fixed, the specific transformation of the abstract topology into a graph structure and the construction of the MIP remain non-uniquely. These choices can significantly impact user-friendliness, problem size, and computational efficiency, thus affecting the feasibility and efficiency of modeling efforts. In this work, we identify and analyze the additional degrees of freedom and describe two distinct approaches to address them. The approaches are compared regarding mathematical equivalence, suitability for solution algorithms, and clarity of the underlying topology. A case study on a realistic subarea of Berlin’s district heating network involving tri-objective optimization for a unit commitment problem demonstrates the practical significance of these decisions. By highlighting these critical yet often overlooked aspects, our work equips energy system modelers with insights to improve computational efficiency, scalability, and interpretability in their optimization efforts, ultimately enhancing the practicality and effectiveness of multi-energy system models. Y1 - 2025 ER - TY - GEN A1 - Mehl, Lukas A1 - Lindner, Niels A1 - Bartoszuk, Karolina A1 - Zittel, Janina T1 - Prototypical warm-starts for demand-robust LP-based energy system optimization N2 - The expressiveness of energy system optimization models (ESOMs) depends on a multitude of exogenous parameters. For example, sound estimates of the future energy demand are essential to enable qualified decisions on long-term investments. However, the enormous demand fluctuations even on a fine-grained scale diminish the computational performance of large-scale ESOMs. We therefore propose a clustering-and-decomposition method for linear programming based ESOMs that first identifies and solves prototypical demand scenarios with the dual simplex algorithm, and then composes dual optimal prototype bases to a warm-start basis for the full model. We evaluate the feasibility and computational efficiency our approach on a real-world case study, using a sector-coupled ESOM with hourly resolution for the Berlin-Brandenburg area in Germany, based on the oemof framework. T3 - ZIB-Report - 25-15 Y1 - 2025 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-101242 SN - 1438-0064 ER - TY - GEN A1 - Riedmüller, Stephanie A1 - Zittel, Janina A1 - Koch, Thorsten T1 - Warm-starting Strategies in Scalarization Methods for Multi-Objective Optimization N2 - We explore how warm-starting strategies can be integrated into scalarization-based approaches for multi-objective optimization in (mixed) integer linear programming. Scalarization methods remain widely used classical techniques to compute Pareto-optimal solutions in applied settings. They are favored due to their algorithmic simplicity and broad applicability across continuous and integer programs with an arbitrary number of objectives. While warm-starting has been applied in this context before, a systematic methodology and analysis remain lacking. We address this gap by providing a theoretical characterization of warm-starting within scalarization methods, focusing on the sequencing of subproblems. However, optimizing the order of subproblems to maximize warm-start efficiency may conflict with alternative criteria, such as early identification of infeasible regions. We quantify these trade-offs through an extensive computational study. T3 - ZIB-Report - 25-12 Y1 - 2025 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-101073 SN - 1438-0064 ER - TY - CHAP A1 - Gotzes, Uwe A1 - Buchholz, Annika A1 - Kallrath, Josef A1 - Lindner, Niels A1 - Koch, Thorsten T1 - Flexible Pooling Pattern Design with Integer Programming T2 - Theory, Algorithms and Experiments in Applied Optimization. In Honor of the 70th Birthday of Panos Pardalos N2 - Sample pooling has the potential to significantly enhance large-scale screening procedures, especially in scenarios like the COVID-19 pandemic, where rapid and widespread PCR testing has been crucial. Efficient strategies are essential to increase the testing capacity, i.e., the number of tests that can be processed within a given timeframe. Non-adaptive pooling strategies can further streamline the testing process by reducing the required testing rounds. In contrast to adaptive strategies, where subsequent tests depend on prior results, non-adaptive pooling processes all samples in a single round, eliminating the need for sequential retesting and reducing delays. This paper presents a highly flexible method based on integer programming to design optimized pooling patterns suitable for various applications, including medical diagnostics and quality control in industrial production. Using coronavirus testing as a case study, we formulate and solve optimization and satisfiability models that compute efficient pool designs. Our optimized pooling does not only increase testing capacity, but also accelerates the testing process and reduces overall costs. The proposed method is adaptable and can be seamlessly integrated into automated testing systems. Y1 - 2025 VL - 226 PB - Springer ER - TY - JOUR A1 - Zhou, Lei A1 - Chen, Ying A1 - Peng, Hanqiu A1 - Koch, Thorsten T1 - Is innovation slowing down? Insights from the AIMS framework of patent values JF - Expert Systems with Applications N2 - Amidst the unprecedented expansion of scientific and technological knowledge over the past century, concerns persist regarding a slowdown in innovation. To address this, we introduce the AIMS framework, which categorizes patents into four types—Aurora, Invisible, Mirage, and Success—based on their respective inherent scientific values and market-recognized economic values. Utilizing USPTO patent and citation data from 1976 to 2022, our analysis reveals an increasing volume of patent issuances but a concerning dilution in scientific quality starting in the 2000s. This trend is primarily attributed to the rise of low scientific value patents—categorized as Mirage and Invisible—and a modest decline in high-impact scientific patents—categorized as Success and Aurora. Meanwhile, the economic value of patents has risen, especially noted with the growth in Mirage patents since the 2010s, indicating a shift towards strategies that prioritize market-driven patenting. This study highlights the evolving nature of patents from mere indicators of scientific innovation to strategic tools for market dominance, providing an alternative understanding of patent value and its implications for firms’ strategic decisions over patent issuance across different sectors. Y1 - 2025 U6 - https://doi.org/10.1016/j.eswa.2025.127355 VL - 280 SP - 127355 ER - TY - JOUR A1 - Riedmüller, Stephanie A1 - Koch, Thorsten T1 - Exact Objective Space Contraction for the Preprocessing of Multi-objective Integer Programs N2 - 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. Y1 - 2025 ER - TY - JOUR A1 - Chen, Ying A1 - Koch, Thorsten A1 - Peng, Hanqui A1 - Zhang, Hongrui T1 - Benchmarking of Quantum and Classical Computing in Large-Scale Dynamic Portfolio Optimization Under Market Frictions N2 - 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. Y1 - 2025 ER - TY - JOUR A1 - Petkovic, Milena A1 - Zittel, Janina T1 - Leveraging Transfer Learning to Overcome Data Limitations in Czochralski Crystal Growth JF - Advanced Theory and Simulations Y1 - 2025 U6 - https://doi.org/10.1002/adts.202500677 VL - 8 IS - 11 ER - TY - GEN A1 - Tateiwa, Nariaki A1 - Shinano, Yuji A1 - Yasuda, Masaya A1 - Kaji, Shizuo A1 - Yamamura, Keiichiro A1 - Fujisawa, Katsuki T1 - Massively parallel sharing lattice basis reduction N2 - For cryptanalysis in lattice-based schemes, the performance evaluation of lattice basis reduction using high-performance computers is becoming increasingly important for the determination of the security level. We propose a distributed and asynchronous parallel reduction algorithm based on randomization and DeepBKZ, which is an improved variant of the block Korkine-Zolotarev (BKZ) reduction algorithm. Randomized copies of a lattice basis are distributed to up to 103,680 cores and independently reduced in parallel, while some basis vectors are shared asynchronously among all processes via MPI. There is a trade-off between randomization and information sharing; if a substantial amount of information is shared, all processes will work on the same problem, thereby diminishing the benefit of parallelization. To monitor this balance between randomness and sharing, we propose a metric to quantify the variety of lattice bases. We empirically find an optimal parameter of sharing for high-dimensional lattices. We demonstrate the efficacy of our proposed parallel algorithm and implementation with respect to both performance and scalability through our experiments. T3 - ZIB-Report - 21-38 KW - Discrete optimization KW - Lattice problem KW - Lattice-based cryptography KW - Shortest vector problem KW - Parallel algorithms KW - Ubiquity Generator Framework Y1 - 2021 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-85209 SN - 1438-0064 N1 - under review ER - TY - GEN A1 - Fujii, Koichi A1 - Kim, Sunyoung A1 - Kojima, Masakazu A1 - Mittelmann, Hans D. A1 - Shinano, Yuji T1 - An Exceptionally Difficult Binary Quadratic Optimization Problem with Symmetry: a Challenge for The Largest Unsolved QAP Instance Tai256c N2 - Tai256c is the largest unsolved quadratic assignment problem (QAP) instance in QAPLIB. It is known that QAP tai256c can be converted into a 256 dimensional binary quadratic optimization problem (BQOP) with a single cardinality constraint which requires the sum of the binary variables to be 92. As the BQOP is much simpler than the original QAP, the conversion increases the possibility to solve the QAP. Solving exactly the BQOP, however, is still very difficult. Indeed, a 1.48% gap remains between the best known upper bound (UB) and lower bound (LB) of the unknown optimal value. This paper shows that the BQOP admits a nontrivial symmetry, a property that makes the BQOP very hard to solve. The symmetry induces equivalent subproblems in branch and bound (BB) methods. To effectively improve the LB, we propose an efficient BB method that incorporates a doubly nonnegative relaxation, the standard orbit branching and a technique to prune equivalent subproblems. With this BB method, a new LB with 1.25% gap is successfully obtained, and computing an LB with 1.0% gap is shown to be still quite difficult. T3 - ZIB-Report - 23-27 Y1 - 2023 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-93072 SN - 1438-0064 ER - TY - JOUR A1 - Xu, Xiaofei A1 - Chen, Ying A1 - Zhang, Ge A1 - Koch, Thorsten T1 - Modeling Functional Time Series and Mixed-Type Predictors With Partially Functional Autoregressions JF - Journal of Business & Economic Statistics Y1 - 2022 U6 - https://doi.org/https://doi.org/10.1080/07350015.2021.2011299 SN - 0735-0015 VL - 42 IS - 2 SP - 349 EP - 366 PB - Informa UK Limited ER - TY - CHAP A1 - Hadjidimitriou, Natalia Selini A1 - Lippi, Marco A1 - Nastro, Raffaele A1 - Koch, Thorsten A1 - Mamei, Marco T1 - Short-Term Forecasting of Energy Consumption and Production in Local Energy Communities T2 - 2024 32nd International Conference on Enabling Technologies: Infrastructure for Collaborative Enterprises (WETICE) Y1 - 2024 U6 - https://doi.org/10.1109/WETICE64632.2024.00022 SP - 74 EP - 79 PB - IEEE ER - TY - JOUR A1 - Yokoyama, Ryohei A1 - Kamada, Hiroki A1 - Shinano, Yuji A1 - Wakui, Tetsuya T1 - A hierarchical optimization approach to robust design of energy supply systems based on a mixed-integer linear model JF - Energy N2 - In designing energy supply systems, designers should heighten the robustness in performance criteria against the uncertainty in energy demands. In this paper, a robust optimal design method using a hierarchical mixed-integer linear programming (MILP) method is proposed to maximize the robustness of energy supply systems under uncertain energy demands based on a mixed-integer linear model. A robust optimal design problem is formulated as a three-level min-max-min MILP one by expressing uncertain energy demands by intervals, evaluating the robustness in a performance criterion based on the minimax regret criterion, and considering relationships among integer design variables, uncertain energy demands, and integer and continuous operation variables. This problem is solved by evaluating upper and lower bounds for the minimum of the maximum regret of the performance criterion repeatedly outside, and evaluating lower and upper bounds for the maximum regret repeatedly inside. Different types of optimization problems are solved by applying a hierarchical MILP method developed for ordinary optimal design problems without and with its modifications. In a case study, the proposed approach is applied to the robust optimal design of a cogeneration system. Through the study, its validity and effectiveness are ascertained, and some features of the obtained robust designs are clarified. Y1 - 2021 U6 - https://doi.org/https://doi.org/10.1016/j.energy.2021.120343 VL - 229 ER - TY - JOUR A1 - Lenz, Ralf A1 - Becker, Kai-Helge T1 - Optimization of Capacity Expansion in Potential-driven Networks including Multiple Looping - A comparison of modelling approaches JF - OR Spectrum N2 - In commodity transport networks such as natural gas, hydrogen and water networks, flows arise from nonlinear potential differences between the nodes, which can be represented by so-called "potential-driven" network models. When operators of these networks face increasing demand or the need to handle more diverse transport situations, they regularly seek to expand the capacity of their network by building new pipelines parallel to existing ones ("looping"). The paper introduces a new mixed-integer non-linear programming (MINLP) model and a new non-linear programming (NLP) model and compares these with existing models for the looping problem and related problems in the literature, both theoretically and experimentally. On this basis, we give recommendations about the circumstances under which a certain model should be used. In particular, it turns out that one of our novel models outperforms the existing models. Moreover, the paper is the first to include the practically relevant option that a particular pipeline may be looped several times. Y1 - 2022 U6 - https://doi.org/https://doi.org/10.1007/s00291-021-00648-7 VL - 44 SP - 179 EP - 224 ER - TY - JOUR A1 - Rehfeldt, Daniel A1 - Koch, Thorsten T1 - Implications, Conflicts, and Reductions for Steiner Trees JF - Mathematical Programming Y1 - 2023 U6 - https://doi.org/10.1007/s10107-021-01757-5 VL - 197 SP - 903 EP - 966 PB - Springer ER - TY - JOUR A1 - Fujii, Koichi A1 - Kim, Sunyoung A1 - Kojima, Masakazu A1 - Mittelmann, Hans D. A1 - Shinano, Yuji T1 - An exceptionally difficult binary quadratic optimization problem with symmetry: a challenge for the largest unsolved QAP instance Tai256c JF - Optimization Letters N2 - Tai256c is the largest unsolved quadratic assignment problem (QAP) instance in QAPLIB. It is known that QAP tai256c can be converted into a 256 dimensional binary quadratic optimization problem (BQOP) with a single cardinality constraint which requires the sum of the binary variables to be 92. As the BQOP is much simpler than the original QAP, the conversion increases the possibility to solve the QAP. Solving exactly the BQOP, however, is still very difficult. Indeed, a 1.48% gap remains between the best known upper bound (UB) and lower bound (LB) of the unknown optimal value. This paper shows that the BQOP admits a nontrivial symmetry, a property that makes the BQOP very hard to solve. Despite this difficulty, it is imperative to decrease the gap in order to ultimately solve the BQOP exactly. To effectively improve the LB, we propose an efficient BB method that incorporates a doubly nonnegative relaxation, the orbit branching and the isomorphism pruning. With this BB method, a new LB with 1.25% gap is successfully obtained, and computing an LB with gap is shown to be still quite difficult. Y1 - 2024 U6 - https://doi.org/10.1007/s11590-024-02157-2 SN - 1862-4472 PB - Springer Science and Business Media LLC ER - TY - JOUR A1 - Hosoda, Junko A1 - Maher, Stephen J. A1 - Shinano, Yuji A1 - Villumsen, Jonas Christoffer T1 - A parallel branch-and-bound heuristic for the integrated long-haul and local vehicle routing problem on an adaptive transportation network JF - Computers & Operations Research N2 - Consolidation of commodities and coordination of vehicle routes are fundamental features of supply chain management problems. While locations for consolidation and coordination are typically known a priori, in adaptive transportation networks this is not the case. The identification of such consolidation locations forms part of the decision making process. Supply chain management problems integrating the designation of consolidation locations with the coordination of long haul and local vehicle routing is not only challenging to solve, but also very difficult to formulate mathematically. In this paper, the first mathematical model integrating location clustering with long haul and local vehicle routing is proposed. This mathematical formulation is used to develop algorithms to find high quality solutions. A novel parallel framework is developed that combines exact and heuristic methods to improve the search for high quality solutions and provide valid bounds. The results demonstrate that using exact methods to guide heuristic search is an effective approach to find high quality solutions for difficult supply chain management problems. Y1 - 2024 U6 - https://doi.org/10.1016/j.cor.2024.106570 SN - 0305-0548 VL - 165 PB - Elsevier BV ER - TY - GEN A1 - Yueksel-Erguen, Inci A1 - Litzel, Ida A1 - Peng, Hanqiu T1 - Integrating Large Citation Datasets N2 - This paper explores methods for building a comprehensive citation graph using big data techniques to evaluate scientific impact more accurately. Traditional citation metrics have limitations, and this work investigates merging large citation datasets to create a more accurate picture. Challenges of big data, like inconsistent data formats and lack of unique identifiers, are addressed through deduplication efforts, resulting in a streamlined and reliable merged dataset with over 119 million records and 1.4 billion citations. We demonstrate that merging large citation datasets builds a more accurate citation graph facilitating a more robust evaluation of scientific impact. T3 - ZIB-Report - 24-10 KW - big data preprocessing KW - data analytics KW - citation graphs Y1 - 2024 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-98033 SN - 1438-0064 ER - TY - JOUR A1 - Abbas, Amira A1 - Ambainis, Andris A1 - Augustino, Brandon A1 - Bärtschi, Andreas A1 - Buhrman, Harry A1 - Coffrin, Carleton A1 - Cortiana, Giorgio A1 - Dunjko, Vedran A1 - Egger, Daniel J. A1 - Elmegreen, Bruce G. A1 - Franco, Nicola A1 - Fratini, Filippo A1 - Fuller, Bryce A1 - Gacon, Julien A1 - Gonciulea, Constantin A1 - Gribling, Sander A1 - Gupta, Swati A1 - Hadfield, Stuart A1 - Heese, Raoul A1 - Kircher, Gerhard A1 - Kleinert, Thomas A1 - Koch, Thorsten A1 - Korpas, Georgios A1 - Lenk, Steve A1 - Marecek, Jakub A1 - Markov, Vanio A1 - Mazzola, Guglielmo A1 - Mensa, Stefano A1 - Mohseni, Naeimeh A1 - Nannicini, Giacomo A1 - O’Meara, Corey A1 - Tapia, Elena Peña A1 - Pokutta, Sebastian A1 - Proissl, Manuel A1 - Rebentrost, Patrick A1 - Sahin, Emre A1 - Symons, Benjamin C. B. A1 - Tornow, Sabine A1 - Valls, Víctor A1 - Woerner, Stefan A1 - Wolf-Bauwens, Mira L. A1 - Yard, Jon A1 - Yarkoni, Sheir A1 - Zechiel, Dirk A1 - Zhuk, Sergiy A1 - Zoufal, Christa T1 - Challenges and opportunities in quantum optimization JF - Nature Reviews Physics Y1 - 2024 U6 - https://doi.org/10.1038/s42254-024-00770-9 SN - 2522-5820 VL - 6 SP - 718 EP - 735 PB - Springer Science and Business Media LLC ER - TY - GEN A1 - Vu, Thi Huong A1 - Koch, Thorsten A1 - Xu, Hong-Kun T1 - The gradient projection method: Is the Polyak adaptive stepsize rule optimal? N2 - 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. Y1 - 2024 ER - TY - CHAP A1 - Hadjidimitriou, Natalia Selini A1 - Koch, Thorsten A1 - Lippi, Marco A1 - Petkovic, Milena A1 - Mamei, Marco T1 - Analysis of the Impact of COVID-19 and Russo-Ukraine War on Natural Gas Flow Using Time Series Forecasting T2 - Preceedings of the 16th International Conference on Management of Digital Ecosystems Y1 - 2024 ER - TY - GEN A1 - Riedmüller, Stephanie A1 - Rivetta, Fabian A1 - Zittel, Janina T1 - Long-Term Multi-Objective Optimization for Integrated Unit Commitment and Investment Planning for District Heating Networks N2 - The need to decarbonize the energy system has intensified the focus on district heating networks in urban and suburban areas. Therefore, exploring transformation pathways with reasonable trade-offs between economic viability and environmental goals became necessary. We introduce a network-flow-based model class integrating unit commitment and long-term investment planning for multi-energy systems. While the integration of unit commitment and investment planning has been applied to multi-energy systems, a formal introduction and suitability for the application of long-term portfolio planning of an energy provider on an urban scale has yet to be met. Based on mixed integer linear programming, the model bridges the gap between overly detailed industrial modeling tools not designed for computational efficiency at scale and rather abstract academic models. The formulation is tested on Berlin's district heating network. Hence, the challenge lies in a large number of variables and constraints and the coupling of time steps, for example, through investment decisions. A case study explores different solutions on the Pareto front defined by optimal trade-offs between minimizing costs and emissions through a lexicographic optimization approach. The resulting solution catalog can provide decision-makers valuable insights into feasible transformation pathways, highlighting distinctions between robust and target-dependent investments. T3 - ZIB-Report - 24-09 KW - multi-objective optimization KW - multi-energy systems KW - investment planning KW - unit commitment Y1 - 2024 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-97804 SN - 1438-0064 ER - TY - GEN A1 - Lindner, Niels A1 - Bartoszuk, Karolina A1 - Debgupta, Srinwanti A1 - Gering, Marie-Claire A1 - Muschner, Christoph A1 - Zittel, Janina T1 - Warm-starting modeling to generate alternatives for energy transition paths in the Berlin-Brandenburg area N2 - Energy system optimization models are key to investigate energy transition paths towards a decarbonized future. Since this approach comes with intrinsic uncertainties, it is insufficient to compute a single optimal solution assuming perfect foresight to provide a profound basis for decision makers. The paradigm of modeling to generate alternatives enables to explore the near-optimal solution space to a certain extent. However, large-scale energy models require a non-negligible computation time to be solved. We propose to use warm start methods to accelerate the process of finding close-to-optimal alternatives. In an extensive case study for the energy transition of the Berlin-Brandenburg area, we make use of the sector-coupled linear programming oemof-B3 model to analyze a scenario for the year 2050 with a resolution of one hour and 100% reduction of greenhouse gas emissions. We demonstrate that we can actually achieve a significant computational speedup. T3 - ZIB-Report - 24-08 KW - Energy System Optimization KW - Energy Transition KW - Modeling to Generate Alternatives Y1 - 2024 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-97835 SN - 1438-0064 ER - TY - GEN A1 - Le, Thi Thai T1 - Effect of viscous forces on the interface stability of a tangential-velocity discontinuity in compressible fluids T2 - Journal N2 - Compressible flows are prevalent in natural and technological processes, particularly in the energy transition to renewable energy systems. Consequently, extensive research has focused on understanding the stability of tangential--velocity discontinuity in compressible media. Despite recent advancements that address industrial challenges more realistically, many studies have ignored viscous stress tensors' impact, leading to inaccuracies in predicting interface stability. This omission becomes critical, especially in high Reynolds or low Mach number flows, where viscous forces dissipate kinetic energy across interfaces, affect total energy dissipation, and dampen flow instabilities. Our work is thus motivated to analyze the viscosity force effect by including the viscous stress tensor terms in the motion equations. Our results show that by considering the effect of viscous forces, the tangential-velocity discontinuity interface is constantly destabilized for the entire range of the Mach number. T3 - ZIB-Report - 24-04 Y1 - 2024 ER - TY - JOUR A1 - Pedersen, Jaap A1 - Le, Thi Thai A1 - Koch, Thorsten A1 - Zittel, Janina T1 - Optimal discrete pipe sizing for tree-shaped CO2 networks JF - OR Spectrum N2 - 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. Y1 - 2024 U6 - https://doi.org/10.1007/s00291-024-00773-z VL - 46 SP - 1163 EP - 1187 ER - TY - JOUR A1 - Van Bulck, David A1 - Goossens, Dries A1 - Clarner, Jan-Patrick A1 - Dimitsas, Angelos A1 - Fonseca, Georg H. G. A1 - Lamas-Fernandez, Carlos A1 - Lester, Martin Mariusz A1 - Pedersen, Jaap A1 - Phillips, Antony E. A1 - Rosati, Roberto Maria T1 - Which algorithm to select in sports timetabling? JF - European Journal of Operational Research N2 - Any sports competition needs a timetable, specifying when and where teams meet each other. The recent International Timetabling Competition (ITC2021) on sports timetabling showed that, although it is possible to develop general algorithms, the performance of each algorithm varies considerably over the problem instances. This paper provides a problem type analysis for sports timetabling, resulting in powerful insights into the strengths and weaknesses of eight state-of-the-art algorithms. Based on machine learning techniques, we propose an algorithm selection system that predicts which algorithm is likely to perform best based on the type of competition and constraints being used (i.e., the problem type) in a given sports timetabling problem instance. Furthermore, we visualize how the problem type relates to algorithm performance, providing insights and possibilities to further enhance several algorithms. Finally, we assess the empirical hardness of the instances. Our results are based on large computational experiments involving about 50 years of CPU time on more than 500 newly generated problem instances. Y1 - 2024 U6 - https://doi.org/10.1016/j.ejor.2024.06.005 VL - 318 IS - 2 SP - 575 EP - 591 ER - TY - GEN A1 - Yueksel-Erguen, Inci A1 - Koch, Thorsten A1 - Zittel, Janina T1 - Mathematical optimization based flow scenario generation for operational analysis of European gas transport networks based on open data N2 - 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. T3 - ZIB-Report - 24-03 Y1 - 2024 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-95789 SN - 1438-0064 ER - TY - CHAP A1 - Zittel, Janina A1 - Clarner, Jan-Patrick A1 - Tawfik, Christine A1 - Dykes, Maxwell A1 - Rivetta, Fabian A1 - Riedmüller, Stephanie T1 - A multi-objective optimization strategy for district heating production portfolio planning T2 - 37th International Conference on Efficiency, Cost, Optimization, Simulation and Environmental Impact of Energy Systems (ECOS 2024) N2 - The imperative to decarbonize energy systems has intensified the need for efficient transformations within the heating sector, with a particular focus on district heating networks. This study addresses this challenge by proposing a comprehensive optimization approach evaluated on the district heating network of the Märkisches Viertel of Berlin. Our objective is to simultaneously optimize heat production with three targets: minimizing costs, minimizing CO2-emissions, and maximizing heat generation from Combined Heat and Power (CHP) plants for enhanced efficiency. To tackle this optimization problem, we employed a Mixed-Integer Linear Program (MILP) that encompasses the conversion of various fuels into heat and power, integration with relevant markets, and considerations for technical constraints on power plant operation. These constraints include startup and minimum downtime, activation costs, and storage limits. The ultimate goal is to delineate the Pareto front, representing the optimal trade-offs between the three targets. We evaluate variants of the 𝜖-constraint algorithm for their effectiveness in coordinating these objectives, with a simultaneous focus on the quality of the estimated Pareto front and computational efficiency. One algorithm explores solutions on an evenly spaced grid in the objective space, while another dynamically adjusts the grid based on identified solutions. Initial findings highlight the strengths and limitations of each algorithm, providing guidance on algorithm selection depending on desired outcomes and computational constraints. Our study emphasizes that the optimal choice of algorithm hinges on the density and distribution of solutions in the feasible space. Whether solutions are clustered or evenly distributed significantly influences algorithm performance. These insights contribute to a nuanced understanding of algorithm selection for multi-objective multi-energy system optimization, offering valuable guidance for future research and practical applications for planning sustainable district heating networks. Y1 - 2024 U6 - https://doi.org/10.52202/077185-0066 SP - 764 EP - 775 ER - TY - JOUR A1 - Pedersen, Jaap A1 - Weinand, Jann Michael A1 - Syranidou, Chloi A1 - Rehfeldt, Daniel T1 - An efficient solver for large-scale onshore wind farm siting including cable routing JF - European Journal of Operational Research N2 - 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. Y1 - 2024 U6 - https://doi.org/10.1016/j.ejor.2024.04.026 VL - 317 IS - 2 SP - 616 EP - 630 ER - TY - CHAP A1 - Kiessling, David A1 - Vanaret, Charlie A1 - Astudillo, Alejandro A1 - Decré, Wilm A1 - Swevers, Jan T1 - An Almost Feasible Sequential Linear Programming Algorithm T2 - 2024 European Control Conference (ECC), Stockholm, Sweden N2 - This paper proposes an almost feasible Sequential Linear Programming (afSLP) algorithm. In the first part, the practical limitations of previously proposed Feasible Sequential Linear Programming (FSLP) methods are discussed along with illustrative examples. Then, we present a generalization of FSLP based on a tolerance-tube method that addresses the shortcomings of FSLP. The proposed algorithm afSLP consists of two phases. Phase I starts from random infeasible points and iterates towards a relaxation of the feasible set. Once the tolerance-tube around the feasible set is reached, phase II is started and all future iterates are kept within the tolerance-tube. The novel method includes enhancements to the originally proposed tolerance-tube method that are necessary for global convergence. afSLP is shown to outperform FSLP and the state-of-the-art solver IPOPT on a SCARA robot optimization problem. Y1 - 2024 U6 - https://doi.org/10.23919/ECC64448.2024.10590864 SP - 2328 EP - 2335 ER - TY - GEN A1 - Petkovic, Milena A1 - Zakiyeva, Nazgul A1 - Zittel, Janina T1 - Statistical analysis and modeling for detecting regime changes in gas nomination time series N2 - As a result of the legislation for gas markets introduced by the European Union in 2005, separate independent companies have to conduct the transport and trading of natural gas. The current gas market of Germany, which has a market value of more than 54 billion USD, consists of Transmission System Operators (TSO), network users, and traders. Traders can nominate a certain amount of gas anytime and anywhere in the network. Such unrestricted access for the traders, on the other hand, increase the uncertainty in the gas supply management. Some customers’ behaviors may cause abrupt structural changes in gas flow time series. In particular, it is a challenging task for the TSO operators to predict gas nominations 6 to 10 hours ahead. In our study, we aim to investigate the regime changes in the time series of nominations to predict the 6 to 10 hours ahead of gas nominations. T3 - ZIB-Report - 21-22 KW - Time series Y1 - 2021 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-82988 SN - 1438-0064 ER - TY - JOUR A1 - Petkovic, Milena A1 - Chen, Ying A1 - Gamrath, Inken A1 - Gotzes, Uwe A1 - Hadjidimitrou, Natalia Selini A1 - Zittel, Janina A1 - Xu, Xiaofei A1 - Koch, Thorsten T1 - A hybrid approach for high precision prediction of gas flows JF - Energy Systems N2 - 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. Y1 - 2022 U6 - https://doi.org/10.1007/s12667-021-00466-4 VL - 13 SP - 383 EP - 408 ER - TY - JOUR A1 - Hiller, Benjamin A1 - Saitenmacher, René A1 - Walther, Tom T1 - Improved models for operation modes of complex compressor stations JF - Mathematical Methods of Operations Research N2 - We study combinatorial structures in large-scale mixed-integer (nonlinear) programming problems arising in gas network optimization. We propose a preprocessing strategy exploiting the observation that a large part of the combinatorial complexity arises in certain subnetworks. Our approach analyzes these subnetworks and the combinatorial structure of the flows within these subnetworks in order to provide alternative models with a stronger combinatorial structure that can be exploited by off-the-shelve solvers. In particular, we consider the modeling of operation modes for complex compressor stations (i.e., ones with several in- or outlets) in gas networks. We propose a refined model that allows to precompute tighter bounds for each operation mode and a number of model variants based on the refined model exploiting these tighter bounds. We provide a procedure to obtain the refined model from the input data for the original model. This procedure is based on a nontrivial reduction of the graph representing the gas flow through the compressor station in an operation mode. We evaluate our model variants on reference benchmark data, showing that they reduce the average running time between 10% for easy instances and 46% for hard instances. Moreover, for three of four considered networks, the average number of search tree nodes is at least halved, showing the effectivity of our model variants to guide the solver’s search. Y1 - 2021 U6 - https://doi.org/https://doi.org/10.1007/s00186-021-00745-x VL - 94 SP - 171 EP - 195 ER - TY - JOUR A1 - Yokoyama, Ryohei A1 - Takeuchi, Kotaro A1 - Shinano, Yuji A1 - Wakui, Tetsuya T1 - Effect of model reduction by time aggregation in multiobjective optimal design of energy supply systems by a hierarchical MILP method JF - Energy N2 - The mixed-integer linear programming (MILP) method has been applied widely to optimal design of energy supply systems. A hierarchical MILP method has been proposed to solve such optimal design problems efficiently. In addition, a method of reducing model by time aggregation has been proposed to search design candidates accurately and efficiently at the upper level. In this paper, the hierarchical MILP method and model reduction by time aggregation are applied to the multiobjective optimal design. The methods of clustering periods by the order of time series, by the k-medoids method, and based on an operational strategy are applied for the model reduction. As a case study, the multiobjective optimal design of a gas turbine cogeneration system is investigated by adopting the annual total cost and primary energy consumption as the objective functions, and the clustering methods are compared with one another in terms of the computation efficiency. It turns out that the model reduction by any clustering method is effective to enhance the computation efficiency when importance is given to minimizing the first objective function, but that the model reduction only by the k-medoids method is effective very limitedly when importance is given to minimizing the second objective function. Y1 - 2021 U6 - https://doi.org/https://doi.org/10.1016/j.energy.2021.120505 VL - 228 ER - TY - JOUR A1 - Le, Thi Thai A1 - Fukumoto, Yasuhide T1 - Effect of depth discontinuity on interfacial stability of tangential-velocity discontinuity in shallow-water flow JF - Physics Letters A N2 - It is well known as the Kelvin-Helmholtz instability (KHI) that an interface of tangential velocity discontinuity is necessarily unstable, regardless of the velocity difference's strength. However, the KHI is suppressed for shallow water flows if the Froude number, defined by the ratio of the velocity difference to the gravity wave's speed, is sufficiently large. In this investigation, we examine the effect of the depth difference of two fluid layers on the KHI. The depth difference enhances instability. Given the Froude number in the instability range, the growth rate sensitively depends on the depth ratio and increases monotonically with the depth ratio difference from unity. The critical value of the Froude number for stabilization varies with the depth ratio and attains the minimum value √8 for equal depth. This behavior is verified by asymptotic analysis. Y1 - 2022 U6 - https://doi.org/10.1016/j.physleta.2022.128073 VL - 436 SP - 128073 PB - ELSEVIER ER - TY - CHAP A1 - Pedersen, Jaap A1 - Hoppmann-Baum, Kai A1 - Zittel, Janina A1 - Koch, Thorsten T1 - Blending hydrogen into natural gas: An assessment of the capacity of the German gas grid T2 - Operations Research Proceedings 2021 N2 - 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. Y1 - 2022 U6 - https://doi.org/https://doi.org/10.1007/978-3-031-08623-6_28 SP - 182 EP - 187 ER - TY - JOUR A1 - Berthold, Timo A1 - Koch, Thorsten A1 - Shinano, Yuji T1 - MILP. Try. Repeat. JF - Proceedings of the 13th International Conference on the Practice and Theory of Automated Timetabling - PATAT 2021 Y1 - 2021 VL - 2 ER - TY - GEN A1 - Zakiyeva, Nazgul A1 - Petkovic, Milena T1 - Modeling and forecasting gas network flows with multivariate time series and mathematical programming approach N2 - With annual consumption of approx. 95 billion cubic me-ters and similar amounts of gas just transshipped through Germany toother EU states, Germany’s gas transport system plays a vital role inEuropean energy supply. The complex, more than 40,000 km long high-pressure transmission network is controlled by several transmission sys-tem operators (TSOs) whose main task is to provide security of supplyin a cost-efficient way. Given the slow speed of gas flows through the gastransmission network pipelines, it has been an essential task for the gasnetwork operators to enhance the forecast tools to build an accurate andeffective gas flow prediction model for the whole network. By incorpo-rating the recent progress in mathematical programming and time seriesmodeling, we aim to model natural gas network and predict gas in- andout-flows at multiple supply and demand nodes for different forecastinghorizons. Our model is able to describe the dynamics in the network bydetecting the key nodes, which may help to build an optimal manage-ment strategy for transmission system operators. T3 - ZIB-Report - 21-23 Y1 - 2021 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-82966 SN - 1438-0064 ER - TY - JOUR A1 - Petkovic, Milena A1 - Koch, Thorsten A1 - Zittel, Janina T1 - Deep learning for spatio-temporal supply anddemand forecasting in natural gas transmission networks JF - Energy Science and Engineering N2 - 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. Y1 - 2021 U6 - https://doi.org/https://doi.org/10.1002/ese3.932 ER - TY - CHAP A1 - Diekerhof, M. A1 - Monti, A. A1 - Lebedeva, E. A1 - Tkaczyk, A. H. A1 - Yüksel-Ergün, I. A1 - Zittel, J. A1 - Escudero, L. F. A1 - Soroudi, A. A1 - Helmberg, C. A1 - Kanovíc, Ž. A1 - Petkovic, M. A1 - Lacalandra, F. A1 - Frangioni, A. A1 - Lee, J. A1 - De Filippo, A. A1 - Lombardi, M. A1 - Milano, M. A1 - Ezran, P. A1 - Haddad, Y. T1 - Production and Demand Management T2 - Mathematical Optimization for Efficient and Robust Energy Networks N2 - Demand Side Management (DSM) is usually considered as a process of energy consumption shifting from peak hours to off-peak times. DSM does not always reduce total energy consumption, but it helps to meet energy demand and supply. For example, it balances variable generation from renewables (such as solar and wind) when energy demand differs from renewable generation. Y1 - 2020 SN - 978-3-030-57442-0 U6 - https://doi.org/https://doi.org/10.1007/978-3-030-57442-0_1 VL - 4 PB - Springer ER - TY - CHAP A1 - Schwarz, R. A1 - Lacalandra, F. A1 - Schewe, L. A1 - Bettinelli, A. A1 - Vigo, D. A1 - Bischi, A. A1 - Parriani, T. A1 - Martelli, E. A1 - Vuik, K. A1 - Lenz, R. A1 - Madsen, H. A1 - Blanco, I. A1 - Guericke, D. A1 - Yüksel-Ergün, I. A1 - Zittel, J. T1 - Network and Storage T2 - Mathematical Optimization for Efficient and Robust Energy Networks N2 - Natural gas is considered by many to be the most important energy source for the future. The objectives of energy commodities strategic problems can be mainly related to natural gas and deal with the definition of the “optimal” gas pipelines design which includes a number of related sub problems such as: Gas stations (compression) location and Gas storage locations, as well as compression station design and optimal operation. Y1 - 2020 SN - 978-3-030-57442-0 U6 - https://doi.org/https://doi.org/10.1007/978-3-030-57442-0_6 VL - 4 PB - Springer ER - TY - GEN A1 - Tateiwa, Nariaki A1 - Shinano, Yuji A1 - Yamamura, Keiichiro A1 - Yoshida, Akihiro A1 - Kaji, Shizuo A1 - Yasuda, Masaya A1 - Fujisawa, Katsuki T1 - CMAP-LAP: Configurable Massively Parallel Solver for Lattice Problems N2 - Lattice problems are a class of optimization problems that are notably hard. There are no classical or quantum algorithms known to solve these problems efficiently. Their hardness has made lattices a major cryptographic primitive for post-quantum cryptography. Several different approaches have been used for lattice problems with different computational profiles; some suffer from super-exponential time, and others require exponential space. This motivated us to develop a novel lattice problem solver, CMAP-LAP, based on the clever coordination of different algorithms that run massively in parallel. With our flexible framework, heterogeneous modules run asynchronously in parallel on a large-scale distributed system while exchanging information, which drastically boosts the overall performance. We also implement full checkpoint-and-restart functionality, which is vital to high-dimensional lattice problems. Through numerical experiments with up to 103,680 cores, we evaluated the performance and stability of our system and demonstrated its high capability for future massive-scale experiments. T3 - ZIB-Report - 21-16 KW - Discrete optimization KW - Lattice problem KW - Lattice-based cryptography KW - Shortest vector problem KW - Parallel algorithms KW - Ubiquity Generator Framework Y1 - 2021 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-82802 SN - 1438-0064 N1 - Revised version is accepted to HiPC 2021 ER - TY - GEN A1 - Koch, Thorsten A1 - Berthold, Timo A1 - Pedersen, Jaap A1 - Vanaret, Charlie T1 - Progress in Mathematical Programming Solvers from 2001 to 2020 N2 - 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. T3 - ZIB-Report - 21-20 Y1 - 2022 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-82779 SN - 1438-0064 ER - TY - GEN A1 - Pedersen, Jaap A1 - Hoppmann-Baum, Kai A1 - Zittel, Janina A1 - Koch, Thorsten T1 - Blending hydrogen into natural gas: An assessment of the capacity of the German gas grid; Technical Report N2 - 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. T3 - ZIB-Report - 21-21 Y1 - 2021 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-82838 SN - 1438-0064 ER - TY - JOUR A1 - Hennings, Felix T1 - Large-scale empirical study on the momentum equation's inertia term JF - Journal of Natural Gas Science and Engineering N2 - A common approach to reduce the Euler equations' complexity for the simulation and optimization of gas networks is to neglect small terms that contribute little to the overall equations. An example is the inertia term of the momentum equation, which is said to be of negligible size under real-world operating conditions. However, this justification has always only been based on experience or single sets of artificial data points. This study closes this gap by presenting a large-scale empirical evaluation of the absolute and relative size of the inertia term when operating a real-world gas network. Our data consists of three years of fine-granular state data of one of the largest gas networks in Europe, featuring over 6,000 pipes with a total length of over 10,000 km. We found that there are only 120 events in which a subnetwork consisting of multiple pipes has an inertia term of high significance for more than three minutes. On average, such an event occurs less often than once every ten days. Therefore, we conclude that the inertia term is indeed negligible for real-world transient gas network control problems. Y1 - 2021 U6 - https://doi.org/10.1016/j.jngse.2021.104153 VL - 95 PB - Elsevier ER - TY - JOUR A1 - Le, Thi Thai A1 - Koch, Thorsten T1 - Interface stability of compressible fluids in porous media JF - Physics of Fluids N2 - 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. Y1 - 2021 U6 - https://doi.org/10.1063/5.0059336 VL - 33 IS - 8 SP - 084102 PB - AIP Publishing ER - TY - JOUR A1 - Hoppmann-Baum, Kai T1 - On the Complexity of Computing Maximum and Minimum Min‐Cost‐Flows JF - Networks N2 - Consider a flow network, i.e., a directed graph where each arc has a nonnegative capacity value and an associated length, together with nonempty supply intervals for the sources and nonempty demand intervals for the sinks. The Maximum Min-Cost-Flow Problem (MaxMCF) is to find fixed supply and demand values within these intervals such that the optimal objective value of the induced Min-Cost-Flow Problem (MCF) is maximized. In this paper, we show that MaxMCF as well as its uncapacitated variant, the Maximum Transportation Problem (MaxTP), are NP-hard. Further, we prove that MaxMCF is APX-hard if a connectedness-condition regarding the sources and the sinks of the flow network is dropped. Finally, we show how the Minimum Min-Cost-Flow Problem (MinMCF) can be solved in polynomial time. Y1 - 2021 U6 - https://doi.org/10.1002/net.22060 ER -