TY - JOUR A1 - Hintermüller, Michael A1 - Strogies, Nikolai T1 - Identification of the friction function in a semilinear system for gas transport through a network JF - Optimization Methods and Software N2 - An identification problem for the friction parameter in a semilinear system of balance laws, describing the transport of gas through a passive network of pipelines, is considered. The existence of broad solutions to the state system is proven and sensitivity results for the corresponding solution operator are obtained. The existence of solutions to the output least squares formulation of the identification problem, based on noisy measurements over time at fixed spatial positions is established. Finally, numerical experiments validate the theoretical findings. Y1 - 2017 VL - 35 SP - 576 EP - 617 ER - TY - JOUR A1 - Mehrmann, Volker A1 - Schmidt, Martin A1 - Stolwijk, Jeroen J. T1 - Model and Discretization Error Adaptivity within Stationary Gas Transport Optimization JF - Vietnam Journal of Mathematics N2 - The minimization of operation costs for natural gas transport networks is studied. Based on a recently developed model hierarchy ranging from detailed models of instationary partial differential equations with temperature dependence to highly simplified algebraic equations, modeling and discretization error estimates are presented to control the overall error in an optimization method for stationary and isothermal gas flows. The error control is realized by switching to more detailed models or finer discretizations if necessary to guarantee that a prescribed model and discretization error tolerance is satisfied in the end. We prove convergence of the adaptively controlled optimization method and illustrate the new approach with numerical examples. KW - Gas network optimization KW - Isothermal stationary Euler equations KW - Model hierarchy KW - Adaptive error control KW - Marking strategy Y1 - 2017 IS - 46(4) SP - 779 EP - 801 ER - TY - JOUR A1 - Schneider, Moritz A1 - Lang, Jens A1 - Hundsdorfer, Willem T1 - Extrapolation-Based Super-Convergent Implicit-Explicit Peer Methods with A-stable Implicit Part N2 - In this paper we extend the implicit-explicit (IMEX) methods of Peer type recently developed in [Lang, Hundsdorfer, J. Comp. Phys., 337:203–215, 2017] to a broader class of two-step methods that allow the construction of super- convergent IMEX-Peer methods with A-stable implicit part. IMEX schemes combine the necessary stability of implicit and low computational costs of ex- plicit methods to efficiently solve systems of ordinary differential equations with both stiff and non-stiff parts included in the source term. To construct super- convergent IMEX-Peer methods with favourable stability properties, we derive necessary and sufficient conditions on the coefficient matrices and apply an extrapolation approach based on already computed stage values. Optimised super-convergent IMEX-Peer methods of order s + 1 for s = 2, 3, 4 stages are given as result of a search algorithm carefully designed to balance the size of the stability regions and the extrapolation errors. Numerical experiments and a comparison to other IMEX-Peer methods are included. Y1 - 2017 U6 - https://doi.org/10.1016/j.jcp.2018.04.006 VL - J. Comput. Physics IS - Vol. 367 SP - 121 EP - 133 ER - TY - JOUR A1 - Krebs, Vanessa A1 - Schmidt, Martin T1 - Uniqueness of Market Equilibria on Networks with Transport Costs JF - Operations Research Perspectives N2 - We study the existence and uniqueness of equilibria for perfectly competitive markets in capacitated transport networks. The model under consideration is rather general so that it captures basic aspects of related models in, e.g., gas or electricity networks. We formulate the market equilibrium model as a mixed complementarity problem and show the equivalence to a welfare maximization problem. Using the latter we prove uniqueness of the resulting equilibrium for piecewise linear and symmetric transport costs under additional mild assumptions. Moreover, we show the necessity of these assumptions by illustrating examples that possess multiple solutions if our assumptions are violated. KW - Market Equilibria KW - Networks KW - Transport Costs KW - Uniqueness KW - Perfect Competition Y1 - 2017 IS - 5 SP - 169 EP - 173 ER - TY - JOUR A1 - Burlacu, Robert A1 - Egger, Herbert A1 - Groß, Martin A1 - Martin, Alexander A1 - Pfetsch, Marc A1 - Schewe, Lars A1 - Sirvent, Mathias A1 - Skutella, Martin T1 - Maximizing the storage capacity of gas networks: a global MINLP approach N2 - In this paper, we study the transient optimization of gas networks, focusing in particular on maximizing the storage capacity of the network. We include nonlinear gas physics and active elements such as valves and compressors, which due to their switching lead to discrete decisions. The former is described by a model derived from the Euler equations that is given by a coupled system of nonlinear parabolic partial differential equations (PDEs). We tackle the resulting mathematical optimization problem by a first-discretize-then-optimize approach. To this end, we introduce a new discretization of the underlying system of parabolic PDEs and prove well-posedness for the resulting nonlinear discretized system. Endowed with this discretization, we model the problem of maximizing the storage capacity as a non-convex mixed-integer nonlinear problem (MINLP). For the numerical solution of the MINLP, we algorithmically extend a well-known relaxation approach that has already been used very successfully in the field of stationary gas network optimization. This method allows us to solve the problem to global optimality by iteratively solving a series of mixed-integer problems (MIPs). Finally, we present two case studies that illustrate the applicability of our approach. KW - Mixed-Integer Nonlinear Programming KW - Transient Gas Transport Optimization KW - Storage Capacity Maximization KW - Power-to-Gas KW - First-Discretize-Then-Optimize Y1 - 2019 U6 - https://doi.org/10.1007/s11081-018-9414-5 VL - 20 SP - 543 EP - 573 ET - Optimization and Engineering ER - TY - JOUR A1 - Grimm, Veronika A1 - Grübel, Julia A1 - Schewe, Lars A1 - Schmidt, Martin A1 - Zöttl, Gregor T1 - Nonconvex Equilibrium Models for Gas Market Analysis: Failure of Standard Techniques and Alternative Modeling Approaches JF - European Journal on Operational Research N2 - This paper provides a first approach to assess gas market interaction on a network with nonconvex flow models. In the simplest possible setup that adequately reflects gas transport and market interaction, we elaborate on the relation of the solution of a simultaneous competitive gas market game, its corresponding mixed nonlinear complementarity problem (MNCP), and a first-best benchmark. We provide conditions under which the solution of the simultaneous game is also the solution of the corresponding MNCP. However, equilibria cannot be determined by the MNCP as the transmission system operator's (TSO’s) first-order conditions are insufficient, which goes back to nonconvexities of the gas flow model. This also implies that the welfare maximization problem may have multiple solutions that sometimes do not even coincide with any of the market equilibria. Our analysis shows that, even in the absence of strategic firms, market interaction fails to implement desirable outcomes from a welfare perspective due to the TSO’s incentive structure. We conclude that the technical environment calls for a market design that commits the TSO to a welfare objective through regulation and propose a design where the market solution corresponds to a welfare maximum and vice versa. KW - Natural Gas Markets KW - Nonconvex Equilibrium Models KW - Uniqueness KW - Multiplicity KW - Fundamental Welfare Theorems Y1 - 2017 IS - 273(3) SP - 1097 EP - 1108 ER - TY - RPRT 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. KW - disjunctive set KW - convex hull reformulation KW - branch-and-bound KW - approximate convex decomposition Y1 - 2017 ER - TY - INPR A1 - Egger, Herbert A1 - Kugler, Thomas A1 - Wollner, Winnifried T1 - Numerical optimal control of instationary gas transport with control and state constraints N2 - We consider the optimal control of a nonlinear hyperbolic system of balance laws on a one-dimensional network which arises in the context of gas transport in pipeline systems. State constraints, which are required for the safe operation of the system, are incorporated by a barrier method. We discuss the well-posedness of the governing system of partial differential-algebraic equations and investigate the existence of minimizers. For the numerical solution, we then consider the approximation of the state equation by mixed finite elements in space and a particular linear implicit time integration scheme that can be interpreted as a discontinuous Galerkin approximation. We establish well- posedness of this discretization scheme and prove the existence of minimizers for the corresponding discretized optimal control problem and discuss its numerical solution by a projected Gauß-Newton method. The efficient realization of the Jacobian and Hessian of the quadratic approximations that have to be minimized in every iteration of the Gauß-Newton method can be obtained via the solution of discretized sensitivity and adjoint equations. These are obtained by formal differentiation and transposition of the Galerkin methods employed for the discretization of the state equations. All approximations obtained after discretization can thus be interpreted as functions on the continuous level and, since the functional analytic setting is not changed by the Galerkin discretization, we observe mesh independence of the resulting fully discrete methods. For illustration of our theoretical results and to demonstrate the efficiency of the proposed method, we present numerical results for two test problems that model typical situations that may arise in the daily operation of gas networks. Y1 - 2017 ER - TY - JOUR A1 - Adelhütte, Dennis A1 - Aßmann, Denis A1 - Gonzàlez Grandòn, Tatiana A1 - Gugat, Martin A1 - Heitsch, Holger A1 - Liers, Frauke A1 - Henrion, René A1 - Nitsche, Sabrina A1 - Schultz, Rüdiger A1 - Stingl, Michael A1 - Wintergerst, David T1 - Joint model of probabilistic/robust (probust) constraints applied to gas network optimization N2 - Optimization tasks under uncertain conditions abound in many real-life applications. Whereas solution approaches for probabilistic constraints are often developed in case the uncertainties can be assumed to follow a certain probability distribution, robust approaches are usually used in case solutions are sought that are feasible for all realizations of uncertainties within some pre-defined uncertainty set. As many applications contain different types of uncertainties that require robust as well as probabilistic treatments, we deal with a class of joint probabilistic/robust constraints as its appears in optimization problems under uncertainty. Focusing on complex uncertain gas network optimization problems, we show the relevance of this class of problems for the task of maximizing free booked capacities in an algebraic model for a stationary gas network. We furthermore present approaches for their solution. Finally, we study the problem of controlling a transient system that is governed by the wave equation. The task consists in determining controls such that a certain robustness measure remains below some given upper bound, with high probability. KW - robust optimization KW - chance constraints KW - optimal control KW - spheric-radial decomposition Y1 - 2017 U6 - https://doi.org/10.1007/s10013-020-00434-y ER - TY - INPR A1 - Egger, Herbert A1 - Böttcher, Anke T1 - Energy stable discretization of Allen-Cahn type problems modeling the motion of phase boundaries N2 - We study the systematic numerical approximation of a class of Allen-Cahn type problems modeling the motion of phase interfaces. The common feature of these models is an underlying gradient flow structure which gives rise to a decay of an associated energy functional along solution trajectories. We first study the discretization in space by a conforming Galerkin approximation of a variational principle which characterizes smooth solutions of the problem. Well-posedness of the resulting semi-discretization is established and the energy decay along discrete solution trajectories is proven. A problem adapted implicit time-stepping scheme is then proposed and we establish its well-posed and decay of the free energy for the fully discrete scheme. Some details about the numerical realization by finite elements are discussed, in particular the iterative solution of the nonlinear problems arising in every time-step. The theoretical results are illustrated by numerical tests which also provide further evidence for asymptotic expansions of the interface velocities derived by Alber et al. Y1 - 2017 ER - TY - INPR A1 - Egger, Herbert A1 - Radu, Bogdan T1 - Super-convergence and post-processing for mixed finite element approximations of the wave equation N2 - We consider the numerical approximation of acoustic wave propagation problems by mixed BDM(k+1)-P(k) finite elements on unstructured meshes. Optimal convergence of the discrete velocity and super-convergence of the pressure by one order are established. Based on these results, we propose a post-processing strategy that allows us to construct an improved pressure approximation from the numerical solution. Corresponding results are well-known for mixed finite element approximations of elliptic problems and we extend these analyses here to the hyperbolic problem under consideration. We also consider the subsequent time discretization by the Crank-Nicolson method and show that the analysis and the post-processing strategy can be generalized to the fully discrete schemes. Our proofs do not rely on duality arguments or inverse inequalities and the results therefore apply also for non-convex domains and non-uniform meshes. Y1 - 2017 ER - TY - INPR A1 - Egger, Herbert T1 - A mixed variational discretization for non-isothermal compressible flow in pipelines N2 - We consider the non-isothermal flow of a compressible fluid through pipes. Starting from the full set of Euler equations, we propose a variational characterization of solutions that encodes the conservation of mass, energy, and entropy in a very direct manner. This variational principle is suitable for a conforming Galerkin approximation in space which automatically inherits the basic physical conservation laws. Three different spaces are used for approximation of density, mass flux, and temperature, and we consider a mixed finite element method as one possible choice of suitable approximation spaces. We also investigate the subsequent discretization in time by a problem adapted implicit time stepping scheme for which exact conservation of mass as well as a slight dissipation of energy and increase of entropy are proven which are due to the numerical dissipation of the implicit time discretization. The main arguments of our analysis are rather general and allow us to extend the approach with minor modification to more general boundary conditions and flow models taking into account friction, viscosity, heat conduction, and heat exchange with the surrounding medium. Y1 - 2017 ER - TY - INPR A1 - Aßmann, Denis A1 - Liers, Frauke A1 - Stingl, Michael T1 - Decomposable Robust Two-Stage Optimization: An Application to Gas Network Operations Under Uncertainty N2 - We study gas network problems with compressors and control valves under uncertainty that can be formulated as two-stage robust optimization problems. Uncertain data are present in the physical parameters of the pipes as well as in the overall demand. We show how to exploit the special decomposable structure of the problem in order to reformulate the two-stage robust problem as a standard single-stage optimization problem. Since this structure is present in similar problems on e.g., water or direct current electricity networks, we investigate the consequences of the decomposable structure in an abstract setting: The right-hand side of the single-stage problem can be precomputed by solving a series of optimization problems and multiple elements of the right-hand side can be combined into one optimization task. In order to apply our results to gas network problems, we extend piecewise relaxations and preprocessing techniques to incorporate uncertain input data. The practical feasibility and effectiveness of our approach is demonstrated with benchmarks on realistic gas network instances. We observe large speedups due to the described aggregation method together with the developed preprocessing strategies. Furthermore, we are able to solve even comparably large gas network instances quickly for the price of slightly more conservative solutions. KW - robust optimization KW - gas networks KW - relaxations Y1 - 2017 ER - TY - INPR A1 - Egger, Herbert A1 - Pietschmann, Jan-Frederik A1 - Schlottbom, Matthias T1 - On the uniqueness of nonlinear diffusion coefficients in the presence of lower order terms N2 - We consider the identification of nonlinear diffusion coefficients of the form a(t,u) or a(u) in quasi-linear parabolic and elliptic equations. Uniqueness for this inverse problem is established under very general assumptions using partial knowledge of the Dirichlet-to-Neumann map. The proof of our main result relies on the construction of a series of appropriate Dirichlet data and test functions with a particular singular behavior at the boundary. This allows us to localize the analysis and to separate the principal part of the equation from the remaining terms. We therefore do not require specific knowledge of lower order terms or initial data which allows to apply our results to a variety of applications. This is illustrated by discussing some typical examples in detail. Y1 - 2017 ER - TY - INPR A1 - Egger, Herbert T1 - Enhancement of flow measurements using fluid dynamic constraints N2 - Novel experimental modalities acquire spatially resolved velocity measurements for steady state and transient flows which are of interest for engineering and biological applications. One of the drawbacks of such high resolution velocity data is their susceptibility to measurement errors. In this paper, we propose a novel filtering strategy that allows enhancement of noisy measurements to obtain reconstruction of smooth divergence free velocity and corresponding pressure fields, which together approximately comply to a prescribed flow model. The main step in our approach consists of the appropriate use of the velocity measurements in the design of a linearized flow model which can be shown to be well-posed and consistent with the true velocity and pressure fields up to measurement and modeling errors. The reconstruction procedure is formulated as a linear quadratic optimal control problem and the resulting filter has analyzable smoothing and approximation properties. We also discuss briefly the discretization of our approach by finite element methods and comment on the efficient solution of the linear optimality system by iterative solvers. The capability of the proposed method to significantly reduce data noise is demonstrated by numerical tests in which we also compare to other methods like smoothing and solenoidal filtering. Y1 - 2017 ER - TY - INPR A1 - Egger, Herbert A1 - Kugler, Thomas T1 - An asymptotic preserving mixed finite element method for wave propagation in pipelines N2 - We consider a parameter dependent family of damped hyperbolic equations with interesting limit behavior: the system approaches steady states exponentially fast and for parameter to zero the solutions converge to that of a parabolic limit problem. We establish sharp estimates and elaborate their dependence on the model parameters. For the numerical approximation we then consider a mixed finite element method in space together with a Runge-Kutta method in time. Due to the variational and dissipative nature of this approximation, the limit behavior of the infinite dimensional level is inherited almost automatically by the discrete problems. The resulting numerical method thus is asymptotic preserving in the parabolic limit and uniformly exponentially stable. These results are further shown to be independent of the discretization parameters. Numerical tests are presented for a simple model problem which illustrate that the derived estimates are sharp in general. Y1 - 2017 ER - TY - INPR A1 - Egger, Herbert T1 - A class of Galerkin schemes for time-dependent radiative transfer N2 - The numerical solution of time-dependent radiative transfer problems is challenging, both, due to the high dimension as well as the anisotropic structure of the underlying integro-partial differential equation. In this paper we propose a general framework for designing numerical methods for time-dependent radiative transfer based on a Galerkin discretization in space and angle combined with appropriate time stepping schemes. This allows us to systematically incorporate boundary conditions and to preserve basic properties like exponential stability and decay to equilibrium also on the discrete level. We present the basic a-priori error analysis and provide abstract error estimates that cover a wide class of methods. The starting point for our considerations is to rewrite the radiative transfer problem as a system of evolution equations which has a similar structure like first order hyperbolic systems in acoustics or electrodynamics. This analogy allows us to generalize the main arguments of the numerical analysis for such applications to the radiative transfer problem under investigation. We also discuss a particular discretization scheme based on a truncated spherical harmonic expansion in angle, a finite element discretization in space, and the implicit Euler method in time. The performance of the resulting mixed PN-finite element time stepping scheme is demonstrated by computational results. Y1 - 2017 ER - TY - INPR A1 - Beckers, Susanne A1 - Behrens, Jörn A1 - Wollner, Winnifried T1 - Duality Based Error Estimation in the Presence of Discontinuities N2 - Goal-oriented mesh adaptation, in particular using the dual-weighted residual (DWR) method, is known in many cases to produce very efficient meshes. For obtaining such meshes the (numerical) solution of an adjoint problem is needed to weight the residuals appropriately with respect to their relevance for the overall error. For hyperbolic problems already the weak primal problem requires in general an additional entropy condition to assert uniqueness of solutions; this difficulty is also reflected when considering adjoints to hyperbolic problems involving discontinuities where again an additional requirement (reversibility) is needed to select appropriate solutions. Within this article, an approach to the DWR method for hyperbolic problems based on an artificial viscosity approximation is proposed. It is discussed why the proposed method provides a well-posed dual problem, while a direct, formal, application of the dual problem does not. Moreover, we will discuss a further, novel, approach in which the forward problem need not be modified, thus allowing for an unchanged forward solution. The latter procedure introduces an additional residual term in the error estimation, accounting for the inconsistency between primal and dual problem. Finally, the effectivity of the extended error estimator, assessing the global error by a suitable functional of interest, is tested numerically; and the advantage over a formal estimator approach is demonstrated. KW - dual weighted residual, hyperbolic problems, discontinuous Galerkin, artificial viscosity Y1 - 2017 ER - TY - JOUR A1 - Hanke, Michael A1 - März, Roswitha A1 - Tischendorf, Caren T1 - Least-Squares Collocation for Higher-Index Linear Differential-Algebraic Equations: Estimating the Instability Threshold JF - Math. Comp. N2 - Differential-algebraic equations with higher index give rise to essentially ill-posed problems. The least-squares collocation by discretizing the pre-image space is not much more computationally expensive than standard collocation methods used in the numerical solution of ordinary differential equations and index-1 differential-algebraic equations. This approach has displayed excellent convergence properties in numerical experiments, however, theoretically, till now convergence could be established merely for regular linear differential-algebraic equations with constant coefficients. We present now an estimate of the instability threshold which serves as the basic key for proving convergence for general regular linear DAEs. KW - differential-algebraic equation, higher index, essentially ill-posed problem, collocation, boundary value problem, initial value problem Y1 - 2017 U6 - https://doi.org/10.1090/mcom/3393 VL - 88 SP - 1647 EP - 1683 ER - TY - RPRT A1 - Walther, Tom A1 - Hiller, Benjamin T1 - Modelling compressor stations in gas networks N2 - 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. KW - gas compressor modeling KW - compressor station KW - polyhedral model KW - MINLP model KW - nonlinear model Y1 - 2017 ER - TY - INPR A1 - Walther, Tom A1 - Hiller, Benjamin A1 - Saitenmacher, René T1 - Polyhedral 3D Models for compressors in gas networks N2 - 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. KW - gas compressor modeling KW - polyhedral model KW - accuracy KW - z factor Y1 - 2017 ER - TY - JOUR A1 - Leugering, Günter A1 - Martin, Alexander A1 - Schmidt, Martin A1 - Sirvent, Mathias T1 - Nonoverlapping Domain Decomposition for Optimal Control Problems governed by Semilinear Models for Gas Flow in Networks N2 - We consider optimal control problems for gas flow in pipeline networks. The equations of motion are taken to be represented by a first-order system of hyperbolic semilinear equations derived from the fully nonlinear isothermal Euler gas equations. We formulate an optimal control problem on a network and introduce a tailored time discretization thereof. In order to further reduce the complexity, we consider an instantaneous control strategy. The main part of the paper is concerned with a nonoverlapping domain decomposition of the optimal control problem on the graph into local problems on smaller sub-graphs - ultimately on single edges. We prove convergence of the domain decomposition method on networks and study the wellposedness of the corresponding time-discrete optimal control problems. The point of the paper is that we establish virtual control problems on the decomposed subgraphs such that the corresponding optimality systems are in fact equal to the systems obtained via the domain decomposition of the entire optimality system. KW - Optimal control, Gas networks, Euler's equation, Semilinear PDE, Nonoverlapping domain decomposition Y1 - 2017 VL - 46 IS - 3 SP - 191 EP - 225 PB - Control and Cybernetics ER - TY - INPR 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. KW - model reformulation KW - bound tightening KW - multi-way compressor station KW - flow patterns Y1 - 2017 ER - TY - JOUR A1 - Lang, Jens A1 - Mindt, Pascal T1 - Entropy-Preserving Coupling Conditions for One-dimensional Euler Systems at Junctions N2 - This paper is concerned with a set of novel coupling conditions for the 3x3 one-dimensional Euler system with source terms at a junction of pipes with possibly different cross-sectional areas. Beside conservation of mass, we require the equality of the total enthalpy at the junction and that the specific entropy for pipes with outgoing flow equals the convex combination of all entropies that belong to pipes with incoming flow. These conditions ensure energy as well as entropy conservation at the junction. We prove the existence and uniqueness of solutions to the generalised Riemann problem at a junction in the neighbourhood of constant stationary states which belong to the subsonic region. This provides the basis for the well-posedness of the homogeneous and inhomogeneous Cauchy problems for initial data with sufficiently small total variation. Y1 - 2017 U6 - https://doi.org/10.3934/nhm.2018008 VL - Networks and Heterogeneous Media IS - Vol. 13 SP - 177 EP - 190 ER - TY - JOUR A1 - Lang, Jens A1 - Hundsdorfer, Willem T1 - Extrapolation-based implicit–explicit Peer methods with optimised stability regions N2 - In this paper we investigate a new class of implicit–explicit (IMEX) two-step methods of Peer type for systems of ordinary differential equations with both non-stiff and stiff parts included in the source term. An extrapolation approach based on already computed stage values is applied to construct IMEX methods with favourable stability properties. Optimised IMEX-Peer methods of order p=2,3,4, are given as result of a search algorithm carefully designed to balance the size of the stability regions and the extrapolation errors. Numerical experiments and a comparison to other implicit–explicit methods are included. Y1 - 2017 U6 - https://doi.org/doi:10.1016/j.jcp.2017.02.034 VL - J. Comput. Phys. IS - 337 SP - 203 EP - 215 ER - TY - INPR A1 - Gugat, Martin A1 - Perrollaz, Vincent A1 - Rosier, Lionel T1 - Boundary stabilization of quasilinear hyperbolic systems of balance laws: Exponential decay for small source terms N2 - We investigate the long-time behavior of solutions of quasilinear hyperbolic systems with transparent boundary conditions when small source terms are incorporated in the system. Even if the finite-time stability of the system is not preserved, it is shown here that an exponential convergence towards the steady state still holds with a decay rate which is proportional to the logarithm of the amplitude of the source term. The result is stated for a system with dynamical boundary conditions in order to deal with initial data that are free of any compatibility condition. Y1 - 2017 ER - TY - CHAP A1 - Leugering, Günter A1 - Mophou, Gisèle ED - Schulz, Volker T1 - Instantaneous optimal control of friction dominated flow in a gas-network T2 - DFG-AIMS-Workshop, in Mbour, Senegal, 13-16. March 2017 N2 - We consider optimal control problems for the flow of gas in a pipe network. The equations of motions are taken to be represented by a nonlinear model derived from a semi-linear approximation of the fully nonlinear isothermal Euler gas equations. We formulate an optimal control problem on a given network and introduce a time discretization thereof. We then study the well-posedness of the corresponding time-discrete optimal control problem. In order to further reduce the complexity, we consider an instantaneous control strategy. This involves a p-Laplace-type problem on the graph with p =3/2. We prove well-posedness, existence of optimal controls and derive a first order optimality condition. Y1 - 2017 VL - International Series for Numerical Mathematics PB - Birkhäuser ER - TY - INPR A1 - Domschke, Pia A1 - Hiller, Benjamin A1 - Lang, Jens A1 - Tischendorf, Caren T1 - Modellierung von Gasnetzwerken: Eine Übersicht N2 - Mit dieser Übersicht wollen wir eine Zusammenstellung von unterschiedlichen Modellen zur Beschreibung des Gasflusses in Netzwerken bereitstellen, um den Einstieg in das Thema zu erleichtern. Besonderes Augenmerk wird dabei auf die der Modellierung inneliegende hierarchische Struktur und die detaillierte Beschreibung einzelner Bauteile wie Ventile und Kompressoren gelegt. Daneben finden sich ebenfalls Netzmodellklassen, die auf rein algebraische Relationen aufbauen. Am Ende geben wir einen kurzen Überblick über grundlegende numerische Verfahren und Konzepte zur Behandlung von hyperbolischen Bilanzgleichungen. Wir erheben keinen Anspruch auf Vollständigkeit und verweisen an vielen Stellen auf die bestehende Literatur. Die Idee eines Modellkataloges ist uns im Rahmen der Antragstellung zum SFB/Transregio 154 „Mathematische Modellierung, Simulation und Optimierung am Beispiel von Gasnetzwerken“ gekommen. Wir möchten an dieser Stelle die Förderung durch die DFG dankend erwähnen. KW - Euler-Gleichungen, isotherme Euler-Gleichungen, Modellhierarchie, Netzelemente Y1 - 2017 VL - 2717 ER - TY - JOUR A1 - Hintermüller, Michael A1 - Rautenberg, Carlos A1 - Strogies, Nikolai T1 - Dissipative and Non-dissipative Evolutionary Quasi-variational Inequalities with Gradient Constraints JF - Set-Valued and Variational Analysis N2 - Evolutionary quasi-variational inequality (QVI) problems of dissipative and non-dissipative nature with pointwise constraints on the gradient are studied. A semi-discretization in time is employed for the study of the problems and the derivation of a numerical solution scheme, respectively. Convergence of the discretization procedure is proven and properties of the original infinite dimensional problem, such as existence, extra regularity and non-decrease in time, are derived. The proposed numerical solver reduces to a finite number of gradient-constrained convex optimization problems which can be solved rather efficiently. The paper ends with a report on numerical tests obtained by a variable splitting algorithm involving different nonlinearities and types of constraints. Y1 - 2017 VL - 27 SP - 433 EP - 468 ER - TY - JOUR A1 - Hintermüller, Michael A1 - Strogies, Nikolai T1 - On the consistency of Runge--Kutta methods up to order three applied to the optimal control of scalar conservation laws JF - Numerical Analysis and Optimization N2 - Higher-order Runge-Kutta (RK) time discretization methods for the optimal control of scalar conservation laws are analyzed and numerically tested. The hyperbolic nature of the state system introduces specific requirements on discretization schemes such that the discrete adjoint states associated with the control problem converge as well. Moreover, conditions on the RK-coefficients are derived that coincide with those characterizing strong stability preserving Runge-Kutta methods. As a consequence, the optimal order for the adjoint state is limited, e.g., to two even in the case where the conservation law is discretized by a third-order method. Finally, numerical tests for controlling Burgers equation validate the theoretical results. Y1 - 2017 U6 - https://doi.org/10.20347/WIAS.PREPRINT.2442 SP - 119 EP - 154 ER - TY - JOUR A1 - Gugat, Martin A1 - Herty, Michael A1 - Müller, Siegfried ED - Piccoli, Benedetto T1 - Coupling conditions for the transition from supersonic to subsonic fluid states JF - Networks and Heterogeneous Media (NHM) N2 - We discuss coupling conditions for the p-system in case of a transition from supersonic states to subsonic states. A single junction with adjacent pipes is considered where on each pipe the gas ow is governed by a general p-system. By extending the notion of demand and supply known from traffic fiow analysis we obtain a constructive existence result of solutions compatible with the introduced conditions. KW - p-system KW - coupling conditions KW - network Y1 - 2017 U6 - https://doi.org/10.3934/nhm.2017016 VL - 12 IS - 3 SP - 371 EP - 380 ER - TY - JOUR A1 - Habeck, Oliver A1 - Pfetsch, Marc E. A1 - Ulbrich, Stefan T1 - Global optimization of mixed-integer ODE constrained network problems using the example of stationary gas transport N2 - In this paper we propose a new approach for finding global solutions of mixed-integer nonlinear optimization problems with ordinary differential equation constraints on networks. Instead of using a first discretize then optimize approach, we combine spatial and variable branching with appropriate discretizations of the differential equations to derive relaxations of the original problem. To construct the relaxations we derive convex under- and concave over-estimators for the ODE solution operators using numerical discretization schemes. Thereby, we make use of the underlying network structure, where the solutions of the ODEs only need to be known at a finite number of points. This property enables us to adaptively refine the discretization and relaxation without introducing new variables. The incorporation into a spatial branch-and-bound process allows to compute global epsilon-optimal solutions or decide infeasibility. We prove that this algorithm terminates finitely under some natural assumptions. We then show how this approach works for the example of stationary gas transport and provide some illustrative computational examples. KW - Global Optimization KW - Mixed-Integer Nonlinear Optimization Y1 - 2017 U6 - https://doi.org/10.1137/17M1152668 VL - 29 IS - 4 SP - 2949 EP - 2985 ET - SIAM Journal of Optimization ER - TY - CHAP A1 - Benner, Peter A1 - Grundel, Sarah 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 - 2017 U6 - https://doi.org/10.1007/11221_2018_5 VL - DAE-FORUM SP - 171 EP - 197 PB - Springer CY - Cham ER - TY - CHAP A1 - Huck, Christoph A1 - Tischendorf, Caren T1 - Transient Modeling and Simulation of Gas Pipe Networks with Characteristic Diagram Models for Compressors T2 - Proceedings in Applied Mathematics and Mechanics N2 - One challenge for the simulation and optimization of real gas pipe networks is the treatment of compressors. Their behavior is usually described by characteristic diagrams reflecting the connection of the volumetric flow and the enthalpy change or shaft torque. Such models are commonly used for an optimal control of compressors and compressor stations [4, 7] using stationary models for the gas flow through the pipes. For transient simulations of gas networks, simplified compressor models have been studied in [1–3]. Here, we present a transient simulation of gas pipe networks with characteristic diagram models of compressors using a stable network formulation as (partial) differential-algebraic system. Y1 - 2017 U6 - https://doi.org/10.1002/pamm.201710322 VL - 17 IS - 1 SP - 707 EP - 708 ER - TY - INPR A1 - Huck, Christoph A1 - Tischendorf, Caren T1 - Perturbation analysis of hyperbolic PDAEs describing flow networks Y1 - 2017 ER - TY - JOUR A1 - Gugat, Martin A1 - Leugering, Günter A1 - Wang, Ke ED - Zhang, Xu T1 - Neumann boundary feedback stabilization for a nonlinear wave equation: A strict H2-Lyapunov function JF - Mathematical Control and Related Fields (MCRF) N2 - For a system that is governed by the isothermal Euler equations with friction for ideal gas, the corresponding field of characteristic curves is determined by the velocity of the flow. This velocity is determined by a second-order quasilinear hyperbolic equation. For the corresponding initial-boundary value problem with Neumann-boundary feedback, we consider non-stationary solutions locally around a stationary state on a finite time interval and discuss the well-posedness of this kind of problem. We introduce a strict H2-Lyapunov function and show that the boundary feedback constant can be chosen such that the H2-Lyapunov function and hence also the H2-norm of the difference between the non-stationary and the stationary state decays exponentially with time. KW - Boundary feedback control, feedback stabilization, exponential stability, isothermal Euler equations, second-order quasilinear equation, Lyapunov function, stationary state, non-stationary state, gas pipeline. Y1 - 2017 U6 - https://doi.org/10.3934/mcrf.2017015 VL - 7 IS - 3 SP - 419 EP - 448 ER - TY - JFULL A1 - Leugering, Günter T1 - Domain Decomposition of an Optimal Control Problem for Semi-Linear Elliptic Equations on Metric Graphs with Application to Gas Networks N2 - We consider optimal control problems for the flow of gas in a pipe network. The equations of motions are taken to be represented by a semi-linear model derived from the fully nonlinear isothermal Euler gas equations. We formulate an optimal control problem on a given network and introduce a time discretization thereof. We then study the well-posedness of the corresponding time-discrete optimal control problem. In order to further reduce the complexity, we consider an instantaneous control strategy. The main part of the paper is concerned with a non-overlapping domain decomposition of the semi-linear elliptic optimal control problem on the graph into local problems on a small part of the network, ultimately on a single edge. KW - 28 KW - nonoverlapping omain decomposition, optimal control of semi-linear ellioptic systems on netowrks Y1 - 2017 U6 - https://doi.org/https://doi.org/10.4236/am.2017.88082 SN - 2152-7393 VL - 8 ER - TY - JOUR A1 - Gugat, Martin A1 - Ulbrich, Stefan ED - CHEN, GOONG T1 - The isothermal Euler equations for ideal gas with source term: Product solutions, flow reversal and no blow up JF - Journal of Mathematical Analysis and Applications KW - Global classical solutions Ideal gas Bi-directional flow Transsonic flow Y1 - 2017 U6 - https://doi.org/10.1016/j.jmaa.2017.04.064 VL - 454 IS - 1 SP - 439 EP - 452 ER - TY - CHAP A1 - Gugat, Martin A1 - Herty, Michael A1 - Yu, Hui ED - Westdickenberg, Michael T1 - On the relaxation approximation for 2 × 2 hyperbolic balance laws N2 - The relaxation approximation for systems of conservation laws has been studied intensively for example by [17, 5, 19, 24]. In this paper the corresponding relaxation approximation for 2x2 systems of balance laws is studied. Our driving example is gas flow in pipelines described by the isothermal Euler equations. We are interested in the limiting behavior as the relaxation parameter tends to zero. We give conditions where the relaxation converges to the states of the original system and counterexamples for cases where the steady states depend on the space variable. Y1 - 2017 VL - x IS - x SP - x EP - x PB - Springer CY - Springer Proceedings in Mathematics and Statistics ER - TY - JOUR A1 - Krebs, Vanessa A1 - Schewe, Lars A1 - Schmidt, Martin T1 - Uniqueness and Multiplicity of Market Equilibria on DC Power Flow Networks JF - European Journal on Operations Research N2 - We consider uniqueness and multiplicity of market equilibria in a short-run setup where traded quantities of electricity are transported through a capacitated network in which power flows have to satisfy the classical lossless DC approximation. The firms face fluctuating demand and decide on their production, which is constrained by given capacities. Today, uniqueness of such market outcomes are especially important in more complicated multilevel models for measuring market (in)efficiency. Thus, our findings are important prerequisites for such studies. We show that market equilibria are unique on tree networks under mild assumptions and we also present a priori conditions under which equilibria are unique on cycle networks. On general networks, uniqueness fails to hold and we present simple examples for which multiple equilibria exist. However, we prove a posteriori criteria for the uniqueness of a given solution and characterize situations in which multiple solutions exist. KW - Market Equilibria KW - Uniqueness KW - Multiplicity KW - Networks KW - DC Power Flow Y1 - 2017 IS - 271(1) SP - 165 EP - 178 ER - TY - CHAP A1 - Rüffler, Fabian A1 - Hante, Falk T1 - Optimality Conditions for Switching Operator Differential Equations N2 - We consider optimal switching of hybrid abstract evolution equations. The framework includes switching semilinear partial differential equations of parabolic or hyperbolic type, discontinuous state resets, switching costs and allows switching of the principle parts of the equations. We present adjoint-based formulae for the gradient of the cost functional with respect to position and number of switching time points that lead to first order necessary conditions. Moreover, we discuss an alternate-direction approach for implementing descent methods. As an application we consider optimal open/close-switching of valves and on/off-switching control of compressors in a gas network modelled by a graph with simplified euler equations on edges and suitable coupling conditions at nodes. Y1 - 2017 ER - TY - INPR A1 - Gugat, Martin A1 - Schultz, Rüdiger T1 - Boundary feedback stabilization of the isothermal Euler-equations with uncertain boundary data N2 - In a gas transport system, the customer behavior is uncertain. Motivated by this situation, we consider a boundary stabilization problem for the flow through a gas pipeline, where the outflow at one end of the pipe %that is governed by the customer's behavior is uncertain. The control action is located at the other end of the pipe. The feedback law is a classical Neumann velocity feedback with a feedback parameter $k>0$. We show that as long as the $H^1$-norm of the function that describes the noise in the customer's behavior decays exponentially with a rate that is sufficiently large, the velocity of the gas can be stabilized exponentially fast in the sense that a suitably chosen Lyapunov function decays exponentially. For the exponential stability it is sufficient that the feedback parameter $k$ is sufficiently large and the stationary state to which the system is stabilized is sufficiently small. The stability result is local, that is it holds for initial states that are sufficiently close to the stationary state. This result is an example for the exponential boundary feedback stabilization of a quasilinear hyperbolic system with uncertain boundary data. The analysis is based upon the choice of a suitably Lyapunov function. The decay of this Lyapunov function implies that also the $L^2$-norm of the difference of the system state and the stationary state decays exponentially. Y1 - 2017 ER - TY - JOUR A1 - Hante, Falk A1 - Schmidt, Martin T1 - Complementarity-Based Nonlinear Programming Techniques for Optimal Mixing in Gas Networks JF - EURO Journal on Computational Optimization N2 - We consider nonlinear and nonsmooth mixing aspects in gas transport optimization problems. As mixed-integer reformulations of pooling-type mixing models already render small-size instances computationally intractable, we investigate the applicability of smooth nonlinear programming techniques for equivalent complementarity-based reformulations. Based on recent results for remodeling piecewise affine constraints using an inverse parametric quadratic programming approach, we show that classical stationarity concepts are meaningful for the resulting complementarity-based reformulation of the mixing equations. Further, we investigate in a numerical study the performance of this reformulation compared to a more compact complementarity-based one that does not feature such beneficial regularity properties. All computations are performed on publicly available data of real-world size problem instances from steady-state gas transport. KW - Gas transport networks KW - Mixing KW - Inverse parametric quadratic programming KW - Complementarity constraints KW - MPCC Y1 - 2017 IS - 7(3) SP - 299 EP - 323 ER - TY - JOUR A1 - Schmidt, Martin A1 - Aßmann, Denis A1 - Burlacu, Robert A1 - Humpola, Jesco A1 - Joormann, Imke A1 - Kanelakis, Nikolaos A1 - Koch, Thorsten A1 - Oucherif, Djamal A1 - Pfetsch, Marc E. A1 - Schewe, Lars A1 - Schwarz, Robert A1 - Sirvent, Mathias T1 - GasLib – A Library of Gas Network Instances JF - Data N2 - The development of mathematical simulation and optimization models and algorithms for solving gas transport problems is an active field of research. In order to test and compare these models and algorithms, gas network instances together with demand data are needed. The goal of GasLib is to provide a set of publicly available gas network instances that can be used by researchers in the field of gas transport. The advantages are that researchers save time by using these instances and that different models and algorithms can be compared on the same specified test sets. The library instances are encoded in an XML format. In this paper, we explain this format and present the instances that are available in the library. KW - Gas Transport KW - Networks KW - Problem Instances KW - Mixed-Integer Nonlinear Optimization KW - GasLib Y1 - 2017 U6 - https://doi.org/10.3390/data2040040 VL - 4 IS - 2 ER - TY - JOUR A1 - Hintermüller, Michael A1 - Surowiec, Thomas T1 - On the Directional Differentiability of the Solution Mapping for a Class of Variational Inequalities of the Second Kind JF - Set-Valued and Variational Analysis N2 - The directional differentiability of the solution mapping for a class of variational inequali- ties of the second kind inspired by applications in fluid mechanics and moving free boundary problems is investigated. The result is particularly relevant for the model predictive control or optimal control of such variational inequalities in that it can be used to derive stationarity conditions and efficient numerical methods. Y1 - 2017 U6 - https://doi.org/10.1007/s11228-017-0408-9 VL - 26 SP - 631 EP - 642 ER - TY - JOUR A1 - Hintermüller, Michael A1 - Surowiec, Thomas T1 - A Bundle-Free Implicit Programming Approach for a Class of MPECs in Function Space JF - Mathematical Programming N2 - Using a standard first-order optimality condition for nonsmooth optimization prob- lems, a general framework for a descent method is developed. This setting is applied to a class of mathematical programs with equilibrium constraints in function space from which a new algorithm is derived. Global convergence of the algorithm is demonstrated in function space and the results are then illustrated by numerical experiments. Y1 - 2017 U6 - https://doi.org/10.1007/s10107-016-0983-9 VL - 160 IS - 1-2 SP - 271 EP - 305 ER - TY - JOUR A1 - Hintermüller, Michael A1 - Rautenberg, Carlos A1 - Mohammadi, Masoumeh A1 - Kanitsar, Martin T1 - Optimal sensor placement: A robust approach JF - SIAM Journal on Control and Optimization N2 - We address the problem of optimally placing sensor networks for convection-diffusion processes where the convective part is perturbed. The problem is formulated as an optimal control problem where the integral Riccati equation is a constraint and the design variables are sensor locations. The objective functional involves a term associated to the trace of the solution to the Riccati equation and a term given by a constrained optimization problem for the directional derivative of the previous quantity over a set of admissible perturbations. The paper addresses the existence of the derivative with respect to the convective part of the solution to the Riccati equation, the well-posedness of the optimization problem and finalizes with a range of numerical tests. Y1 - 2017 VL - 55 SP - 3609 EP - 3639 ER - TY - JOUR A1 - Groß, Martin A1 - Pfetsch, Marc E. A1 - Skutella, Martin T1 - On the Complexity of Instationary Gas Flows N2 - We study a simplistic model of instationary gas flows consisting of a sequence of k stationary gas flows. We present efficiently solvable cases and NP-hardness results, establishing complexity gaps between stationary and instationary gas flows (already for k=2) as well as between instationary gas s-t-flows and instationary gas b-flows. Y1 - 2017 U6 - https://doi.org/10.1016/j.orl.2018.01.007 VL - 46 IS - 3 SP - 286 EP - 290 ET - Operations Research Letters ER - TY - JOUR A1 - Keil, Tobias A1 - Hintermüller, Michael A1 - Wegner, Donat T1 - Optimal control of a semidiscrete Cahn-Hilliard-Navier-Stokes system with non-matched fluid densities JF - SIAM Journal on Control and Optimization N2 - This paper is concerned with the distributed optimal control of a time-discrete Cahn– Hilliard/Navier–Stokes system with variable densities. It focuses on the double-obstacle potential which yields an optimal control problem for a family of coupled systems in each time instant of a variational inequality of fourth order and the Navier–Stokes equation. By proposing a suitable time- discretization, energy estimates are proved and the existence of solutions to the primal system and of optimal controls is established for the original problem as well as for a family of regularized problems. The latter correspond to Moreau–Yosida type approximations of the double-obstacle potential. The consistency of these approximations is shown and first order optimality conditions for the regularized problems are derived. Through a limit process with respect to the regularization parameter, a stationarity system for the original problem is established. The resulting system corresponds to a function space version of C-stationarity which is a special notion of stationarity for MPECs. Y1 - 2017 VL - 55 SP - 1954 EP - 1989 ER - TY - JOUR A1 - Papafitsoros, Konstantinos A1 - Hintermüller, Michael A1 - Rautenberg, Carlos T1 - Analytical aspects of spatially adapted total variation regularisation JF - Journal of Mathematical Analysis and Applications N2 - In this paper we study the structure of solutions of the one dimensional weighted total variation regularisation problem, motivated by its application in signal recovery tasks. We study in depth the relationship between the weight function and the creation of new discontinuities in the solution. A partial semigroup property relating the weight function and the solution is shown and analytic solutions for simply data functions are computed. We prove that the weighted total variation minimisation problem is well-posed even in the case of vanishing weight function, despite the lack of coercivity. This is based on the fact that the total variation of the solution is bounded by the total variation of the data, a result that it also shown here. Finally the relationship to the corresponding weighted fidelity problem is explored, showing that the two problems can produce completely different solutions even for very simple data functions. Y1 - 2017 VL - 454 SP - 891 EP - 935 ER - TY - INPR A1 - Wintergerst, David T1 - Application of Chance Constrained Optimization to Gas Networks N2 - We consider optimization problems with a joint probabilistic constraint under normally distributed uncertain parameters. The parametric constraints are replaced by one constraint stating that the probability of being feasible shall exceed or be equal to a prescribed threshold. In order to apply the concept to gas network optimization under uncertain boundary flows, which corresponds to the demand of customers, we derive an analytic gradient formula. The integral corresponding to the probability can be parameterized by spherical radial decomposition. For this parameterization gradient formulas are known under convexity assumptions of the parametric constraints in the parameter. For the application in gas networks that we have in mind, the convexity assumption of the parametric constraints is not satisfied. Therefore, we weaken it to convexity of the region of feasible parameters for a fixed optimization variable. We proceed to show that the assumptions needed for the gradient formula are met in the gas network optimization problem on a tree. For the numerical implementation we propose a multilevel sampling algorithm that uses a coarse approximation of the chance constraint to generate a warm start for the expensive approximation with fine sampling. The numerical results illustrate that this approach significantly reduces the computation time. KW - chance constraint KW - spherical radial decomposition KW - isothermal Euler equations KW - gas networks KW - multilevel Y1 - 2017 ER - TY - JOUR A1 - Bernstein, Aaron A1 - Disser, Yann A1 - Groß, Martin T1 - General Bounds for Incremental Maximization N2 - We propose a theoretical framework to capture incremental s olutions to cardinality con- strained maximization problems. The defining characterist ic of our framework is that the cardinality/support of the solution is bounded by a value k ∈ N that grows over time, and we allow the solution to be extended one element at a time. We i nvestigate the best-possible competitive ratio of such an incremental solution, i.e., th e worst ratio over all k between the incremental solution after k steps and an optimum solution of cardinality k . We define a large class of problems that contains many important cardin ality constrained maximization problems like maximum matching, knapsack, and packing/cov ering problems. We provide a general 2 . 618-competitive incremental algorithm for this class of pr oblems, and show that no algorithm can have competitive ratio below 2 . 18 in general. In the second part of the paper, we focus on the inherently inc remental greedy algorithm that increases the objective value as much as possible in eac h step. This algorithm is known to be 1 . 58-competitive for submodular objective functions, but it has unbounded competitive ratio for the class of incremental problems mentioned above . We define a relaxed submod- ularity condition for the objective function, capturing pr oblems like maximum (weighted) ( b -)matching and a variant of the maximum flow problem. We show t hat the greedy algo- rithm has competitive ratio (exactly) 2 . 313 for the class of problems that satisfy this relaxed submodularity condition. Note that our upper bounds on the competitive ratios transla te to approximation ratios for the underlying cardinality constrained problems. Y1 - 2017 ER - TY - INPR A1 - Groß, Martin A1 - Gupta, Anupam A1 - Kumar, Amit A1 - Matuschke, Jannik A1 - Schmidt, Daniel R. A1 - Schmidt, Melanie A1 - Verschae, José T1 - A Local-Search Algorithm for Steiner Forest N2 - In the Steiner Forest problem, we are given a graph and a collection of source-sink pairs, and the goal is to find a subgraph of minimum total length such that all pairs are connected. The problem is APX-Hard and can be 2 -approximated by, e.g., the elegant primal-dual algorithm of Agrawal, Klein, and Ravi from 1995. We give a local-search-based constant-factor approximati on for the problem. Local search brings in new techniques to an area that has for long not seen any improv ements and might be a step towards a combinatorial algorithm for the more general survivable n etwork design problem. Moreover, local search was an essential tool to tackle the dynamic MST/Stein er Tree problem, whereas dynamic Steiner Forest is still wide open. It is easy to see that any constant factor local search algori thm requires steps that add/drop many edges together. We propose natural local moves which, at each step , either (a) add a shortest path in the current graph and then drop a bunch of inessential edges, or (b) add a s et of edges to the current solution. This second type of moves is motivated by the potential function w e use to measure progress, combining the cost of the solution with a penalty for each connected compon ent. Our carefully-chosen local moves and potential function work in tandem to eliminate bad local min ima that arise when using more traditional local moves. Our analysis first considers the case where the local optimum is a single tree, and shows optimality w.r.t. moves that add a single edge (and drop a set of edges) is enough to bound the locality gap. For the general case, we show how to “project” the optimal solution o nto the different trees of the local optimum without incurring too much cost (and this argument uses opti mality w.r.t. both kinds of moves), followed by a tree-by-tree argument. We hope both the potential funct ion, and our analysis techniques will be useful to develop and analyze local-search algorithms in ot her contexts. Y1 - 2017 ER - TY - JOUR A1 - Abed, Fidaa A1 - Chen, Lin A1 - Disser, Yann A1 - Groß, Martin A1 - Megow, Nicole A1 - Meißner, Julie A1 - Richter, Alexander T. A1 - Rischke, Roman T1 - Scheduling Maintenance Jobs in Networks N2 - We investigate the problem of scheduling the maintenance of edges in a network, motivated by the goal of minimizing outages in transportation or telecommunication networks. We focus on maintaining connectivity between two nodes over time; for the special case of path networks, this is related to the problem of minimizing the busy time of machines. We show that the problem can be solved in polynomial time in arbitrary networks if preemption is allowed. If preemption is restricted to integral time points, the problem is NP-hard and in the non-preemptive case we give strong non-approximability results. Furthermore, we give tight bounds on the power of preemption, that is, the maximum ratio of the values of non-preemptive and preemptive optimal solutions. Interestingly, the preemptive and the non-preemptive problem can be solved efficiently on paths, whereas we show that mixing both leads to a weakly NP-hard problem that allows for a simple 2-approximation. Y1 - 2017 ER - TY - JOUR A1 - Groß, Martin A1 - Marc E., Pfetsch A1 - Schewe, Lars A1 - Schmidt, Martin A1 - Skutella, Martin T1 - Algorithmic Results for Potential-Based Flows: Easy and Hard Cases N2 - Potential-based flows are an extension of classical network flows in which the flow on an arc is determined by the difference of the potentials of its incident nodes. Such flows are unique and arise, for example, in energy networks. Two important algorithmic problems are to determine whether there exists a feasible flow and to maximize the flow between two designated nodes. We show that these problems can be solved for the single source and sink case by reducing the network to a single arc. However, if we additionally consider switches that allow to force the flow to 0 and decouple the potentials, these problems are NP-hard. Nevertheless, for particular series-parallel networks, one can use algorithms for the subset sum problem. Moreover, applying network presolving based on generalized series-parallel structures allows to significantly reduce the size of realistic energy networks. KW - Potential networks KW - Potential-based flows KW - Maximum flow problem KW - Series-parallel graphs KW - Network reduction Y1 - 2017 U6 - https://doi.org/10.1002/net.21865 VL - 73 IS - 3 SP - 303 EP - 324 ET - Networks ER -