@article{Rehfeldt2022, author = {Rehfeldt, Daniel}, title = {Faster Algorithms for Steiner Tree and related Problems: From Theory to Practice}, journal = {OR News: Das Magazin der GOR}, year = {2022}, language = {en} } @misc{TurnerBertholdBesanconetal.2022, author = {Turner, Mark and Berthold, Timo and Besan{\c{c}}on, Mathieu and Koch, Thorsten}, title = {Cutting Plane Selection with Analytic Centers and Multiregression}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-89065}, year = {2022}, abstract = {Cutting planes are a crucial component of state-of-the-art mixed-integer programming solvers, with the choice of which subset of cuts to add being vital for solver performance. We propose new distance-based measures to qualify the value of a cut by quantifying the extent to which it separates relevant parts of the relaxed feasible set. For this purpose, we use the analytic centers of the relaxation polytope or of its optimal face, as well as alternative optimal solutions of the linear programming relaxation. We assess the impact of the choice of distance measure on root node performance and throughout the whole branch-and-bound tree, comparing our measures against those prevalent in the literature. Finally, by a multi-output regression, we predict the relative performance of each measure, using static features readily available before the separation process. Our results indicate that analytic center-based methods help to significantly reduce the number of branch-and-bound nodes needed to explore the search space and that our multiregression approach can further improve on any individual method.}, language = {en} } @inproceedings{ZakiyevaPetkovic2022, author = {Zakiyeva, Nazgul and Petkovic, Milena}, title = {Modeling and Forecasting Gas Network Flows with Multivariate Time Series and Mathematical Programming Approach}, booktitle = {Operations Research Proceedings 2021. OR 2021.}, publisher = {Springer, Cham}, doi = {10.1007/978-3-031-08623-6_31}, pages = {200 -- 205}, year = {2022}, abstract = {With annual consumption of approx. 95 billion cubic meters and similar amounts of gas just transshipped through Germany to other EU states, Germany's gas transport system plays a vital role in European energy supply. The complex, more than 40,000 km long high-pressure transmission network is controlled by several transmission system operators (TSOs) whose main task is to provide security of supply in a cost-efficient way. Given the slow speed of gas flows through the gas transmission network pipelines, it has been an essential task for the gas network operators to enhance the forecast tools to build an accurate and effective gas flow prediction model for the whole network. By incorporating the recent progress in mathematical programming and time series modeling, we aim to model natural gas network and predict gas in- and out-flows at multiple supply and demand nodes for different forecasting horizons. Our model is able to describe the dynamics in the network by detecting the key nodes, which may help to build an optimal management strategy for transmission system operators.}, language = {en} } @inproceedings{PetkovicZakiyevaZittel2022, author = {Petkovic, Milena and Zakiyeva, Nazgul and Zittel, Janina}, title = {Statistical Analysis and Modeling for Detecting Regime Changes in Gas Nomination Time Series}, booktitle = {Operations Research Proceedings 2021. OR 2021}, publisher = {Springer, Cham}, doi = {10.1007/978-3-031-08623-6_29}, pages = {188 -- 193}, year = {2022}, abstract = {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 h-ahead. In our study, we aim to investigate the regime changes in time series of nominations to predict the 6 to 10 h-ahead of gas nominations.}, language = {en} } @article{KochBertholdPedersenetal.2022, author = {Koch, Thorsten and Berthold, Timo and Pedersen, Jaap and Vanaret, Charlie}, title = {Progress in mathematical programming solvers from 2001 to 2020}, volume = {10}, journal = {EURO Journal on Computational Optimization}, doi = {10.1016/j.ejco.2022.100031}, pages = {100031}, year = {2022}, abstract = {This study investigates the progress made in lp and milp solver performance during the last two decades by comparing the solver software from the beginning of the millennium with the codes available today. On average, we found out that for solving lp/milp, computer hardware got about 20 times faster, and the algorithms improved by a factor of about nine for lp and around 50 for milp, which gives a total speed-up of about 180 and 1,000 times, respectively. However, these numbers have a very high variance and they considerably underestimate the progress made on the algorithmic side: many problem instances can nowadays be solved within seconds, which the old codes are not able to solve within any reasonable time.}, language = {en} } @misc{RehfeldtFujisawaKochetal.2022, author = {Rehfeldt, Daniel and Fujisawa, Katsuki and Koch, Thorsten and Nakao, Masahiro and Shinano, Yuji}, title = {Computing single-source shortest paths on graphs with over 8 trillion edges}, issn = {1438-0064}, doi = {10.12752/8818}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-88180}, year = {2022}, abstract = {This paper introduces an implementation for solving the single-source shortest path problem on distributed-memory machines. It is tailored to power-law graphs and scales to trillions of edges. The new implementation reached 2nd and 10th place in the latest Graph500 benchmark in June 2022 and handled the largest and second-largest graphs among all participants.}, language = {en} } @misc{VuLitzelKoch2025, author = {Vu, Thi Huong and Litzel, Ida and Koch, Thorsten}, title = {Similarity-based fuzzy clustering scientific articles: potentials and challenges from mathematical and computational perspectives}, arxiv = {http://arxiv.org/abs/2506.04045}, year = {2025}, abstract = {Fuzzy clustering, which allows an article to belong to multiple clusters with soft membership degrees, plays a vital role in analyzing publication data. This problem can be formulated as a constrained optimization model, where the goal is to minimize the discrepancy between the similarity observed from data and the similarity derived from a predicted distribution. While this approach benefits from leveraging state-of-the-art optimization algorithms, tailoring them to work with real, massive databases like OpenAlex or Web of Science -- containing about 70 million articles and a billion citations -- poses significant challenges. We analyze potentials and challenges of the approach from both mathematical and computational perspectives. Among other things, second-order optimality conditions are established, providing new theoretical insights, and practical solution methods are proposed by exploiting the problem's structure. Specifically, we accelerate the gradient projection method using GPU-based parallel computing to efficiently handle large-scale data.}, language = {en} } @misc{ZakiyevaPetkovic2025, author = {Zakiyeva, Nazgul and Petkovic, Milena}, title = {Large-scale functional network time series model solved with mathematical programming approach}, journal = {Econometrics and Statistics}, doi = {10.1016/j.ecosta.2025.10.001}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-101936}, year = {2025}, abstract = {A functional network autoregressive model is proposed for studying large-scale network time series observed at high temporal resolution. The model incorporates high-dimensional curves to capture both serial and cross-sectional dependence in large-scale network functional time series. Estimation of the model is approached using a Mixed Integer Optimization method. Simulation studies confirm the consistency of parameter and adjacency matrix estimation. The method is applied to data from a real-life natural gas supply network. Compared to alternative prediction models, the proposed model delivers more accurate day-ahead hourly out-of-sample forecasts of the gas inflows and outflows at most gas nodes.}, language = {en} } @article{ZakiyevaPetkovic2025, author = {Zakiyeva, Nazgul and Petkovic, Milena}, title = {Large-scale functional network time series model solved with mathematical programming approach}, journal = {Econometrics and Statistics}, publisher = {Elsevier BV}, issn = {2452-3062}, doi = {10.1016/j.ecosta.2025.10.001}, year = {2025}, language = {en} } @misc{ShinanoVigerske2025, author = {Shinano, Yuji and Vigerske, Stefan}, title = {Smoothie: Mixing the strongest MIP solvers to solve hard MIP instances on supercomputers - Phase I development}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-101906}, year = {2025}, abstract = {Mixed-Integer Linear Programming (MIP) is applicable to such a wide range of real-world decision problems that the competition for the best code to solve such problems has lead to tremendous progress over the last decades. While current solvers can solve some of the problems that seemed completely out-of-reach just 10 years ago, there are always relevant MIP problems that currently cannot be solved. With the Smoothie solver we intend to solve extremely hard MIP problems by building on the many years that went into the development of several state-of-the-art MIP solvers and by utilizing some of the largest computing resources available. The high-level task parallelization framework UG (Ubiquity Generator) is used and extended by Smoothie to build a solver that uses large-scale parallelization to distribute the solution of a single MIP on a shared- or distributed-memory computing infrastructure, thereby employing several established MIP solvers simultaneously. For the first development phase, which is the topic of this report, both FICO Xpress and Gurobi are used in concurrent mode on a single machine, while information on incumbent solutions and explored branch-and-bound subtrees is exchanged. A dynamic restarting mechanism ensures that solver configurations are selected that promise most suitable for the MIP to be solved. We report on initial findings using this early version of Smoothie on unsolved problems from MIPLIB 2017.}, language = {en} } @misc{VuKoch2025, author = {Vu, Thi Huong and Koch, Thorsten}, title = {Clustering scientific publications: lessons learned through experiments with a real citation network}, arxiv = {http://arxiv.org/abs/2505.18180}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-100418}, year = {2025}, abstract = {Clustering scientific publications helps uncover research structures within bibliographic databases. Graph-based methods such as spectral, Louvain, and Leiden clustering are commonly used due to their ability to model citation networks. However, their effectiveness can diminish when applied to real-world data. This study evaluates these clustering algorithms on a citation graph of about 700,000 articles and 4.6 million citations from the Web of Science. The results show that while scalable methods like Louvain and Leiden perform efficiently, their default settings often yield poor partitioning. Meaningful outcomes require careful parameter tuning, especially for large networks with uneven structures, including a dense core and loosely connected papers. These findings highlight practical lessons about the challenges of large-scale data, method selection and tuning based on specific structures of bibliometric clustering tasks.}, language = {en} } @article{KiesslingLeyfferVanaret2025, author = {Kießling, David and Leyffer, Sven and Vanaret, Charlie}, title = {A Unified Funnel Restoration SQP Algorithm}, journal = {Mathematical Programming B}, doi = {10.1007/s10107-025-02284-3}, year = {2025}, abstract = {We consider nonlinearly constrained optimization problems and discuss a generic double-loop framework consisting of basic algorithmic ingredients that unifies a broad range of nonlinear optimization solvers. This framework has been implemented in the open-source solver Uno, a Swiss Army knife-like C++ optimization framework that unifies many nonlinearly constrained nonconvex optimization solvers. We illustrate the framework with a sequential quadratic programming (SQP) algorithm that maintains an acceptable upper bound on the constraint violation, called a funnel, that is monotonically decreased to control the feasibility of the iterates. Infeasible quadratic subproblems are handled by a feasibility restoration strategy. Globalization is controlled by a line search or a trust-region method. We prove global convergence of the trust-region funnel SQP method, building on known results from filter methods. We implement the algorithm in Uno, and we provide extensive test results for the trust-region line-search funnel SQP on small CUTEst instances.}, language = {en} } @article{KempkeRehfeldtKoch2025, author = {Kempke, Nils-Christian and Rehfeldt, Daniel and Koch, Thorsten}, title = {A Massively Parallel Interior-Point-Method for Arrowhead Linear Programs}, journal = {SIAM Journal on Scientific Computing}, arxiv = {http://arxiv.org/abs/2412.07731}, year = {2025}, language = {en} } @article{RongChenMaetal.2025, author = {Rong, Guoyang and Chen, Ying and Ma, Feicheng and Koch, Thorsten}, title = {Exploring Interdisciplinary Research Trends through Critical Years for Interdisciplinary Citation}, volume = {19}, journal = {Journal of Informetrics}, number = {4}, doi = {10.1016/j.joi.2025.101726}, year = {2025}, language = {en} } @misc{PedersenLindnerRehfeldtetal.2025, author = {Pedersen, Jaap and Lindner, Niels and Rehfeldt, Daniel and Koch, Thorsten}, title = {Integrated Wind Farm Design: Optimizing Turbine Placement and Cable Routing with Wake Effects}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-99218}, year = {2025}, abstract = {An accelerated deployment of renewable energy sources is crucial for a successful transformation of the current energy system, with wind energy playing a key role in this transition. This study addresses the integrated wind farm layout and cable routing problem, a challenging nonlinear optimization problem. We model this problem as an extended version of the Quota Steiner Tree Problem (QSTP), optimizing turbine placement and network connectivity simultaneously to meet specified expansion targets. Our proposed approach accounts for the wake effect - a region of reduced wind speed induced by each installed turbine - and enforces minimum spacing between turbines. We introduce an exact solution framework in terms of the novel Quota Steiner Tree Problem with interference (QSTPI). By leveraging an interference-based splitting strategy, we develop an advanced solver capable of tackling large-scale problem instances. The presented approach outperforms generic state-of-the-art mixed integer programming solvers on our dataset by up to two orders of magnitude. Moreover, we demonstrate that our integrated method significantly reduces the costs in contrast to a sequential approach. Thus, we provide a planning tool that enhances existing planning methodologies for supporting a faster and cost-efficient expansion of wind energy.}, language = {en} } @misc{KempkeKuntKatamishetal.2025, author = {Kempke, Nils-Christian and Kunt, Tim and Katamish, Bassel and Vanaret, Charlie and Sasanpour, Shima and Clarner, Jan-Patrick and Koch, Thorsten}, title = {Developing heuristic solution techniques for large-scale unit commitment models}, issn = {1438-0064}, arxiv = {http://arxiv.org/abs/2502.19012}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-99555}, year = {2025}, abstract = {Shifting towards renewable energy sources and reducing carbon emissions necessitate sophisticated energy system planning, optimization, and extension. Energy systems optimization models (ESOMs) often form the basis for political and operational decision-making. ESOMs are frequently formulated as linear (LPs) and mixed-integer linear (MIP) problems. MIPs allow continuous and discrete decision variables. Consequently, they are substantially more expressive than LPs but also more challenging to solve. The ever-growing size and complexity of ESOMs take a toll on the computational time of state-of-the-art commercial solvers. Indeed, for large-scale ESOMs, solving the LP relaxation -- the basis of modern MIP solution algorithms -- can be very costly. These time requirements can render ESOM MIPs impractical for real-world applications. This article considers a set of large-scale decarbonization-focused unit commitment models with expansion decisions based on the REMix framework (up to 83 million variables and 900,000 discrete decision variables). For these particular instances, the solution to the LP relaxation and the MIP optimum lie close. Based on this observation, we investigate the application of relaxation-enforced neighborhood search (RENS), machine learning guided rounding, and a fix-and-propagate (FP) heuristic as a standalone solution method. Our approach generated feasible solutions 20 to 100 times faster than GUROBI, achieving comparable solution quality with primal-dual gaps as low as 1\% and up to 35\%. This enabled us to solve numerous scenarios without lowering the quality of our models. For some instances that Gurobi could not solve within two days, our FP method provided feasible solutions in under one hour.}, language = {en} } @article{LePetkovic2025, author = {Le, Thi Thai and Petkovic, Milena}, title = {Predicting Fluid Interface Instability in Energy Systems for Sustainable Energy Transition}, journal = {Operations Research Proceedings 2023. OR 2023.}, publisher = {Springer}, doi = {10.1007/978-3-031-58405-3_45}, pages = {349 -- 356}, year = {2025}, abstract = {Due to the coexistence of different gases in underground storage, this work explores the interface stability's impact on energy storage, specifically during the injection and withdrawal of gases such as hydrogen and natural gas. A new approach of combing simulation and time series analysis is used to accurately predict instability modes in energy systems. Our simulation is based on the 2D Euler equations, solved using a second-order finite volume method with a staggered grid. The solution is validated by comparing them to experimental data and analytical solutions, accurately predicting the instability's behavior. We use time series analysis and state-of-the-art regime-switching methods to identify critical features of the interface dynamics, providing crucial insights into system optimization and design.}, language = {en} } @inproceedings{LindnerBartoszukDebguptaetal.2025, author = {Lindner, Niels and Bartoszuk, Karolina and Debgupta, Srinwanti and Gering, Marie-Claire and Muschner, Christoph and Zittel, Janina}, title = {Warm-starting modeling to generate alternatives for energy transition paths in the Berlin-Brandenburg area}, booktitle = {Operations Research Proceedings 2024. OR 2024}, doi = {10.1007/978-3-031-92575-7_35}, pages = {248 -- 253}, year = {2025}, abstract = {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.}, language = {en} } @inproceedings{StomporZittelKochetal.2025, author = {Stompor, Tomasz and Zittel, Janina and Koch, Thorsten and Rusch, Beate}, title = {Fully Algorithmic Librarian: Large-Scale Citation Experiments}, booktitle = {20th International Society of Scientometrics and Informetrics Conference 2025, June 23-27, 2025 | Yerevan, Armenia}, doi = {10.51408/issi2025_204}, year = {2025}, abstract = {The Fully Algorithmic Librarian (FAN) project explores application scenarios for algorithmic-intelligence(AI)-supported methods in academic libraries as central institutions for research support. To this end, the study builds on two algorithmic approaches for analyzing large-scale citation networks. A comparison of Web of Science (WoS) and OpenAlex structures using the PageRank algorithm reveals key differences. Additionally, a multi-label clustering technique designed for large-scale citation networks accounts for disciplinary variations in publication practices.}, language = {en} } @article{ChenKochPengetal.2025, author = {Chen, Ying and Koch, Thorsten and Peng, Hanqui and Zhang, Hongrui}, title = {Benchmarking of Quantum and Classical Computing in Large-Scale Dynamic Portfolio Optimization Under Market Frictions}, arxiv = {http://arxiv.org/abs/2502.05226}, year = {2025}, language = {en} } @inproceedings{TurnerBertholdBesancon2025, author = {Turner, Mark and Berthold, Timo and Besan{\c{c}}on, Mathieu}, title = {A Context-Aware Cutting Plane Selection Algorithm for Mixed-Integer Programming}, booktitle = {Operations Research Proceedings 2023. OR 2023.}, doi = {10.1007/978-3-031-58405-3_28}, pages = {217 -- 244}, year = {2025}, abstract = {The current cut selection algorithm used in mixed-integer programming solvers has remained largely unchanged since its creation. In this paper, we propose a set of new cut scoring measures, cut filtering techniques, and stopping criteria, extending the current state-of-the-art algorithm and obtaining a 5\\% performance improvement for SCIP over the MIPLIB 2017 benchmark set.}, language = {en} } @article{ShinanoFujii2025, author = {Shinano, Yuji and Fujii, Koichi}, title = {Introduction to Quadratic Programming Solvers}, volume = {64}, journal = {Journal of The Society of Instrument and Control Engineers}, number = {8}, doi = {10.11499/sicejl.64.532}, pages = {532 -- 540}, year = {2025}, language = {en} } @article{ChenXuKoch2020, author = {Chen, Ying and Xu, Xiuqin and Koch, Thorsten}, title = {Day-ahead high-resolution forecasting of natural gas demand and supply in Germany with a hybrid model}, volume = {262}, journal = {Applied Energy}, number = {114486}, doi = {https://doi.org/10.1016/j.apenergy.2019.114486}, year = {2020}, abstract = {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.}, language = {en} } @misc{ZakiyevaPetkovic2023, author = {Zakiyeva, Nazgul and Petkovic, Milena}, title = {High-dimensional high-frequency time series prediction with a mixed integer optimisation method}, journal = {Operations Research Proceedings}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-93114}, year = {2023}, language = {en} } @phdthesis{Turner2024, author = {Turner, Mark}, title = {Cutting Plane Selection for Mixed-Integer Linear Programming}, year = {2024}, abstract = {Mixed-Integer Linear Programming (MILP) is a ubiquitous and practical modelling paradigm that is essential for optimising a broad range of real-world systems. The backbone of all modern MILP solvers is the branch-and-cut algorithm, which is a hybrid of the branch-and-bound and cutting planes algorithms. Cutting planes (cuts) are linear inequalities that tighten the relaxation of a MILP. While a lot of research has gone into deriving valid cuts for MILPs, less emphasis has been put on determining which cuts to select. Cuts in general are generated in rounds, and a subset of the generated cuts must be added to the relaxation. The decision on which subset of cuts to add is called cut selection. This is a crucial task since adding too many cuts makes the relaxation large and slow to optimise over. Conversely, adding too few cuts results in an insufficiently tightened relaxation, and more relaxations need to be enumerated. To further emphasise the difficulty, the effectiveness of an applied cut is both dependent on the other applied cuts, and the state of the MILP solver. In this thesis, we present theoretical results on the importance and difficulty of cut selection, as well as practical results that use cut selection to improve general MILP solver performance. Improving general MILP solver performance is of great importance for practitioners and has many runoff effects. Reducing the solve time of currently solved systems can directly improve efficiency within the application area. In addition, improved performance enables larger systems to be modelled and optimised, and MILP to be used in areas where it was previously impractical due to time restrictions. Each chapter of this thesis corresponds to a publication on cut selection, where the contributions of this thesis can naturally be divided into four components. The first two components are motivated by instance-dependent performance. In practice, for each subroutine, including cut selection, MILP solvers have adjustable parameters with hard-coded default values. It is ultimately unrealistic to expect these default values to perform well for every instance. Rather, it would be ideal if the parameters were dependent on the given instance. To show this motivation is well founded, we first introduce a family of parametric MILP instances and cuts to showcase worst-case performance of cut selection for any fixed parameter value. We then introduce a graph neural network architecture and reinforcement learning framework for learning instance-dependent cut scoring parameters. In the following component, we formalise language for determining if a cut has theoretical usefulness from a polyhedral point of view in relation to other cuts. In addition, to overcome issues of infeasible projections and dual degeneracy, we introduce analytic center based distance measures. We then construct a lightweight multi-output regression model that predicts relative solver performance of an instance for a set of distance measures. The final two components are motivated by general MILP solver improvement via cut selection. Such improvement was shown to be possible, albeit difficult to achieve, by the first half of this thesis. We relate branch-and-bound and cuts through their underlying disjunctions. Using a history of previously computed Gomory mixed-integer cuts, we reduce the solve time of SCIP over the 67\% of affected MIPLIB 2017 instances by 4\%. In the final component, we introduce new cut scoring measures and filtering methods based on information from other MILP solving processes. The new cut selection techniques reduce the solve time of SCIP over the 97\% of affected MIPLIB 2017 instances by 5\%.}, language = {en} } @article{YuekselErguenMostWyrwolletal.2023, author = {Yueksel-Erguen, Inci and Most, Dieter and Wyrwoll, Lothar and Schmitt, Carlo and Zittel, Janina}, title = {Modeling the transition of the multimodal pan-European energy system including an integrated analysis of electricity and gas transport}, journal = {Energy Systems}, doi = {10.1007/s12667-023-00637-5}, year = {2023}, abstract = {Most recently, the European energy system has undergone a fundamental transformation to meet decarbonization targets without compromising the security of the energy supply. The transition involves several energy-generating and consuming sectors emphasizing sector coupling. The increase in the share of renewable energy sources has revealed the need for flexibility in supporting the electricity grid to cope with the resulting high degree of uncertainty. The new technologies accompanying the energy system transition and the recent political crisis in Europe threatening the security of the energy supply have invalidated the experience from the past by drastically changing the conventional scenarios. Hence, supporting strategic planning tools with detailed operational energy network models with appropriate mathematical precision has become more important than ever to understand the impacts of these disruptive changes. In this paper, we propose a workflow to investigate optimal energy transition pathways considering sector coupling. This workflow involves an integrated operational analysis of the electricity market, its transmission grid, and the gas grid in high spatio-temporal resolution. Thus, the workflow enables decision-makers to evaluate the reliability of high-level models even in case of disruptive events. We demonstrate the capabilities of the proposed workflow using results from a pan-European case study. The case study, spanning 2020-2050, illustrates that feasible potential pathways to carbon neutrality are heavily influenced by political and technological constraints. Through integrated operational analysis, we identify scenarios where strategic decisions become costly or infeasible given the existing electricity and gas networks.}, language = {en} } @article{TjusilaBesanconTurneretal.2024, author = {Tjusila, Gennesaret and Besan{\c{c}}on, Mathieu and Turner, Mark and Koch, Thorsten}, title = {How Many Clues To Give? A Bilevel Formulation For The Minimum Sudoku Clue Problem}, volume = {54}, journal = {Operations Research Letters}, doi = {10.1016/j.orl.2024.107105}, pages = {107105}, year = {2024}, abstract = {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.}, language = {en} } @article{Vanaret2024, author = {Vanaret, Charlie}, title = {Interval constraint programming for globally solving catalog-based categorical optimization}, volume = {89}, journal = {Journal of Global Optimization}, arxiv = {http://arxiv.org/abs/2104.03652}, doi = {10.1007/s10898-023-01362-0}, pages = {457 -- 476}, year = {2024}, abstract = {In this article, we propose an interval constraint programming method for globally solving catalog-based categorical optimization problems. It supports catalogs of arbitrary size and properties of arbitrary dimension, and does not require any modeling effort from the user. A novel catalog-based contractor (or filtering operator) guarantees consistency between the categorical properties and the existing catalog items. This results in an intuitive and generic approach that is exact, rigorous (robust to roundoff errors) and can be easily implemented in an off-the-shelf interval-based continuous solver that interleaves branching and constraint propagation. We demonstrate the validity of the approach on a numerical problem in which a categorical variable is described by a two-dimensional property space. A Julia prototype is available as open-source software under the MIT license.}, language = {en} } @article{LeTranPhung2016, author = {Le, Thi Thai and Tran, Van Cuc and Phung, Dang Hieu}, title = {Numerical simulation of tidal flow in Danang Bay Based on non-hydrostatic shallow water equations}, volume = {8}, journal = {Pacific Journal of Mathematics for Industry}, number = {1}, doi = {10.1186/s40736-015-0020-6}, year = {2016}, abstract = {This paper presents a numerical simulation of the tidal flow in Danang Bay (Vietnam) based on the non-hydrostatic shallow water equations. First, to test the simulation capability of the non-hydrostatic model, we have made a test simulation comparing it with the experiment by Beji and Battjes 1993. Simulation results for this case are compared with both the experimental data and calculations obtained from the traditional hydrostatic model. It is shown that the non-hydrostatic model is better than the hydrostatic model when the seabed topography variation is complex. The usefulness of the non-hydrostatic model is father shown by successfully simulating the tidal flow of Danang Bay.}, language = {en} } @article{HenningsHoppmannBaumZittel2024, author = {Hennings, Felix and Hoppmann-Baum, Kai and Zittel, Janina}, title = {Optimizing transient gas network control for challenging real-world instances using MIP-based heuristics}, volume = {5}, journal = {Open Journal of Mathematical Optimization}, arxiv = {http://arxiv.org/abs/2205.11369}, doi = {10.5802/ojmo.29}, pages = {34}, year = {2024}, language = {en} } @incollection{PedersenLjubić2024, author = {Pedersen, Jaap and Ljubić, Ivana}, title = {Prize-Collecting Steiner Tree Problem and its Variants}, booktitle = {Encyclopedia of Optimization}, editor = {Pardalos, Panos M. and Prokopyev, Oleg A.}, publisher = {Springer International Publishing}, address = {Cham}, doi = {10.1007/978-3-030-54621-2_869-1}, year = {2024}, language = {en} } @misc{TurnerBertholdBesanconetal.2023, author = {Turner, Mark and Berthold, Timo and Besan{\c{c}}on, Mathieu and Koch, Thorsten}, title = {Branching via Cutting Plane Selection: Improving Hybrid Branching}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-91120}, year = {2023}, abstract = {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.}, language = {en} } @misc{TurnerBertholdBesancon2023, author = {Turner, Mark and Berthold, Timo and Besan{\c{c}}on, Mathieu}, title = {A Context-Aware Cutting Plane Selection Algorithm for Mixed-Integer Programming}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-91691}, year = {2023}, abstract = {The current cut selection algorithm used in mixed-integer programming solvers has remained largely unchanged since its creation. In this paper, we propose a set of new cut scoring measures, cut filtering techniques, and stopping criteria, extending the current state-of-the-art algorithm and obtaining a 5\\% performance improvement for SCIP over the MIPLIB 2017 benchmark set.}, language = {en} } @article{LeFukumotoKoch2024, author = {Le, Thi Thai and Fukumoto, Yasuhide and Koch, Thorsten}, title = {Linear stability of a simple shear layer between two parallel streams in a shallow water flow}, volume = {493}, journal = {Physics Letters A}, publisher = {Elservier}, doi = {10.1016/j.physleta.2023.129264}, year = {2024}, abstract = {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.}, language = {en} } @article{YokoyamaShinanoWakui2023, author = {Yokoyama, Ryohei and Shinano, Yuji and Wakui, Tetsuya}, title = {An effective approach for deriving and evaluating approximate optimal design solutions of energy supply systems by time series aggregation}, volume = {11}, journal = {Frontiers in Energy Research}, doi = {10.3389/fenrg.2023.1128681}, pages = {1 -- 14}, year = {2023}, abstract = {It is important to design multi-energy supply systems optimally in consideration of their operations for variations in energy demands. An approach for efficiently solving such an optimal design problem with a large number of periods for variations in energy demands is to derive an approximate optimal design solution by time series aggregation. However, such an approach does not provide any information on the accuracy for the optimal value of the objective function. In this paper, an effective approach for time series aggregation is proposed to derive an approximate optimal design solution and evaluate a proper gap between the upper and lower bounds for the optimal value of the objective function based on a mixed-integer linear model. In accordance with aggregation, energy demands are relaxed to uncertain parameters and the problem for deriving an approximate optimal design solution and evaluating it is transformed to a three-level optimization problem, and it is solved by applying both the robust and hierarchical optimization methods. A case study is conducted on a cogeneration system with a practical configuration, and it turns out that the proposed approach enables one to derive much smaller gaps as compared with those obtained by a conventional approach.}, language = {en} } @misc{PedersenWeinandSyranidouetal.2023, author = {Pedersen, Jaap and Weinand, Jann Michael and Syranidou, Chloi and Rehfeldt, Daniel}, title = {An efficient solver for multi-objective onshore wind farm siting and network integration}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-90590}, year = {2023}, abstract = {Existing planning approaches for onshore wind farm siting and network integration often do not meet minimum cost solutions or social and environmental considerations. In this paper, we develop an approach for the multi-objective optimization of turbine locations and their network connection using a 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. Although our case studies in selected regions of Germany 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, network integration must be simultaneously optimized in order 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.}, language = {en} } @misc{TjusilaBesanconTurneretal.2023, author = {Tjusila, Gennesaret and Besancon, Mathieu and Turner, Mark and Koch, Thorsten}, title = {How Many Clues To Give? A Bilevel Formulation For The Minimum Sudoku Clue Problem}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-90902}, year = {2023}, abstract = {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.}, language = {en} } @phdthesis{Hennings2023, author = {Hennings, Felix}, title = {Modeling and solving real-world transient gas network transport problems using mathematical programming}, year = {2023}, abstract = {This thesis considers the transient gas network control optimization problem for on-shore pipeline-based transmission networks with numerous gas routing options. As input, the problem is given the network's topology, its initial state, and future demands at the boundaries of the network, which prescribe the gas flow exchange and potentially the pressure values. The task is to find a set of future control measures for all the active, i.e., controllable, elements in the network that minimizes a combination of different penalty functions. The problem is examined in the context of a decision support tool for gas network dispatchers. This results in detailed models featuring a diverse set of constraints, large and challenging real-world instances, and demanding time limit requirements. All these factors further complicate the problem, which is already difficult to solve in theory due to the inherent combination of non-linear and combinatorial aspects. Our contributions concern different steps of the process of solving the problem. Regarding the model formulation, we investigate the validity of two common approximations of the gas flow description in transport pipes: neglecting the inertia term and assuming a friction term that linearly depends on the gas flow and the pressure. For both, we examine if they can be applied under real-world conditions by evaluating a large amount of historical state data of the network of our project partner, the gas network operator Open Grid Europe. While we can confirm that it is reasonable to ignore the influence of the inertia term, the friction term linearization leads to significant errors and, as a consequence, cannot be used for describing the general gas flow behavior in transport pipes. As another topic of this thesis, we introduce the target value concept as a more realistic approach to express control actions of dispatchers regarding regulators and compressor stations. Here, we derive the mechanisms defined for target values based on the gas flow principles in pipes and develop a mixed-integer programming model capturing their behavior. The accuracy of this model is demonstrated in comparison to a target-value-based industry-standard simulator. Furthermore, we present two heuristics for the transient gas network control optimization problem featuring target values that are based on approximative models for the target-value-based control and determine the final decisions in a post-processing step. To compare the performance of the two heuristics with the approach of directly solving the corresponding model, we evaluate them on a set of artificially created test instances. Finally, we develop problem-specific algorithms for two variants of the described problem. One considers the control optimization for a single network station, which represents a local operation site featuring a large number of active elements. The used transient model is very detailed and includes a sophisticated representation of the compressor stations. Based on the shortness of the pipes in the station, the corresponding algorithm finds valid solutions by solving a series of stationary model variants as well as a transient rolling horizon approach. As the second variant, we consider the problem on the entire network but assume an approximative model representing the control capabilities of network stations. Aside from a new description of the compression capabilities, we introduce an algorithm that uses a combination of sequential mixed-integer programming, two heuristics based on reduced time horizons, and a specialized dynamic branch-and-bound node limit to determine promising values for the binary variables of the model. Complete solutions for the problem are obtained by fixing the binary values and solving the remaining non-linear program. Both algorithms are investigated in extensive empirical studies based on real-world instances of the corresponding model variants.}, language = {en} } @article{HenningsPetkovicStreubel2024, 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}, volume = {25}, journal = {Optimization and Engineering}, publisher = {Springer Nature}, doi = {10.1007/s11081-023-09812-0}, pages = {491 -- 527}, year = {2024}, abstract = {Due to the current and foreseeable shifts towards carbon dioxide neutral energy production, which will likely result in balancing fluctuating renewable energy generation by transforming power-to-gas-to-power as well as building a large-scale hydrogen transport infrastructure, 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 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 widely adopted commercial simulation tool SIMONE, serving as our substitute for actual real-world transport operations.}, language = {en} } @article{品野2020, author = {品野, 勇治}, title = {MIPLIB と Hans Mittelmann's benchmarks}, volume = {65}, journal = {機関誌「オペレーションズ・リサーチ」}, number = {1}, pages = {49 -- 56}, year = {2020}, abstract = {混合整数計画法 (Mixed Integer Programming: MIP) は,MIP を解くソフトウェアである MIP ソルバが大規模な現実問題を解けるようになったこともあり,現実問題を解く有用な OR の手法として広く知られるようになった.しかしながら,MIP ソルバの開発に欠かせないベンチマーク・データセットおよび性能測定方法についてはそれほど広く知られているとは言い難い.ベンチマーク・データセットは注意を払って作成しないと,多くのバイアスがかかってしまう.それらのバイアスを可能な限りのぞき,真に有用なベンチマーク・テストの結果を得るためには複数の人数で多大な労力を割く必要がある.本稿では,そのような MIP ソルバ開発の背景として重要な役割を果たしてきた MIPLIB と Hans Mittelmann's benchmarks について解説する.また,本稿において Hans Mittelmann's benchmarks は,BENCHMARKS FOR OPTIMIZATION SOFTWAREのページ (http://plato.asu.edu/bench.html) に示されているベンチマークである.}, language = {ja} } @article{品野藤井2019, author = {品野, 勇治 and 藤井, 浩一}, title = {使ってみよう線形計画ソルバ}, volume = {64}, journal = {機関誌「オペレーションズ・リサーチ」}, number = {4}, pages = {238 -- 245}, year = {2019}, abstract = {本稿では,線形計画問題を解くソフトウェアである線形計画ソルバの標準的な利用方法と,原稿執筆時点で利用可能なソルバを可能な限り紹介する.筆者らはソルバ開発コミュニティの中で仕事をしているので,この機会に現在のソルバ開発現場の様子も紹介するとともに,各ソルバの特徴として何を紹介するべきかは,できる限り開発者,または,開発者に近い研究者に問い合わせて記述した.本稿は,多くの線形計画ソルバの選択肢がある中で,読者がもつ問題を解くのに最も適当なソルバを選択するための指針を与えることを主たる目的としている.}, language = {ja} } @inproceedings{PetkovicZittel2024, author = {Petkovic, Milena and Zittel, Janina}, title = {Forecasting and modeling the dynamics of large-scale energy networks under the supply and demand balance constraint}, volume = {12}, booktitle = {Optimization in Green Sustainability and Ecological Transition. ODS 2023}, doi = {10.1007/978-3-031-47686-0_29}, year = {2024}, abstract = {With the emergence of "Big Data" the analysis of large data sets of high-dimensional energy time series in network structures have become feasible. However, building large-scale data-driven and computationally efficient models to accurately capture the underlying spatial and temporal dynamics and forecast the multivariate time series data remains a great challenge. Additional constraints make the problem more challenging to solve with conventional methods. For example, to ensure the security of supply, energy networks require the demand and supply to be balanced. This paper introduces a novel large-scale Hierarchical Network Regression model with Relaxed Balance constraint (HNR-RB) to investigate the network dynamics and predict multistep-ahead flows in the natural gas transmission network, where the total in- and out-flows of the network have to be balanced over a period of time. We concurrently address three main challenges: high dimensionality of networks with more than 100 nodes, unknown network dynamics, and constraint of balanced supply and demand in the network. The effectiveness of the proposed model is demonstrated through a real-world case study of forecasting demand and supply in a large-scale natural gas transmission network. The results demonstrate that HNR-RB outperforms alternative models for short- and mid-term horizons.}, language = {en} } @article{TateiwaShinanoYasudaetal.2023, author = {Tateiwa, Nariaki and Shinano, Yuji and Yasuda, Masaya and Kaji, Shizuo and Yamamura, Keiichiro and Fujisawa, Katsuki}, title = {Development and analysis of massive parallelization of a lattice basis reduction algorithm}, volume = {40}, journal = {Japan Journal of Industrial and Applied Mathematics}, number = {1}, doi = {10.1007/s13160-023-00580-z}, pages = {13 -- 56}, year = {2023}, abstract = {The security of lattice-based cryptography relies on the hardness of solving lattice problems. Lattice basis reduction is a strong tool for solving lattice problems, and the block Korkine-Zolotarev (BKZ) reduction algorithm is the de facto standard in cryptanalysis. We propose a parallel algorithm of BKZ-type reduction based on randomization. Randomized copies of an input lattice basis are independently reduced in parallel, while several basis vectors are shared asynchronously among all processes. There is a trade-off between randomization and information sharing; if a substantial amount of information is shared, all processes might work on the same problem, which diminishes the benefit of parallelization. To monitor the balance between randomness and sharing, we propose a new metric to quantify the variety of lattice bases, and we empirically find an optimal parameter of sharing for high-dimensional lattices. We also demonstrate the effectiveness of our parallel algorithm and metric through experiments from multiple perspectives.}, language = {en} } @misc{PrauseHoppmannBaumDefournyetal.2020, author = {Prause, Felix and Hoppmann-Baum, Kai and Defourny, Boris and Koch, Thorsten}, title = {The Maximum Diversity Assortment Selection Problem}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-81039}, year = {2020}, abstract = {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.}, language = {en} } @misc{AndersonTurnerKoch2020, author = {Anderson, Lovis and Turner, Mark and Koch, Thorsten}, title = {Generative deep learning for decision making in gas networks}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-81103}, year = {2020}, abstract = {A decision support system relies on frequent re-solving of similar problem instances. While the general structure remains the same in corresponding applications, the input parameters are updated on a regular basis. We propose a generative neural network design for learning integer decision variables of mixed-integer linear programming (MILP) formulations of these problems. We utilise a deep neural network discriminator and a MILP solver as our oracle to train our generative neural network. In this article, we present the results of our design applied to the transient gas optimisation problem. With the trained network we produce a feasible solution in 2.5s, use it as a warm-start solution, and thereby decrease global optimal solution solve time by 60.5\%.}, language = {en} } @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{ZakiyevaXu2020, author = {Zakiyeva, Nazgul and Xu, X.}, title = {Nonlinear network autoregressive model with application to natural gas network forecasting}, journal = {Mathematics Japonica}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-81025}, year = {2020}, language = {en} } @article{StreubelTischendorfGriewank2020, author = {Streubel, Tom and Tischendorf, Caren and Griewank, Andreas}, title = {Piecewise Polynomial Taylor Expansions - The Generalization of Fa{\`a} di Bruno's Formula}, journal = {Modeling, Simulation and Optimization of Complex Processes HPSC 2018}, number = {Modeling, Simulation and Optimization of Complex Processes HPSC 2018}, publisher = {Springer International Publishing}, doi = {10.1007/978-3-030-55240-4_3}, pages = {63 -- 82}, year = {2020}, abstract = {We present an extension of Taylor's Theorem for the piecewise polynomial expansion of non-smooth evaluation procedures involving absolute value operations. Evaluation procedures are computer programs of mathematical functions in closed form expression and allow a different treatment of smooth operations or calls to the absolute value function. The well known classical Theorem of Taylor defines polynomial approximations of sufficiently smooth functions and is widely used for the derivation and analysis of numerical integrators for systems of ordinary differential- or differential-algebraic equations, for the construction of solvers for continuous non-linear optimization of finite dimensional objective functions and for root solving of non-linear systems of equations. The long term goal is the stabilization and acceleration of already known methods and the derivation of new methods by incorporating piecewise polynomial Taylor expansions. The herein provided proof of the higher order approximation quality of the new generalized expansions is constructive and allows efficiently designed algorithms for the execution and computation of the piecewise polynomial expansions. As a demonstration towards the ultimate goal we will derive a prototype of a {\\$}{\\$}k{\\$}{\\$}k-step method on the basis of polynomial interpolation and the proposed generalized expansions.}, 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} } @misc{HoppmannBaumMexiBurdakovetal.2020, author = {Hoppmann-Baum, Kai and Mexi, Gioni and Burdakov, Oleg and Casselgren, Carl Johan and Koch, Thorsten}, title = {Length-Constrained Cycle Partition with an Application to UAV Routing}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-80489}, year = {2020}, abstract = {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.}, language = {en} }