@inproceedings{RehfeldtKoch2021, author = {Rehfeldt, Daniel and Koch, Thorsten}, title = {Implications, conflicts, and reductions for Steiner trees}, booktitle = {Integer Programming and Combinatorial Optimization: 22th International Conference, IPCO 2021}, doi = {10.1007/978-3-030-73879-2_33}, pages = {473 -- 487}, year = {2021}, language = {en} } @misc{Hennings2021, author = {Hennings, Felix}, title = {Large-scale empirical study on the momentum equation's inertia term}, issn = {1438-0064}, doi = {10.1016/j.jngse.2021.104153}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-81881}, year = {2021}, abstract = {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 since it 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.}, language = {en} } @article{Le2021, author = {Le, Thi Thai}, title = {Effect of water depth on Kelvin - Helmholtz instability in a shallow-water flow}, volume = {62}, journal = {Journal of Mathematical Physics}, number = {10}, publisher = {AIP Publishing}, doi = {10.1063/1.5145060}, pages = {103101}, year = {2021}, abstract = {It is well known that the interface between two regions of an incompressible ideal fluid flow moving in a relative motion is necessarily destabilized, regardless of the velocity difference's strength. This phenomenon is the so-called Kelvin-Helmholtz instability (KHI). However, a large number of works demonstrated a surprising result that the instability is suppressed for shallow water flows; the interface is stabilized if the Froude number, defined by the velocity difference's ratio to the gravity wave's speed, is sufficiently large. In a limited way, these authors have been used the shallow-water equations without the higher-order effect of the dispersive terms. Thus, this investigation aims to examine these higher-order dispersive effects to analyze the interface stability problem of tangential-velocity discontinuity in shallow-water flows. In particular, we use the Green-Naghdi equations to introduce the dispersive terms related to the depth and the depth-averaged horizontal velocities of the fluid. We show that the interface stability depends on the Froude number (i.e., the velocity difference's strength) and the water depth. A critical value of the Froude number to stabilize the interface is smaller than the case of no dispersive terms, and the flow in a deeper region is more stable than in a shallower one. We also consider the distribution of kinetic and potential energy to clarify a feature characteristic of a large class of instabilities in shallow water flow. The instability of flows is caused by the decrease in the kinetic energy during the perturbation of waves. This phenomenon is known as negative energy modes and plays a vital role in applying the model to industrial equipment. A conclusion is that the equipartition of energies occurs if and only if the velocity difference is zero and the water depth is shallow enough to ignore the dispersive terms.}, language = {en} } @article{TawfikGendronLimbourg2021, author = {Tawfik, Christine and Gendron, Bernard and Limbourg, Sabine}, title = {An iterative two-stage heuristic algorithm for a bilevel service network design and pricing model}, journal = {European Journal of Operational Research}, publisher = {Elsevier}, address = {European Journal of Operational Research}, doi = {https://doi.org/10.1016/j.ejor.2021.07.052}, year = {2021}, abstract = {Building upon earlier research, we revisit a bilevel formulation of service design and pricing for freight networks, with the aim of investigating its algorithmic aspects. The model adds substantial computational challenges to the existing literature, as it deals with general integer network design variables. An iterative heuristic algorithm is introduced, based on the concepts of inverse optimization and neighbourhood search. The procedure alternates between two versions of restricted formulations of the model while inducing promising changes into the service assignments. The approach has proven a high performance for all of the considered real-world instances. Its efficiency rests on its ability to deliver results within a close proximity to those obtained by the exact solver in terms of quality, yet within a significantly smaller amount of time, and to land feasible solutions for the large-sized instances that could not be previously solved. In line with the sustainable transport goals, a deeper observation of the transport management side highlights the strategy of the algorithm favouring freight consolidation and achieving high load factors.}, language = {en} } @inproceedings{PedersenSchachlerHeideretal.2021, author = {Pedersen, Jaap and Schachler, Birgit and Heider, Anya and Pleßmann, Guido}, title = {Distribution System Planning with Battery Storage using Multiperiod Optimal Power Flow}, volume = {6}, booktitle = {14th International Renewable Energy Storage Conference 2020 (IRES 2020)}, doi = {https://doi.org/10.2991/ahe.k.210202.007}, pages = {41 -- 48}, year = {2021}, abstract = {The ongoing energy transition introduces new challenges for distribution networks and brings about the need to expand existing power grid capacities. In order to contain network expansion and with it economic costs, utilization of various flexibility options to reduce expansion needs is discussed. This paper proposes a multiperiod optimal power flow (MPOPF) approach with a new continuous network expansion formulation to optimize the deployment of flexibility options under the objective of minimizing network expansion costs. In a comparison of the newly proposed continuous network expansion formulation with an existing mixed integer formulation and a continuous interpretation of the latter the here proposed formulation is shown to be useful in order to obtain a solvable problem and contain computational efforts. The presented MPOPF including the flexibility options storage units and curtailment is then assessed on synthetic medium voltage grids and applied to evaluate the benefit of a combined vs. a stepwise optimization of these flexibility options. It is demonstrated that using a local solver the proposed approach is applicable and yields a solution in reasonable time. Furthermore, it is shown that the combined optimization generally leads to a more efficient utilization of the considered flexibility options and therefore lower grid expansion costs than the stepwise consideration.}, language = {en} } @article{RehfeldtKoch2021, author = {Rehfeldt, Daniel and Koch, Thorsten}, title = {On the exact solution of prize-collecting Steiner tree problems}, journal = {INFORMS Journal on Computing}, doi = {10.1287/ijoc.2021.1087}, year = {2021}, language = {en} } @article{HenningsAndersonHoppmannBaumetal.2021, author = {Hennings, Felix and Anderson, Lovis and Hoppmann-Baum, Kai and Turner, Mark and Koch, Thorsten}, title = {Controlling transient gas flow in real-world pipeline intersection areas}, volume = {22}, journal = {Optimization and Engineering}, edition = {2}, publisher = {Springer Nature}, doi = {https://doi.org/10.1007/s11081-020-09559-y}, pages = {687 -- 734}, year = {2021}, abstract = {Compressor stations are the heart of every high-pressure gas transport network. Located at intersection areas of the network they are contained in huge complex plants, where they are in combination with valves and regulators responsible for routing and pushing the gas through the network. Due to their complexity and lack of data compressor stations are usually dealt with in the scientific literature in a highly simplified and idealized manner. As part of an ongoing project with one of Germany's largest Transmission System Operators to develop a decision support system for their dispatching center, we investigated how to automatize control of compressor stations. Each station has to be in a particular configuration, leading in combination with the other nearby elements to a discrete set of up to 2000 possible feasible operation modes in the intersection area. Since the desired performance of the station changes over time, the configuration of the station has to adapt. Our goal is to minimize the necessary changes in the overall operation modes and related elements over time, while fulfilling a preset performance envelope or demand scenario. This article describes the chosen model and the implemented mixed integer programming based algorithms to tackle this challenge. By presenting extensive computational results on real world data we demonstrate the performance of our approach.}, language = {en} } @phdthesis{Rehfeldt2021, author = {Rehfeldt, Daniel}, title = {Faster algorithms for Steiner tree and related problems: From theory to practice}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-85148}, year = {2021}, language = {en} } @misc{HenningsPetkovicStreubel2021, author = {Hennings, Felix and Petkovic, Milena and Streubel, Tom}, title = {On the Numerical Treatment of Interlaced Target Values - Modeling, Optimization and Simulation of Regulating Valves in Gas Networks}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-85359}, year = {2021}, abstract = {Due to the current and foreseeable shifts in energy production, the trading and transport operations of gas will become more dynamic, volatile, and hence also less predictable. Therefore, computer-aided support in terms of rapid simulation and control optimization will further broaden its importance for gas network dispatching. In this paper, we aim to contribute and openly publish two new mathematical models for regulators, also referred to as control valves, which together with compressors make up the most complex and involved types of active elements in gas network infrastructures. They provide full direct control over gas networks but are in turn controlled via target values, also known as set-point values, themselves. Our models incorporate up to six dynamical target values to define desired transient states for the elements' local vicinity within the network. That is, each pair of every two target values defines a bounding box for the inlet pressure, outlet pressure as well as the passing mass flow of gas. In the proposed models, those target values are prioritized differently and are constantly in competition with each other, which can only be resolved dynamically at run-time of either a simulation or optimization process. Besides careful derivation, we compare simulation and optimization results with predictions of the commercial simulation tool SIMONE.}, language = {en} } @article{AignerClarnerLiersetal.2021, author = {Aigner, Kevin-Martin and Clarner, Jan-Patrick and Liers, Frauke and Martin, Alexander}, title = {Robust Approximation of Chance Constrained DC Optimal Power Flow under Decision-Dependent Uncertainty}, journal = {European Journal of Operational Research}, year = {2021}, abstract = {We propose a mathematical optimization model and its solution for joint chance constrained DC Optimal Power Flow. In this application, it is particularly important that there is a high probability of transmission limits being satisfied, even in the case of uncertain or fluctuating feed-in from renewable energy sources. In critical network situations where the network risks overload, renewable energy feed-in has to be curtailed by the transmission system operator (TSO). The TSO can reduce the feed-in in discrete steps at each network node. The proposed optimization model minimizes curtailment while ensuring that there is a high probability of transmission limits being maintained. The latter is modeled via (joint) chance constraints that are computationally challenging. Thus, we propose a solution approach based on the robust safe approximation of these constraints. Hereby, probabilistic constraints are replaced by robust constraints with suitably defined uncertainty sets constructed from historical data. The ability to discretely control the power feed-in then leads to a robust optimization problem with decision-dependent uncertainties, i.e. the uncertainty sets depend on decision variables. We propose an equivalent mixed-integer linear reformulation for box uncertainties with the exact linearization of bilinear terms. Finally, we present numerical results for different test cases from the Nesta archive, as well as for a real network. We consider the discrete curtailment of solar feed-in, for which we use real-world weather and network data. The experimental tests demonstrate the effectiveness of this method and run times are very fast. Moreover, on average the calculated robust solutions only lead to a small increase in curtailment, when compared to nominal solutions.}, language = {en} } @inproceedings{TateiwaShinanoYamamuraetal.2021, author = {Tateiwa, Nariaki and Shinano, Yuji and Yamamura, Keiichiro and Yoshida, Akihiro and Kaji, Shizuo and Yasuda, Masaya and Fujisawa, Katsuki}, title = {CMAP-LAP: Configurable Massively Parallel Solver for Lattice Problems}, booktitle = {HiPC 2021 proceedings}, year = {2021}, abstract = {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.}, language = {en} } @article{XuChenZhangetal.2021, author = {Xu, Xiaofei and Chen, Ying and Zhang, Ge and Koch, Thorsten}, title = {Modeling functional time series and mixed-type predictors with partially functional autoregressions*}, journal = {Journal of Business and Economic Statistics}, doi = {10.1080/07350015.2021.2011299}, pages = {1 -- 43}, year = {2021}, abstract = {In many business and economics studies, researchers have sought to measure the dynamic dependence of curves with high-dimensional mixed-type predictors. We propose a partially functional autoregressive model (pFAR) where the serial dependence of curves is controlled by coefficient operators that are defined on a two-dimensional surface, and the individual and group effects of mixed-type predictors are estimated with a two-layer regularization. We develop an efficient estimation with the proven asymptotic properties of consistency and sparsity. We show how to choose the sieve and tuning parameters in regularization based on a forward-looking criterion. In addition to the asymptotic properties, numerical validation suggests that the dependence structure is accurately detected. The implementation of the pFAR within a real-world analysis of dependence in German daily natural gas flow curves, with seven lagged curves and 85 scalar predictors, produces superior forecast accuracy and an insightful understanding of the dynamics of natural gas supply and demand for the municipal, industry, and border nodes, respectively.}, language = {en} } @misc{MostLotharSchmittetal.2021, author = {Most, Dieter and Lothar, Wyrwoll and Schmitt, Carlo and Y{\"u}ksel-Erg{\"u}n, Inci}, title = {plan4res D2.2 - Case Study 1 Report - Multimodal energy concept for achieving Europe's carbon reduction goals}, doi = {10.5281/zenodo.5809338}, year = {2021}, language = {en} } @phdthesis{Lenz2021, author = {Lenz, Ralf}, title = {Optimization of Stationary Expansion Planning and Transient Network Control by Mixed-Integer Nonlinear Programming}, doi = {10.14279/depositonce-12765}, year = {2021}, language = {en} } @article{YokoyamaShinanoWakui2021, author = {Yokoyama, Ryohei and Shinano, Yuji and Wakui, Tetsuya}, title = {エネルギー供給システムの設計および運用の 階層的関係を考慮した最適化 (蓄エネルギー機器を有するシステムへの適用)}, journal = {第40回エネルギー・資源学会研究発表会講演論文集}, pages = {398 -- 403}, year = {2021}, abstract = {Mixed-integer linear programming (MILP) methods have 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, some strategies have been proposed to enhance the computation efficiency furthermore. As one of the strategies, a method of reducing model by time aggregation has been proposed to search design candidates efficiently in the relaxed optimal design problem at the upper level. In this paper, the hierarchical MILP method with the strategies has been extendedly applied to the optimal design of energy supply systems with storage units. Especially, the method of re- ducing model is extended by aggregating representative days and sampling times differently in consideration of the characteristics of storage units. A case study is conducted on the optimal design of a gas turbine cogeneration system with a thermal storage unit for district energy supply. Through the study, it turns out the hierarchical MILP method is effective to derive the optimal solution as compared with a conventional method. It also turns out that the model reduction with the special time aggregation is effective to shorten the computation time as compared with that without time aggregation in case that the number of candidates for equipment capacities is relatively small.}, language = {ja} } @misc{PetkovicKochZittel2021, author = {Petkovic, Milena and Koch, Thorsten and Zittel, Janina}, title = {Deep learning for spatio-temporal supply and demand forecasting in natural gas transmission networks}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-81221}, 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} } @article{LeKoch2021, author = {Le, Thi Thai and Koch, Thorsten}, title = {Instability of a tangential discontinuity surface in a three-dimensional compressible medium}, volume = {33}, journal = {Physics of Fluids}, number = {1}, doi = {10.1063/5.0033753}, pages = {016106}, year = {2021}, abstract = {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.}, language = {en} } @article{HoppmannBaumHenningsZitteletal.2021, author = {Hoppmann-Baum, Kai and Hennings, Felix and Zittel, Janina and Gotzes, Uwe and Spreckelsen, Eva-Maria and Spreckelsen, Klaus and Koch, Thorsten}, title = {An Optimization Approach for the Transient Control of Hydrogen Transport Networks}, journal = {Mathematical Methods of Operations Research}, number = {Special Issue on Energy Networks}, year = {2021}, language = {en} } @article{HoppmannBaumHenningsLenzetal.2021, author = {Hoppmann-Baum, Kai and Hennings, Felix and Lenz, Ralf and Gotzes, Uwe and Heinecke, Nina and Spreckelsen, Klaus and Koch, Thorsten}, title = {Optimal Operation of Transient Gas Transport Networks}, volume = {22}, journal = {Optimization and Engineering}, doi = {10.1007/s11081-020-09584-x}, pages = {735 -- 781}, year = {2021}, abstract = {In this paper, we describe an algorithmic framework for the optimal operation of transient gas transport networks consisting of a hierarchical MILP formulation together with a sequential linear programming inspired post-processing routine. Its implementation is part of the KOMPASS decision support system, which is currently used in an industrial setting. Real-world gas transport networks are controlled by operating complex pipeline intersection areas, which comprise multiple compressor units, regulators, and valves. In the following, we introduce the concept of network stations to model them. Thereby, we represent the technical capabilities of a station by hand-tailored artificial arcs and add them to network. Furthermore, we choose from a predefined set of flow directions for each network station and time step, which determines where the gas enters and leaves the station. Additionally, we have to select a supported simple state, which consists of two subsets of artificial arcs: Arcs that must and arcs that cannot be used. The goal is to determine a stable control of the network satisfying all supplies and demands. The pipeline intersections, that are represented by the network stations, were initially built centuries ago. Subsequently, due to updates, changes, and extensions, they evolved into highly complex and involved topologies. To extract their basic properties and to model them using computer-readable and optimizable descriptions took several years of effort. To support the dispatchers in controlling the network, we need to compute a continuously updated list of recommended measures. Our motivation for the model presented here is to make fast decisions on important transient global control parameters, i.e., how to route the flow and where to compress the gas. Detailed continuous and discrete technical control measures realizing them, which take all hardware details into account, are determined in a subsequent step. In this paper, we present computational results from the KOMPASS project using detailed real-world data.}, language = {en} } @article{PrauseHoppmannBaumDefournyetal.2021, author = {Prause, Felix and Hoppmann-Baum, Kai and Defourny, Boris and Koch, Thorsten}, title = {The maximum diversity assortment selection problem}, volume = {93}, journal = {Mathematical Methods of Operations Research}, publisher = {Mathematical Methods of Operations Research}, doi = {https://doi.org/10.1007/s00186-021-00740-2}, pages = {521 -- 554}, year = {2021}, abstract = {In this article, we introduce the Maximum Diversity Assortment Selection Problem (MDASP), which is a generalization of the two-dimensional Knapsack Problem (2D-KP). Given a set of rectangles and a rectangular container, the goal of 2D-KP 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. MDASP is 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 the minimum or average normalized Hamming distance of all assortment pairs. MDASP was the topic of the 11th AIMMS-MOPTA Competition in 2019. The methods described in this article and the resulting 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 2D-KP literature.}, language = {en} }