TY - RPRT A1 - Arulselvan, Ashwin A1 - Cseh, Ágnes A1 - Groß, Martin A1 - Manlove, David F. A1 - Matuschke, Jannik T1 - Matchings with lower quotas: Algorithms and complexity N2 - We study a natural generalization of the maximum weight many-to-one matching problem. We are given an undirected bipartite graph G = (A∪P,E) with weights on the edges in E, and with lower and upper quotas on the vertices in P. We seek a maximum weight many-to-one matching satisfying two sets of constraints: vertices in A are incident to at most one matching edge, while vertices in P are either unmatched or they are incident to a number of matching edges between their lower and upper quota. This problem, which we call maximum weight many-to-one matching with lower and upper quotas (wmlq), has applications to the assignment of students to projects within university courses, where there are constraints on the minimum and maximum numbers of students that must be assigned to each project. In this paper, we provide a comprehensive analysis of the complexity of wmlq from the viewpoints of classical polynomial time algorithms, fixed-parameter tractability, as well as approximability. We draw the line between NP-hard and polynomially tractable instances in terms of degree and quota constraints and provide efficient algorithms to solve the tractable ones. We further show that the problem can be solved in polynomial time for instances with bounded treewidth; however, the corresponding runtime is exponential in the treewidth with the maximum upper quota u_max as basis, and we prove that this dependence is necessary unless FPT = W[1]. The approximability of wmlq is also discussed: we present an approximation algorithm for the general case with performance guarantee umax + 1, which is asymptotically best possible unless P = NP. Finally, we elaborate on how most of our positive results carry over to matchings in arbitrary graphs with lower quotas. Y1 - 2016 U6 - https://doi.org/10.1007/978-3-662-48971-0_16 ER - TY - INPR A1 - Bärmann, Andreas A1 - Gellermann, Thorsten A1 - Merkert, Maximilian A1 - Schneider, Oskar T1 - Staircase Compatibility and its Applications in Scheduling and Piecewise Linearization N2 - We consider the clique problem with multiple-choice constraints (CPMC) and characterize a case where it is possible to give an efficient description of the convex hull of its feasible solutions. This case, which we call staircase compatibility, generalizes common properties in applications and allows for a linear description of the integer feasible solutions to (CPMC) with a totally unimodular constraint matrix of polynomial size. We derive two such totally unimodular reformulations for the problem: one that is obtained by a strengthening of the compatibility constraints and one that is based on a representation as a dual network flow problem. Furthermore, we show a natural way to derive integral solutions from fractional solutions to the problem by determining integral extreme points generating this fractional solution. We also evaluate our reformulations from a computational point of view by applying them to two different real-world applications. The first one is a problem in railway timetabling where we try to adapt a given timetable slightly such that energy costs from operating the trains are reduced. The second one is the piecewise linearization of non-linear flow problems on a gas network. In both cases, we are able to reduce the solution times significantly by passing to the theoretically stronger formulations of the problem. KW - Clique Problem KW - Multiple-Choice Constraints KW - Total Unimodularity KW - Scheduling KW - Piecewise Linearization Y1 - 2016 ER - TY - JOUR A1 - Liers, Frauke A1 - Merkert, Maximilian T1 - Structural Investigation of Piecewise Linearized Network Flow Problems N2 - In this work we study polyhedra in the context of network flow problems, where the flow value on each arc lies in one of several predefined intervals. This is motivated by nonlinear problems on transportation networks, where nonlinearities are handled by piecewise linear approximation or relaxation - a common and established approach in many applications. Several methods for modeling piecewise linear functions are known which provide a complete description for a single network arc. However, in general this property is lost when considering multiple arcs. We show how to strengthen the formulation for specific substructures consisting of multiple arcs by linear inequalities. For the case of paths of degree-two-nodes we give a complete description of the polyhedron projected to the integer variables. Our model is based on - but not limited to - the multiple choice method; we also show how to transfer our results to a formulation based on the incremental method. Computational results show that a state-of-the-art MIP-solver greatly benefits from using our cutting planes for random and realistic network topologies. KW - Combinatorial optimization KW - Complete description KW - Network flow problems KW - Piecewise linear functions Y1 - 2016 U6 - https://doi.org/10.1137/15M1006751 VL - 26 SP - 2863 EP - 2886 ER - TY - JOUR A1 - Bärmann, Andreas A1 - Liers, Frauke A1 - Martin, Alexander A1 - Merkert, Maximilian A1 - Thurner, Christoph A1 - Weninger, Dieter T1 - Solving network design problems via iterative aggregation JF - Mathematical Programming Computation N2 - In this work, we present an exact approach for solving network design problems that is based on an iterative graph aggregation procedure. The scheme allows existing preinstalled capacities. Starting with an initial aggregation, we solve a sequence of network design master problems over increasingly fine-grained representations of the original network. In each step, a subproblem is solved that either proves optimality of the solution or gives a directive where to refine the representation of the network in the subsequent iteration. The algorithm terminates with a globally optimal solution to the original problem. Our implementation uses a standard integer programming solver for solving the master problems as well as the subproblems. The computational results on random and realistic instances confirm the profitable use of the iterative aggregation technique. The computing time often reduces drastically when our method is compared to solving the original problem from scratch. KW - Aggregation KW - Network design KW - Combinatorial optimization KW - Mixed-integer programming KW - Branch-and-cut Y1 - 2015 U6 - https://doi.org/10.1007/s12532-015-0079-1 VL - 7 IS - 2 SP - 189 EP - 217 ER - TY - JOUR A1 - Gugat, Martin A1 - Wintergerst, David A1 - Schultz, Rüdiger ED - Iske, Armin T1 - Networks of pipelines for gas with nonconstant compressibility factor: stationary states JF - Computational and Applied Mathematics N2 - For the management of gas transportation networks, it is essential to know how the stationary states of the system are determined by the boundary data. The isothermal Euler equations are an accurate pde-model for the gas flow through each pipe. A compressibility factor is used to model the nonlinear relationship between density and pressure that occurs in real gas in contrast to ideal gas. The gas flow through the nodes is governed by algebraic node conditions that require the conservation of mass and the continuity of the pressure. We examine networks that are described by arbitrary finite graphs and show that for suitably chosen boundary data, subsonic stationary states exist and are uniquely determined by the boundary data. Our construction of the stationary states is based upon explicit representations of the stationary states on each single pipe that can easily be evaluated numerically. We also use the monotonicity properties of these states as functions of the boundary data. Y1 - 2016 U6 - https://doi.org/10.1007/s40314-016-0383-z ER - TY - JOUR A1 - Gugat, Martin A1 - Leugering, Günter ED - Zuazua, Enrique T1 - Time delay in optimal control loops for wave equations JF - ESAIM: COCV N2 - In optimal control loops delays can occur, for example through transmission via digital communication channels. Such delays influence the state that is generated by the implemented control. We study the effect of a delay in the implementation of L 2-norm minimal Neumann boundary controls for the wave equation. The optimal controls are computed as solutions of problems of exact optimal control, that is if they are implemented without delay, they steer the system to a position of rest in a given finite time T. We show that arbitrarily small delays δ > 0 can have a destabilizing effect in the sense that we can find initial states such that if the optimal control u is implemented in the form yx(t, 1) = u(t − δ) for t > δ, the energy of the system state at the terminal time T is almost twice as big as the initial energy. We also show that for more regular initial states, the effect of a delay in the implementation of the optimal control is bounded above in the sense that for initial positions with derivatives of BV-regularity and initial velocities with BV-regularity, the terminal energy is bounded above by the delay δ multiplied with a factor that depends on the BV-norm of the initial data. We show that for more general hyperbolic optimal exact control problems the situation is similar. For systems that have arbitrarily large eigenvalues, we can find terminal times T and arbitrarily small time delays δ, such that at the time T + δ, in the optimal control loop with delay the norm of the state is twice as large as the corresponding norm for the initial state. Moreover, if the initial state satisfies an additional regularity condition, there is an upper bound for the effect of time delay of the order of the delay with a constant that depends on the initial state only. KW - PDE constrained optimization KW - delay KW - wave equation KW - boundary control KW - hyperbolic system Y1 - 2016 U6 - https://doi.org/http://dx.doi.org/10.1051/cocv/2015038 ER - TY - JOUR A1 - Gugat, Martin A1 - Keimer, Alexander A1 - Leugering, Günter A1 - Wang, Zhiqiang ED - Piccoli, Benedetto T1 - Analysis of a system of nonlocal conservation laws for multi-commodity flow on networks JF -  Networks and Heterogeneous Media N2 - We consider a system of scalar nonlocal conservation laws on networks that model a highly re-entrant multi-commodity manufacturing system as encountered in semiconductor production. Every single commodity is mod-eled by a nonlocal conservation law, and the corresponding PDEs are coupled via a collective load, the work in progress. We illustrate the dynamics for two commodities. In the applications, directed acyclic networks naturally occur, therefore this type of networks is considered. On every edge of the network we have a system of coupled conservation laws with nonlocal velocity. At the junctions the right hand side boundary data of the foregoing edges is passed as left hand side boundary data to the following edges and PDEs. For distributing junctions, where we have more than one outgoing edge, we impose time dependent distribution functions that guarantee conservation of mass. We provide results of regularity, existence and well-posedness of the multi-commodity network model for L p-, BV-and W 1,p-data. Moreover, we define an L 2-tracking type objective and show the existence of minimizers that solve the corresponding optimal control problem. KW - conservation laws on network KW - nonlocal conservation laws KW - optimal nodal control KW - systems of hyperbolic pdes Y1 - 2016 U6 - https://doi.org/DOI: 10.3934/nhm.2015.10.749 VL - 10 IS - 4 SP - 749 EP - 785 ER - TY - JOUR A1 - Gottschalk, Corinna A1 - Koster, Arie M.C.A. A1 - Liers, Frauke A1 - Peis, Britta A1 - Schmand, Daniel A1 - Wierz, Andreas T1 - Robust Flows over Time: Models and Complexity Results N2 - We study dynamic network flows with uncertain input data under a robust optimization perspective. In the dynamic maximum flow problem, the goal is to maximize the flow reaching the sink within a given time horizon T, while flow requires a certain travel time to traverse an arc. In our setting, we account for uncertain travel times of flow. We investigate maximum flows over time under the assumption that at most Γ travel times may be prolonged simultaneously due to delay. We develop and study a mathematical model for this problem. As the dynamic robust flow problem generalizes the static version, it is NP-hard to compute an optimal flow. However, our dynamic version is considerably more complex than the static version. We show that it is NP-hard to verify feasibility of a given candidate solution. Furthermore, we investigate temporally repeated flows and show that in contrast to the non-robust case (i.e., without uncertainties) they no longer provide optimal solutions for the robust problem, but rather yield a worst case optimality gap of at least T. We finally show that for infinite delays, the optimality gap is at most O(k log T), where k is a newly introduced instance characteristic. The results obtained in this paper yield a first step towards understanding robust dynamic flow problems with uncertain travel times. KW - Dynamic Network Flows KW - Uncertain Travel Times KW - Dynamic Robust Flow Y1 - 2017 U6 - https://doi.org/10.1007/s10107-017-1170-3 ER - TY - JOUR A1 - Cacchiani, Valentina A1 - Jünger, Michael A1 - Liers, Frauke A1 - Lodi, Andrea A1 - Schmidt, Daniel T1 - Single-commodity robust network design with finite and Hose demand sets JF - Mathematical Programming N2 - We study a single-commodity robust network design problem (sRND) defined on an undirected graph. Our goal is to determine minimum cost capacities such that any traffic demand from a given uncertainty set can be satisfied by a feasible single-commodity flow. We consider two ways of representing the uncertainty set, either as a finite list of scenarios or as a polytope. We propose a branch-and-cut algorithm to derive optimal solutions to sRND, built on a capacity-based integer linear programming formulation. It is strengthened with valid inequalities derived as {0, 1/2}-Chvátal–Gomory cuts. Since the formulation contains exponentially many constraints, we provide practical separation algorithms. Extensive computational experiments show that our approach is effective, in comparison to existing approaches from the literature as well as to solving a flow based formulation by a general purpose solver. KW - Robust network design KW - Branch-and-cut KW - Cut-set inequalities KW - Polyhedral demand uncertainty KW - Separation under uncertainty Y1 - 2016 U6 - https://doi.org/10.1007/s10107-016-0991-9 VL - 157 IS - 1 SP - 297 EP - 342 ER - TY - JOUR A1 - Gugat, Martin ED - Bloch, Anthony M. T1 - Exponential Stabilization of the Wave Equation by Dirichlet Integral Feedback JF - SIAM Journal on Control and Optimization (SICON) N2 - We consider the problem of boundary feedback stabilization of a vibrating string that is fixed at one end and with control action at the other end. In contrast to previous studies that have required L 2-regularity for the initial position and H −1-regularity for the initial velocity, in this paper we allow for initial positions with L 1-regularity and initial velocities in W −1,1 on the space interval. It is well known that for a certain feedback parameter, for sufficiently regular initial states the classical energy of the closed-loop system with Neumann velocity feedback is controlled to zero after a finite time that is equal to the minimal time where exact controllability holds. In this paper, we present a Dirichlet boundary feedback that yields a well-defined closed-loop system in the (L 1 , W −1,1) framework and also has this property. Moreover, for all positive feedback parameters our feedback law leads to exponential decay of a suitably defined L 1-energy. For more regular initial states with (L 2 , H −1) regularity, the proposed feedback law leads to exponential decay of an energy that corresponds to this framework. If the initial states are even more regular with H 1-regularity of the initial position and L 2-regularity of the initial velocity, our feedback law also leads to exponential decay of the classical energy. KW - exponential stability KW - Dirichlet boundary control KW - energy decay KW - exact control Y1 - 2016 U6 - https://doi.org/DOI: 10.1137/140977023 VL - 53 IS - 1 SP - 526 EP - 546 ER - TY - JOUR A1 - Gugat, Martin ED - Khalique, Chaudry T1 - Exact Boundary Controllability for Free Traffic Flow with Lipschitz Continuous State JF - Mathematical Problems in Engineering N2 - We consider traffic flow governed by the LWR model. We show that a Lipschitz continuous initial density with free-flow and sufficiently small Lipschitz constant can be controlled exactly to an arbitrary constant free-flow density in finite time by a piecewise linear boundary control function that controls the density at the inflow boundary if the outflow boundary is absorbing. Moreover, this can be done in such a way that the generated state is Lipschitz continuous. Since the target states need not be close to the initial state, our result is a global exact controllability result. The Lipschitz constant of the generated state can be made arbitrarily small if the Lipschitz constant of the initial density is sufficiently small and the control time is sufficiently long. This is motivated by the idea that finite or even small Lipschitz constants are desirable in traffic flow since they might help to decrease the speed variation and lead to safer traffic. KW - Traffic flow Y1 - 2016 U6 - https://doi.org/doi:10.1155/2016/2743251 Creative Commons Attribution License VL - 2016 IS - 2016 SP - 1 EP - 11 ER - TY - JOUR A1 - Pfaff, Sebastian A1 - Ulbrich, Stefan T1 - Optimal Control of Nonlinear Hyperbolic Conservation Laws by On/Off-Switching JF - Optimization Methods and Software N2 - This paper studies the differentiability properties of the control-to-state mapping for entropy solutions to a scalar hyperbolic conservation law on R with respect to the switching times of an on/off-control. The switching times between on-modes and off-modes are the control variables of the considered optimization problem, where a general tracking-type functional is minimized.We investigate the differentiability of the reduced objective function, also in the presence of shocks. We show that the state y(t,·) at some observation time t depends differentiably on the switching times in a generalized sense that implies total differentiability for the composition with a tracking functional. Furthermore, we present an adjoint-based formula for the gradient of the reduced objective functional with respect to the switching times. KW - optimal control, scalar conservation law, network Y1 - 2017 U6 - https://doi.org/10.1080/10556788.2016.1236796 VL - 32 SP - 904 EP - 939 ER - TY - JOUR A1 - Pfaff, Sebastian A1 - Ulbrich, Stefan T1 - Optimal Boundary Control of Nonlinear Hyperbolic Conservation Laws with Switched Boundary Data JF - SIAM Journal on Control and Optimization N2 - We consider the optimal control of initial-boundary value problems for entropy solutions of scalar hyperbolic conservation laws. In particular, we consider initial-boundary value problems where the initial and boundary data switch between different C¹-functions at certain switching points and both the functions and the switching points are controlled. We show that the control-to-state mapping is differentiable in a certain generalized sense, which implies Fréchet-differentiability with respect to the control functions and the switching points for the composition with a tracking type functional, even in the presence of shocks. We also present an adjoint-based formula for the gradient of the reduced objective functional. KW - optimal control, scalar conservation law, differentiability, adjoint state, shock sensitivity Y1 - 2016 U6 - https://doi.org/10.1137/140995799 VL - 53 IS - 3 SP - 1250 EP - 1277 ER - TY - JOUR A1 - Egger, Herbert A1 - Kugler, Thomas A1 - Strogies, Nikolai T1 - Parameter identification in a semilinear hyperbolic system JF - Inverse Problems N2 - We consider the identification of a nonlinear friction law in a one-dimensional damped wave equation from additional boundary measurements. Well-posedness of the governing semilinear hyperbolic system is established via semigroup theory and con- traction arguments. We then investigte the inverse problem of recovering the unknown nonlinear damping law from additional boundary measurements of the pressure drop along the pipe. This coefficient inverse problem is shown to be ill-posed and a varia- tional regularization method is considered for its stable solution. We prove existence of minimizers for the Tikhonov functional and discuss the convergence of the regularized so- lutions under an approximate source condition. The meaning of this condition and some arguments for its validity are discussed in detail and numerical results are presented for illustration of the theoretical findings Y1 - 2016 VL - 33 IS - 055022 ER - TY - JOUR A1 - Egger, Herbert T1 - A robust conservative mixed finite element method for compressible flow on pipe networks N2 - We consider the numerical approximation of compressible flow in a pipe net- work. Appropriate coupling conditions are formulated that allow us to derive a variational characterization of solutions and to prove global balance laws for the conservation of mass and energy on the whole network. This variational principle, which is the basis of our fur- ther investigations, is amenable to a conforming Galerkin approximation by mixed finite elements. The resulting semi-discrete problems are well-posed and automatically inherit the global conservation laws for mass and energy from the continuous level. We also consider the subsequent discretization in time by a problem adapted implicit time stepping scheme which leads to conservation of mass and a slight dissipation of energy of the full discretization. The well-posedness of the fully discrete scheme is established and a fixed-point iteration is proposed for the solution of the nonlinear systems arising in every single time step. Some computational results are presented for illustration of our theoretical findings and for demon- stration of the robustness and accuracy of the new method Y1 - 2016 ER - TY - INPR A1 - Egger, Herbert A1 - Kugler, Thomas T1 - Uniform exponential stability of Galerkin approximations for damped wave systems N2 - We consider the numerical approximation of linear damped wave systems by Galerkin approximations in space and appropriate time-stepping schemes. Based on a dissipation estimate for a modified energy, we prove exponential decay of the physical energy on the continuous level provided that the damping is effective everywhere in the domain. The methods of proof allow us to analyze also a class of Galerkin approximations based on a mixed variational formulation of the problem. Uniform exponential stabil- ity can be guaranteed for these approximations under a general compatibility condition on the discretization spaces. As a particular example, we discuss the discretization by mixed finite element methods for which we obtain convergence and uniform error esti- mates under minimal regularity assumptions. We also prove unconditional and uniform exponential stability for the time discretization by certain one-step methods. The valid- ity of the theoretical results as well as the necessity of some of the conditions required for our analysis are demonstrated in numerical tests Y1 - 2016 ER - TY - INPR A1 - Egger, Herbert A1 - Kugler, Thomas T1 - Damped wave systems on networks: exponential stability and uniform approximations N2 - We consider a damped linear hyperbolic system modelling the propagation of pressure waves in a network of pipes. Well-posedness is established via semi-group theory and the existence of a unique steady state is proven in the absence of driving forces. Under mild assumptions on the network topology and the model parameters, we show exponential stability and convergence to equilibrium. This generalizes related results for single pipes and multi-dimensional domains to the network context. Our proof of the exponential stability estimate is based on a variational formulation of the problem, some graph theoretic results, and appropriate energy estimates. The main arguments are rather generic and can be applied also for the analysis of Galerkin approximations. Uniform exponential stability can be guaranteed for the resulting semi-discretizations under mild compatibility conditions on the approximation spaces. A particular realiza- tion by mixed finite elements is discussed and the theoretical results are illustrated by numerical tests in which also bounds for the decay rate are investigated. Y1 - 2016 ER - TY - CHAP A1 - Lu, Yi A1 - Marheineke, Nicole A1 - Mohring, Jan T1 - Stability-Preserving Interpolation Strategy for Parametric MOR of Gas Pipeline-Networks N2 - Optimization and control of large transient gas networks require the fast simulation of the underlying parametric partial differential algebraic systems. Sur- rogate modeling techniques based on linearization around specific stationary states, spatial semi-discretization and model order reduction allow for the set-up of para- metric reduced order models that can act as basis sample to cover a wide parameter range by means of matrix interpolations. However, the interpolated models are often not stable. In this paper, we develop a stability-preserving interpolation method. Y1 - 2016 ER - TY - JOUR A1 - Gugat, Martin A1 - Leugering, Günter A1 - Hante, Falk ED - Piccoli, Benedetto T1 - Stationary States in Gas Networks JF - Networks and Heterogeneous Media N2 - Pipeline networks for gas transportation often contain circles. For such networks it is more difficult to determine the stationary states than for networks without circles. We present a method that allows to compute the stationary states for subsonic pipe flow governed by the isothermal Euler equations for certain pipeline networks that contain circles. We also show that suitably chosen boundary data determine the stationary states uniquely. The construction is based upon novel explicit representations of the stationary states on single pipes for the cases with zero slope and with nonzero slope. In the case with zero slope, the state can be represented using the Lambert-W function. KW - Network Y1 - 2016 U6 - https://doi.org/doi:10.3934/nhm.2015.10.295 VL - 10 IS - 2 SP - 295 EP - 320 ER - TY - CHAP A1 - Lu, Yi A1 - Marheineke, Nicole A1 - Mohring, Jan T1 - MOR via quadratic-linear representation of nonlinear-parametric PDEs N2 - This work deals with the model order reduction (MOR) of a nonlinear- parametric system of partial differential equations (PDEs). Applying a semidis- cretization in space and replacing the nonlinearities by introducing new state vari- ables, we set up quadratic-linear differential algebraic systems (QLDAE) and use a Krylov-subspace MOR. The approach is investigated for gas pipeline modeling Y1 - 2016 ER - TY - CHAP A1 - Lu, Yi A1 - Marheineke, Nicole A1 - Mohring, Jan T1 - Interpolation strategy for BT-based parametric MOR of gas pipeline-networks N2 - Proceeding from balanced truncation-based parametric reduced order models (BT-pROM) a matrix interpolation strategy is presented that allows the cheap evaluation of reduced order models at new parameter sets. The method ex- tends the framework of model order reduction (MOR) for high-order parameter- dependent linear time invariant systems in descriptor form by Geuss (2013) by treating not only permutations and rotations but also distortions of reduced order basis vectors. The applicability of the interpolation strategy and different variants is shown on BT-pROMs for gas transport in pipeline-networks Y1 - 2016 ER - TY - JOUR A1 - Geißler, Björn A1 - Morsi, Antonio A1 - Schewe, Lars A1 - Schmidt, Martin T1 - Solving Power-Constrained Gas Transportation Problems using an MIP-based Alternating Direction Method JF - Computers & Chemical Engineering N2 - We present a solution algorithm for problems from steady-state gas transport optimization. Due to nonlinear and nonconvex physics and engineering models as well as discrete controllability of active network devices, these problems lead to difficult nonconvex mixed-integer nonlinear optimization models. The proposed method is based on mixed-integer linear techniques using piecewise linear relaxations of the nonlinearities and a tailored alternating direction method. Most other publications in the field of gas transport optimization only consider pressure and flow as main physical quantities. In this work, we additionally incorporate heat power supplies and demands as well as a mixing model for different gas qualities. We demonstrate the capabilities of our method on Germany's largest transport networks and hereby present numerical results on the largest instances that were ever reported in the literature for this problem class. Y1 - 2016 U6 - https://doi.org/10.1016/j.compchemeng.2015.07.005 VL - 82 IS - 2 SP - 303 EP - 317 ER - TY - JOUR A1 - Sirvent, Mathias A1 - Kanelakis, Nikolaos A1 - Geißler, Björn A1 - Biskas, Pandelis T1 - A Linearized Model for the Optimization of the Coupled Electricity and Natural Gas System JF - Journal of Modern Power Systems and Clean Energy N2 - In the following paper a combined optimization of a coupled electricity and gas system is presented. For the electricity network a unit commitment problem with optimization of energy and reserves under a power pool, considering all system operational and unit technical constraints is solved. The gas network subproblem is a medium-scale mixed-integer nonconvex and nonlinear programming problem. The coupling constraints between the two networks are nonlinear as well. The resulting mixed-integer nonlinear program is linearized with the extended incremental method and an outer approximation technique. The resulting model is evaluated using the Greek power and gas system comprising fourteen gas-fired units under four different approximation accuracy levels. The results indicate the efficiency of the proposed MIP model and the interplay between computational requirements and accuracy. KW - Electricity System KW - Natural Gas System KW - Mixed-Integer (Non)Linear Programming KW - Extended Incremental Method KW - Outer Approximation Y1 - 2017 U6 - https://doi.org/10.1007/s40565-017-0275-2 VL - 5 IS - 3 SP - 364 EP - 374 ER - TY - JOUR A1 - Gugat, Martin A1 - Leugering, Günter A1 - Martin, Alexander A1 - Schmidt, Martin A1 - Sirvent, Mathias A1 - Wintergerst, David T1 - Towards Simulation Based Mixed-Integer Optimization with Differential Equations JF - Networks N2 - We propose a decomposition based method for solving mixed-integer nonlinear optimization problems with “black-box” nonlinearities, where the latter, e.g., may arise due to differential equations or expensive simulation runs. The method alternatingly solves a mixed-integer linear master problem and a separation problem for iteratively refining the mixed-integer linear relaxation of the nonlinear equalities. The latter yield nonconvex feasible sets for the optimization model but we have to restrict ourselves to convex and monotone constraint functions. Under these assumptions, we prove that our algorithm finitely terminates with an approximate feasible global optimal solution of the mixed integer nonlinear problem. Additionally, we show the applicability of our approach for three applications from optimal control with integer variables, from the field of pressurized flows in pipes with elastic walls, and from steady-state gas transport. For the latter we also present promising numerical results of our method applied to real-world instances that particularly show the effectiveness of our method for problems defined on networks. KW - Mixed-Integer Optimization KW - Simulation Based Optimization KW - Optimization with Differential Equations KW - Decomposition Method KW - Gas Transport Networks Y1 - 2018 U6 - https://doi.org/10.1002/net.21812 ER - TY - JOUR A1 - Rüffler, Fabian A1 - Hante, Falk T1 - Optimal Switching for Hybrid Semilinear Evolutions JF - Nonlinear Analysis: Hybrid Systems Y1 - 2016 U6 - https://doi.org/10.1016/j.nahs.2016.05.001 VL - 22 SP - 215 EP - 227 ER - TY - INPR A1 - Wintergerst, David A1 - Gugat, Martin T1 - Finite Time Blow-up of Traveling Wave Solutions for the Flow of Real Gas through Pipeline Networks N2 - In the context of gas transportation, analytical solutions are essential for the understanding of the underlying dynamics described by a system of partial differential equations. We derive traveling wave solutions for the 1-d isothermal Euler equations. A non-constant compressibility factor is used to describe the correlation between density and pressure. The blow-up of the traveling wave solution in � finite time is proven. We then extend our analysis to networks under appropriate coupling conditions and derive compatibility conditions to fulfill these coupling conditions. KW - isothermal Euler equations KW - real gas KW - finite time blow-up KW - traveling waves KW - networks Y1 - 2016 ER - TY - INPR A1 - Mehrmann, Volker A1 - Stolwijk, Jeroen J. T1 - Error Analysis for the Euler Equations in Purely Algebraic Form N2 - The presented work contains both a theoretical and a statistical error analysis for the Euler equations in purely algebraic form, also called the Weymouth equations or the temperature dependent algebraic model. These equations are obtained by performing several simplifications of the full Euler equations, which model the gas flow through a pipeline. The theoretical analysis is executed by first calculating the backward error and then the individual relative condition numbers. This error analysis results in a statement about the maximum pipeline length such that the algebraic model can be used safely. The statistical analysis is performed using both a Monte Carlo Simulation and the Univariate Reduced Quadrature Method and is used to illustrate and confirm the obtained theoretical results. KW - error analysis KW - measurement error KW - condition number KW - backward error KW - statistical analysis Y1 - 2015 ER -