@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} } @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} } @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} } @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{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} } @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} } @article{GotzesHoppmannBaum2020, author = {Gotzes, Uwe and Hoppmann-Baum, Kai}, title = {Bounding the final rank during a round robin tournament with integer programming}, volume = {1866-1505}, journal = {Operational Research}, doi = {https://doi.org/10.1007/s12351-020-00546-w}, year = {2020}, abstract = {This article is mainly motivated by the urge to answer two kinds of questions regarding the Bundesliga, which is Germany's primary football (soccer) division having the highest average stadium attendance worldwide: "At any point in the season, what is the lowest final rank a certain team can achieve?" and "At any point in the season, what is the highest final rank a certain team can achieve?". Although we focus on the Bundesliga in particular, the integer programming formulations we introduce to answer these questions can easily be adapted to a variety of other league systems and tournaments.}, language = {en} } @article{KochSchmidtHilleretal.2020, author = {Koch, Thorsten and Schmidt, Martin and Hiller, Benjamin and Pfetsch, Marc and Geißler, Bj{\"o}rn and Henrion, Ren{\´e} and Joormann, Imke and Martin, Alexander and Morsi, Antonio and R{\"o}misch, Werner and Schewe, Lars and Schultz, R{\"u}diger}, title = {Capacity Evaluation for Large-Scale Gas Networks}, volume = {35}, journal = {German Success Stories in Industrial Mathematics}, isbn = {978-3-030-81454-0}, doi = {10.1007/978-3-030-81455-7}, pages = {23 -- 28}, year = {2020}, language = {en} } @article{ChenZakiyevaZhuetal.2020, author = {Chen, Ying and Zakiyeva, Nazgul and Zhu, Bangzhu and Koch, Thorsten}, title = {Modeling and Forecasting the Dynamics of the Natural Gas Transmission Network in Germany with the Demand and Supply Balance Constraint}, journal = {Applied Energy}, number = {278}, doi = {10.1016/j.apenergy.2020.115597}, year = {2020}, language = {en} } @article{KochChenLimetal.2020, author = {Koch, Thorsten and Chen, Ying and Lim, Kian Guan and Xu, Xiaofei and Zakiyeva, Nazgul}, title = {A review study of functional autoregressive models with application to energy forecasting}, journal = {WIREs Computational Statistics}, doi = {10.1002/wics.1525}, year = {2020}, language = {en} } @misc{HoppmannBaumHenningsZitteletal.2020, author = {Hoppmann-Baum, Kai and Hennings, Felix and Zittel, Janina and Gotzes, Uwe and Spreckelsen, Eva-Maria and Spreckelsen, Klaus and Koch, Thorsten}, title = {From Natural Gas towards Hydrogen - A Feasibility Study on Current Transport Network Infrastructure and its Technical Control}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-79901}, year = {2020}, abstract = {This study examines the usability of a real-world, large-scale natural gas transport infrastructure for hydrogen transport. We investigate whether a converted network can transport the amounts of hydrogen necessary to satisfy current energy demands. After introducing an optimization model for the robust transient control of hydrogen networks, we conduct computational experiments based on real-world demand scenarios. Using a representative network, we demonstrate that replacing each turbo compressor unit by four parallel hydrogen compressors, each of them comprising multiple serial compression stages, and imposing stricter rules regarding the balancing of in- and outflow suffices to realize transport in a majority of scenarios. However, due to the reduced linepack there is an increased need for technical and non-technical measures leading to a more dynamic network control. Furthermore, the amount of energy needed for compression increases by 364\% on average.}, 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{GriewankStreubelTischendorf2020, author = {Griewank, Andreas and Streubel, Tom and Tischendorf, Caren}, title = {On the abs-polynomial expansion of piecewise smooth functions}, journal = {Optimization Methods and Software}, publisher = {Taylor \& Francis}, doi = {10.1080/10556788.2020.1817448}, year = {2020}, abstract = {Tom Streubel has observed that for functions in abs-normal form, generalized Taylor expansions of arbitrary order \$\bar d-1\$ can be generated by algorithmic piecewise differentiation. Abs-normal form means that the real or vector valued function is defined by an evaluation procedure that involves the absolute value function \$|...|\$ apart from arithmetic operations and \$\bar d\$ times continuously differentiable univariate intrinsic functions. The additive terms in Streubel's expansion are abs-polynomial, i.e. involve neither divisions nor intrinsics. When and where no absolute values occur, Moore's recurrences can be used to propagate univariate Taylor polynomials through the evaluation procedure with a computational effort of \$\mathcal O({\bar d}^2)\$, provided all univariate intrinsics are defined as solutions of linear ODEs. This regularity assumption holds for all standard intrinsics, but for irregular elementaries one has to resort to Faa di Bruno's formula, which has exponential complexity in \$\bar d\$. As already conjectured we show that the Moore recurrences can be adapted for regular intrinsics to the abs-normal case. Finally, we observe that where the intrinsics are real analytic the expansions can be extended to infinite series that converge absolutely on spherical domains.}, language = {en} } @incollection{HoppmannBaumMexiBurdakovetal.2020, author = {Hoppmann-Baum, Kai and Mexi, Gioni and Burdakov, Oleg and Casselgren, Carl Johan and Koch, Thorsten}, title = {Minimum Cycle Partition with Length Requirements}, volume = {12296}, booktitle = {Integration of Constraint Programming, Artificial Intelligence, and Operations Research}, editor = {Hebrard, Emmanuel and Musliu, Nysret}, publisher = {Springer International Publishing}, address = {Cham}, isbn = {978-3-030-58941-7}, doi = {10.1007/978-3-030-58942-4_18}, pages = {273 -- 282}, year = {2020}, abstract = {In this article we introduce a Minimum Cycle Partition Problem with Length Requirements (CPLR). This generalization of the Travelling Salesman Problem (TSP) originates from routing Unmanned Aerial Vehicles (UAVs). Apart from nonnegative edge weights, CPLR has an individual critical weight value associated with each vertex. A cycle partition, i.e., a vertex disjoint cycle cover, is regarded as a feasible solution if the length of each cycle, which is the sum of the weights of its edges, is not greater than the critical weight of each of its vertices. The goal is to find a feasible partition, which minimizes the number of cycles. In this article, a heuristic algorithm is presented together with a Mixed Integer Programming (MIP) formulation of CPLR. We furthermore introduce a conflict graph, whose cliques yield valid constraints for the MIP model. Finally, we report on computational experiments conducted on TSPLIB-based test instances.}, 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} } @misc{YuekselErguenZittelWangetal.2020, author = {Yueksel-Erguen, Inci and Zittel, Janina and Wang, Ying and Hennings, Felix and Koch, Thorsten}, title = {Lessons learned from gas network data preprocessing}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-78262}, year = {2020}, abstract = {The German high-pressure natural gas transport network consists of thousands of interconnected elements spread over more than 120,000 km of pipelines built during the last 100 years. During the last decade, we have spent many person-years to extract consistent data out of the available sources, both public and private. Based on two case studies, we present some of the challenges we encountered. Preparing consistent, high-quality data is surprisingly hard, and the effort necessary can hardly be overestimated. Thus, it is particularly important to decide which strategy regarding data curation to adopt. Which precision of the data is necessary? When is it more efficient to work with data that is just sufficiently correct on average? In the case studies we describe our experiences and the strategies we adopted to deal with the obstacles and to minimize future effort. Finally, we would like to emphasize that well-compiled data sets, publicly available for research purposes, provide the grounds for building innovative algorithmic solutions to the challenges of the future.}, language = {en} } @misc{PetkovicZakiyeva2022, author = {Petkovic, Milena and Zakiyeva, Nazgul}, title = {Mathematical Optimization for Analyzing and Forecasting Nonlinear Network Time Series}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-88037}, year = {2022}, abstract = {This work presents an innovative short to mid-term forecasting model that analyzes nonlinear complex spatial and temporal dynamics in energy networks under demand and supply balance constraints using Network Nonlinear Time Series (TS) and Mathematical Programming (MP) approach. We address three challenges simultaneously, namely, the adjacency matrix is unknown; the total amount in the network has to be balanced; dependence is unnecessarily linear. We use a nonparametric approach to handle the nonlinearity and estimate the adjacency matrix under the sparsity assumption. The estimation is conducted with the Mathematical Optimisation method. We illustrate the accuracy and effectiveness of the model on the example of the natural gas transmission network of one of the largest transmission system operators (TSOs) in Germany, Open Grid Europe. The obtained results show that, especially for shorter forecasting horizons, the proposed method outperforms all considered benchmark models, improving the average nMAPE for 5.1\% and average RMSE for 79.6\% compared to the second-best model. The model is capable of capturing the nonlinear dependencies in the complex spatial-temporal network dynamics and benefits from both sparsity assumption and the demand and supply balance constraint.}, language = {en} } @article{PetkovicZakiyeva2022, author = {Petkovic, Milena and Zakiyeva, Nazgul}, title = {Mathematical Optimization for Analyzing and Forecasting Nonlinear Network Time Series}, journal = {Operations Research Proceedings 2022}, year = {2022}, abstract = {This work presents an innovative short to mid-term forecasting model that analyzes nonlinear complex spatial and temporal dynamics in energy networks under demand and supply balance constraints using Network Nonlinear Time Series (TS) and Mathematical Programming (MP) approach. We address three challenges simultaneously, namely, the adjacency matrix is unknown; the total amount in the network has to be balanced; dependence is unnecessarily linear. We use a nonparametric approach to handle the nonlinearity and estimate the adjacency matrix under the sparsity assumption. The estimation is conducted with the Mathematical Optimisation method. We illustrate the accuracy and effectiveness of the model on the example of the natural gas transmission network of one of the largest transmission system operators (TSOs) in Germany, Open Grid Europe. The obtained results show that, especially for shorter forecasting horizons, proposed method outperforms all considered benchmark models, improving the avarage nMAPE for 5.1\% and average RMSE for 79.6\% compared to the second-best model. The model is capable to capture the nonlinear dependencies in the complex spatial-temporal network dynamics and benefits from both sparsity assumption and the demand and supply balance constraint.}, language = {en} } @misc{HenningsHoppmannBaumZittel2022, 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}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-86842}, year = {2022}, abstract = {Optimizing the transient control of gas networks is a highly challenging task. The corresponding model incorporates the combinatorial complexity of determining the settings for the many active elements as well as the non-linear and non-convex nature of the physical and technical principles of gas transport. In this paper, we present the latest improvements of our ongoing work to solve this problem for real-world, large-scale problem instances: By adjusting our mixed-integer non-linear programming model regarding the gas compression capabilities in the network, we reflect the technical limits of the underlying units more accurately while maintaining a similar overall model size. In addition, we introduce a new algorithmic approach that is based on splitting the complexity of the problem by first finding assignments for discrete variables and then determining the continuous variables as locally optimal solution of the corresponding non-linear program. For the first task, we design multiple different heuristics based on concepts for general time-expanded optimization problems that find solutions by solving a sequence of sub-problems defined on reduced time horizons. To demonstrate the competitiveness of our approach, we test our algorithm on particularly challenging historic demand scenarios. The results show that high-quality solutions are obtained reliably within short solving times, making the algorithm well-suited to be applied at the core of time-critical industrial applications.}, language = {en} } @misc{PedersenLeKochetal.2022, author = {Pedersen, Jaap and Le, Thi Thai and Koch, Thorsten and Zittel, Janina}, title = {Optimal discrete pipe sizing for tree-shaped CO2 networks}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-87574}, year = {2022}, abstract = {While energy-intensive industries like the steel industry plan to switch to renewable energy sources, other industries, such as the cement industry, have to rely on carbon capture storage and utilization technologies to reduce the inevitable carbon dioxide (CO2) emissions of their production processes. In this context, we investigate the problem of finding optimal pipeline diameters from a discrete set of diameters for a tree-shaped network transporting captured CO2 from multiple sources to a single sink. The general problem of optimizing arc capacities in potential-based fluid networks is a challenging mixed-integer nonlinear program. Additionally, the behaviour of CO2 is highly sensitive and nonlinear regarding temperature and pressure changes. We propose an iterative algorithm splitting the problem into two parts: a) the pipe-sizing problem under a fixed supply scenario and temperature distribution and b) the thermophysical modelling including mixing effects, the Joule-Thomson effect, and heat exchange with the surrounding environment. We show the effectiveness of our approach by applying our algorithm to a real-world network planning problem for a CO2 network in Western Germany.}, language = {en} } @article{LeKoch2022, author = {Le, Thi Thai and Koch, Thorsten}, title = {Viscosity and porosity effects on tangential-discontinuity surface stability in 3D Compressible Media}, volume = {34}, journal = {Physics of Fluids}, number = {7}, publisher = {AIP Publishing}, doi = {10.1063/5.0095970}, year = {2022}, abstract = {The stability of a flow in porous media relates to the velocity rate of injecting and withdrawing natural gases inside porous storage. We thus aim to analyze the stability of flows in porous media to accelerate the energy transition process. This research examines a flow model of a tangential--velocity discontinuity with porosity and viscosity changes in a three-dimensional (3D) compressible medium because of a co-existence of different gases in a storage. The fluids are assumed to move in a relative motion where the plane y=0 is a tangential-velocity discontinuity surface. We obtain that the critical value of the Mach number to stabilize a tangential discontinuity surface of flows via porous media is smaller than the one of flows in a plane. The critical value of the Mach number M to stabilize a discontinuity surface of the 3D flow is different by a factor |cosθ| compared to the two-dimensional (2D) flow. Here, θ is the angle between velocity and wavenumber vectors. Our results also show that the flow model with viscosity and porosity effects is stable faster than those without these terms. Our analysis is done for both infinite and finite flows. The effect of solid walls along the flow direction could suppress the instability, i.e., the tangential-discontinuity surface is stabilized faster}, language = {en} } @article{LenzSerrano2022, author = {Lenz, Ralf and Serrano, Felipe}, title = {Tight Convex Relaxations for the Expansion Planning Problem}, volume = {194}, journal = {Journal of Optimization Theory and Applications}, doi = {10.1007/s10957-022-02029-8}, pages = {325 -- 352}, year = {2022}, abstract = {Secure energy transport is considered as highly relevant for the basic infrastructure of nowadays society and economy. To satisfy increasing demands and to handle more diverse transport situations, operators of energy networks regularly expand the capacity of their network by building new network elements, known as the expansion planning problem. A key constraint function in expansion planning problems is a nonlinear and nonconvex potential loss function. In order to improve the algorithmic performance of state-of-the-art MINLP solvers, this paper presents an algebraic description for the convex envelope of this function. Through a thorough computational study, we show that this tighter relaxation tremendously improves the performance of the MINLP solver SCIP on a large test set of practically relevant instances for the expansion planning problem. In particular, the results show that our achievements lead to an improvement of the solver performance for a development version by up to 58\%.}, language = {en} } @misc{HosodaMaherShinano2024, author = {Hosoda, Junko and Maher, Stephen J. and Shinano, Yuji}, title = {Combining Benders' decomposition and parallelisation to solve large-scale adaptive network supply chain management problems}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-98744}, year = {2024}, abstract = {Integrated supply chain network design—combining warehouse clustering with inter- and intra-cluster vehicle routing—is a fundamental feature of supply chain management problems. In this paper, a Benders' decomposition-based parallel heuristic approach for the integrated long-haul and local vehicle routing problem is proposed. The proposed algorithm comprises lower- and upper-bound search algorithms running in parallel to find high-quality solutions for challenging supply chain management problems. A novel Benders' decomposition approach is proposed to aid the improvement in the lower bound for large-scale problems. The results demonstrate that the Benders' decomposition approach is effective in finding strong lower bounds and is beneficial for obtaining high-quality solutions.}, language = {en} } @article{ChenKochZakiyevaetal.2022, author = {Chen, Ying and Koch, Thorsten and Zakiyeva, Nazgul and Liu, Kailiang and Xu, Zhitong and Chen, Chun-houh and Nakano, Junji and Honda, Keisuke}, title = {Article's Scientific Prestige: Measuring the Impact of Individual Articles in the Web of Science}, volume = {17}, number = {1}, doi = {https://doi.org/10.1016/j.joi.2023.101379}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-86380}, pages = {101379}, year = {2022}, abstract = {We performed a citation analysis on the Web of Science publications consisting of more than 63 million articles and 1.45 billion citations on 254 subjects from 1981 to 2020. We proposed the Article's Scientific Prestige (ASP) metric and compared this metric to number of citations (\#Cit) and journal grade in measuring the scientific impact of individual articles in the large-scale hierarchical and multi-disciplined citation network. In contrast to \#Cit, ASP, that is computed based on the eigenvector centrality, considers both direct and indirect citations, and provides steady-state evaluation cross different disciplines. We found that ASP and \#Cit are not aligned for most articles, with a growing mismatch amongst the less cited articles. While both metrics are reliable for evaluating the prestige of articles such as Nobel Prize winning articles, ASP tends to provide more persuasive rankings than \#Cit when the articles are not highly cited. The journal grade, that is eventually determined by a few highly cited articles, is unable to properly reflect the scientific impact of individual articles. The number of references and coauthors are less relevant to scientific impact, but subjects do make a difference.}, language = {en} } @misc{TurnerKochSerranoetal.2022, author = {Turner, Mark and Koch, Thorsten and Serrano, Felipe and Winkler, Michael}, title = {Adaptive Cut Selection in Mixed-Integer Linear Programming}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-86055}, year = {2022}, abstract = {Cut selection is a subroutine used in all modern mixed-integer linear programming solvers with the goal of selecting a subset of generated cuts that induce optimal solver performance. These solvers have millions of parameter combinations, and so are excellent candidates for parameter tuning. Cut selection scoring rules are usually weighted sums of different measurements, where the weights are parameters. We present a parametric family of mixed-integer linear programs together with infinitely many family-wide valid cuts. Some of these cuts can induce integer optimal solutions directly after being applied, while others fail to do so even if an infinite amount are applied. We show for a specific cut selection rule, that any finite grid search of the parameter space will always miss all parameter values, which select integer optimal inducing cuts in an infinite amount of our problems. We propose a variation on the design of existing graph convolutional neural networks, adapting them to learn cut selection rule parameters. We present a reinforcement learning framework for selecting cuts, and train our design using said framework over MIPLIB 2017. Our framework and design show that adaptive cut selection does substantially improve performance over a diverse set of instances, but that finding a single function describing such a rule is difficult. Code for reproducing all experiments is available at https://github.com/Opt-Mucca/Adaptive-Cutsel-MILP.}, language = {en} } @article{HoppmannBaumBurdakovMexietal.2022, author = {Hoppmann-Baum, Kai and Burdakov, Oleg and Mexi, Gioni and Casselgren, Carl Johan and Koch, Thorsten}, title = {Length-Constrained Cycle Partition with an Application to UAV Routing}, journal = {Optimization Methods and Software}, doi = {10.1080/10556788.2022.2053972}, year = {2022}, abstract = {This article discusses the Length-Constrained Cycle Partition Problem (LCCP), which constitutes a new generalization of the Travelling Salesperson Problem (TSP). Apart from nonnegative edge weights, the undirected graph in LCCP features a nonnegative critical length parameter for each vertex. A cycle partition, i.e., a vertex-disjoint cycle cover, is a feasible solution for LCCP if the length of each cycle is not greater than the critical length of each vertex contained in it. The goal is to find a feasible partition having a minimum number of cycles. Besides analyzing theoretical properties and developing preprocessing techniques, we propose an elaborate heuristic algorithm that produces solutions of good quality even for large-size instances. Moreover, we present two exact mixed-integer programming formulations (MIPs) for LCCP, which are inspired by well-known modeling approaches for TSP. Further, we introduce the concept of conflict hypergraphs, whose cliques yield valid constraints for the MIP models. We conclude with a discussion on computational experiments that we conducted using (A)TSPLIB-based problem instances. As a motivating example application, we describe a routing problem where a fleet of uncrewed aerial vehicles (UAVs) must patrol a given set of areas.}, language = {en} } @article{TurnerKochSerranoetal.2023, author = {Turner, Mark and Koch, Thorsten and Serrano, Felipe and Winkler, Michael}, title = {Adaptive Cut Selection in Mixed-Integer Linear Programming}, volume = {4}, journal = {Open Journal of Mathematical Optimization}, doi = {10.5802/ojmo.25}, pages = {5}, year = {2023}, abstract = {Cutting plane selection is a subroutine used in all modern mixed-integer linear programming solvers with the goal of selecting a subset of generated cuts that induce optimal solver performance. These solvers have millions of parameter combinations, and so are excellent candidates for parameter tuning. Cut selection scoring rules are usually weighted sums of different measurements, where the weights are parameters. We present a parametric family of mixed-integer linear programs together with infinitely many family-wide valid cuts. Some of these cuts can induce integer optimal solutions directly after being applied, while others fail to do so even if an infinite amount are applied. We show for a specific cut selection rule, that any finite grid search of the parameter space will always miss all parameter values, which select integer optimal inducing cuts in an infinite amount of our problems. We propose a variation on the design of existing graph convolutional neural networks, adapting them to learn cut selection rule parameters. We present a reinforcement learning framework for selecting cuts, and train our design using said framework over MIPLIB 2017 and a neural network verification data set. Our framework and design show that adaptive cut selection does substantially improve performance over a diverse set of instances, but that finding a single function describing such a rule is difficult. Code for reproducing all experiments is available at https://github.com/Opt-Mucca/Adaptive-Cutsel-MILP.}, language = {en} } @misc{Pedersen2020, type = {Master Thesis}, author = {Pedersen, Jaap}, title = {Multiperiod Optimal Power Flow Problem In Distribution System Planning}, pages = {61}, year = {2020}, abstract = {Growing demand, distributed generation, such as renewable energy sources (RES), and the increasing role of storage systems to mitigate the volatility of RES on a medium voltage level, push existing distribution grids to their limits. Therefore, necessary network expansion needs to be evaluated to guarantee a safe and reliable electricity supply in the future taking these challenges into account. This problem is formulated as an optimal power flow (OPF) problem which combines network expansion, volatile generation and storage systems, minimizing network expansion and generation costs. As storage systems introduce a temporal coupling into the system, a multiperiod OPF problem is needed and analysed in this thesis. To reduce complexity, the network expansion problem is represented in a continuous nonlinear programming formulation by using fundamental properties of electrical engeneering. This formulation is validated succesfully against a common mixed integer programming approach on a 30 and 57 bus network with respect to solution and computing time. As the OPF problem is, in general, a nonconvex, nonlinear problem and, thus, hard to solve, convex relaxations of the power flow equations have gained increasing interest. Sufficient conditions are represented which guarantee exactness of a second-order cone (SOC) relaxation of an operational OPF in radial networks. In this thesis, these conditions are enhanced for the network expansion planning problem. Additionally, nonconvexities introduced by the choice of network expansion variables are relaxed by using McCormick envelopes. These relaxations are then applied on the multiperiod OPF and compared to the original problem on a 30 and a 57 bus network. In particular, the computational time is decreased by an order up to 10^2 by the SOC relaxation while it provides either an exact solution or a sufficient lower bound on the original problem. Finally, a sensitivity study is performed on weights of network expansion costs showing strong dependency of both the solution of performed expansion and solution time on the chosen weights.}, language = {en} } @article{RiedmuellerLindner2025, author = {Riedm{\"u}ller, Stephanie and Lindner, Niels}, title = {Column Generation for Periodic Timetabling}, arxiv = {http://arxiv.org/abs/2510.12466}, year = {2025}, abstract = {Periodic timetabling for public transportation networks is typically modelled as a Periodic Event Scheduling Problem (PESP). Solving instances of the benchmark library PESPlib to optimality continues to pose a challenge. As a further approach towards this goal, we remodel the problem by a time discretization of the underlying graph and consider arc-based as well as path-based integer programming formulations. For the path-based case, we use cycles on the graph expansion of the operational lines as variables and, therefore, include more of the problem inherent structure into the model. A consequence is the validity of several known inequalities and a lower bound on the LP-relaxation, that is the best known to date. As an extension we integrate passenger routing into the new model. The proposed models have an advantage in the linear programming relaxation, on the one hand, but have an increased problem size, on the other hand. We define the corresponding pricing problems for the use of column generation to handle the size. Both models are practically tested on different problem instances.}, language = {en} } @misc{LindnerMehlBartoszuketal.2025, author = {Lindner, Niels and Mehl, Lukas and Bartoszuk, Karolina and Berendes, Sarah and Zittel, Janina}, title = {Demand Uncertainty in Energy Systems: Scenario Catalogs vs. Integrated Robust Optimization}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-102404}, year = {2025}, abstract = {Designing efficient energy systems is indispensable for shaping a more sustainable society. This involves making infrastructure investment decisions that must be valid for a long-term time horizon. While energy system optimization models constitute a powerful technique to support planning decisions, they need to cope with inherent uncertainty. For example, predicting future demand on a scale of decades is not only an intricate challenge in itself, but small fluctuations in such a forecast might also largely impact the layout of a complex energy system. In this paper, we compare two methodologies of capturing demand uncertainty for linear-programming based energy system optimization models. On one hand, we generate and analyze catalogs of varying demand scenarios, where each individual scenario is considered independently, so that the optimization produces scenario-specific investment pathways. On the other hand, we make use of robust linear programming to meet the demand of all scenarios at once. Since including a multitude of scenarios increases the size and complexity of the optimization model, we will show how to use warm-starting approaches to accelerate the computation process, by exploiting the similar structure of the linear program across different demand inputs. This allows to integrate a meaningful number of demand scenarios with fully-fledged energy system models. We demonstrate the practical use of our methods in a case study of the Berlin-Brandenburg area in Germany, a region that contains both a metropolitan area and its rural surroundings. As a backbone, we use the open-source framework oemof to create a sector-coupled optimization model for planning an energy system with up to 100\% reduction of greenhouse gas emissions. This model features a fine-grained temporal resolution of one hour for the full year 2050. We consider uncertainty in demand for electricity, hydrogen, natural gas, central, and decentral heat. Based on our computations, we analyze the trade-offs in terms of quality and computation time for scenario catalogs and the robust optimization approach. We further demonstrate that our procedure provides a valuable strategy for decision makers to gain insight on the robustness and sensitivity of solutions regarding demand variability.}, language = {en} } @inproceedings{LindnerMehlBartoszuketal.2025, author = {Lindner, Niels and Mehl, Lukas and Bartoszuk, Karolina and Berendes, Sarah and Zittel, Janina}, title = {Demand Uncertainty in Energy Systems: Scenario Catalogs vs. Integrated Robust Optimization}, booktitle = {Proceedings of the 38th International Conference on Efficiency, Cost, Optimization, Simulation and Environmental Impact of Energy Systems}, year = {2025}, abstract = {Designing efficient energy systems is indispensable for shaping a more sustainable society. This involves making infrastructure investment decisions that must be valid for a long-term time horizon. While energy system optimization models constitute a powerful technique to support planning decisions, they need to cope with inherent uncertainty. For example, predicting future demand on a scale of decades is not only an intricate challenge in itself, but small fluctuations in such a forecast might also largely impact the layout of a complex energy system. In this paper, we compare two methodologies of capturing demand uncertainty for linear-programming based energy system optimization models. On one hand, we generate and analyze catalogs of varying demand scenarios, where each individual scenario is considered independently, so that the optimization produces scenario-specific investment pathways. On the other hand, we make use of robust linear programming to meet the demand of all scenarios at once. Since including a multitude of scenarios increases the size and complexity of the optimization model, we will show how to use warm-starting approaches to accelerate the computation process, by exploiting the similar structure of the linear program across different demand inputs. This allows to integrate a meaningful number of demand scenarios with fully-fledged energy system models. We demonstrate the practical use of our methods in a case study of the Berlin-Brandenburg area in Germany, a region that contains both a metropolitan area and its rural surroundings. As a backbone, we use the open-source framework oemof to create a sector-coupled optimization model for planning an energy system with up to 100\% reduction of greenhouse gas emissions. This model features a fine-grained temporal resolution of one hour for the full year 2050. We consider uncertainty in demand for electricity, hydrogen, natural gas, central, and decentral heat. Based on our computations, we analyze the trade-offs in terms of quality and computation time for scenario catalogs and the robust optimization approach. We further demonstrate that our procedure provides a valuable strategy for decision makers to gain insight on the robustness and sensitivity of solutions regarding demand variability.}, language = {en} } @misc{TurnerChmielaKochetal.2023, author = {Turner, Mark and Chmiela, Antonia and Koch, Thorsten and Winkler, Michael}, title = {PySCIPOpt-ML: Embedding Trained Machine Learning Models into Mixed-Integer Programs}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-93095}, year = {2023}, abstract = {A standard tool for modelling real-world optimisation problems is mixed-integer programming (MIP). However, for many of these problems there is either incomplete information describing variable relations, or the relations between variables are highly complex. To overcome both these hurdles, machine learning (ML) models are often used and embedded in the MIP as surrogate models to represent these relations. Due to the large amount of available ML frameworks, formulating ML models into MIPs is highly non-trivial. In this paper we propose a tool for the automatic MIP formulation of trained ML models, allowing easy integration of ML constraints into MIPs. In addition, we introduce a library of MIP instances with embedded ML constraints. The project is available at https://github.com/Opt-Mucca/PySCIPOpt-ML.}, language = {en} } @inproceedings{TurnerChmielaKochetal.2025, author = {Turner, Mark and Chmiela, Antonia and Koch, Thorsten and Winkler, Michael}, title = {PySCIPOpt-ML: Embedding Trained Machine Learning Models into Mixed-Integer Programs}, volume = {15763}, booktitle = {Integration of Constraint Programming, Artificial Intelligence, and Operations Research. CPAIOR 2025}, doi = {10.1007/978-3-031-95976-9_14}, year = {2025}, abstract = {A standard tool for modelling real-world optimisation problems is mixed-integer programming (MIP). However, for many of these problems there is either incomplete information describing variable relations, or the relations between variables are highly complex. To overcome both these hurdles, machine learning (ML) models are often used and embedded in the MIP as surrogate models to represent these relations. Due to the large amount of available ML frameworks, formulating ML models into MIPs is highly non-trivial. In this paper we propose a tool for the automatic MIP formulation of trained ML models, allowing easy integration of ML constraints into MIPs. In addition, we introduce a library of MIP instances with embedded ML constraints. The project is available at https://github.com/Opt-Mucca/PySCIPOpt-ML.}, language = {en} } @article{KotilPelofskeRiedmuelleretal.2025, author = {Kotil, Ayse and Pelofske, Elijah and Riedm{\"u}ller, Stephanie and Egger, Daniel J. and Eidenbenz, Stephan and Koch, Thorsten and Woerner, Stefan}, title = {Quantum Approximate Multi-Objective Optimization}, journal = {Nature Computational Science}, arxiv = {http://arxiv.org/abs/2503.22797}, doi = {10.1038/s43588-025-00873-y}, pages = {1168 -- 1177}, year = {2025}, abstract = {The goal of multi-objective optimization is to understand optimal trade-offs between competing objective functions by finding the Pareto front, i.e., the set of all Pareto optimal solutions, where no objective can be improved without degrading another one. Multi-objective optimization can be challenging classically, even if the corresponding single-objective optimization problems are efficiently solvable. Thus, multi-objective optimization represents a compelling problem class to analyze with quantum computers. In this work, we use low-depth Quantum Approximate Optimization Algorithm to approximate the optimal Pareto front of certain multi-objective weighted maximum cut problems. We demonstrate its performance on an IBM Quantum computer, as well as with Matrix Product State numerical simulation, and show its potential to outperform classical approaches.}, language = {en} } @article{ZittelPetkovicEinck2025, author = {Zittel, Janina and Petkovic, Milena and Einck, Mathias}, title = {Forecasting Hourly Gas Flows}, volume = {79}, journal = {Foresight - The International Journal of Applied Forecasting}, pages = {40 -- 44}, year = {2025}, language = {en} } @article{ShimadaMakoYaegashietal.2025, author = {Shimada, Naoki and Mako, Sato and Yaegashi, Yuta and Koch, Thorsten and Le, Thi Thai}, title = {An Application of Modified S-CLSVOF Method to Kelvin-Helmholtz Instability and Comparison with Theoretical Result}, volume = {58}, journal = {Journal of Chemical Engineering of Japan}, number = {1}, publisher = {Taylor and Francis}, doi = {10.1080/00219592.2025.2451953}, year = {2025}, abstract = {This study focuses on validating a two-phase flow solver based on the modified Simple Coupled Level Set and Volume of Fluid method (Uchihashi et al. (2023)) through viscous Kelvin-Helmholtz instability simulations. Our numerical simulation results are compared with the ones given by Funada and Joseph (2001) to provide reliable predictions of interface behavior under the influence of viscosity. The primary goal is to accurately assess the solver's ability to replicate theoretical analysis of interface behaviors under various conditions. First, the wave between two fluids of identical density is calculated. In addition, the effect of surface tension is investigated. By comparing growth rates, numerical simulations obtain well-agreements with the analytical results on the effect of the fluid viscosity, the wave number, and the surface tension. Finally, fluid density is changed to an air-water system. When relative velocity U is smaller than the criteria of relative velocity U_c given by analytical solutions, the wave is not broken. However, waves are splashed into droplets in the condition of U>U_c. This result agrees with the analysis by Funada and Joseph (2001). These findings provide a robust framework for applying the solver to more complex two-phase flow problems, supporting advancements in numerical simulations of fluid interfaces.}, language = {en} } @article{RongChenKochetal.2026, author = {Rong, Guoyang and Chen, Ying and Koch, Thorsten and Honda, Keisuke}, title = {Assessing data quality in citation analysis: A case study of web of science and Crossref}, volume = {20}, journal = {Journal of Informetrics}, number = {1}, publisher = {Elsevier BV}, issn = {1751-1577}, doi = {10.1016/j.joi.2026.101775}, year = {2026}, language = {en} } @misc{KempkeKoch2025, author = {Kempke, Nils-Christian and Koch, Thorsten}, title = {Low-precision first-order method-based fix-and-propagate heuristics for large-scale mixed-integer linear optimization}, issn = {1438-0064}, arxiv = {http://arxiv.org/abs/2503.10344}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-99612}, year = {2025}, abstract = {We investigate the use of low-precision first-order methods (FOMs) within a fix-and-propagate (FP) framework for solving mixed-integer programming problems (MIPs). FOMs, using only matrix-vector products instead of matrix factorizations, are well suited for GPU acceleration and have recently gained more attention for their application to large-scale linear programming problems (LPs). We employ PDLP, a variant of the Primal-Dual Hybrid Gradient (PDHG) method specialized to LP problems, to solve the LP-relaxation of our MIPs to low accuracy. This solution is used to motivate fixings within our fix-and-propagate framework. We implemented four different FP variants using primal and dual LP solution information. We evaluate the performance of our heuristics on MIPLIB 2017, showcasing that the low-accuracy LP solution produced by the FOM does not lead to a loss in quality of the FP heuristic solutions when compared to a high-accuracy interior-point method LP solution. Further, we use our FP framework to produce high-accuracy solutions for large-scale (up to 243 million non-zeros and 8 million decision variables) unit-commitment energy-system optimization models created with the modeling framework REMix. For the largest problems, we can generate solutions with under 2\% primal-dual gap in less than 4 hours, whereas commercial solvers cannot generate feasible solutions within two days of runtime. This study represents the first successful application of FOMs in large-scale mixed-integer optimization, demonstrating their efficacy and establishing a foundation for future research in this domain.}, language = {en} } @inproceedings{GhannamGleixner2025, author = {Ghannam, Mohammed and Gleixner, Ambros}, title = {Hybrid Genetic Search for Dynamic Vehicle Routing with Time Windows}, booktitle = {Operations Research Proceedings 2023. OR 2023}, doi = {10.1007/978-3-031-58405-3_35}, year = {2025}, language = {en} } @inproceedings{PedersenLindnerRehfeldtetal.2026, author = {Pedersen, Jaap and Lindner, Niels and Rehfeldt, Daniel and Koch, Thorsten}, title = {Comparing Branching Rules for the Quota Steiner Tree Problem with Interference}, booktitle = {Operations Research Proceedings 2025}, year = {2026}, abstract = {Branching decisions play a crucial role in branch-and-bound algorithms for solving combinatorial optimization problems. In this paper, we investigate several branching rules applied to the Quota Steiner Tree Problem with Interference (QSTPI). The Quota Steiner Tree Problem (QSTP) generalizes the classical Steiner Tree Problem (STP) in graphs by seeking a minimum-cost tree that connects a subset of profit-associated vertices whose cumulative profit meets or exceeds a given quota. The QSTPI introduces interference among vertices: Selecting certain vertices simultaneously reduces their individual contributions to the overall profit. This problem arises, for example, in positioning and connecting wind turbines, where turbines possibly shadow other turbines, reducing their energy yield. Unlike classical STP variants, large QSTPI instances require significantly more branching to compute provably optimal solutions. In contrast to branching on variables, we utilize the combinatorial structure of the QSTPI by branching on the graph's vertices. We adapt classical and problem-specific branching rules and present a comprehensive computational study comparing the effectiveness of these branching strategies.}, language = {en} } @inproceedings{KochKempkeLindneretal.2026, author = {Koch, Thorsten and Kempke, Nils-Christian and Lindner, Niels and Mehl, Lukas and Wetzel, Manuel and Zittel, Janina}, title = {High-Performance Robust Energy System Planning with Storage: A Single-LP Approach}, booktitle = {Proceedings of URBSENSE 2026 - 1st International Workshop on URBan SENSEmaking and Intelligence for Safer Cities}, year = {2026}, language = {en} } @article{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}, publisher = {Springer}, 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} } @article{HadjidimitriouKochLippietal.2026, author = {Hadjidimitriou, Natalia Selini and Koch, Thorsten and Lippi, Marco and Petkovic, Milena and Mamei, Marco}, title = {Spatial analysis of COVID-19 and the Russia-Ukraine war impacts on natural gas flows using statistical and machine learning models}, volume = {29}, journal = {World Wide Web}, number = {2}, publisher = {Springer Science and Business Media LLC}, issn = {1386-145X}, doi = {https://doi.org/10.1007/s11280-025-01402-7}, year = {2026}, language = {en} } @misc{KempkeMaherRehfeldtetal.2026, author = {Kempke, Nils-Christian and Maher, Stephen John and Rehfeldt, Daniel and Gleixner, Ambros and Koch, Thorsten and Uslu, Svenja}, title = {Distributed Parallel Structure-Aware Presolving for Arrowhead Linear Programs}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-103034}, year = {2026}, abstract = {We present a structure-aware parallel presolve framework specialized to arrowhead linear programs (AHLPs) and designed for high-performance computing (HPC) environments, integrated into the parallel interior point solver PIPS-IPM++. Large-scale LPs arising from automated model generation frequently contain redundancies and numerical pathologies that necessitate effective presolve, yet existing presolve techniques are primarily serial or structure-agnostic and can become time-consuming in parallel solution workflows. Within PIPS-IPM++, AHLPs are stored in distributed memory, and our presolve builds on this to apply a highly parallel, distributed presolve across compute nodes while keeping communication overhead low and preserving the underlying arrowhead structure. We demonstrate the scalability and effectiveness of our approach on a diverse set of AHLPs and compare it against state-of-the-art presolve implementations, including PaPILO and the presolve implemented within Gurobi. Even on a single machine, our presolve significantly outperforms PaPILO by a factor of 18 and Gurobi's presolve by a factor of 6 in terms of shifted geometric mean runtime, while reducing the problems by a similar amount to PaPILO. Using a distributed compute environment, we outperform Gurobi's presolve by a factor of 13.}, language = {en} } @article{SatoKochLe2026, author = {Sato, Mako and Koch, Thorsten and Le, Thi Thai}, title = {Influence of frictional drag on Kelvin-Helmholtz instability in viscous fluids}, volume = {38}, journal = {Physics of Fluids}, number = {1}, publisher = {AIP Publishing}, address = {Physics of Fluids}, doi = {10.1063/5.0306177}, year = {2026}, abstract = {The Kelvin-Helmholtz instability arises at the interface between two fluid layers with a tangential velocity discontinuity, significantly impacting the safety of systems in industrial applications. Despite extensive studies, many theoretical analyses neglect viscosity and frictional drag due to the complexity of solving the dispersion equation. However, including these effects is crucial, as viscosity alters the growth rate of the instability, while frictional drag influences energy dissipation and momentum transfer. In this study, these effects are incorporated into both finite and infinite flows. The assumption of a potential flow combined with a dissipation method is employed to derive the dispersion equation, providing a more tractable approach than direct calculation methods. The results indicate that, in the case of infinite flows, the frictional drag suppresses the growth of the instability for long waves (small wavenumber k) but enhances it for short waves (large k). In contrast, the surface tension dominates, while the frictional drag only slightly affects the growth rate in the case of finite flows bounded by solid walls.}, language = {en} } @inproceedings{RiedmuellerZittelKoch2026, author = {Riedm{\"u}ller, Stephanie and Zittel, Janina and Koch, Thorsten}, title = {Warm-starting Strategies in Scalarization Methods for Multi-Objective Optimization}, booktitle = {Operations Research Proceedings 2025}, arxiv = {http://arxiv.org/abs/2507.21933}, year = {2026}, abstract = {We explore how warm-starting strategies can be integrated into scalarization-based approaches for multi-objective optimization in (mixed) integer linear programming. Scalarization methods remain widely used classical techniques to compute Pareto-optimal solutions in applied settings. They are favored due to their algorithmic simplicity and broad applicability across continuous and integer programs with an arbitrary number of objectives. While warm-starting has been applied in this context before, a systematic methodology and analysis remain lacking. We address this gap by providing a theoretical characterization of warm-starting within scalarization methods, focusing on the sequencing of subproblems. However, optimizing the order of subproblems to maximize warm-start efficiency may conflict with alternative criteria, such as early identification of infeasible regions. We quantify these trade-offs through an extensive computational study.}, language = {en} }