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 Y1 - 2025 ER - TY - JOUR A1 - Chen, Ying A1 - Xu, Xiuqin A1 - Koch, Thorsten T1 - Day-ahead high-resolution forecasting of natural gas demand and supply in Germany with a hybrid model JF - Applied Energy N2 - As the natural gas market is moving towards short-term planning, accurate and robust short-term forecasts of the demand and supply of natural gas is of fundamental importance for a stable energy supply, a natural gas control schedule, and transport operation on a daily basis. We propose a hybrid forecast model, Functional AutoRegressive and Convolutional Neural Network model, based on state-of-the-art statistical modeling and artificial neural networks. We conduct short-term forecasting of the hourly natural gas flows of 92 distribution nodes in the German high-pressure gas pipeline network, showing that the proposed model provides nice and stable accuracy for different types of nodes. It outperforms all the alternative models, with an improved relative accuracy up to twofold for plant nodes and up to fourfold for municipal nodes. For the border nodes with rather flat gas flows, it has an accuracy that is comparable to the best performing alternative model. KW - Natural gas flow forecasting KW - Neural network KW - Hybrid model KW - Functional autoregressive Y1 - 2020 U6 - https://doi.org/https://doi.org/10.1016/j.apenergy.2019.114486 VL - 262 IS - 114486 ER - TY - JOUR A1 - Tjusila, Gennesaret A1 - Besançon, Mathieu A1 - Turner, Mark A1 - Koch, Thorsten T1 - How Many Clues To Give? A Bilevel Formulation For The Minimum Sudoku Clue Problem JF - Operations Research Letters N2 - It has been shown that any 9 by 9 Sudoku puzzle must contain at least 17 clues to have a unique solution. This paper investigates the more specific question: given a particular completed Sudoku grid, what is the minimum number of clues in any puzzle whose unique solution is the given grid? We call this problem the Minimum Sudoku Clue Problem (MSCP). We formulate MSCP as a binary bilevel linear program, present a class of globally valid inequalities, and provide a computational study on 50 MSCP instances of 9 by 9 Sudoku grids. Using a general bilevel solver, we solve 95% of instances to optimality, and show that the solution process benefits from the addition of a moderate amount of inequalities. Finally, we extend the proposed model to other combinatorial problems in which uniqueness of the solution is of interest. Y1 - 2024 U6 - https://doi.org/10.1016/j.orl.2024.107105 VL - 54 SP - 107105 ER - TY - GEN A1 - Turner, Mark A1 - Berthold, Timo A1 - Besançon, Mathieu A1 - Koch, Thorsten T1 - Branching via Cutting Plane Selection: Improving Hybrid Branching N2 - Cutting planes and branching are two of the most important algorithms for solving mixed-integer linear programs. For both algorithms, disjunctions play an important role, being used both as branching candidates and as the foundation for some cutting planes. We relate branching decisions and cutting planes to each other through the underlying disjunctions that they are based on, with a focus on Gomory mixed-integer cuts and their corresponding split disjunctions. We show that selecting branching decisions based on quality measures of Gomory mixed-integer cuts leads to relatively small branch-and-bound trees, and that the result improves when using cuts that more accurately represent the branching decisions. Finally, we show how the history of previously computed Gomory mixed-integer cuts can be used to improve the performance of the state-of-the-art hybrid branching rule of SCIP. Our results show a 4% decrease in solve time, and an 8% decrease in number of nodes over affected instances of MIPLIB 2017. T3 - ZIB-Report - 23-17 KW - cutting plane selection KW - variable selection KW - mixed-integer programming Y1 - 2023 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-91120 SN - 1438-0064 ER - TY - JOUR A1 - Le, Thi Thai A1 - Fukumoto, Yasuhide A1 - Koch, Thorsten T1 - Linear stability of a simple shear layer between two parallel streams in a shallow water flow JF - Physics Letters A N2 - The stability of shear layers in fluid flows is a crucial factor in forming vortices and jets and plays a fundamental role in the development of turbulence. Such shear layer instabilities are ubiquitous in natural phenomena, such as atmospheric and oceanic flows, contributing to the formation of weather systems and predicting tsunamis. This study specifically focuses on the stability of a shear layer sandwiched between two semi-infinite layers within a two-dimensional flow. The velocity profile of the shear layer is assumed to be linearly dependent on the vertical coordinate, while the velocity of the other layers remains uniform with differing strengths. The effect of viscosity and surface tension is ignored to simplify the analysis. The shallow water equations are used to analyze the interface stability of the shear layer, and the resulting dispersion relation between wave frequency and other wave characteristics is obtained. This relation incorporates Whittaker functions and their first derivatives and is used to derive appropriate limits corresponding to various physical conditions. Our study thus contributes to a deeper understanding of the stability of shear layers and their implications for natural phenomena. Y1 - 2024 U6 - https://doi.org/10.1016/j.physleta.2023.129264 VL - 493 PB - Elservier ER - TY - GEN A1 - Tjusila, Gennesaret A1 - Besancon, Mathieu A1 - Turner, Mark A1 - Koch, Thorsten T1 - How Many Clues To Give? A Bilevel Formulation For The Minimum Sudoku Clue Problem N2 - It has been shown that any 9 by 9 Sudoku puzzle must contain at least 17 clues to have a unique solution. This paper investigates the more specific question: given a particular completed Sudoku grid, what is the minimum number of clues in any puzzle whose unique solution is the given grid? We call this problem the Minimum Sudoku Clue Problem (MSCP). We formulate MSCP as a binary bilevel linear program, present a class of globally valid inequalities, and provide a computational study on 50 MSCP instances of 9 by 9 Sudoku grids. Using a general bilevel solver, we solve 95\% of instances to optimality, and show that the solution process benefits from the addition of a moderate amount of inequalities. Finally, we extend the proposed model to other combinatorial problems in which uniqueness of the solution is of interest. T3 - ZIB-Report - 23-15 Y1 - 2023 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-90902 ER - TY - GEN A1 - Prause, Felix A1 - Hoppmann-Baum, Kai A1 - Defourny, Boris A1 - Koch, Thorsten T1 - The Maximum Diversity Assortment Selection Problem N2 - In this paper, we introduce the Maximum Diversity Assortment Selection Problem (MADASS), which is a generalization of the 2-dimensional Cutting Stock Problem (2CSP). Given a set of rectangles and a rectangular container, the goal of 2CSP is to determine a subset of rectangles that can be placed in the container without overlapping, i.e., a feasible assortment, such that a maximum area is covered. In MADASS, we need to determine a set of feasible assortments, each of them covering a certain minimum threshold of the container, such that the diversity among them is maximized. Thereby, diversity is defined as minimum or average normalized Hamming-Distance of all assortment pairs. The MADASS Problem was used in the 11th AIMMS-MOPTA Competition in 2019. The methods we describe in this article and the computational results won the contest. In the following, we give a definition of the problem, introduce a mathematical model and solution approaches, determine upper bounds on the diversity, and conclude with computational experiments conducted on test instances derived from the 2CSP literature. T3 - ZIB-Report - 20-34 KW - Combinatorial Optimization KW - Mixed Integer Programming KW - 2-dim Cutting Stock Problem KW - Maximum Diversity Problem Y1 - 2020 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-81039 SN - 1438-0064 ER - TY - GEN A1 - Anderson, Lovis A1 - Turner, Mark A1 - Koch, Thorsten T1 - Generative deep learning for decision making in gas networks N2 - A decision support system relies on frequent re-solving of similar problem instances. While the general structure remains the same in corresponding applications, the input parameters are updated on a regular basis. We propose a generative neural network design for learning integer decision variables of mixed-integer linear programming (MILP) formulations of these problems. We utilise a deep neural network discriminator and a MILP solver as our oracle to train our generative neural network. In this article, we present the results of our design applied to the transient gas optimisation problem. With the trained network we produce a feasible solution in 2.5s, use it as a warm-start solution, and thereby decrease global optimal solution solve time by 60.5%. T3 - ZIB-Report - 20-38 Y1 - 2020 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-81103 SN - 1438-0064 ER - TY - GEN A1 - Petkovic, Milena A1 - Koch, Thorsten A1 - Zittel, Janina T1 - Deep learning for spatio-temporal supply and demand forecasting in natural gas transmission networks 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. T3 - ZIB-Report - 21-01 Y1 - 2021 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-81221 SN - 1438-0064 ER - TY - JOUR A1 - Le, Thi Thai A1 - Koch, Thorsten T1 - Instability of a tangential discontinuity surface in a three-dimensional compressible medium JF - Physics of Fluids N2 - Compressible flows appear in many natural and technological processes, for instance, the flow of natural gases in a pipe system. Thus, a detailed study of the stability of tangential velocity discontinuity in compressible media is relevant and necessary. The first early investigation in two-dimensional (2D) media was given more than 70 years ago. In this article, we continue investigating the stability in three-dimensional (3D) media. The idealized statement of this problem in an infinite spatial space was studied by Syrovatskii in 1954. However, the omission of the absolute sign of cos θ with θ being the angle between vectors of velocity and wave number in a certain inequality produced the inaccurate conclusion that the flow is always unstable for entire values of the Mach number M. First, we revisit this case to arrive at the correct conclusion, namely that the discontinuity surface is stabilized for a large Mach number with a given value of the angle θ. Next, we introduce a real finite spatial system such that it is bounded by solid walls along the flow direction. We show that the discontinuity surface is stable if and only if the dispersion relation equation has only real roots, with a large value of the Mach number; otherwise, the surface is always unstable. In particular, we show that a smaller critical value of the Mach number is required to make the flow in a narrow channel stable. Y1 - 2021 U6 - https://doi.org/10.1063/5.0033753 VL - 33 IS - 1 SP - 016106 ER - TY - JOUR A1 - Hoppmann-Baum, Kai A1 - Hennings, Felix A1 - Zittel, Janina A1 - Gotzes, Uwe A1 - Spreckelsen, Eva-Maria A1 - Spreckelsen, Klaus A1 - Koch, Thorsten T1 - An Optimization Approach for the Transient Control of Hydrogen Transport Networks JF - Mathematical Methods of Operations Research Y1 - 2021 IS - Special Issue on Energy Networks ER - TY - GEN A1 - Hoppmann-Baum, Kai A1 - Mexi, Gioni A1 - Burdakov, Oleg A1 - Casselgren, Carl Johan A1 - Koch, Thorsten T1 - Length-Constrained Cycle Partition with an Application to UAV Routing N2 - In this article, we discuss the Length-Constrained Cycle Partition Problem (LCCP). Besides edge weights, the undirected graph in LCCP features an individual critical weight value for each vertex. A cycle partition, i.e., a vertex disjoint cycle cover, is a feasible solution if the length of each cycle is not greater than the critical weight of each of the vertices in the cycle. The goal is to find a feasible partition with the minimum number of cycles. In this article, we discuss theoretical properties, preprocessing techniques, and two mixed-integer programming models (MIP) for LCCP both inspired by formulations for the closely related Travelling Salesperson Problem (TSP). Further, we introduce conflict hypergraphs, whose cliques yield valid constraints for the MIP models. We conclude with a report on computational experiments conducted on (A)TSPLIB-based instances. As an example, we use a routing problem in which a fleet of uncrewed aerial vehicles (UAVs) patrols a set of areas. T3 - ZIB-Report - 20-30 Y1 - 2020 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-80489 SN - 1438-0064 ER -