@article{HoppmannBaum2021, author = {Hoppmann-Baum, Kai}, title = {On the Complexity of Computing Maximum and Minimum Min-Cost-Flows}, journal = {Networks}, doi = {10.1002/net.22060}, year = {2021}, abstract = {Consider a flow network, i.e., a directed graph where each arc has a nonnegative capacity value and an associated length, together with nonempty supply intervals for the sources and nonempty demand intervals for the sinks. The Maximum Min-Cost-Flow Problem (MaxMCF) is to find fixed supply and demand values within these intervals such that the optimal objective value of the induced Min-Cost-Flow Problem (MCF) is maximized. In this paper, we show that MaxMCF as well as its uncapacitated variant, the Maximum Transportation Problem (MaxTP), are NP-hard. Further, we prove that MaxMCF is APX-hard if a connectedness-condition regarding the sources and the sinks of the flow network is dropped. Finally, we show how the Minimum Min-Cost-Flow Problem (MinMCF) can be solved in polynomial time.}, language = {en} } @article{HenningsAndersonHoppmannBaumetal.2021, author = {Hennings, Felix and Anderson, Lovis and Hoppmann-Baum, Kai and Turner, Mark and Koch, Thorsten}, title = {Controlling transient gas flow in real-world pipeline intersection areas}, volume = {22}, journal = {Optimization and Engineering}, edition = {2}, publisher = {Springer Nature}, doi = {https://doi.org/10.1007/s11081-020-09559-y}, pages = {687 -- 734}, year = {2021}, abstract = {Compressor stations are the heart of every high-pressure gas transport network. Located at intersection areas of the network they are contained in huge complex plants, where they are in combination with valves and regulators responsible for routing and pushing the gas through the network. Due to their complexity and lack of data compressor stations are usually dealt with in the scientific literature in a highly simplified and idealized manner. As part of an ongoing project with one of Germany's largest Transmission System Operators to develop a decision support system for their dispatching center, we investigated how to automatize control of compressor stations. Each station has to be in a particular configuration, leading in combination with the other nearby elements to a discrete set of up to 2000 possible feasible operation modes in the intersection area. Since the desired performance of the station changes over time, the configuration of the station has to adapt. Our goal is to minimize the necessary changes in the overall operation modes and related elements over time, while fulfilling a preset performance envelope or demand scenario. This article describes the chosen model and the implemented mixed integer programming based algorithms to tackle this challenge. By presenting extensive computational results on real world data we demonstrate the performance of our approach.}, language = {en} } @inproceedings{BeulertzCharoussetBrignolMostetal.2019, author = {Beulertz, Daniel and Charousset-Brignol, Sandrine and Most, Dieter and Giannelos, Spyros and Yueksel-Erguen, Inci}, title = {Development of a Modular Framework for Future Energy System Analysis}, booktitle = {54th International Universities Power Engineering Conference (UPEC)}, doi = {10.1109/UPEC.2019.8893472}, year = {2019}, abstract = {This paper gives an overview of the modeling framework that is being developed within the Horizon2020 project plan4res. In the context of energy transition, integration of high shares of renewable energies will play a vital role for achieving the proposed climate targets. This brings new challenges to modeling tools, including data construction, implementation and solution techniques. In order to address these challenges, plan4res aims to create a well-structured and highly modular framework that will provide insights into the needs of future energy systems. An overview of the central modeling aspects is given in this paper. Finally, three case studies are presented that show the adequacy and relevance of the proposed optimization framework.}, language = {en} } @misc{Roessig2019, type = {Master Thesis}, author = {R{\"o}ssig, Ansgar}, title = {Verification of Neural Networks}, pages = {143}, year = {2019}, language = {en} } @misc{GotzesHoppmann2019, author = {Gotzes, Uwe and Hoppmann, Kai}, title = {Bounds for the final ranks during a round robin tournament}, journal = {Operational Research - An International Journal (ORIJ)}, doi = {https://doi.org/10.1007/s12351-020-00546-w}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-74638}, year = {2019}, abstract = {This article answers two kinds of questions regarding the Bundesliga which is Germany's primary football (soccer) competition having the highest average stadium attendance worldwide. First "At any point of the season, what final rank will a certain team definitely reach?" and second "At any point of the season, what final rank can a certain team at most reach?". Although we focus especially on the Bundesliga, the models that we use to answer the two questions can easily be adopted to league systems that are similar to that of the Bundesliga.}, language = {en} } @misc{HoppmannHenningsLenzetal.2019, author = {Hoppmann, 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}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-73639}, year = {2019}, language = {en} } @misc{HenningsAndersonHoppmannetal.2019, author = {Hennings, Felix and Anderson, Lovis and Hoppmann, Kai and Turner, Mark and Koch, Thorsten}, title = {Controlling transient gas flow in real-world pipeline intersection areas}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-73645}, year = {2019}, abstract = {Compressor stations are the heart of every high-pressure gas transport network. Located at intersection areas of the network they are contained in huge complex plants, where they are in combination with valves and regulators responsible for routing and pushing the gas through the network. Due to their complexity and lack of data compressor stations are usually dealt with in the scientific literature in a highly simplified and idealized manner. As part of an ongoing project with one of Germany's largest Transmission System Operators to develop a decision support system for their dispatching center, we investigated how to automatize control of compressor stations. Each station has to be in a particular configuration, leading in combination with the other nearby elements to a discrete set of up to 2000 possible feasible operation modes in the intersection area. Since the desired performance of the station changes over time, the configuration of the station has to adapt. Our goal is to minimize the necessary changes in the overall operation modes and related elements over time, while fulfilling a preset performance envelope or demand scenario. This article describes the chosen model and the implemented mixed integer programming based algorithms to tackle this challenge. By presenting extensive computational results on real world data we demonstrate the performance of our approach.}, language = {en} } @misc{GamrathPetkovic2019, author = {Gamrath, Inken and Petkovic, Milena}, title = {Prediction of Intermitted Flows in Large Gas Networks}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-73717}, year = {2019}, language = {en} } @misc{Weltsch2018, type = {Master Thesis}, author = {Weltsch, Andr{\´e}}, title = {Fast Approximation of Equations of transient Gasflow}, year = {2018}, 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{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} } @misc{GriewankStreubelTischendorf2020, author = {Griewank, Andreas and Streubel, Tom and Tischendorf, Caren}, title = {On the abs-polynomial expansion of piecewise smooth functions}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-78448}, 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{BennerGrundelHimpeetal.2019, author = {Benner, Peter and Grundel, Sara and Himpe, Christian and Huck, Christoph and Streubel, Tom and Tischendorf, Caren}, title = {Gas Network Benchmark Models}, booktitle = {Applications of Differential-Algebraic Equations: Examples and Benchmarks}, publisher = {Springer International Publishing}, isbn = {978-3-030-03718-5}, doi = {10.1007/11221_2018_5}, pages = {171 -- 197}, year = {2019}, abstract = {The simulation of gas transportation networks becomes increasingly more important as its use-cases broaden to more complex applications. Classically, the purpose of the gas network was the transportation of predominantly natural gas from a supplier to the consumer for long-term scheduled volumes. With the rise of renewable energy sources, gas-fired power plants are often chosen to compensate for the fluctuating nature of the renewables, due to their on-demand power generation capability. Such an only short-term plannable supply and demand setting requires sophisticated simulations of the gas network prior to the dispatch to ensure the supply of all customers for a range of possible scenarios and to prevent damages to the gas network. In this work we describe the modeling of gas networks and present benchmark systems to test implementations and compare new or extended models.}, language = {en} } @misc{HasenfelderLehmannRadonsetal.2018, author = {Hasenfelder, Richard and Lehmann, Lutz and Radons, Manuel and Streubel, Tom and Strohm, Christian and Griewank, Andreas}, title = {Computational aspects of the Generalized Trapezoidal Rule}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-68615}, year = {2018}, abstract = {In this article we analyze a generalized trapezoidal rule for initial value problems with piecewise smooth right hand side F:IR^n -> IR^n. When applied to such a problem, the classical trapezoidal rule suffers from a loss of accuracy if the solution trajectory intersects a non-differentiability of F. In such a situation the investigated generalized trapezoidal rule achieves a higher convergence order than the classical method. While the asymptotic behavior of the generalized method was investigated in a previous work, in the present article we develop the algorithmic structure for efficient implementation strategies and estimate the actual computational cost of the latter. Moreover, energy preservation of the generalized trapezoidal rule is proved for Hamiltonian systems with piecewise linear right hand side.}, language = {en} } @misc{StreubelTischendorfGriewank2018, author = {Streubel, Tom and Tischendorf, Caren and Griewank, Andreas}, title = {Piecewise Polynomial Taylor Expansions - The Generalization of Fa{\`a} di Bruno's Formula}, issn = {1438-0064}, doi = {10.1007/978-3-030-55240-4_3}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-68859}, year = {2018}, abstract = {We present an extension of Taylor's theorem towards nonsmooth evalua- tion procedures incorporating absolute value operaions. Evaluations procedures are computer programs of mathematical functions in closed form expression and al- low a different treatment of smooth operations and calls to the absolute value value function. The well known classical Theorem of Taylor defines polynomial approx- imation 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 the continuous nonlinear op- timization of finite dimensional objective functions and for root solving of nonlinear systems of equations. The herein provided proof is construtive and allow efficiently designed algorithms for the execution and computation of generalized piecewise polynomial expansions. As a demonstration we will derive a k-step method on the basis of polynomial interpolation and the proposed generalized expansions.}, language = {en} } @misc{RadonsLehmannStreubeletal.2018, author = {Radons, Manuel and Lehmann, Lutz and Streubel, Tom and Griewank, Andreas}, title = {An Open Newton Method for Piecewise Smooth Systems}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-70418}, year = {2018}, abstract = {Recent research has shown that piecewise smooth (PS) functions can be approximated by piecewise linear functions with second order error in the distance to a given reference point. A semismooth Newton type algorithm based on successive application of these piecewise linearizations was subsequently developed for the solution of PS equation systems. For local bijectivity of the linearization at a root, a radius of quadratic convergence was explicitly calculated in terms of local Lipschitz constants of the underlying PS function. In the present work we relax the criterium of local bijectivity of the linearization to local openness. For this purpose a weak implicit function theorem is proved via local mapping degree theory. It is shown that there exist PS functions f:IR^2 --> IR^2 satisfying the weaker criterium where every neighborhood of the root of f contains a point x such that all elements of the Clarke Jacobian at x are singular. In such neighborhoods the steps of classical semismooth Newton are not defined, which establishes the new method as an independent algorithm. To further clarify the relation between a PS function and its piecewise linearization, several statements about structure correspondences between the two are proved. Moreover, the influence of the specific representation of the local piecewise linear models on the robustness of our method is studied. An example application from cardiovascular mathematics is given.}, language = {en} } @misc{Schweiger2018, author = {Schweiger, Jonas}, title = {Exploiting structure in non-convex quadratic optimization}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-69476}, year = {2018}, abstract = {The amazing success of computational mathematical optimization over the last decades has been driven more by insights into mathematical structures than by the advance of computing technology. In this vein, we address applications, where nonconvexity in the model poses principal difficulties. This paper summarizes the dissertation of Jonas Schweiger for the occasion of the GOR dissertation award 2018. We focus on the work on non-convex quadratic programs and show how problem specific structure can be used to obtain tight relaxations and speed up Branch\&Bound methods. Both a classic general QP and the Pooling Problem as an important practical application serve as showcases.}, language = {en} }