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 - Becker, Kai-Helge A1 - Hiller, Benjamin T1 - ASTS Orientations on Undirected Graphs: Structural analysis and enumeration N2 - All feasible flows in potential-driven networks induce an orientation on the undirected graph underlying the network. Clearly, these orientations must satisfy two conditions: they are acyclic and there are no "dead ends" in the network, i.e. each source requires outgoing flows, each sink requires incoming flows, and each transhipment vertex requires both an incoming and an outgoing flow. In this paper we will call orientations that satisfy these conditions acyclic source-transhipment-sink orientations (ASTS-orientation) and study their structure. In particular, we characterize graphs that allow for such an orientation, describe a way to enumerate all possible ASTS-orientations of a given graph, present an algorithm to simplify and decompose a graph before such an enumeration and shed light on the role of zero flows in the context of ASTS-orientations. T3 - ZIB-Report - 18-31 Y1 - 2018 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-69632 SN - 1438-0064 ER - TY - GEN A1 - Hiller, Benjamin A1 - Becker, Kai-Helge T1 - Improving relaxations for potential-driven network flow problems via acyclic flow orientations N2 - The class of potential-driven network flow problems provides important models for a range of infrastructure networks. For real-world applications, they need to be combined with integer models for switching certain network elements, giving rise to hard-to-solve MINLPs. We observe that on large-scale real-world meshed networks the usually employed relaxations are rather weak due to cycles in the network. We propose acyclic flow orientations as a combinatorial relaxation of feasible solutions of potential-driven flow problems and show how they can be used to strengthen existing relaxations. First computational results indicate that the strengthend model is much tighter than the original relaxation, thus promising a computational advantage. T3 - ZIB-Report - 18-30 KW - potential-driven network flows KW - acyclic orientations KW - flow orientations KW - MINLPs Y1 - 2018 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-69622 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 - Anderson, Lovis A1 - Hiller, Benjamin T1 - A Sweep-Plane Algorithm for the Computation of the Volume of a Union of Polytopes N2 - Optimization models often feature disjunctions of polytopes as submodels. Such a disjunctive set is initially (at best) relaxed to its convex hull, which is then refined by branching. To measure the error of the convex relaxation, the (relative) difference between the volume of the convex hull and the volume of the disjunctive set may be used. This requires a method to compute the volume of the disjunctive set. Naively, this can be done via inclusion/exclusion and leveraging the existing code for the volume of polytopes. However, this is often inefficient. We propose a revised variant of an old algorithm by Bieri and Nef (1983) for this purpose. The algorithm uses a sweep-plane to incrementally calculate the volume of the disjunctive set as a function of the offset parameter of the sweep-plane. T3 - ZIB-Report - 18-37 KW - Disjunctive Programming KW - Volume Algorithm KW - Union of Polytopes Y1 - 2018 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-69489 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 - Hiller, Benjamin A1 - Saitenmacher, René A1 - Walther, Tom T1 - Analysis of operating modes of complex compressor stations N2 - We consider the modeling of operation modes for complex compressor stations (i.e., ones with several in- or outlets) in gas networks. In particular, we propose a refined model that allows to precompute tighter relaxations for each operation mode. These relaxations may be used to strengthen the compressor station submodels in gas network optimization problems. We provide a procedure to obtain the refined model from the input data for the original model. This procedure is based on a nontrivial reduction of the graph representing the gas flow through the compressor station in an operation mode. T3 - ZIB-Report - 17-65 KW - bound tightening KW - flow patterns KW - model reformulation KW - multi-way compressor station Y1 - 2018 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-68179 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 - GEN A1 - Lenz, Ralf A1 - Serrano, Felipe T1 - Tight Convex Relaxations for the Expansion Planning Problem N2 - 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 improve 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%. T3 - ZIB-Report - 21-05 KW - Convex envelopes KW - Mixed-Integer Nonlinear Programming KW - Expansion planning of energy networks Y1 - 2021 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-81459 SN - 1438-0064 ER - TY - GEN A1 - Fügenschuh, Armin A1 - Hiller, Benjamin A1 - Humpola, Jesco A1 - Koch, Thorsten A1 - Lehmann, Thomas A1 - Schwarz, Robert A1 - Schweiger, Jonas A1 - Szabó, Jácint T1 - Gas Network Topology Optimization for Upcoming Market Requirements N2 - Gas distribution networks are complex structures that consist of passive pipes, and active, controllable elements such as valves and compressors. Controlling such network means to find a suitable setting for all active components such that a nominated amount of gas can be transmitted from entries to exits through the network, without violating physical or operational constraints. The control of a large-scale gas network is a challenging task from a practical point of view. In most companies the actual controlling process is supported by means of computer software that is able to simulate the flow of the gas. However, the active settings have to be set manually within such simulation software. The solution quality thus depends on the experience of a human planner. When the gas network is insufficient for the transport then topology extensions come into play. Here a set of new pipes or active elements is determined such that the extended network admits a feasible control again. The question again is how to select these extensions and where to place them such that the total extension costs are minimal. Industrial practice is again to use the same simulation software, determine extensions by experience, add them to the virtual network, and then try to find a feasible control of the active elements. The validity of this approach now depends even more on the human planner. Another weakness of this manual simulation-based approach is that it cannot establish infeasibility of a certain gas nomination, unless all settings of the active elements are tried. Moreover, it is impossible to find a cost-optimal network extension in this way. In order to overcome these shortcomings of the manual planning approach we present a new approach, rigorously based on mathematical optimization. Hereto we describe a model for finding feasible controls and then extend this model such that topology extensions can additionally and simultaneously be covered. Numerical results for real-world instances are presented and discussed. T3 - ZIB-Report - 11-09 KW - Mathematical Optimization KW - Gas Distribution Networks KW - Topology Planning Y1 - 2011 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-12348 ER - TY - GEN A1 - Humpola, Jesco A1 - Fügenschuh, Armin A1 - Lehmann, Thomas T1 - A Primal Heuristic for MINLP based on Dual Information N2 - We present a novel heuristic algorithm to identify feasible solutions of a mixed-integer nonlinear programming problem arising in natural gas transportation: the selection of new pipelines to enhance the network's capacity to a desired level in a cost-efficient way. We solve this problem in a linear programming based branch-and-cut approach, where we deal with the nonlinearities by linear outer approximation and spatial branching. At certain nodes of the branching tree, we compute a KKT point for a nonlinear relaxation. Based on the information from the KKT point we alter some of the integer variables in a locally promising way. We describe this heuristic for general MINLPs and then show how to tailor the heuristic to exploit our problem-specific structure. On a test set of real-world instances, we are able to increase the chance of identifying feasible solutions by some order of magnitude compared to standard MINLP heuristics that are already built in the general-purpose MINLP solver SCIP. T3 - ZIB-Report - 13-49 KW - Mixed-Integer Nonlinear Programming KW - Relaxations KW - Heuristics KW - Duality KW - Nonlinear Network Design Applications Y1 - 2013 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-43110 SN - 1438-0064 ER - TY - GEN A1 - Hiller, Benjamin A1 - Saitenmacher, René A1 - Walther, Tom T1 - Analysis of operating modes of complex compressor stations N2 - We consider the modeling of operation modes for complex compressor stations (i.e., ones with several in- or outlets) in gas networks. In particular, we propose a refined model that allows to precompute tighter relaxations for each operation mode. These relaxations may be used to strengthen the compressor station submodels in gas network optimization problems. We provide a procedure to obtain the refined model from the input data for the original model. T3 - ZIB-Report - 16-61 Y1 - 2016 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-61092 SN - 1438-0064 ER - TY - GEN A1 - Hiller, Benjamin A1 - Walther, Tom T1 - Improving branching for disjunctive polyhedral models using approximate convex decompositions N2 - Disjunctive sets arise in a variety of optimization models and much esearch has been devoted to obtain strong relaxations for them. This paper focuses on the evaluation of the relaxation during the branch-and-bound search process. We argue that the branching possibilities (\ie binary variables) of the usual formulations are unsuitable to obtain strong bounds early in the search process as they do not capture the overall shape of the the entire disjunctive set. To analyze and exploit the shape of the disjunctive set we propose to compute a hierarchy of approximate convex decompositions and show how to extend the known formulations to obtain improved branching behavior. T3 - ZIB-Report - 17-68 KW - approximate convex decomposition KW - branch-and-bound KW - convex hull reformulation KW - disjunctive set Y1 - 2018 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-67462 SN - 1438-0064 ER - TY - GEN A1 - Lenz, Ralf A1 - Schwarz, Robert T1 - Optimal Looping of Pipelines in Gas Networks N2 - In this paper, we compare several approaches for the problem of gas network expansions using loops, that is, to build new pipelines in parallel to existing ones. We present different model formulations for the problem of continuous loop expansions as well as discrete loop expansions. We then analyze problem properties, such as the structure and convexity of the underlying feasible regions. The paper concludes with a computational study comparing the continuous and the discrete formulations. T3 - ZIB-Report - 16-67 KW - Mixed Integer Nonlinear Programming KW - Gas Network Applications KW - Expansion Planning Y1 - 2016 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-61564 SN - 1438-0064 ER - TY - GEN A1 - Hennig, Kai A1 - Schwarz, Robert T1 - Using Bilevel Optimization to find Severe Transport Situations in Gas Transmission Networks N2 - In the context of gas transmission in decoupled entry-exit systems, many approaches to determine the network capacity are based on the evaluation of realistic and severe transport situations. In this paper, we review the Reference Point Method, which is an algorithm used in practice to generate a set of scenarios using the so-called transport moment as a measure for severity. We introduce a new algorithm for finding severe transport situations that considers an actual routing of the flow through the network and is designed to handle issues arising from cyclic structures in a more dynamical manner. Further, in order to better approximate the physics of gas, an alternative, potential based flow formulation is proposed. The report concludes with a case study based on data from the benchmark library GasLib. T3 - ZIB-Report - 16-68 KW - bilevel optimization KW - gas networks KW - network flow Y1 - 2016 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-61519 SN - 1438-0064 ER - TY - GEN A1 - Szabó, Jácint T1 - The set of solutions to nomination validation in passive gas transportation networks with a generalized flow formula N2 - In this paper we give an analytical description on the structure of solutions to the gas nomination validation problem in gas transportation networks. These networks are assumed to contain no active devices, only certain hypothetical pipelines, where the flow of gas is modeled by a generalized version of the quadratic Weymouth's equation. The purpose of considering generalized flow formulas is to be able to adapt our results to various gas network optimization problems involving gas flow formulas beyond Weymouth's equation. Such formulas can appear in leaves of branch and bound trees, or they can stem from discretization and linearization carried out at active devices. We call a balanced supply-demand vector a nomination, and the passive nomination validation problem is to decide whether there exist pressures at the nodes generating a given nomination. We prove that in our setup the pressure square vectors generating a given nomination form a one-dimensional connected and continuous curve in the pressure square space, and this curve is a line for the classical Weymouth's equation. We also present a visual approach for the easy comprehension of how this solution curve arises; we give a short investigation of the set of feasible nominations; and finally we give a proof that the nomination validation problem in gas networks with active devices is NP-complete. T3 - ZIB-Report - 11-44 KW - pressure drop equation KW - gas networks KW - generalized flow formula Y1 - 2012 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-15151 SN - 1438-0064 ER - TY - GEN A1 - Martin, Alexander A1 - Geißler, Björn A1 - Hayn, Christine A1 - Hiller, Benjamin A1 - Humpola, Jesco A1 - Koch, Thorsten A1 - Lehmann, Thomas A1 - Morsi, Antonio A1 - Pfetsch, Marc A1 - Schewe, Lars A1 - Schmidt, Martin A1 - Schultz, Rüdiger A1 - Schwarz, Robert A1 - Schweiger, Jonas A1 - Steinbach, Marc A1 - Willert, Bernhard T1 - Optimierung Technischer Kapazitäten in Gasnetzen N2 - Die mittel- und längerfristige Planung für den Gastransport hat sich durch Änderungen in den regulatorischen Rahmenbedingungen stark verkompliziert. Kernpunkt ist die Trennung von Gashandel und -transport. Dieser Artikel diskutiert die hieraus resultierenden mathematischen Planungsprobleme, welche als Validierung von Nominierungen und Buchungen, Bestimmung der technischen Kapazität und Topologieplanung bezeichnet werden. Diese mathematischen Optimierungsprobleme werden vorgestellt und Lösungsansätze skizziert. T3 - ZIB-Report - 11-56 KW - Gasnetzplanung KW - Technische Kapazitäten KW - Nominierungsvalidierung KW - Buchungsvalidierung KW - Topologieplanung Y1 - 2012 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-15121 SN - 1438-0064 ER - TY - GEN A1 - Hiller, Benjamin A1 - Koch, Thorsten A1 - Schewe, Lars A1 - Schwarz, Robert A1 - Schweiger, Jonas T1 - A System to Evaluate Gas Network Capacities: Concepts and Implementation N2 - In 2005 the European Union liberalized the gas market with a disruptive change and decoupled trading of natural gas from its transport. The gas is now transported by independent so-called transmissions system operators or TSOs. The market model established by the European Union views the gas transmission network as a black box, providing shippers (gas traders and consumers) the opportunity to transport gas from any entry to any exit. TSOs are required to offer the maximum possible capacities at each entry and exit such that any resulting gas flow can be realized by the network. The revenue from selling these capacities more than one billion Euro in Germany alone, but overestimating the capacity might compromise the security of supply. Therefore, evaluating the available transport capacities is extremely important to the TSOs. This is a report on a large project in mathematical optimization, set out to develop a new toolset for evaluating gas network capacities. The goals and the challenges as they occurred in the project are described, as well as the developments and design decisions taken to meet the requirements. T3 - ZIB-Report - 18-11 Y1 - 2018 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-67438 SN - 1438-0064 N1 - An earlier version of this report is available as ZR 17-03 at https://opus4.kobv.de/opus4-zib/frontdoor/index/index/docId/6193. ER - TY - GEN A1 - Benner, Peter A1 - Grundel, Sara A1 - Himpe, Christian A1 - Huck, Christoph A1 - Streubel, Tom A1 - Tischendorf, Caren T1 - Gas Network Benchmark Models N2 - The simulation of gas transportation networks becomes increasingly more important as its use-cases broadens 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 modelling of gas networks and present benchmark systems to test implementations and compare new or extended models. T3 - ZIB-Report - 17-73 Y1 - 2017 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-66274 SN - 1438-0064 ER - TY - GEN A1 - Griewank, Andreas A1 - Hasenfelder, Richard A1 - Radons, Manuel A1 - Lehmann, Lutz A1 - Streubel, Tom T1 - Integrating Lipschitzian Dynamical Systems using Piecewise Algorithmic Differentiation N2 - In this article we analyze a generalized trapezoidal rule for initial value problems with piecewise smooth right hand side \(F:R^n \to R^n\) based on a generalization of algorithmic differentiation. When applied to such a problem, the classical trapezoidal rule suffers from a loss of accuracy if the solution trajectory intersects a nondifferentiability of \(F\). The advantage of the proposed generalized trapezoidal rule is threefold: Firstly, we can achieve a higher convergence order than with the classical method. Moreover, the method is energy preserving for piecewise linear Hamiltonian systems. Finally, in analogy to the classical case we derive a third order interpolation polynomial for the numerical trajectory. In the smooth case the generalized rule reduces to the classical one. Hence, it is a proper extension of the classical theory. An error estimator is given and numerical results are presented. T3 - ZIB-Report - 17-44 KW - Automatic Differentiation KW - Lipschitz Continuity KW - Piecewise Linearization KW - Nonsmooth KW - Trapezoidal Rule KW - Energy Preservation KW - Dense Output Y1 - 2017 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-64639 SN - 1438-0064 ER -