TY - JOUR A1 - Hoppmann-Baum, Kai T1 - On the Complexity of Computing Maximum and Minimum Min‐Cost‐Flows JF - Networks N2 - 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. Y1 - 2021 U6 - https://doi.org/10.1002/net.22060 ER - TY - JOUR A1 - Hennings, Felix A1 - Anderson, Lovis A1 - Hoppmann-Baum, Kai A1 - Turner, Mark A1 - Koch, Thorsten T1 - Controlling transient gas flow in real-world pipeline intersection areas JF - Optimization and Engineering N2 - 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. Y1 - 2021 U6 - https://doi.org/https://doi.org/10.1007/s11081-020-09559-y VL - 22 SP - 687 EP - 734 PB - Springer Nature ET - 2 ER - TY - CHAP A1 - Beulertz, Daniel A1 - Charousset-Brignol, Sandrine A1 - Most, Dieter A1 - Giannelos, Spyros A1 - Yueksel-Erguen, Inci T1 - Development of a Modular Framework for Future Energy System Analysis T2 - 54th International Universities Power Engineering Conference (UPEC) N2 - 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. Y1 - 2019 U6 - https://doi.org/10.1109/UPEC.2019.8893472 ER - TY - THES A1 - Rössig, Ansgar T1 - Verification of Neural Networks KW - Neural Network Verification Y1 - 2019 ER - TY - GEN A1 - Gotzes, Uwe A1 - Hoppmann, Kai T1 - Bounds for the final ranks during a round robin tournament T2 - Operational Research - An International Journal (ORIJ) N2 - 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. T3 - ZIB-Report - 19-50 Y1 - 2019 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-74638 ER - TY - GEN A1 - Hoppmann, Kai A1 - Hennings, Felix A1 - Lenz, Ralf A1 - Gotzes, Uwe A1 - Heinecke, Nina A1 - Spreckelsen, Klaus A1 - Koch, Thorsten T1 - Optimal Operation of Transient Gas Transport Networks T3 - ZIB-Report - 19-23 Y1 - 2019 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-73639 SN - 1438-0064 ER - TY - GEN A1 - Hennings, Felix A1 - Anderson, Lovis A1 - Hoppmann, Kai A1 - Turner, Mark A1 - Koch, Thorsten T1 - Controlling transient gas flow in real-world pipeline intersection areas N2 - 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. T3 - ZIB-Report - 19-24 Y1 - 2019 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-73645 SN - 1438-0064 ER - TY - GEN A1 - Gamrath, Inken A1 - Petkovic, Milena T1 - Prediction of Intermitted Flows in Large Gas Networks T3 - ZIB-Report - 19-29 Y1 - 2019 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-73717 SN - 1438-0064 ER - TY - THES A1 - Weltsch, André T1 - Fast Approximation of Equations of transient Gasflow Y1 - 2018 ER - TY - JOUR A1 - Streubel, Tom A1 - Tischendorf, Caren A1 - Griewank, Andreas T1 - Piecewise Polynomial Taylor Expansions - The Generalization of Faà di Bruno's Formula JF - Modeling, Simulation and Optimization of Complex Processes HPSC 2018 N2 - 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. Y1 - 2020 U6 - https://doi.org/10.1007/978-3-030-55240-4_3 IS - Modeling, Simulation and Optimization of Complex Processes HPSC 2018 SP - 63 EP - 82 PB - Springer International Publishing ER - TY - JOUR A1 - Griewank, Andreas A1 - Streubel, Tom A1 - Tischendorf, Caren T1 - On the abs-polynomial expansion of piecewise smooth functions JF - Optimization Methods and Software N2 - 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. Y1 - 2020 U6 - https://doi.org/10.1080/10556788.2020.1817448 PB - Taylor & Francis ER - TY - GEN A1 - Griewank, Andreas A1 - Streubel, Tom A1 - Tischendorf, Caren T1 - On the abs-polynomial expansion of piecewise smooth functions N2 - 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. T3 - ZIB-Report - 20-14 KW - Nonsmooth Taylor polynomial/series KW - forward mode propagation KW - abs-normal form KW - abs-linear form KW - absolute convergence KW - Moore recurrences KW - quadratic complexity Y1 - 2020 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-78448 SN - 1438-0064 ER - TY - CHAP A1 - Benner, Peter A1 - Grundel, Sara A1 - Himpe, Christian A1 - Huck, Christoph A1 - Streubel, Tom A1 - Tischendorf, Caren T1 - Gas Network Benchmark Models T2 - Applications of Differential-Algebraic Equations: Examples and Benchmarks N2 - 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. Y1 - 2019 SN - 978-3-030-03718-5 U6 - https://doi.org/10.1007/11221_2018_5 SP - 171 EP - 197 PB - Springer International Publishing ER - TY - GEN A1 - Hasenfelder, Richard A1 - Lehmann, Lutz A1 - Radons, Manuel A1 - Streubel, Tom A1 - Strohm, Christian A1 - Griewank, Andreas T1 - Computational aspects of the Generalized Trapezoidal Rule N2 - 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. T3 - ZIB-Report - 18-23 KW - Algorithmic Differentiation KW - Automatic Differentiation KW - Lipschitz Continuity KW - Piecewise Linearization KW - Nonsmooth KW - Trapezoidal Rule KW - Implementation KW - Computational Cost Y1 - 2018 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-68615 SN - 1438-0064 ER - TY - GEN A1 - Streubel, Tom A1 - Tischendorf, Caren A1 - Griewank, Andreas T1 - Piecewise Polynomial Taylor Expansions – The Generalization of Faà di Bruno’s Formula N2 - 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. T3 - ZIB-Report - 18-24 KW - generalized Taylor expansion KW - implicit generation of splines KW - nonsmooth integration of differential algebraic equations (DAE and ODE) KW - multistep methods KW - generalized hermite interpolation KW - algorithmic piecewise differentiation (AD and APD) KW - evaluation procedures KW - treating absolute values (abs, max and min) Y1 - 2018 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-68859 SN - 1438-0064 ER - TY - GEN A1 - Radons, Manuel A1 - Lehmann, Lutz A1 - Streubel, Tom A1 - Griewank, Andreas T1 - An Open Newton Method for Piecewise Smooth Systems N2 - 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. T3 - ZIB-Report - 18-43 Y1 - 2018 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-70418 SN - 1438-0064 ER - TY - GEN A1 - Schweiger, Jonas T1 - Exploiting structure in non-convex quadratic optimization N2 - 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. T3 - ZIB-Report - 18-35 KW - Nonconvexity KW - Quadratic Programming KW - Relaxations KW - Cutting Planes KW - Standard Quadratic Programming KW - Pooling Problem Y1 - 2018 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-69476 SN - 1438-0064 ER - TY - GEN A1 - Luedtke, James A1 - D'Ambrosio, Claudia A1 - Linderoth, Jeff A1 - Schweiger, Jonas T1 - Strong Convex Nonlinear Relaxations of the Pooling Problem N2 - We investigate new convex relaxations for the pooling problem, a classic nonconvex production planning problem in which input materials are mixed in intermediate pools, with the outputs of these pools further mixed to make output products meeting given attribute percentage requirements. Our relaxations are derived by considering a set which arises from the formulation by considering a single product, a single attibute, and a single pool. The convex hull of the resulting nonconvex set is not polyhedral. We derive valid linear and convex nonlinear inequalities for the convex hull, and demonstrate that different subsets of these inequalities define the convex hull of the nonconvex set in three cases determined by the parameters of the set. Computational results on literature instances and newly created larger test instances demonstrate that the inequalities can significantly strengthen the convex relaxation of the pq-formulation of the pooling problem, which is the relaxation known to have the strongest bound. T3 - ZIB-Report - 18-12 KW - Pooling Problem KW - Relaxation KW - Valid Inequalities Y1 - 2018 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-67824 SN - 1438-0064 ER - TY - GEN A1 - Luedtke, James A1 - D'Ambrosio, Claudia A1 - Linderoth, Jeff A1 - Schweiger, Jonas T1 - Strong Convex Nonlinear Relaxations of the Pooling Problem: Extreme Points N2 - We investigate new convex relaxations for the pooling problem, a classic nonconvex production planning problem in which products are mixed in intermediate pools in order to meet quality targets at their destinations. In this technical report, we characterize the extreme points of the convex hull of our non-convex set, and show that they are not finite, i.e., the convex hull is not polyhedral. This analysis was used to derive valid nonlinear convex inequalities and show that, for a specific case, they characterize the convex hull of our set. The new valid inequalities and computational results are presented in ZIB Report 18-12. T3 - ZIB-Report - 18-13 KW - Pooling Problem KW - Relaxation KW - Extreme Points Y1 - 2018 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-67801 SN - 1438-0064 ER - TY - JOUR A1 - Gotzes, Uwe A1 - Gotzes, Claudia T1 - The Jeep Problem: A Flexible MIP Formulation JF - Journal of Nepal Mathematical Society N2 - This article deals with the Jeep Problem (also known as Desert Crossing Problem), which reads as follows: An unlimited supply of fuel is available at one edge of a desert, but there is no source on the desert itself. A vehicle can carry enough fuel to go a certain distance, and it can built up its own refuelling stations. What is the minimum amount of fuel the vehicle will require in order to cross the desert? Under these mild conditions this question is answered since the 1940s. But what is the answer if the caches are restricted to certain areas or if the fuel consumption does not depend linearly on the distance travelled? To answer these and similar questions we develop and solve a flexible mixed-integer programming (MIP) model for the classical problem and enhance it with new further aspects of practical relevance. Y1 - 2018 SN - 2616-0161 VL - 1 SP - 11 EP - 17 ER -