@article{DomschkeGrossHanteetal.2015, author = {Domschke, Pia and Groß, Martin and Hante, Falk M. and Hiller, Benjamin and Schewe, Lars and Schmidt, Martin}, title = {Mathematische Modellierung, Simulation und Optimierung von Gastransportnetzwerken}, volume = {156}, journal = {gwf - Gas+Energie}, number = {11}, pages = {880 -- 885}, year = {2015}, language = {de} } @incollection{KochPfetschRoevekamp2015, author = {Koch, Thorsten and Pfetsch, Marc and R{\"o}vekamp, Jessica}, title = {Introduction}, booktitle = {Evaluating Gas Network Capacities}, publisher = {Society for Industrial and Applied Mathematics}, isbn = {9781611973686}, pages = {3 -- 16}, year = {2015}, language = {en} } @inproceedings{MartinGeisslerHeynetal.2011, author = {Martin, Alexander and Geißler, Bj{\"o}rn and Heyn, Christine and Hiller, Benjamin and Humpola, Jesco and Koch, Thorsten and Lehmann, Thomas and Morsi, Antonio and Pfetsch, Marc and Schewe, Lars and Schmidt, Martin and Schultz, R{\"u}diger and Schwarz, Robert and Schweiger, Jonas and Steinbach, Marc and Willert, Bernhard}, title = {Optimierung Technischer Kapazit{\"a}ten in Gasnetzen}, booktitle = {Optimierung in der Energiewirtschaft}, publisher = {VDI-Verlag, D{\"u}sseldorf}, pages = {105 -- 114}, year = {2011}, language = {en} } @misc{HillerSaitenmacherWalther2016, author = {Hiller, Benjamin and Saitenmacher, Ren{\´e} and Walther, Tom}, title = {Analysis of operating modes of complex compressor stations}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-61092}, year = {2016}, abstract = {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.}, language = {en} } @article{GamrathKochMaheretal.2017, author = {Gamrath, Gerald and Koch, Thorsten and Maher, Stephen J. and Rehfeldt, Daniel and Shinano, Yuji}, title = {SCIP-Jack - A solver for STP and variants with parallelization extensions}, volume = {9}, journal = {Mathematical Programming Computation}, number = {2}, doi = {10.1007/s12532-016-0114-x}, pages = {231 -- 296}, year = {2017}, abstract = {The Steiner tree problem in graphs is a classical problem that commonly arises in practical applications as one of many variants. While often a strong relationship between different Steiner tree problem variants can be observed, solution approaches employed so far have been prevalently problem-specific. In contrast, this paper introduces a general-purpose solver that can be used to solve both the classical Steiner tree problem and many of its variants without modification. This versatility is achieved by transforming various problem variants into a general form and solving them by using a state-of-the-art MIP-framework. The result is a high-performance solver that can be employed in massively parallel environments and is capable of solving previously unsolved instances.}, language = {en} } @misc{HillerWalther2018, author = {Hiller, Benjamin and Walther, Tom}, title = {Improving branching for disjunctive polyhedral models using approximate convex decompositions}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-67462}, year = {2018}, abstract = {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.}, language = {en} } @article{GriewankHasenfelderRadonsetal.2018, author = {Griewank, Andreas and Hasenfelder, Richard and Radons, Manuel and Lehmann, Lutz and Streubel, Tom}, title = {Integrating Lipschitzian dynamical systems using piecewise algorithmic differentiation}, volume = {33}, journal = {Optimization Methods and Software}, publisher = {Taylor \& Francis}, doi = {10.1080/10556788.2017.1378653}, pages = {1089 -- 1107}, year = {2018}, abstract = {In this article we analyse a generalized trapezoidal rule for initial value problems with piecewise smooth right-hand side F : IR^n -> IR^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.}, language = {en} } @article{GriewankStreubelLehmannetal.2018, author = {Griewank, Andreas and Streubel, Tom and Lehmann, Lutz and Radons, Manuel and Hasenfelder, Richard}, title = {Piecewise linear secant approximation via algorithmic piecewise differentiation}, volume = {33}, journal = {Optimization Methods and Software}, number = {4-6}, publisher = {Taylor \& Francis}, doi = {10.1080/10556788.2017.1387256}, pages = {1108 -- 1126}, year = {2018}, abstract = {It is shown how piecewise differentiable functions F : IR^n -> IR^m that are defined by evaluation programmes can be approximated locally by a piecewise linear model based on a pair of sample points \check x and \hat x. We show that the discrepancy between function and model at any point x is of the bilinear order O(||x - \check x||*||x - \hat x||). As an application of the piecewise linearization procedure we devise a generalized Newton's method based on successive piecewise linearization and prove for it sufficient conditions for convergence and convergence rates equalling those of semismooth Newton. We conclude with the derivation of formulas for the numerically stable implementation of the aforedeveloped piecewise linearization methods.}, language = {en} } @article{SchweigerLiers2018, author = {Schweiger, Jonas and Liers, Frauke}, title = {A Decomposition Approach for Optimal Gas Network Extension with a Finite Set of Demand Scenarios}, volume = {19}, journal = {Optimization and Engineering}, number = {2}, publisher = {Springer}, pages = {297 -- 326}, year = {2018}, abstract = {Today's gas markets demand more flexibility from the network operators which in turn have to invest into their network infrastructure. As these investments are very cost-intensive and long-living, network extensions should not only focus on a single bottleneck scenario, but should increase the flexibility to fulfill different demand scenarios. In this work, we formulate a model for the network extension problem for multiple demand scenarios and propose a scenario decomposition in order to solve the arising challenging optimization tasks. In fact, each subproblem consists of a mixed-integer nonlinear optimization problem (MINLP). Valid bounds on the objective value are derived even without solving the subproblems to optimality. Furthermore, we develop heuristics that prove capable of improving the initial solutions substantially. Results of computational experiments on realistic network topologies are presented. It turns out that our method is able to solve these challenging instances to optimality within a reasonable amount of time.}, language = {en} } @article{HillerKochScheweetal.2018, author = {Hiller, Benjamin and Koch, Thorsten and Schewe, Lars and Schwarz, Robert and Schweiger, Jonas}, title = {A System to Evaluate Gas Network Capacities: Concepts and Implementation}, volume = {270}, journal = {European Journal of Operational Research}, number = {3}, pages = {797 -- 808}, year = {2018}, abstract = {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 trans- ported 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.}, language = {en} } @inproceedings{StreubelStrohmTrunschkeetal.2018, author = {Streubel, Tom and Strohm, Christian and Trunschke, Philipp and Tischendorf, Caren}, title = {Generic Construction and Efficient Evaluation of Network DAEs and Their Derivatives in the Context of Gas Networks}, booktitle = {Operations Research Proceedings 2017}, publisher = {Springer International Publishing}, isbn = {978-3-319-89920-6}, doi = {10.1007/978-3-319-89920-6_83}, pages = {627 -- 632}, year = {2018}, abstract = {We present a concept that provides an efficient description of differential-algebraic equations (DAEs) describing flow networks which provides the DAE function f and their Jacobians in an automatized way such that the sparsity pattern of the Jacobians is determined before their evaluation and previously determined values of f can be exploited. The user only has to provide the network topology and local function descriptions for each network element. The approach uses automatic differentiation (AD) and is adapted to switching element functions via the abs-normal-form (ANF).}, language = {en} } @inproceedings{HoppmannSchwarz2018, author = {Hoppmann, Kai and Schwarz, Robert}, title = {Finding Maximum Minimum Cost Flows to Evaluate Gas Network Capacities}, booktitle = {Operations Research Proceedings 2017}, isbn = {978-3-319-89919-0}, doi = {10.1007/978-3-319-89920-6_46}, pages = {339 -- 346}, year = {2018}, abstract = {In this article we consider the following problem arising in the context of scenario generation to evaluate the transport capacity of gas networks: In the Uncapacitated Maximum Minimum Cost Flow Problem (UMMCF) we are given a flow network where each arc has an associated nonnegative length and infinite capacity. Additionally, for each source and each sink a lower and an upper bound on its supply and demand are known, respectively. The goal is to find values for the supplies and demands respecting these bounds, such that the optimal value of the induced Minimum Cost Flow Problem is maximized, i.e., to determine a scenario with maximum transportmoment. In this article we propose two linear bilevel optimization models for UMMCF, introduce a greedy-style heuristic, and report on our first computational experiment.}, language = {en} } @inproceedings{Hennings2018, author = {Hennings, Felix}, title = {Benefits and Limitations of Simplified Transient Gas Flow Formulations}, volume = {Operations Research Proceedings}, booktitle = {Operations Research Proceedings 2017}, publisher = {Springer, Cham}, doi = {10.1007/978-3-319-89920-6_32}, pages = {231 -- 237}, year = {2018}, abstract = {Although intensively studied in recent years, the optimization of the transient (time-dependent) control of large real-world gas networks is still out of reach for current state-of-the-art approaches. For this reason, we present further simplifications of the commonly used model, which lead to a linear description of the gas flow on pipelines. In an empirical analysis of real-world data, we investigate the properties of the involved quantities and evaluate the errors made by our simplification.}, language = {en} } @misc{LenzSchwarz2016, author = {Lenz, Ralf and Schwarz, Robert}, title = {Optimal Looping of Pipelines in Gas Networks}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-61564}, year = {2016}, abstract = {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.}, language = {en} } @misc{HennigSchwarz2016, author = {Hennig, Kai and Schwarz, Robert}, title = {Using Bilevel Optimization to find Severe Transport Situations in Gas Transmission Networks}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-61519}, year = {2016}, abstract = {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.}, language = {en} } @article{HumpolaFuegenschuh2015, author = {Humpola, Jesco and F{\"u}genschuh, Armin}, title = {Convex reformulations for solving a nonlinear network design problem}, volume = {62}, journal = {Computational Optimization and Applications}, number = {3}, publisher = {Springer US}, doi = {10.1007/s10589-015-9756-2}, pages = {717 -- 759}, year = {2015}, abstract = {We consider a nonlinear nonconvex network design problem that arises, for example, in natural gas or water transmission networks. Given is such a network with active and passive components, that is, valves, compressors, control valves (active) and pipelines (passive), and a desired amount of flow at certain specified entry and exit nodes in the network. The active elements are associated with costs when used. Besides flow conservation constraints in the nodes, the flow must fulfill nonlinear nonconvex pressure loss constraints on the arcs subject to potential values (i.e., pressure levels) in both end nodes of each arc. The problem is to compute a cost minimal setting of the active components and numerical values for the flow and node potentials. We examine different (convex) relaxations for a subproblem of the design problem and benefit from them within a branch-and-bound approach. We compare different approaches based on nonlinear optimization numerically on a set of test instances.}, language = {en} } @incollection{HaynHumpolaKochetal.2015, author = {Hayn, Christine and Humpola, Jesco and Koch, Thorsten and Schewe, Lars and Schweiger, Jonas and Spreckelsen, Klaus}, title = {Perspectives}, volume = {SIAM-MOS series on Optimization}, booktitle = {Evaluating Gas Network Capacities}, isbn = {9781611973686}, year = {2015}, abstract = {After we discussed approaches to validate nominations and to verify bookings, we consider possible future research paths. This includes determining technical capacities and planning of network extensions.}, language = {en} } @misc{Szabo2012, author = {Szab{\´o}, J{\´a}cint}, title = {The set of solutions to nomination validation in passive gas transportation networks with a generalized flow formula}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-15151}, year = {2012}, abstract = {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.}, language = {en} } @misc{MartinGeisslerHaynetal.2012, author = {Martin, Alexander and Geißler, Bj{\"o}rn and Hayn, Christine and Hiller, Benjamin and Humpola, Jesco and Koch, Thorsten and Lehmann, Thomas and Morsi, Antonio and Pfetsch, Marc and Schewe, Lars and Schmidt, Martin and Schultz, R{\"u}diger and Schwarz, Robert and Schweiger, Jonas and Steinbach, Marc and Willert, Bernhard}, title = {Optimierung Technischer Kapazit{\"a}ten in Gasnetzen}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-15121}, year = {2012}, abstract = {Die mittel- und l{\"a}ngerfristige Planung f{\"u}r den Gastransport hat sich durch {\"A}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{\"a}t und Topologieplanung bezeichnet werden. Diese mathematischen Optimierungsprobleme werden vorgestellt und L{\"o}sungsans{\"a}tze skizziert.}, language = {de} } @misc{HillerKochScheweetal.2018, author = {Hiller, Benjamin and Koch, Thorsten and Schewe, Lars and Schwarz, Robert and Schweiger, Jonas}, title = {A System to Evaluate Gas Network Capacities: Concepts and Implementation}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-67438}, year = {2018}, abstract = {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.}, language = {en} } @misc{BennerGrundelHimpeetal.2017, author = {Benner, Peter and Grundel, Sara and Himpe, Christian and Huck, Christoph and Streubel, Tom and Tischendorf, Caren}, title = {Gas Network Benchmark Models}, issn = {1438-0064}, doi = {10.1007/11221_2018_5}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-66274}, year = {2017}, abstract = {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.}, language = {en} } @misc{GriewankHasenfelderRadonsetal.2017, author = {Griewank, Andreas and Hasenfelder, Richard and Radons, Manuel and Lehmann, Lutz and Streubel, Tom}, title = {Integrating Lipschitzian Dynamical Systems using Piecewise Algorithmic Differentiation}, issn = {1438-0064}, doi = {10.1080/10556788.2017.1378653}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-64639}, year = {2017}, abstract = {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.}, language = {en} } @misc{Hennings2017, author = {Hennings, Felix}, title = {Benefits and Limitations of Simplified Transient Gas Flow Formulations}, issn = {1438-0064}, doi = {10.1007/978-3-319-89920-6_32}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-64570}, year = {2017}, abstract = {Although intensively studied in recent years, the optimization of the transient (time-dependent) control of large real-world gas networks is still out of reach for current state-of-the-art approaches. For this reason, we present further simplifications of the commonly used model, which lead to a linear description of the gas flow on pipelines. In an empirical analysis of real-world data, we investigate the properties of the involved quantities and evaluate the errors made by our simplification.}, language = {en} } @misc{StreubelStrohmTrunschkeetal.2017, author = {Streubel, Tom and Strohm, Christian and Trunschke, Philipp and Tischendorf, Caren}, title = {Generic Construction and Efficient Evaluation of Network DAEs and Their Derivatives in the Context of Gas Networks}, issn = {1438-0064}, doi = {10.1007/978-3-319-89920-6_83}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-64582}, year = {2017}, abstract = {We present a concept that provides an efficient description of differential-algebraic equations (DAEs) describing flow networks which provides the DAE function f and their Jacobians in an automatized way such that the sparsity pattern of the Jacobians is determined before their evaluation and previously determined values of f can be exploited. The user only has to provide the network topology and local function descriptions for each network element. The approach uses automatic differentiation (AD) and is adapted to switching element functions via the abs-normal-form (ANF).}, language = {en} } @incollection{BargmannEbbersHeineckeetal.2015, author = {Bargmann, Dagmar and Ebbers, Mirko and Heinecke, Nina and Koch, Thorsten and K{\"u}hl, Veronika and Pelzer, Antje and Pfetsch, Marc and R{\"o}vekamp, Jessica and Spreckelsen, Klaus}, title = {State-of-the-art in evaluating gas network capacities}, booktitle = {Evaluating Gas Network Capacities}, publisher = {Society for Industrial and Applied Mathematics}, isbn = {9781611973686}, pages = {65 -- 84}, year = {2015}, language = {en} } @incollection{ScheweKochMartinetal.2015, author = {Schewe, Lars and Koch, Thorsten and Martin, Alexander and Pfetsch, Marc}, title = {Mathematical optimization for evaluating gas network capacities}, booktitle = {Evaluating Gas Network Capacities}, publisher = {Society for Industrial and Applied Mathematics}, isbn = {9781611973686}, pages = {87 -- 102}, year = {2015}, language = {en} } @misc{Humpola2015, author = {Humpola, Jesco}, title = {Sufficient Pruning Conditions for MINLP in Gas Network Design}, doi = {10.1007/s13675-016-0077-8}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-53489}, year = {2015}, abstract = {One quarter of Europe's energy demand is provided by natural gas distributed through a vast pipeline network covering the whole of Europe. At a cost of 1 million Euros per kilometer the extension of the European pipeline network is already a multi billion Euro business. Therefore, automatic planning tools that support the decision process are desired. We model the topology extension problem in gas networks by a mixed-integer nonlinear program (MINLP). This gives rise to a so-called active transmission problem, a continuous nonlinear non-convex feasibility problem which emerges from the MINLP model by fixing all integral variables. In this article we offer novel sufficient conditions for proving the infeasibility of this active transmission problem. These conditions can be expressed in the form of a mixed-integer program (MILP), i.e., the infeasibility of a non-convex NLP can be certified by solving an MILP. These results provide an efficient bounding procedure in a branch-and-bound algorithm. Our computational results demonstrate a substantial speed-up for the necessary computations.}, language = {en} } @phdthesis{Humpola2014, author = {Humpola, Jesco}, title = {Gas Network Optimization by MINLP}, school = {Technische Universit{\"a}t Berlin}, year = {2014}, abstract = {One quarter of Europe's energy demand is provided by natural gas distributed through a vast pipeline network covering the whole of Europe. At a cost of 1 million Euros per kilometer the extension of the European pipeline network is already a multi billion Euro business. The challenging question is how to expand and operate the network in order to facilitate the transportation of specified gas quantities at minimum cost. This task can be formulated as a mathematical optimization problem that reflects to real-world instances of enormous size and complexity. The aim of this thesis is the development of novel theory and optimization algorithms which make it possible to solve these problems. Gas network topology optimization problems can be modeled as nonlinear mixed-integer programs (MINLPs). Such an MINLP gives rise to a so-called active transmission problem (ATP), a continuous nonlinear non-convex feasibility problem which emerges from the MINLP model by fixing all integral variables. The key to solving the ATP as well as the overall gas network topology optimization problem and the main contribution of this thesis is a novel domain relaxation of the variable bounds and constraints in combination with a penalization in the objective function. In case the domain relaxation does not yield a primal feasible solution for the ATP we offer novel sufficient conditions for proving the infeasibility of the ATP. These conditions can be expressed in the form of an MILP, i.e., the infeasibility of a non-convex NLP can be certified by solving an MILP. These results provide an efficient bounding procedure in a branch-and-bound algorithm. If the gas network consists only of pipes and valves, the ATP turns into a passive transmission problem (PTP). Although its constraints are non-convex, its domain relaxation can be proven to be convex. Consequently, the feasibility of the PTP can be checked directly in an efficient way. Another advantage of the passive case is that the solution of the domain relaxation gives rise to a cutting plane for the overall topology optimization problem that expresses the infeasibility of the PTP. This cut is obtained by a Benders argument from the Lagrange function of the domain relaxation augmented by a specially tailored pc-regularization. These cuts provide tight lower bounds for the passive gas network topology optimization problem. The domain relaxation does not only provide certificates of infeasibility and cutting planes, it can also be used to construct feasible primal solutions. We make use of parametric sensitivity analysis in order to identify binary variables to be switched based on dual information. This approach allows for the first time to compute directly MINLP solutions for large-scale gas network topology optimization problems. All the research in this thesis has been realized within the collaborative research project "Forschungskooperation Netzoptimierung (ForNe)". The developed software is in use by the cooperation partner Open Grid Europe GmbH. Parts of this thesis have been published in book chapters, journal articles and technical reports. An overview of the topics and solution approaches within the research project is given by Martin et al. (2011) and F{\"u}genschuh et al. (2013). Gas network operation approaches and solution methods are described in detail by Pfetsch et al. (2014) and with a special focus on topology optimization in F{\"u}genschuh et al. (2011). The primal heuristic presented in this thesis is published by Humpola et al. (2014b). The method for pruning nodes of the branch-and-bound tree for an approximation of the original problem is described in F{\"u}genschuh and Humpola (2013) and Humpola et al. (2014a). The Benders like inequality is introduced by Humpola and F{\"u}genschuh (2013).}, language = {en} } @incollection{HillerHumpolaLehmannetal.2015, author = {Hiller, Benjamin and Humpola, Jesco and Lehmann, Thomas and Lenz, Ralf and Morsi, Antonio and Pfetsch, Marc and Schewe, Lars and Schmidt, Martin and Schwarz, Robert and Schweiger, Jonas and Stangl, Claudia and Willert, Bernhard}, title = {Computational results for validation of nominations}, volume = {SIAM-MOS series on Optimization}, booktitle = {Evaluating Gas Network Capacities}, isbn = {9781611973686}, year = {2015}, abstract = {The different approaches to solve the validation of nomination problem presented in the previous chapters are evaluated computationally in this chapter. Each approach is analyzed individually, as well as the complete solvers for these problems. We demonstrate that the presented approaches can successfully solve large-scale real-world instances.}, language = {en} } @incollection{HumpolaFuegenschuhHilleretal.2015, author = {Humpola, Jesco and F{\"u}genschuh, Armin and Hiller, Benjamin and Koch, Thorsten and Lehmann, Thomas and Lenz, Ralf and Schwarz, Robert and Schweiger, Jonas}, title = {The Specialized MINLP Approach}, volume = {SIAM-MOS series on Optimization}, booktitle = {Evaluating Gas Network Capacities}, isbn = {9781611973686}, year = {2015}, abstract = {We propose an approach to solve the validation of nominations problem using mixed-integer nonlinear programming (MINLP) methods. Our approach handles both the discrete settings and the nonlinear aspects of gas physics. Our main contribution is an innovative coupling of mixed-integer (linear) programming (MILP) methods with nonlinear programming (NLP) that exploits the special structure of a suitable approximation of gas physics, resulting in a global optimization method for this type of problem.}, language = {en} } @book{KochHillerPfetschetal.2015, author = {Koch, Thorsten and Hiller, Benjamin and Pfetsch, Marc and Schewe, Lars}, title = {Evaluating Gas Network Capacities}, publisher = {SIAM}, isbn = {978-1-611973-68-6}, pages = {xvi + 376 pages}, year = {2015}, language = {en} } @inproceedings{MaherMiltenbergerPedrosoetal.2016, author = {Maher, Stephen J. and Miltenberger, Matthias and Pedroso, Jo{\~a}o Pedro and Rehfeldt, Daniel and Schwarz, Robert and Serrano, Felipe}, title = {PySCIPOpt: Mathematical Programming in Python with the SCIP Optimization Suite}, volume = {9725}, booktitle = {Mathematical Software - ICMS 2016}, publisher = {Springer}, doi = {10.1007/978-3-319-42432-3_37}, pages = {301 -- 307}, year = {2016}, abstract = {SCIP is a solver for a wide variety of mathematical optimization problems. It is written in C and extendable due to its plug-in based design. However, dealing with all C specifics when extending SCIP can be detrimental to development and testing of new ideas. This paper attempts to provide a remedy by introducing PySCIPOpt, a Python interface to SCIP that enables users to write new SCIP code entirely in Python. We demonstrate how to intuitively model mixed-integer linear and quadratic optimization problems and moreover provide examples on how new Python plug-ins can be added to SCIP.}, language = {en} } @misc{FuegenschuhHumpola2013, author = {F{\"u}genschuh, Armin and Humpola, Jesco}, title = {A Unified View on Relaxations for a Nonlinear Network Flow Problem}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-18857}, year = {2013}, abstract = {We consider a nonlinear nonconvex network flow problem that arises, for example, in natural gas or water transmission networks. Given is such network with active and passive components, that is, valves, compressors, pressure regulators (active) and pipelines (passive), and a desired amount of flow at certain specified entry and exit nodes of the network. Besides flow conservation constraints in the nodes the flow must fulfill nonlinear nonconvex pressure loss constraints on the arcs subject to potential values (i.e., pressure levels) in both end nodes of each arc. The problem is how to numerically compute this flow and pressures. We review an existing approach of Maugis (1977) and extend it to the case of networks with active elements (for example, compressors). We further examine different ways of relaxations for the nonlinear network flow model. We compare different approaches based on nonlinear optimization numerically on a set of test instances.}, language = {en} } @misc{HumpolaFuegenschuh2013, author = {Humpola, Jesco and F{\"u}genschuh, Armin}, title = {A New Class of Valid Inequalities for Nonlinear Network Design Problems}, issn = {1438-0064}, doi = {10.1007/s00291-015-0390-2}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-17771}, year = {2013}, abstract = {We consider a nonlinear nonconvex network design problem that arises in the extension of natural gas transmission networks. Given is such network with active and passive components, that is, valves, compressors, pressure regulators (active) and pipelines (passive), and a desired amount of flow at certain specified entry and exit nodes of the network. Besides flow conservation constraints in the nodes the flow must fulfill nonlinear nonconvex pressure loss constraints on the arcs subject to potential values (i.e., pressure levels) in both end nodes of each arc. Assume that there does not exist a feasible flow that fulfills all physical constraints and meets the desired entry and exit amounts. Then a natural question is where to extend the network by adding pipes in the most economic way such that this flow becomes feasible. Answering this question is computationally demanding because of the difficult problem structure. We use mixed-integer nonlinear programming techniques that rely on an outer approximation of the overall problem, and a branching on decision variables. We formulate a new class of valid inequalities (or cutting planes) which reduce the overall solution time when added to the formulation. We demonstrate the computational merits of our approach on test instances.}, language = {en} } @misc{FuegenschuhGeisslerGollmeretal.2013, author = {F{\"u}genschuh, Armin and Geißler, Bj{\"o}rn and Gollmer, Ralf and Hayn, Christine and Henrion, Rene and Hiller, Benjamin and Humpola, Jesco and Koch, Thorsten and Lehmann, Thomas and Martin, Alexander and Mirkov, Radoslava and Morsi, Antonio and R{\"o}misch, Werner and R{\"o}vekamp, Jessica and Schewe, Lars and Schmidt, Martin and Schultz, R{\"u}diger and Schwarz, Robert and Schweiger, Jonas and Stangl, Claudia and Steinbach, Marc and Willert, Bernhard}, title = {Mathematical Optimization for Challenging Network Planning Problems in Unbundled Liberalized Gas Markets}, issn = {1438-0064}, doi = {10.1007/s12667-013-0099-8}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-17821}, year = {2013}, abstract = {The recently imposed new gas market liberalization rules in Germany lead to a change of business of gas network operators. While previously network operator and gas vendor where united, they were forced to split up into independent companies. The network has to be open to any other gas trader at the same conditions, and free network capacities have to be identified and publicly offered in a non-discriminatory way. We show that these new paradigms lead to new and challenging mathematical optimization problems. In order to solve them and to provide meaningful results for practice, all aspects of the underlying problems, such as combinatorics, stochasticity, uncertainty, and nonlinearity, have to be addressed. With such special-tailored solvers, free network capacities and topological network extensions can, for instance, be determined.}, language = {en} } @misc{PfetschFuegenschuhGeissleretal.2012, author = {Pfetsch, Marc and F{\"u}genschuh, Armin and Geißler, Bj{\"o}rn and Geißler, Nina and Gollmer, Ralf and Hiller, Benjamin and Humpola, Jesco and Koch, Thorsten and Lehmann, Thomas and Martin, Alexander and Morsi, Antonio and R{\"o}vekamp, Jessica and Schewe, Lars and Schmidt, Martin and Schultz, R{\"u}diger and Schwarz, Robert and Schweiger, Jonas and Stangl, Claudia and Steinbach, Marc and Vigerske, Stefan and Willert, Bernhard}, title = {Validation of Nominations in Gas Network Optimization: Models, Methods, and Solutions}, issn = {1438-0064}, doi = {10.1080/10556788.2014.888426}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-16531}, year = {2012}, abstract = {In this article we investigate methods to solve a fundamental task in gas transportation, namely the validation of nomination problem: Given a gas transmission network consisting of passive pipelines and active, controllable elements and given an amount of gas at every entry and exit point of the network, find operational settings for all active elements such that there exists a network state meeting all physical, technical, and legal constraints. We describe a two-stage approach to solve the resulting complex and numerically difficult mixed-integer non-convex nonlinear feasibility problem. The first phase consists of four distinct algorithms facilitating mixed-integer linear, mixed-integer nonlinear, reduced nonlinear, and complementarity constrained methods to compute possible settings for the discrete decisions. The second phase employs a precise continuous nonlinear programming model of the gas network. Using this setup, we are able to compute high quality solutions to real-world industrial instances whose size is significantly larger than networks that have appeared in the literature previously.}, language = {en} } @misc{MaherMiltenbergerPedrosoetal.2016, author = {Maher, Stephen J. and Miltenberger, Matthias and Pedroso, Jo{\~a}o Pedro and Rehfeldt, Daniel and Schwarz, Robert and Serrano, Felipe}, title = {PySCIPOpt: Mathematical Programming in Python with the SCIP Optimization Suite}, issn = {1438-0064}, doi = {10.1007/978-3-319-42432-3_37}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-61348}, year = {2016}, abstract = {SCIP is a solver for a wide variety of mathematical optimization problems. It is written in C and extendable due to its plug-in based design. However, dealing with all C specifics when extending SCIP can be detrimental to development and testing of new ideas. This paper attempts to provide a remedy by introducing PySCIPOpt, a Python interface to SCIP that enables users to write new SCIP code entirely in Python. We demonstrate how to intuitively model mixed-integer linear and quadratic optimization problems and moreover provide examples on how new Python plug-ins can be added to SCIP.}, language = {en} } @misc{GamrathKochMaheretal.2016, author = {Gamrath, Gerald and Koch, Thorsten and Maher, Stephen J. and Rehfeldt, Daniel and Shinano, Yuji}, title = {SCIP-Jack - A solver for STP and variants with parallelization extensions}, issn = {1438-0064}, doi = {10.1007/s12532-016-0114-x}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-60170}, year = {2016}, abstract = {The Steiner tree problem in graphs is a classical problem that commonly arises in practical applications as one of many variants. While often a strong relationship between different Steiner tree problem variants can be observed, solution approaches employed so far have been prevalently problem-specific. In contrast, this paper introduces a general-purpose solver that can be used to solve both the classical Steiner tree problem and many of its variants without modification. This versatility is achieved by transforming various problem variants into a general form and solving them by using a state-of-the-art MIP-framework. The result is a high-performance solver that can be employed in massively parallel environments and is capable of solving previously unsolved instances.}, language = {en} } @article{HumpolaSerrano2017, author = {Humpola, Jesco and Serrano, Felipe}, title = {Sufficient pruning conditions for MINLP in gas network design}, volume = {5}, journal = {EURO Journal on Computational Optimization}, number = {1-2}, publisher = {Springer Berlin Heidelberg}, doi = {10.1007/s13675-016-0077-8}, pages = {239 -- 261}, year = {2017}, abstract = {One-quarter of Europe's energy demand is provided by natural gas distributed through a vast pipeline network covering the whole of Europe. At a cost of 1 million Euros per kilometer the extension of the European pipeline network is already a multi-billion Euro business. Therefore, automatic planning tools that support the decision process are desired. We model the topology optimization problem in gas networks by a mixed-integer nonlinear program (MINLP). This gives rise to a so-called active transmission problem, a continuous nonlinear non-convex feasibility problem which emerges from the MINLP model by fixing all integral variables. We offer novel sufficient conditions for proving the infeasibility of this active transmission problem. These conditions can be expressed in the form of a mixed-integer program (MILP), i.e., the infeasibility of a non-convex continuous nonlinear program (NLP) can be certified by solving an MILP. This result provides an efficient pruning procedure in a branch-and-bound algorithm. Our computational results demonstrate a substantial speedup for the necessary computations.}, language = {en} } @incollection{GotzesHeineckeHilleretal.2015, author = {Gotzes, Uwe and Heinecke, Nina and Hiller, Benjamin and R{\"o}vekamp, Jessica and Koch, Thorsten}, title = {Regulatory rules for gas markets in Germany and other European countries}, booktitle = {Evaluating gas network capacities}, publisher = {Society for Industrial and Applied Mathematics}, isbn = {978-1-611973-68-6}, pages = {45 -- 64}, year = {2015}, language = {en} } @misc{WaltherHillerSaitenmacher2017, author = {Walther, Tom and Hiller, Benjamin and Saitenmacher, Ren{\´e}}, title = {Polyhedral 3D Models for compressors in gas networks}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-65864}, year = {2017}, abstract = {Compressor machines are crucial elements in a gas transmission network, required to compensate for the pressure loss caused by friction in the pipes. Modelling all physical and technical details of a compressor machine involves a large amount of nonlinearity, which makes it hard to use such models in the optimization of large-scale gas networks. In this paper, we are going to describe a modelling approach for the operating range of a compressor machine, starting from a physical reference model and resulting in a polyhedral representation in the 3D space of mass flow throughput as well as in- and outlet pressure.}, language = {en} } @phdthesis{Schweiger2017, author = {Schweiger, Jonas}, title = {Exploiting structure in non-convex quadratic optimization and gas network planning under uncertainty}, pages = {411}, year = {2017}, 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 and uncertainty in the data pose principal difficulties. The first part of the thesis deals with non-convex quadratic programs. Branch\&Bound methods for this problem class depend on tight relaxations. We contribute in several ways: First, we establish a new way to handle missing linearization variables in the well-known Reformulation-Linearization-Technique (RLT). This is implemented into the commercial software CPLEX. Second, we study the optimization of a quadratic objective over the standard simplex or a knapsack constraint. These basic structures appear as part of many complex models. Exploiting connections to the maximum clique problem and RLT, we derive new valid inequalities. Using exact and heuristic separation methods, we demonstrate the impact of the new inequalities on the relaxation and the global optimization of these problems. Third, we strengthen the state-of-the-art relaxation for the pooling problem, a well-known non-convex quadratic problem, which is, for example, relevant in the petrochemical industry. We propose a novel relaxation that captures the essential non-convex structure of the problem but is small enough for an in-depth study. We provide a complete inner description in terms of the extreme points as well as an outer description in terms of inequalities defining its convex hull (which is not a polyhedron). We show that the resulting valid convex inequalities significantly strengthen the standard relaxation of the pooling problem. The second part of this thesis focuses on a common challenge in real world applications, namely, the uncertainty entailed in the input data. We study the extension of a gas transport network, e.g., from our project partner Open Grid Europe GmbH. For a single scenario this maps to a challenging non-convex MINLP. As the future transport patterns are highly uncertain, we propose a robust model to best prepare the network operator for an array of scenarios. We develop a custom decomposition approach that makes use of the hierarchical structure of network extensions and the loose coupling between the scenarios. The algorithm used the single-scenario problem as black-box subproblem allowing the generalization of our approach to problems with the same structure. The scenario-expanded version of this problem is out of reach for today's general-purpose MINLP solvers. Yet our approach provides primal and dual bounds for instances with up to 256 scenarios and solves many of them to optimality. Extensive computational studies show the impact of our work.}, language = {en} } @article{SchmidtAssmannBurlacuetal.2017, author = {Schmidt, Martin and Assmann, Denis and Burlacu, Robert and Humpola, Jesco and Joormann, Imke and Kanelakis, Nikolaos and Koch, Thorsten and Oucherif, Djamal and Pfetsch, Marc and Schewe, Lars and Schwarz, Robert and Sirvent, Matthias}, title = {GasLib - A Library of Gas Network Instances}, volume = {2}, journal = {Data}, number = {4}, doi = {10.3390/data2040040}, year = {2017}, language = {en} } @article{HumpolaLehmannFuegenschuh2015, author = {Humpola, Jesco and Lehmann, Thomas and F{\"u}genschuh, Armin}, title = {A primal heuristic for optimizing the topology of gas networks based on dual information}, volume = {3}, journal = {EURO Journal on Computational Optimization}, number = {1}, doi = {10.1007/s13675-014-0029-0}, pages = {53 -- 78}, year = {2015}, abstract = {We present a novel heuristic 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 of a nonlinear relaxation. Based on the information from the KKT point we alter some of the binary variables in a locally promising way exploiting 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.}, language = {en} } @misc{HillerWalther2018, author = {Hiller, Benjamin and Walther, Tom}, title = {Modelling compressor stations in gas networks}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-67443}, year = {2018}, abstract = {Gas networks are an important application area for optimization. When considering long-range transmission, compressor stations play a crucial role in these applications. The purpose of this report is to collect and systematize the models used for compressor stations in the literature. The emphasis is on recent work on simple yet accurate polyhedral models that may replace more simplified traditional models without increasing model complexity. The report also describes an extension of the compressor station data available in GasLib (http://gaslib.zib.de/) with the parameters of these models.}, language = {en} } @inproceedings{HillerSaitenmacherWalther2017, author = {Hiller, Benjamin and Saitenmacher, Ren{\´e} and Walther, Tom}, title = {Analysis of operating modes of complex compressor stations}, booktitle = {Proceedings of Operations Research 2016}, doi = {10.1007/978-3-319-55702-1_34}, pages = {251 -- 257}, year = {2017}, abstract = {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.}, language = {en} } @incollection{HillerHaynHeitschetal.2015, author = {Hiller, Benjamin and Hayn, Christine and Heitsch, Holger and Henrion, Ren{\´e} and Le{\"o}vey, Hernan and M{\"o}ller, Andris and R{\"o}misch, Werner}, title = {Methods for verifying booked capacities}, booktitle = {Evaluating gas network capacities}, publisher = {Society for Industrial and Applied Mathematics}, pages = {291 -- 315}, year = {2015}, language = {en} } @misc{HillerKochScheweetal.2017, author = {Hiller, Benjamin and Koch, Thorsten and Schewe, Lars and Schwarz, Robert and Schweiger, Jonas}, title = {A System to Evaluate Gas Network Capacities: Concepts and Implementation}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-61931}, year = {2017}, abstract = {Since 2005, the gas market in the European Union is liberalized and the trading of natural gas is decoupled from its transport. The transport is done by 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 maximum independent capacities at each entry and exit such that the resulting gas flows can be realized by the network without compromising security of supply. Therefore, evaluating the available transport capacities is extremely important to the TSOs. This paper gives an overview of the toolset for evaluating gas network capacities that has been developed within the ForNe project, a joint research project of seven research partners initiated by Open Grid Europe, Germany's biggest TSO. While most of the relevant mathematics is described in the book "Evaluating Gas Network Capacities", this article sketches the system as a whole, describes some developments that have taken place recently, and gives some details about the current implementation.}, language = {en} } @misc{GriewankStreubelLehmannetal.2016, author = {Griewank, Andreas and Streubel, Tom and Lehmann, Lutz and Hasenfelder, Richard and Radons, Manuel}, title = {Piecewise linear secant approximation via Algorithmic Piecewise Differentiation}, issn = {1438-0064}, doi = {10.1080/10556788.2017.1387256}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-61642}, year = {2016}, abstract = {It is shown how piecewise differentiable functions \(F: R^n → R^m\) that are defined by evaluation programs can be approximated locally by a piecewise linear model based on a pair of sample points x̌ and x̂. We show that the discrepancy between function and model at any point x is of the bilinear order O(||x - x̌|| ||x - x̂||). This is a little surprising since x ∈ R^n may vary over the whole Euclidean space, and we utilize only two function samples F̌ = F(x̌) and F̂ = F(x̂), as well as the intermediates computed during their evaluation. As an application of the piecewise linearization procedure we devise a generalized Newton's method based on successive piecewise linearization and prove for it sufficient conditions for convergence and convergence rates equaling those of semismooth Newton. We conclude with the derivation of formulas for the numerically stable implementation of the aforedeveloped piecewise linearization methods.}, language = {en} } @article{KickhoeferKern2015, author = {Kickh{\"o}fer, Benjamin and Kern, Julia}, title = {Pricing local emission exposure of road traffic: An agent-based approach}, volume = {37}, journal = {Transportation Research Part D: Transport and Environment}, doi = {10.1016/j.trd.2015.04.019}, pages = {14 -- 28}, year = {2015}, abstract = {This paper proposes a new approach to iteratively calculate local air pollution exposure tolls in large-scale urban settings by taking the exposure times and locations of individuals into consideration. It explicitly avoids detailed air pollution concentration calculations and is therefore characterized by little data requirements, reasonable computation times for iterative calculations, and open-source compatibility. In a first step, the paper shows how to derive time-dependent vehicle-specific exposure tolls in an agent-based model. It closes the circle from the polluting entity, to the receiving entity, to damage costs, to tolls, and back to the behavioral change of the polluting entity. In a second step, the approach is applied to a large-scale real-world scenario of the Munich metropolitan area in Germany. Changes in emission levels, exposure costs, and user benefits are calculated. These figures are compared to a flat emission toll, and to a regulatory measure (a speed reduction in the inner city), respectively. The results indicate that the flat emission toll reduces overall emissions more significantly than the exposure toll, but its exposure cost reductions are rather small. For the exposure toll, overall emissions increase for freight traffic which implies a potential conflict between pricing schemes to optimize local emission exposure and others to abate climate change. Regarding the mitigation of exposure costs caused by urban travelers, the regulatory measure is found to be an effective strategy, but it implies losses in user benefits.}, language = {en} }