TY - INPR A1 - Gugat, Martin A1 - Habermann, Jens A1 - Hintermüller, Michael A1 - Huber, Olivier T1 - Constrained exact boundary controllability of a semilinear model for pipeline gas flow N2 - While the quasilinear isothermal Euler equations are an excellent model for gas pipeline flow, the operation of the pipeline flow with high pressure and small Mach numbers allows us to obtain approximate solutions by a simpler semilinear model. We provide a derivation of the semilinear model that shows that the semilinear model is valid for sufficiently low Mach numbers and sufficiently high pressures. We prove an existence result for continuous solutions of the semilinear model that takes into account lower and upper bounds for the pressure and an upper bound for the magnitude of the Mach number of the gas flow. These state constraints are important both in the operation of gas pipelines and to guarantee that the solution remains in the set where the model is physically valid. We show the constrained exact boundary controllability of the system with the same pressure and Mach number constraints. Y1 - 2021 ER - TY - INPR A1 - Grübel, Julia A1 - Huber, Olivier A1 - Hümbs, Lukas A1 - Klimm, Max A1 - Schmidt, Martin A1 - Schwartz, Alexandra T1 - Nonconvex Equilibrium Models for Energy Markets: Exploiting Price Information to Determine the Existence of an Equilibrium N2 - Motivated by examples from the energy sector, we consider market equilibrium problems (MEPs) involving players with nonconvex strategy spaces or objective functions, where the latter are assumed to be linear in market prices. We propose an algorithm that determines if an equilibrium of such an MEP exists and that computes an equilibrium in case of existence. Three key prerequisites have to be met. First, appropriate bounds on market prices have to be derived from necessary optimality conditions of some players. Second, a technical assumption is required for those prices that are not uniquely determined by the derived bounds. Third, nonconvex optimization problems have to be solved to global optimality. We test the algorithm on well-known instances from the power and gas literature that meet these three prerequisites. There, nonconvexities arise from considering the transmission system operator as an additional player besides producers and consumers who, e.g., switches lines or faces nonlinear physical laws. Our numerical results indicate that equilibria often exist, especially for the case of continuous nonconvexities in the context of gas market problems. KW - Energy markets KW - Nonconvex games KW - Existence KW - Equilibrium computation KW - Perfect competition Y1 - 2021 ER - TY - JOUR A1 - Bárcena-Petisco, J.A. A1 - Cavalcante, M. A1 - Coclite, G.M. A1 - de Nitti, N. A1 - Zuazua, E. T1 - Control of Hyperbolic and Parabolic Equations on Networks and Singular limits N2 - We study the controllability properties of the transport equation and of parabolic equations posed on a tree. Using a control localized on the exterior nodes, we prove that the hyperbolic and the parabolic systems are null-controllable. The hyperbolic proof relies on the method of characteristics, the parabolic one on duality arguments and Carleman inequalities. We also show that the parabolic system may not be controllable if we do not act on all exterior vertices because of symmetries. Moreover, we estimate the cost of the null-controllability of transport-diffusion equations with diffusivity ε > 0ε>0 and study its asymptotic behavior when ε → 0^+ε→0 + . We prove that the cost of the controllability decays for a time sufficiently large and explodes for short times. This is done by duality arguments allowing to reduce the problem to obtain observability estimates which depend on the viscosity parameter. These are derived by using Agmon and Carleman inequalities. Y1 - 2021 ER - TY - THES A1 - Nowak, Daniel T1 - Nonconvex Nash Games - Solution Concepts and Algorithms N2 - Game theory is a mathematical approach to model competition between several parties, called players. The goal of each player is to choose a strategy, which solves his optimization problem, i.e. minimizes or maximizes his objective function. Due to the competitive setting, this strategy may influence the optimization problems of other players. In the non-cooperative setting each player acts selfish, meaning he does not care about the objective of his opponents. A solution concept for this problem is a Nash equilibrium, which was introduced by John Forbes Nash in his Ph.D. thesis in 1950. Convexity of the optimization problems is a crucial assumption for the existence of Nash equilibria. This work investigates settings, where this convexity assumption fails to hold. The first part of this thesis extends results of Jong-Shi Pang and Gesualdo Scutari from their paper ``Nonconvex Games with Side Constraints'' published in 2011. In this publication, a game with possibly nonconvex objective functions and nonconvex individual and shared inequality constraints was investigated. We extend these results twofold. Firstly, we generalize the individual and shared polyhedral constraints to general convex constraints and, secondly, we introduce convex and nonconvex, individual and shared equality constraints. After a detailed comparison of solution concepts for the generalized Nash game and a related Nash game, we show that so-called quasi-Nash equilibria exist under similar assumptions than in the original work, provided some additional constraint qualification holds. Subsequently, we prove that the existence of Nash equilibria needs additional assumptions on the gradients of the equality constraints. Furthermore, a special case of a multi-leader multi-follower game is investigated. We show the convergence of epsilon-quasi-Nash equilibria to C-stationary points and prove that these are also Clarke-stationary under reasonable assumptions. In the second part of this thesis, an application in computation offloading is investigated. We consider several mobile users that are able to offload parts of a computation task to a connected server. However, the server has limited computation capacities which leads to competition among the mobile users. If a user decides to offload a part of his computation, he needs to wait for the server to finish before he can assemble the results of his computation. This leads to a vanishing constraint in the optimization problem of the mobile users which is a nonconvex and nonsmooth condition. We show the existence of a unique Nash equilibrium for the computation offloading game and provide an efficient algorithm for its computation. Furthermore, we present two extensions to this game, which inherit similar properties and we also show the limitations of these formulations. The third part investigates a hierarchical constrained Cournot game. In the upper level, several firms decide on capacities which act as constraints for the production variables. In the lower level the same firms engage in a Cournot competition, where they choose production variables to maximize profit. The prior chosen capacities are upper bounds on these production variables. This hierarchical setting induces nonconvexity and nonsmoothness in the upper level objective functions. After a detailed sensitivity analysis of the lower level, we give necessary optimality conditions for the upper level, i.e. for the hierarchical Cournot game. Using these conditions, we construct an algorithm which provably finds all Nash equilibria of the game, provided some assumptions are satisfied. This algorithm is numerically tested on several examples which are motivated by the gas market. KW - Game Theory KW - Nash Games KW - Optimization Y1 - 2021 U6 - https://doi.org/10.26083/tuprints-00017637 PB - E-Publishing-Service der TU Darmstadt CY - Darmstadt ER - TY - JOUR A1 - Krug, Richard A1 - Leugering, Günter A1 - Martin, Alexander A1 - Schmidt, Martin A1 - Weninger, Dieter T1 - Time-Domain Decomposition for Optimal Control Problems Governed by Semilinear Hyperbolic Systems with Mixed Two-Point Boundary Conditions JF - Control and Cybernetics N2 - In this article, we continue our work (Krug et al., 2021) on time-domain decomposition of optimal control problems for systems of semilinear hyperbolic equations in that we now consider mixed two-point boundary value problems and provide an in-depth well-posedness analysis. The more general boundary conditions significantly enlarge the scope of applications, e.g., to hyperbolic problems on metric graphs with cycles. We design an iterative method based on the optimality systems that can be interpreted as a decomposition method for the original optimal control problem into virtual control problems on smaller time domains. KW - Time-domain decomposition KW - Optimal control KW - Semilinear hyperbolic systems KW - Convergence Y1 - 2021 ER - TY - JOUR A1 - Kleinert, Thomas A1 - Manns, Julian A1 - Schmidt, Martin A1 - Weninger, Dieter T1 - Presolving Linear Bilevel Optimization Problems JF - EURO Journal on Computational Optimization N2 - Linear bilevel optimization problems are known to be strongly NP-hard and the computational techniques to solve these problems are often motivated by techniques from single-level mixed-integer optimization. Thus, during the last years and decades many branch-and-bound methods, cutting planes, or heuristics have been proposed. On the other hand, there is almost no literature on presolving linear bilevel problems although presolve is a very important ingredient in state-of-the-art mixed-integer optimization solvers. In this paper, we carry over standard presolve techniques from single-level optimization to bilevel problems and show that this needs to be done with great caution since a naive application of well-known techniques does often not lead to correctly presolved bilevel models. Our numerical study shows that presolve can also be very beneficial for bilevel problems but also highlights that these methods have a more heterogeneous effect on the solution process compared to what is known from single-level optimization. As a side result, our numerical experiments reveal that there is an urgent need for better and more heterogeneous test instance libraries to further propel the field of computational bilevel optimization. KW - Linear Bilevel Optimization KW - Presolve KW - Computational Analysis Y1 - 2021 U6 - https://doi.org/10.1016/j.ejco.2021.100020 IS - 9 ER - TY - INPR A1 - Egerer, Jonas A1 - Grimm, Veronika A1 - Grübel, Julia A1 - Zöttl, Gregor T1 - Long-run market equilibria in coupled energy sectors: A study of uniqueness N2 - We propose an equilibrium model for coupled markets of multiple energy sectors. The agents in our model are operators of sector-specific production and sector-coupling technologies, as well as price-sensitive consumers with varying demand. We analyze long-run investment in production capacity in each sector and investment in coupling capacity between sectors, as well as production decisions determined at repeated spot markets. We show that in our multi-sector model, multiplicity of equilibria may occur, even if all assumptions hold that would be sufficient for uniqueness in a single-sector model. We then contribute to the literature by deriving sufficient conditions for the uniqueness of short- and long-run market equilibrium in coupled markets of multiple energy sectors. We illustrate via simple examples that these conditions are indeed required to guarantee uniqueness in general. The uniqueness result is an important step to be able to incorporate the proposed market equilibrium problem in more complex computational multilevel equilibrium models, in which uniqueness of lower levels is a prerequisite for obtaining meaningful solutions. Our analysis also paves the way to understand and analyze more complex sector coupling models in the future. KW - Energy Markets KW - Sector Coupling KW - Regional Pricing KW - Uniqueness KW - Short- and Long-Run Market Equilibrium Y1 - 2021 ER - TY - JOUR A1 - Ruiz-Balet, Domenec A1 - Zuazua, Enrique T1 - Neural ODE Control for Classification, Approximation and Transport N2 - We analyze Neural Ordinary Differential Equations (NODEs) from a control theoretical perspective to address some of the main properties and paradigms of Deep Learning (DL), in particular, data classification and universal approximation. These objectives are tackled and achieved from the perspective of the simultaneous control of systems of NODEs. For instance, in the context of classification, each item to be classified corresponds to a different initial datum for the control problem of the NODE, to be classified, all of them by the same common control, to the location (a subdomain of the euclidean space) associated to each label. Our proofs are genuinely nonlinear and constructive, allowing us to estimate the complexity of the control strategies we develop. The nonlinear nature of the activation functions governing the dynamics of NODEs under consideration plays a key role in our proofs, since it allows deforming half of the phase space while the other half remains invariant, a property that classical models in mechanics do not fulfill. This very property allows to build elementary controls inducing specific dynamics and transformations whose concatenation, along with properly chosen hyperplanes, allows achieving our goals in finitely many steps. The nonlinearity of the dynamics is assumed to be Lipschitz. Therefore, our results apply also in the particular case of the ReLU activation function. We also present the counterparts in the context of the control of neural transport equations, establishing a link between optimal transport and deep neural networks. KW - data classification KW - Neural ODEs KW - Optimal Transport KW - simultaneous control KW - deep learning Y1 - 2021 ER - TY - THES A1 - Kleinert, Thomas T1 - Algorithms for Mixed-Integer Bilevel Problems with Convex Followers N2 - Bilevel problems are optimization problems for which a subset of variables is constrained to be an optimal solution of another optimization problem. As such, bilevel problems are capable of modeling hierarchical decision processes. This is required by many real-world problems from a broad spectrum of applications such as energy markets, traffic planning, or critical infrastructure defense, to name only a few. However, the hierarchy of decisions makes bilevel optimization problems also very challenging to solve—both in theory and practice. This cumulative PhD thesis is concerned with computational bilevel optimization. In the first part, we summarize several solution approaches that we developed over the last years and highlight the significant computational progress that these methods provide. For linear bilevel problems, we review branch-and-bound methods, critically discuss their practical use, and propose valid inequalities to extend the methods to branch-and-cut approaches. Further, we demonstrate on a large test set that it is no longer necessary to use the well-known but error-prone big-M reformulation to solve linear bilevel problems. We also present a bilevel-specific heuristic that is based on a penalty alternating direction method. This heuristic is applicable to a broad class of bilevel problems, e.g., linear or mixed-integer quadratic bilevel problems. In a computational study, we show that the method computes optimal or close-to-optimal feasible points in a very short time and that it outperforms a state-of-the-art local method from the literature. Finally, we review global approaches for mixed-integer quadratic bilevel problems. In addition to a Benders-like decomposition, we present a multi-tree and a single-tree outer-approximation approach. A computational evaluation demonstrates that both variants outperform known benchmark algorithms. The second part of this thesis consists of reprints of our original articles and preprints. These articles contain all details and are referenced throughout the first part of the thesis. Y1 - 2021 ER - TY - JOUR A1 - Esteve, Carlos A1 - Geshkovski, Borjan A1 - Pighin, Dario A1 - Zuazua, Enrique T1 - Turnpike in Lipschitz-nonlinear optimal control N2 - We present a new proof of the turnpike property for nonlinear optimal control problems, when the running target is a steady control-state pair of the underlying dynamics. Our strategy combines the construction of suboptimal quasi-turnpike trajectories via controllability, and a bootstrap argument, and does not rely on analyzing the optimality system or linearization techniques. This in turn allows us to address several optimal control problems for finite-dimensional, control-affine systems with globally Lipschitz (possibly nonsmooth) nonlinearities, without any smallness conditions on the initial data or the running target. These results are motivated by the large-layer regime of residual neural networks, commonly used in deep learning applications. We show that our methodology is applicable to controlled PDEs as well, such as the semilinear wave and heat equation with a globally Lipschitz nonlinearity, once again without any smallness assumptions. Y1 - ER - TY - JOUR A1 - Krug, Richard A1 - Leugering, Günter A1 - Martin, Alexander A1 - Schmidt, Martin A1 - Weninger, Dieter T1 - Time-Domain Decomposition for Optimal Control Problems Governed by Semilinear Hyperbolic Systems JF - SIAM Journal on Control and Optimization N2 - In this article, we extend the time-domain decomposition method described by Lagnese and Leugering (2003) to semilinear optimal control problems for hyperbolic balance laws with spatio-temporal varying coefficients. We provide the design of the iterative method applied to the global first-order optimality system, prove its convergence, and derive an a posteriori error estimate. The analysis is done entirely on the continuous level. A distinguishing feature of the method is that the decomposed optimality system can be interpreted as an optimality system of a local "virtual" optimal control problem. Thus, the iterative time-domain decomposition of the optimality system can be interpreted as an iterative parallel scheme for virtual optimal control problems on the subintervals. A typical example and further comments are given to show the range of potential applications. Moreover, we provide some numerical experiments to give a first interpretation of the role of the parameters involved in the iterative process. KW - Time-domain decomposition KW - Optimal control KW - Semilinear hyperbolic systems KW - Convergence KW - A posteriori error estimates Y1 - 2020 ER - TY - JOUR A1 - Kleinert, Thomas A1 - Labbé, Martine A1 - Ljubić, Ivana A1 - Schmidt, Martin T1 - A Survey on Mixed-Integer Programming Techniques in Bilevel Optimization JF - EURO Journal on Computational Optimization N2 - Bilevel optimization is a field of mathematical programming in which some variables are constrained to be the solution of another optimization problem. As a consequence, bilevel optimization is able to model hierarchical decision processes. This is appealing for modeling real-world problems, but it also makes the resulting optimization models hard to solve in theory and practice. The scientific interest in computational bilevel optimization increased a lot over the last decade and is still growing. Independent of whether the bilevel problem itself contains integer variables or not, many state-of-the-art solution approaches for bilevel optimization make use of techniques that originate from mixed-integer programming. These techniques include branch-and-bound methods, cutting planes and, thus, branch-and-cut approaches, or problem-specific decomposition methods. In this survey article, we review bilevel-tailored approaches that exploit these mixed-integer programming techniques to solve bilevel optimization problems. To this end, we first consider bilevel problems with convex or, in particular, linear lower-level problems. The discussed solution methods in this field stem from original works from the 1980's but, on the other hand, are still actively researched today. Second, we review modern algorithmic approaches to solve mixed-integer bilevel problems that contain integrality constraints in the lower level. Moreover, we also briefly discuss the area of mixed-integer nonlinear bilevel problems. Third, we devote some attention to more specific fields such as pricing or interdiction models that genuinely contain bilinear and thus nonconvex aspects. Finally, we sketch a list of open questions from the areas of algorithmic and computational bilevel optimization, which may lead to interesting future research that will further propel this fascinating and active field of research. KW - Bilevel optimization KW - Mixed-integer programming KW - Applications KW - Branch-and-bound KW - Branch-and-cut Y1 - 2021 ER - TY - INPR A1 - Thürauf, Johannes T1 - Deciding the Feasibility of a Booking in the European Gas Market is coNP-hard N2 - We show that deciding the feasibility of a booking (FB) in the European entry-exit gas market is coNP-hard if a nonlinear potential-based flow model is used. The feasibility of a booking can be characterized by polynomially many load flow scenarios with maximum potential-difference, which are computed by solving nonlinear potential-based flow models. We use this existing characterization of the literature to prove that FB is coNP-hard by reducing Partition to the infeasibility of a booking. We further prove that computing a potential-difference maximizing load flow scenario is NP-hard even if we can determine the flow direction a priori. From the literature, it is known that FB can be decided in polynomial time on trees and a single cycle. Thus, our hardness result draws the first line that separates the easy from the hard variants of FB and finally answers that FB is hard in general. KW - Potential-based flows, Gas networks, Computational complexity, European entry-exit market, Bookings Y1 - 2020 ER - TY - JOUR A1 - Kleinert, Thomas A1 - Labbé, Martine A1 - Schmidt, Martin A1 - Plein, Fränk T1 - Closing the Gap in Linear Bilevel Optimization: A New Valid Primal-Dual Inequality JF - Optimization Letters N2 - Linear bilevel optimization problems are often tackled by replacing the linear lower-level problem with its Karush–Kuhn–Tucker (KKT) conditions. The resulting single-level problem can be solved in a branch-and-bound fashion by branching on the complementarity constraints of the lower-level problem’s optimality conditions. While in mixed-integer single-level optimization branch-and-cut has proven to be a powerful extension of branch-and-bound, in linear bilevel optimization not too many bilevel-tailored valid inequalities exist. In this paper, we briefly review existing cuts for linear bilevel problems and introduce a new valid inequality that exploits the strong duality condition of the lower level. We further discuss strengthened variants of the inequality that can be derived from McCormick envelopes. In a computational study, we show that the new valid inequalities can help to close the optimality gap very effectively on a large test set of linear bilevel instances. Y1 - 2020 IS - 15 SP - 1027 EP - 1040 ER - TY - JOUR A1 - Böttger, Tom A1 - Grimm, Veronika A1 - Kleinert, Thomas A1 - Schmidt, Martin T1 - The Cost of Decoupling Trade and Transport in the European Entry-Exit Gas Market with Linear Physics Modeling JF - European Journal of Operational Research N2 - Liberalized gas markets in Europe are organized as entry-exit regimes so that gas trade and transport are decoupled. The decoupling is achieved via the announcement of technical capacities by the transmission system operator (TSO) at all entry and exit points of the network. These capacities can be booked by gas suppliers and customers in long-term contracts. Only traders who have booked capacities up-front can "nominate" quantities for injection or withdrawal of gas via a day-ahead market. To ensure feasibility of the nominations for the physical network, the TSO must only announce technical capacities for which all possibly nominated quantities are transportable. In this paper, we use a four-level model of the entry-exit gas market to analyze possible welfare losses associated with the decoupling of gas trade and transport. In addition to the multilevel structure, the model contains robust aspects to cover the conservative nature of the European entry-exit system. We provide several reformulations to obtain a single-level mixed-integer quadratic problem. The overall model of the considered market regime is extremely challenging and we thus have to make the main assumption that gas flows are modeled as potential-based linear flows. Using the derived single-level reformulation of the problem, we show that the feasibility requirements for technical capacities imply significant welfare losses due to unused network capacity. Furthermore, we find that the specific structure of the network has a considerable influence on the optimal choice of technical capacities. Our results thus show that trade and transport are not decoupled in the long term. As a further source of welfare losses and discrimination against individual actors, we identify the minimum prices for booking capacity at the individual nodes. KW - Entry-Exit Gas Market KW - Gas Market Design KW - Multilevel Optimization KW - Robust Optimization Y1 - 2020 ER - TY - INPR A1 - Grimm, Veronika A1 - Nowak, Daniel A1 - Schewe, Lars A1 - Schmidt, Martin A1 - Schwartz, Alexandra A1 - Zöttl, Gregor T1 - A Tractable Multi-Leader Multi-Follower Peak-Load-Pricing Model with Strategic Interaction N2 - While single-level Nash equilibrium problems are quite well understood nowadays, less is known about multi-leader multi-follower games. However, these have important applications, e.g., in the analysis of electricity and gas markets, where often a limited number of firms interacts on various subsequent markets. In this paper, we consider a special class of two-level multi-leader multi-follower games that can be applied, e.g., to model strategic booking decisions in the European entry-exit gas market. For this nontrivial class of games, we develop a solution algorithm that is able to compute the complete set of Nash equilibria instead of just individual solutions or a bigger set of stationary points. Additionally, we prove that for this class of games, the solution set is finite and provide examples for instances without any Nash equilibria in pure strategies. We apply the algorithm to a case study in which we compute strategic booking and nomination decisions in a model of the European entry-exit gas market system. Finally, we use our algorithm to provide a publicly available test library for the considered class of multi-leader multi-follower games. This library contains problem instances with different economic and mathematical properties so that other researchers in the field can test and benchmark newly developed methods for this challenging class of problems. KW - Game theory KW - Nash-Cournot equilibria KW - Multi-leader multi-follower game KW - Peak-load pricing Y1 - 2020 U6 - https://doi.org/10.1007/s10107-021-01708-0 ER - TY - JOUR A1 - Gugat, Martin A1 - Hante, Falk A1 - Jin, Li T1 - Closed loop control of gas flow in a pipe: Stability for a transient model JF - at - Automatisierungstechnik N2 - This contribution focuses on the analysis and control of friction-dominated flow of gas in pipes. The pressure in the gas flow is governed by a partial differential equation that is a doubly nonlinear parabolic equation of p-Laplace type, where p=2/3. Such equations exhibit positive solutions, finite speed of propagation and satisfy a maximum principle. The pressure is fixed on one end (upstream), and the flow is specified on the other end (downstream). These boundary conditions determine a unique steady equilibrium flow. We present a boundary feedback flow control scheme, that ensures local exponential stability of the equilibrium in an L2-sense. The analysis is done both for the pde system and an ode system that is obtained by a suitable spatial semi-discretization. The proofs are based upon suitably chosen Lyapunov functions. Y1 - 2020 ER - TY - INPR A1 - Biefel, Christian A1 - Liers, Frauke A1 - Rolfes, Jan A1 - Schmidt, Martin T1 - Affinely Adjustable Robust Linear Complementarity Problems N2 - Linear complementarity problems are a powerful tool for modeling many practically relevant situations such as market equilibria. They also connect many sub-areas of mathematics like game theory, optimization, and matrix theory. Despite their close relation to optimization, the protection of LCPs against uncertainties - especially in the sense of robust optimization - is still in its infancy. During the last years, robust LCPs have only been studied using the notions of strict and Γ-robustness. Unfortunately, both concepts lead to the problem that the existence of robust solutions cannot be guaranteed. In this paper, we consider affinely adjustable robust LCPs. In the latter, a part of the LCP solution is allowed to adjust via a function that is affine in the uncertainty. We show that this notion of robustness allows to establish strong characterizations of solutions for the cases of uncertain matrix and vector, separately, from which existence results can be derived. Our main results are valid for the case of an uncertain LCP vector. Here, we additionally provide sufficient conditions on the LCP matrix for the uniqueness of a solution. Moreover, based on characterizations of the affinely adjustable robust solutions, we derive a mixed-integer programming formulation that allows to solve the corresponding robust counterpart. If, in addition, the certain LCP matrix is positive semidefinite, we prove polynomial-time solvability and uniqueness of robust solutions. If the LCP matrix is uncertain, characterizations of solutions are developed for every nominal matrix, i.e., these characterizations are, in particular, independent of the definiteness of the nominal matrix. Robust solutions are also shown to be unique for positive definite LCP matrix but both uniqueness and mixed-integer programming formulations still remain open problems if the nominal LCP matrix is not positive definite. KW - Linear Complementarity Problems KW - Adjustable Robustness KW - Robust Optimization KW - Existence KW - Uniqueness Y1 - 2020 ER - TY - THES A1 - Manns, Julian T1 - Presolve of Linear Bilevel Programs N2 - Bilevel programs are complex optimization problems that can be used to model hierarchical decision processes, which occur e.g. in energy markets, critical infrastructure defense or pricing models. Even the most simple bilevel programs, where only linear objective functions and constraints appear, are non-convex optimization problems and equivalent single level formulations replace the lower level problem by its non-convex optimality constraints. This makes linear bilevel programs inherently difficult so solve. The simplification of mixed-integer linear programs before solving them, called presolve, significantly accelerated the solving of these problems. However, there is only very few literature on the topic of presolve of bilevel programs. In this thesis we review said literature on presolve of bilevel programs in the context of linear bilevel programming, derive new theoretical foundations for presolve of linear bilevel programs and then apply these results to analyze how common presolve techniques for linear and mixed integer programs can be used to presolve linear bilevel programs. Y1 - 2020 ER - TY - JOUR A1 - Schewe, Lars A1 - Schmidt, Martin A1 - Thürauf, Johannes T1 - Global Optimization for the Multilevel European Gas Market System with Nonlinear Flow Models on Trees JF - Journal of Global Optimization N2 - The European gas market is implemented as an entry-exit system, which aims to decouple transport and trading of gas. It has been modeled in the literature as a multilevel problem, which contains a nonlinear flow model of gas physics. Besides the multilevel structure and the nonlinear flow model, the computation of so-called technical capacities is another major challenge. These lead to nonlinear adjustable robust constraints that are computationally intractable in general. We provide techniques to equivalently reformulate these nonlinear adjustable constraints as finitely many convex constraints including integer variables in the case that the underlying network is tree-shaped. We further derive additional combinatorial constraints that significantly speed up the solution process. Using our results, we can recast the multilevel model as a single-level nonconvex mixed-integer nonlinear problem, which we then solve on a real-world network, namely the Greek gas network, to global optimality. Overall, this is the first time that the considered multilevel entry-exit system can be solved for a real-world sized network and a nonlinear flow model. Y1 - 2020 U6 - https://doi.org/10.1007/s10898-021-01099-8 ER - TY - INPR A1 - Aigner, Kevin-Martin A1 - Burlacu, Robert A1 - Liers, Frauke A1 - Martin, Alexander T1 - Solving AC Optimal Power Flow with Discrete Decisions to Global Optimality N2 - We present a solution framework for general alternating current optimal power flow (AC OPF) problems that include discrete decisions. The latter occur, for instance, in the context of the curtailment of renewables or the switching of power generation units and transmission lines. Our approach delivers globally optimal solutions and is provably convergent. We model AC OPF problems with discrete decisions as mixed-integer nonlinear programs. The solution method starts from a known framework that uses piecewise linear relaxations. These relaxations are modeled as as mixed-integer linear programs and adaptively refined until some termination criterion is fulfilled. In this work, we extend and complement this approach by problem-specific as well as very general algorithmic enhancements. In particular, these are mixed-integer second-order cone programs as well as primal and dual cutting planes. For example objective cuts and no-good-cuts help to compute good feasible solutions as where outer approximation constraints tighten the relaxations. We present extensive numerical results for various AC OPF problems where discrete decisions play a major role. Even for hard instances with a large proportion of discrete decisions, the method is able to generate high quality solutions efficiently. Furthermore, we compare our approach with state-of-the-art MINLP. Our method outperforms all other algorithms. KW - Mixed-Integer Nonlinear Programming KW - Second-Order Cone Programming KW - AC Optimal Power Flow KW - Discrete Decisions KW - Piecewise Linear Relaxation Y1 - 2020 ER - TY - INPR A1 - Leugering, Günter T1 - Space-time-domain decomposition for optimal control problems governed by linear hyperbolic systems N2 - In this article, we combine a domain decomposition method in space and time for optimal control problems with PDE-constraints described by Lagnese and Leugering to a simultaneous space-time decomposition applied to optimal control problems for systems of linear hyperbolic equations with distributed control. We thereby extend the recent work by Krug et al. and answer a long standing open question as to whether the combination of time- and space domain decomposition for the method under consideration can be put into one single convergent iteration procedure. The algorithm is designed for a semi-elliptic system of equations obtained from the hyperbolic optimality system by the way of reduction to the adjoint state. The focus is on the relation to the classical procedure introduced by Lions for elliptic problems. KW - Space- and time-domain decomposition KW - Optimal control KW - linear hyperbolic systems KW - Convergence KW - A posteriori error estimates Y1 - 2021 ER - TY - JOUR A1 - Lance, G A1 - Trelat, E A1 - Zuazua, E T1 - Shape turnpike for linear parabolic PDE models N2 - We introduce and study the turnpike property for time-varying shapes, within the viewpoint of optimal control. We focus here on second-order linear parabolic equations where the shape acts as a source term and we seek the optimal time-varying shape that minimizes a quadratic criterion. We first establish existence of optimal solutions under some appropriate sufficient conditions. We then provide necessary conditions for optimality in terms of adjoint equations and, using the concept of strict dissipativity, we prove that state and adjoint satisfy the measure-turnpike property, meaning that the extremal time-varying solution remains essentially close to the optimal solution of an associated static problem. We show that the optimal shape enjoys the exponential turnpike property in term of Hausdorff distance for a Mayer quadratic cost. We illustrate the turnpike phenomenon in optimal shape design with several numerical simulations. KW - Optimal shape design KW - Turnpike KW - Strict dissipativity KW - Direct methods KW - Parabolic equation Y1 - 2020 U6 - https://doi.org/10.1016/j.sysconle.2020.104733 VL - 142 SP - 104 EP - 733 ER - TY - INPR A1 - Wang, G A1 - Zhang, Y A1 - Zuazua, E T1 - Flow decomposition for heat equations with memory N2 - We build up a decomposition for the flow generated by the heat equation with a real analytic memory kernel. It consists of three components: The first one is of parabolic nature; the second one gathers the hyperbolic component of the dynamics, with null velocity of propagation; the last one exhibits a finite smoothing effect. This decomposition reveals the hybrid parabolic-hyperbolic nature of the flow and clearly illustrates the significant impact of the memory term on the parabolic behavior of the system in the absence of memory terms. KW - Heat equations with memory KW - decomposition of the flow KW - hybrid parabolic-hyperbolic behavior Y1 - 2021 ER - TY - INPR A1 - Barcena-Petisco, J.A. A1 - Zuazua, E T1 - Averaged dynamics and control for heat equations with random diffusion N2 - This paper deals with the averaged dynamics for heat equations in the degenerate case where the diffusivity coefficient, assumed to be constant, is allowed to take the null value. First we prove that the averaged dynamics is analytic. This allows to show that, most often, the averaged dynamics enjoys the property of unique continuation and is approximately controllable. We then determine if the averaged dynamics is actually null controllable or not depending on how the density of averaging behaves when the diffusivity vanishes. In the critical density threshold the dynamics of the average is similar to the \frac{1}{2}-fractional Laplacian, which is wellknown to be critical in the context of the controllability of fractional diffusion processes. Null controllability then fails (resp. holds) when the density weights more (resp. less) in the null diffusivity regime than in this critical regime. Y1 - 2021 ER - TY - INPR A1 - Biccari, U A1 - Zuazua, E T1 - Multilevel control by duality N2 - We discuss the multilevel control problem for linear dynamical systems, consisting in designing a piece-wise constant control function taking values in a finite-dimensional set. In particular, we provide a complete characterization of multilevel controls through a duality approach, based on the minimization of a suitable cost functional. In this manner we build optimal multi-level controls and characterize the time needed for a given ensemble of levels to assure the controllability of the system. Moreover, this method leads to efficient numerical algorithms for computing multilevel controls. Y1 - 2021 ER - TY - JOUR A1 - Ko, D A1 - Zuazua, E T1 - Model predictive control with random batch methods for a guiding problem N2 - We model, simulate and control the guiding problem for a herd of evaders under the action of repulsive drivers. The problem is formulated in an optimal control framework, where the drivers (controls) aim to guide the evaders (states) to a desired region of the Euclidean space. The numerical simulation of such models quickly becomes unfeasible for a large number of interacting agents. To reduce the computational cost, we use the Random Batch Method (RBM), which provides a computationally feasible approximation of the dynamics. At each time step, the RBM randomly divides the set of particles into small subsets (batches), considering only the interactions inside each batch. Due to the averaging effect, the RBM approximation converges to the exact dynamics as the time discretization gets finer. We propose an algorithm that leads to the optimal control of a fixed RBM approximated trajectory using a classical gradient descent. The resulting control is not optimal for the original complete system, but rather for the reduced RBM model. We then adopt a Model Predictive Control (MPC) strategy to handle the error in the dynamics. While the system evolves in time, the MPC strategy consists in periodically updating the state and computing the optimal control over a long-time horizon, which is implemented recursively in a shorter time-horizon. This leads to a semi-feedback control strategy. Through numerical experiments we show that the combination of RBM and MPC leads to a significant reduction of the computational cost, preserving the capacity of controlling the overall dynamics. Y1 - 2021 U6 - https://doi.org/https://doi.org/10.1142/S0218202521500329 VL - 31 IS - 8 SP - 1569 EP - 1592 ER - TY - INPR A1 - Heiland, J A1 - Zuazua, E T1 - Classical system theory revisited for Turnpike in standard state space systems and impulse controllable descriptor systems N2 - The concept of turnpike connects the solution of long but finite time horizon optimal control problems with steady state optimal controls. A key ingredient of the analysis of turnpike phenomena is the linear quadratic regulator problem and the convergence of the solution of the associated differential Riccati equation as the terminal time approaches infinity. This convergence has been investigated in linear systems theory in the 1980s. We extend classical system theoretic results for the investigation of turnpike properties of standard state space systems and descriptor systems. We present conditions for turnpike phenomena in the non detectable case and for impulse controllable descriptor systems. For the latter, in line with the theory for standard linear systems,we establish existence and convergence of solutions to a generalized differential Riccati equation. KW - Riccati equations KW - descriptor systems KW - linear systems KW - long time behavior KW - optimal control Y1 - 2021 ER - TY - INPR A1 - Zhong-Jie, H A1 - Zuazua, E T1 - Slow decay and Turnpike for Infinite-horizon Hyperbolic LQ problems N2 - This paper is devoted to analysing the explicit slow decay rate and turnpike in the infinite-horizon linear quadratic optimal control problems for hyperbolic systems. Assume that some weak observability or controllability are satisfied, by which, the lower and upper bounds of the corresponding algebraic Riccati operator are estimated, respectively. Then based on these two bounds, the explicit slow decay rate of the closed-loop system with Riccati-based optimal feedback control is obtained. The averaged turnpike property for this problem is also further discussed. We then apply these results to the LQ optimal control problems constraint to networks of onedimensional wave equations and also some multi-dimensional ones with local controls which lack of GCC (Geometric Control Condition). Y1 - 2021 ER - TY - INPR A1 - Geshkovski, B A1 - Zuazua, E T1 - Optimal actuator design via Brunovsky’s normal form N2 - In this paper, by using the Brunovsky normal form, we provide a reformulation of the problem consisting in finding the actuator design which minimizes the controllability cost for finite-dimensional linear systems with scalar controls. Such systems may be seen as spatially discretized linear partial differential equations with lumped controls. The change of coordinates induced by Brunovsky’s normal form allows us to remove the restriction of having to work with diagonalizable system dynamics, and does not entail a randomization procedure as done in past literature on diffusion equations or waves. Instead, the optimization problem reduces to a minimization of the norm of the inverse of a change of basis matrix, and allows for an easy deduction of existence of solutions, and for a clearer picture of some of the problem’s intrinsic symmetries. Numerical experiments help to visualize these artifacts, indicate further open problems, and also show a possible obstruction of using gradient-based algorithms – this is alleviated by using an evolutionary algorithm. Y1 - 2021 ER - TY - INPR A1 - Biccari, U A1 - Warma, M A1 - Zuazua, E T1 - Control and Numerical approximation of Fractional Diffusion Equations N2 - The aim of this work is to give a broad panorama of the control properties of fractional diffusive models from a numerical analysis and simulation perspective. We do this by surveying several research results we obtained in the last years, focusing in particular on the numerical computation of controls, though not forgetting to recall other relevant contributions which can be currently found in the literature of this prolific field. Our reference model will be a non-local diffusive dynamics driven by the fractional Laplacian on a bounded domain ΩΩΩ. The starting point of our analysis will be a Finite Element approximation for the associated elliptic model in one and two space-dimensions, for which we also present error estimates and convergence rates in the L2L^2L2 and energy norm. Secondly, we will address two specific control scenarios: firstly, we consider the standard interior control problem, in which the control is acting from a small subset ω⊂Ωω ⊂ Ωω⊂Ω. Secondly, we move our attention to the exterior control problem, in which the control region O⊂ΩcO ⊂ Ω cO⊂Ωc is located outside ΩΩΩ. This exterior control notion extends boundary control to the fractional framework, in which the non-local nature of the models does not allow for controls supported on ∂Ω∂Ω∂Ω. We will conclude by discussing the interesting problem of simultaneous control, in which we consider families of parameter-dependent fractional heat equations and we aim at designing a unique control function capable of steering all the different realizations of the model to the same target configuration. In this framework, we will see how the employment of stochastic optimization techniques may help in alleviating the computational burden for the approximation of simultaneous controls. Our discussion is complemented by several open problems related with fractional models which are currently unsolved and may be of interest for future investigation. Y1 - 2021 ER - TY - INPR A1 - Gugat, Martin A1 - Herty, Michael T1 - Modeling, Control and Numerics of Gas Networks N2 - In this article we survey recent progress on mathematical results on gas flow in pipe networks with a special focus on questions of control and stabilization. We briefly present the modeling of gas flow and coupling conditions for flow through vertices of a network. Our main focus is on gas models for spatially one-dimensional flow governed by hyperbolic balance laws. We survey results on classical solutions as well as weak solutions. We present results on well–posedness, controllability, feedback stabilization, the inclusion of uncertainty in the models and numerical methods. KW - Hyperbolic Balance Laws, Stabilization, Exact Controllability, Modeling of Gas Flow, Finite-Volume Schemes, Optimal control, Uncertainty Y1 - 2020 ER - TY - INPR A1 - Kleinert, Thomas A1 - Schmidt, Martin T1 - Why there is no need to use a big-M in linear bilevel optimization: A computational study of two ready-to-use approaches N2 - Linear bilevel optimization problems have gained increasing attention both in theory as well as in practical applications of Operations Research (OR) during the last years and decades. The latter is mainly due to the ability of this class of problems to model hierarchical decision processes. However, this ability makes bilevel problems also very hard to solve. Since no general-purpose solvers are available, a "best-practice" has developed in the applied OR community, in which not all people want to develop tailored algorithms but "just use" bilevel optimization as a modeling tool for practice. This best-practice is the big-M reformulation of the Karush-Kuhn-Tucker (KKT) conditions of the lower-level problem - an approach that has been shown to be highly problematic by Pineda and Morales (2019). Choosing invalid values for M yields solutions that may be arbitrarily bad. Checking the validity of the big-Ms is however shown to be as hard as solving the original bilevel problem in Kleinert et al. (2019). Nevertheless, due to its appealing simplicity, especially w.r.t. the required implementation effort, this ready-to-use approach still is the most popular method. Until now, there has been a lack of approaches that are competitive both in terms of implementation effort and computational cost. In this note we demonstrate that there is indeed another competitive ready-to-use approach: If the SOS-1 technique is applied to the KKT complementarity conditions, adding the simple additional root-node inequality developed by Kleinert et al. (2020) leads to a competitive performance - without having all the possible theoretical disadvantages of the big-M approach. KW - Bilevel optimization KW - Big-M KW - SOS-1 KW - Valid inequalities KW - Computational analysis Y1 - 2020 ER - TY - JOUR A1 - Bárcena, J.A. A1 - Zuazua, Enrique T1 - Averaged dynamics and control for heat equations with random diffusion N2 - Abstract. This paper deals with the averaged dynamics for heat equations in the degenerate case where the diffusivity coefficient, assumed to be constant, is allowed to take the null value. First we prove that the averaged dynamics is analytic. This allows to show that, most often, the averaged dynamics enjoys the property of unique continuation and is approximately controllable. We then determine if the averaged dynamics is actually null controllable or not depending on how the density of averaging behaves when the diffusivity vanishes. In the critical density threshold the dynamics of the average is similar to the $\frac{1}{2}$-fractional Laplacian, which is wellknown to be critical in the context of the controllability of fractional diffusion processes. Null controllability then fails (resp. holds) when the density weights more (resp. less) in the null diffusivity regime than in this critical regime. KW - Averaged controllability, averaged observability, observability, random heat equation Y1 - 2020 ER - TY - JOUR A1 - Schuster, Michael A1 - Strauch, Elisa A1 - Gugat, Martin A1 - Lang, Jens T1 - Probabilistic Constrained Optimization on Flow Networks N2 - Uncertainty often plays an important role in dynamic flow problems. In this paper, we consider both, a stationary and a dynamic flow model with uncertain boundary data on networks. We introduce two different ways how to compute the probability for random boundary data to be feasible, discussing their advantages and disadvantages. In this context, feasible means, that the flow corresponding to the random boundary data meets some box constraints at the network junctions. The first method is the spheric radial decomposition and the second method is a kernel density estimation. In both settings, we consider certain optimization problems and we compute derivatives of the probabilistic constraint using the kernel density estimator. Moreover, we derive necessary optimality conditions for the stationary and the dynamic case. Throughout the paper, we use numerical examples to illustrate our results by comparing them with a classical Monte Carlo approach to compute the desired probability. KW - Probabilistic Constraints KW - Flow Networks KW - Gas Networks KW - Spheric Radial Decomposition KW - Kernel Density Estimator Y1 - 2020 U6 - https://doi.org/https://doi.org/10.1007/s11081-021-09619-x VL - Optimization and Engineering ER - TY - JOUR A1 - Gugat, Martin A1 - Giesselmann, Jan T1 - Boundary feedback stabilization of a semilinear model for the flow in star-shaped gas networks N2 - The flow of gas through a pipeline network can be modelled by a coupled system of 1-d quasilinear hyperbolic equations. In this system, the influence of certain source terms that model friction effects is essential. Often for the solution of control problems it is convenient to replace the quasilinear model by a simpler semilinear model. In this paper, we analyze the behavior of such a semilinear model on a star-shaped network. The model is derived from the diagonal form of the quasilinear model by replacing the eigenvalues by the sound speed multiplied by 1 or -1 respectively. Thus in the corresponding eigenvalues the influence of the gas velocity is neglected, which is justified in the applications since it is much smaller than the sound speed in the gas. For a star-shaped network of horizontal pipes for suitable coupling conditions we present boundary feedback laws that stabilize the system state exponentially fast to a position of rest for sufficiently small initial data. We show the exponential decay of the $H^1$-norm for arbitrarily long pipes. This is remarkable since in general even for linear systems, for certain source terms the system can become exponentially unstable if the space interval is too long. Our proofs are based upon observability inequalities for the $L^2$ and the $H^1$-norm. Y1 - 2020 U6 - https://doi.org/10.1051/cocv/2021061 CY - ESAIM:COCV ER - TY - JOUR A1 - Burger, Martin T1 - Network structured kinetic models of social interactions N2 - The aim of this paper is to study the derivation of appropriate meso- and macroscopic models for interactions as appearing in social processes. There are two main characteristics the models take into account, namely a network structure of interactions, which we treat by an appropriate mesoscopic description, and a different role of interacting agents. The latter differs from interactions treated in classical statistical mechanics in the sense that the agents do not have symmetric roles, but there is rather an active and a passive agent. We will demonstrate how a certain form of kinetic equations can be obtained to describe such interactions at a mesoscopic level and moreover obtain macroscopic models from monokinetics solutions of those. The derivation naturally leads to systems of nonlocal reaction-diffusion equations (or in a suitable limit local versions thereof), which can explain spatial phase separation phenomena found to emerge from the microscopic interactions. We will highlight the approach in three examples, namely the evolution and coarsening of dialects in human language, the construction of social norms, and the spread of an epidemic. Y1 - 2021 U6 - https://doi.org/10.1007/s10013-021-00505-8 ET - Vietnam Journal of Mathematics ER - TY - INPR A1 - Runge, Philipp A1 - Sölch, Christian A1 - Albert, Jakob A1 - Wasserscheid, Peter A1 - Zöttl, Gregor A1 - Grimm, Veronika T1 - Economic comparison of electric fuels produced at excellent locations for renewable energies: A Scenario for 2035 N2 - The use of electric fuels (e-fuels) enables CO2-neutral mobility and opens therefore an alternative to fossil-fuel-fired engines or battery-powered electric motors. This paper compares the cost-effectiveness of Fischer-Tropsch diesel, methanol, and hydrogen stored as cryogenic liquid (LH2) or in form of liquid organic hydrogen carriers (LOHCs). The production cost of those fuels are to a large extent driven by the energy-intensive electrolytic water splitting. The option of producing e-fuels in Germany competes with international locations with excellent conditions for renewable energy harvesting and thus very low levelized cost of electricity. We developed a mathematical model that covers the entire process chain. Starting with the production of the required resources such as fresh water, hydrogen, carbon dioxide, carbon monoxide, electrical and thermal energy, the subsequent chemical synthesis, the transport to filling stations in Germany and finally the energetic utilization of the fuels in the vehicle. We found that the choice of production site can have a major impact on the mobility cost using the respective fuels. Especially in case of diesel production, the levelized cost of electricity driven by the full load hours of the applied renewable energy source have a huge impact. An LOHC-based system is shown to be less dependent on the kind of electricity source compared to other technologies due to its comparatively low electricity consumption and the low cost for the hydrogenation units. The length of the transportation route and the price of the filling station infrastructure, on the other hand, clearly increase mobility cost for LOHC and LH2. KW - Electric fuels, Hydrogen Utilization, Hydrogen Import, LOHC, Mobility Y1 - 2020 ER - TY - INPR A1 - Bohlayer, Markus A1 - Bürger, Adrian A1 - Fleschutz, Markus A1 - Braun, Marco A1 - Zöttl, Gregor T1 - Multi-period investment pathways - Modeling approaches to design distributed energy systems under uncertainty N2 - Multi-modal distributed energy system planning is applied in the context of smart grids, industrial energy supply,and in the building energy sector. In real-world applications, these systems are commonly characterized by existing system structures of different age where monitoring and investment are conducted in a closed-loop, with the iterative possibility to invest. The literature contains two main approaches to approximate this computationally intensive multiperiod investment problem. The first approach simplifies the temporal decision-making process collapsing the multistage decision to a two-stage decision, considering uncertainty in the second stage decision variables. The second approach considers multi-period investments under the assumption of perfect foresight. In this work, we propose a multi-stage stochastic optimization problem that captures multi-period investment decisions under uncertainty and solves the problem to global optimality, serving as a first-best benchmark to the problem. To evaluate the performance of conventional approaches applied in a multi-year setup and to solve the multi-period problem at lower computational effort, we propose a rolling horizon heuristic that on the one hand reveals the performance of conventional approaches applied in a multi-period set-up and on the other hand enables planners to identify approximate solutions to the original multi-stage stochastic problem. Additionally, we consider an open-loop version of the rolling horizon algorithm to evaluate how single-period investments perform with respect to the entire scenario tree and compared to multi-period investments. We conduct a real-world case study and investigate solution quality as well as the computational performance of the proposed approaches. Our findings indicate that the approximation of multi-period investments by two-stage stochastic approaches yield the best results regarding constraint satisfaction, while deterministic multi-period approximations yield better economic and computational performance. Y1 - 2020 ER - TY - INPR A1 - Gugat, Martin A1 - Herty, Michael T1 - Limits of stabilizabilizy for a semilinear model for gas pipeline flow N2 - We present a positive and a negative stabilization result for a semilinear model of gas flow in pipelines. For feedback boundary conditions we obtain an unconditional stabilization result in the absence and conditional instability in the presence of the source term. We also obtain unconditional instability for the corresponding quasilinear model given by the isothermal Euler equations Y1 - 2020 ER - TY - JOUR A1 - Sarac, Yesim A1 - Zuazua, Enrique T1 - Sidewise control of 1-d waves N2 - We analyze the sidewise controllability for the variable coefficients one-dimensional wave equation. The control is acting on one extreme of the string with the aim that the solution tracks a given path at the otherfree end. This sidewise control problem is also often referred to as nodal profile or tracking control. First, the problem is reformulated as a dual observability property for the corresponding adjoint system. Using sidewiseenergy propagation arguments the sidewise observability is shown to hold, ina sufficiently large time, in the class of BV-coefficients. We also present a number of open problems and perspectives for further research. KW - 1-d wave equations KW - BV-coefficients KW - nodal profile con-trol Y1 - 2021 ER - TY - JOUR A1 - Plein, Fränk A1 - Thürauf, Johannes A1 - Labbé, Martine A1 - Schmidt, Martin T1 - A Bilevel Optimization Approach to Decide the Feasibility of Bookings in the European Gas Market JF - Mathematical Methods of Operations Research N2 - The European gas market is organized as a so-called entry-exit system with the main goal to decouple transport and trading. To this end, gas traders and the transmission system operator (TSO) sign so-called booking contracts that grant capacity rights to traders to inject or withdraw gas at certain nodes up to this capacity. On a day-ahead basis, traders then nominate the actual amount of gas within the previously booked capacities. By signing a booking contract, the TSO guarantees that all nominations within the booking bounds can be transported through the network. This results in a highly challenging mathematical problem. Using potential-based flows to model stationary gas physics, feasible bookings on passive networks, i.e., networks without controllable elements, have been characterized in the recent literature. In this paper, we consider networks with linearly modeled active elements such as compressors or control valves. Since these active elements allow the TSO to control the gas flow, the single-level approaches for passive networks from the literature are no longer applicable. We thus present a bilevel model to decide the feasibility of bookings in networks with active elements. While this model is well-defined for general active networks, we focus on the class of networks for which active elements do not lie on cycles. This assumption allows us to reformulate the original bilevel model such that the lower-level problem is linear for every given upper-level decision. Consequently, we derive several single-level reformulations for this case. Besides the classic Karush-Kuhn-Tucker reformulation, we obtain three problem-specific optimal-value-function reformulations. The latter also lead to novel characterizations of feasible bookings in networks with active elements that do not lie on cycles. We compare the performance of our methods by a case study based on data from the GasLib. KW - Gas networks KW - Bilevel optimization KW - European entry-exit market KW - Bookings KW - Active elements Y1 - 2021 U6 - https://doi.org/10.1007/s00186-021-00752-y ER - TY - INPR A1 - Gugat, Martin A1 - Sokolowski, Jan T1 - On Problems of Dynamic Optimal Nodal control for Gas Networks N2 - We consider a dynamic ptimal control problem for gas pipeline systems. The flow is governed by a quasilinear hyperbolic model. Since in the operation of the gas networks regular solutions without shocks are desirable, we impose appropriate state and control constraint in order to guarantee that a classical solution is generated. Due to a W^{2;inf}-regularization term in the objective function, we can show the existence of an optimal control. Moreover, we give conditions that guarantee that the control becomes constant a the end of the control time interval if the weight of the regularization term is suffciently large. KW - optimal nodal control KW - gas network KW - turnpike property KW - quasilinear hyperbolic problem KW - dynamic control Y1 - 2021 ER - TY - JOUR A1 - Gugat, Martin T1 - On the turnpike property with interior decay for optimal control problems JF - Mathematics of Control, Signals, and Systems N2 - In this paper the turnpike phenomenon is studied for problems of optimal control where both pointwise-in-time state and control constraints can appear. We assume that in the objective function, a tracking term appears that is given as an integral over the time-interval [0, T] and measures the distance to a desired stationary state. In the optimal control problem, both the initial and the desired terminal state are prescribed. We assume that the system is exactly controllable in an abstract sense if the time horizon is long enough. We show that that the corresponding optimal control problems on the time intervals [0, T] give rise to a turnpike structure in the sense that for natural numbers n if T is su� ciently large, the contribution of the objective function from subintervals of [0, T] of the form [t - t/2^n, t + (T-t)/2^n] is of the order 1/min{t^n, (T-t)^n}. We also show that a similar result holds for epsilon-optimal solutions of the optimal control problems if epsilon > 0 is chosen suffciently small. At the end of the paper we present both systems that are governed by ordinary differential equations and systems governed by partial differential equations where the results can be applied. KW - Optimal control KW - Turnpike KW - Control Constraint KW - State constraint KW - Exact controllability Y1 - 2021 U6 - https://doi.org/https://doi.org/10.1007/s00498-021-00280-4 ER - TY - INPR A1 - Heitsch, Holger A1 - Henrion, René A1 - Kleinert, Thomas A1 - Schmidt, Martin T1 - On Convex Lower-Level Black-Box Constraints in Bilevel Optimization with an Application to Gas Market Models with Chance Constraints N2 - Bilevel optimization is an increasingly important tool to model hierarchical decision making. However, the ability of modeling such settings makes bilevel problems hard to solve in theory and practice. In this paper, we add on the general difficulty of this class of problems by further incorporating convex black-box constraints in the lower level. For this setup, we develop a cutting-plane algorithm that computes approximate bilevel-feasible points. We apply this method to a bilevel model of the European gas market in which we use a joint chance constraint to model uncertain loads. Since the chance constraint is not available in closed form, this fits into the black-box setting studied before. For the applied model, we use further problem-specific insights to derive bounds on the objective value of the bilevel problem. By doing so, we are able to show that we solve the application problem to approximate global optimality. In our numerical case study we are thus able to evaluate the welfare sensitivity in dependence of the achieved safety level of uncertain load coverage. KW - Bilevel optimization KW - Black-box constraints KW - Chance constraints KW - Cutting planes KW - European gas market Y1 - 2021 ER - TY - INPR A1 - Leugering, Günter T1 - Space-Time-Domain Decomposition for Optimal Control Problems Governed by Linear Hyperbolic Systems N2 - In this article, we combine a domain decomposition method in space and time for optimal control problems with PDE-constraints described by Lagnese and Leugering to a simultaneous space-time decomposition applied to optimal control problems for systems of linear hyperbolic equations with distributed control. We thereby extend the recent work by Krug et al. and answer a long standing open question as to whether the combination of time- and space domain decomposition for the method under consideration can be put into one single convergent iteration procedure. The algorithm is designed for a semi-elliptic system of equations obtained from the hyperbolic optimality system by the way of reduction to the adjoint state. The focus is on the relation to the classical procedure introduced by Lions for elliptic problems. KW - Space- and time-domain decomposition KW - Optimal control KW - linear hyperbolic systems KW - Convergence KW - A posteriori error estimates Y1 - 2021 ER - TY - JOUR A1 - Leugering, Günter T1 - Industrial Applications of Optimal Control for Partial Differential Equations on Networks: Reduction and Decomposition Methods Applied to the Discrete–Continuous Control of Gas Flow in Complex Pipe Systems N2 - This chapter provides an exemplary road map—in a nutshell—from a given industrial application, the control of gas networks, which is far too complex for a direct approach, to a problem that can be actually handled using well-known methods in control theory. It also provides an iterative non-overlapping domain decomposition that can be interpreted as an Uzawa method. The chapter outline two strategies. The first one can be seen as a Jacobi-type approach. In the second approach, fix the integer controls s and decompose the corresponding optimality system for the entire graph into the subgraphs Gk by a another, but very similar, non-overlapping domain decomposition. The problem is the intrinsic coupling of integer controls, continuous controls, and nonlinear dynamics on a metric graph. The idea is to introduce a virtual control that aims at controlling classical in homogeneous Neumann condition including the iteration history at the interface as inhomogeneity to the Robin-type condition that appears in the decomposition. Y1 - 2021 VL - Computational Science and Its Applications IS - 1st Edition SP - 25 EP - 40 ER - TY - INPR A1 - Biefel, Christian A1 - Liers, Frauke A1 - Rolfes, Jan A1 - Schewe, Lars A1 - Zöttl, Gregor T1 - Robust Market Equilibria under Uncertain Cost N2 - We consider equilibrium problems under uncertainty where firms maximize their profits in a robust way when selling their output. Robust optimization plays an increasingly important role when best guaranteed objective values are to be determined, independently of the specific distributional assumptions regarding uncertainty. In particular, solutions are to be determined that are feasible regardless of how the uncertainty manifests itself within some predefined uncertainty set. Our analysis adopts the robust optimization perspective in the context of equilibrium problems. First, we consider a singlestage, nonadjustable robust setting. We then go one step further and study the more complex two-stage or adjustable case where a part of the variables can adjust to the realization of the uncertainty. We compare equilibrium outcomes with the corresponding centralized robust optimization problem where the sum of all profits are maximized. As we find, the market equilibrium for the perfectly competitive firms differs from the solution of the robust central planner, which is in stark contrast to classical results regarding the efficiency of market equilibria with perfectly competitive firms. For the different scenarios considered, we furthermore are able to determine the resulting price of anarchy. In the case of non-adjustable robustness, for fixed demand in every time step the price of anarchy is bounded whereas it is unbounded if the buyers are modeled by elastic demand functions. For the two-stage adjustable setting, we show how to compute subsidies for the firms that lead to robust welfare optimal equilibria. KW - Continuous Optimization KW - Equilibrium Problems KW - Robust Optimization KW - Adjustable Robustness Y1 - 2021 ER - TY - INPR A1 - Gugat, Martin A1 - Krug, Richard A1 - Martin, Alexander T1 - Transient gas pipeline flow: Analytical examples, numerical simulation and a comparison to the quasi-static approach N2 - The operation of gas pipeline flow with high pressure and small Mach numbers allows to model the flow by a semilinear hyperbolic system of partial differential equations. In this paper we present a number of transient and stationary analytical solutions of this model. They are used to discuss and clarify why a pde model is necessary to handle certain dynamic situations in the operation of gas transportation networks. We show that adequate numerical discretizations can capture the dynamical behavior sufficiently accurate. We also present examples that show that in certain cases an optimization approach that is based upon multi-period optimization of steady states does not lead to approximations that converge to the optimal state. Y1 - 2021 U6 - https://doi.org/10.1007/s11081-021-09690-4 ER - TY - INPR A1 - Adelhütte, Dennis A1 - Biefel, Christitan A1 - Kuchlbauer, Martina A1 - Rolfes, Jan T1 - Pareto Robust optimization on Euclidean vector spaces N2 - Pareto efficiency for robust linear programs was introduced by Iancu and Trichakis in [9]. We generalize their approach and theoretical results to robust optimization problems in Euclidean spaces with linear uncertainty. Additionally, we demonstrate the value of this approach in an exemplary manner in the area of robust semidefinite programming (SDP). In particular, we prove that computing a Pareto robustly optimal solution for a robust SDP is tractable and illustrate the benefit of such solutions at the example of the maximal eigenvalue problem. Furthermore, we modify the famous algorithm of Goemans and Williamson [8] in order to compute cuts for the robust max cut problem that yield an improved approximation guarantee in non-worst-case scenarios. Y1 - ER - TY - INPR A1 - Gugat, Martin T1 - Optimal boundary control of the wave equation: The finite-time turnpike phenomenon N2 - It is well-known that vibrating strings can be steered to a position of rest in finite time by suitably defined boundary control functions, if the time horizon is suffciently long. In optimal control problems, the desired terminal state is often enforced by terminal conditions, that add an additional diffculty to the optimal control problem. In this paper we present an optimal control problem for the wave equation with a time-dependent weight in the objective function such that for a suffciently long time horizon, the optimal state reaches a position of rest in finite time without prescribing a terminal constraint. This situation can be seen as a realization of the finite-time turnpike phenomenon that has been studied recently in [1]. Y1 - 2021 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 - 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 - Schmidt, Martin A1 - Sirvent, Mathias A1 - Wollner, Winnifried T1 - A Decomposition Method for MINLPs with Lipschitz Continuous Nonlinearities JF - Mathematical Programming N2 - Many mixed-integer optimization problems are constrained by nonlinear functions that do not possess desirable analytical properties like convexity or factorability or cannot even be evaluated exactly. This is, e.g., the case for problems constrained by differential equations or for models that rely on black-box simulation runs. For these problem classes, we present, analyze, and test algorithms that solve mixed-integer problems with only Lipschitz continuous nonlinearities. Our theoretical results depend on the assumptions made on the (in)exactness of function evaluations and on the knowledge of Lipschitz constants. If Lipschitz constants are known, we prove finite termination at approximate globally optimal points both for the case of exact and inexact function evaluations. If only approximate Lipschitz constants are known, we prove finite termination and derive additional conditions under which infeasibility can be detected. A computational study for gas transport problems and an academic case study show the applicability of our algorithms to real-world problems and how different assumptions on the constraint functions up- or downgrade the practical performance of the methods. KW - Mixed-Integer Nonlinear Optimization, Lipschitz Optimization, Inexact Function Evaluations, Decomposition Methods, Gas Networks Y1 - 2017 IS - 178(1) SP - 449 EP - 483 ER - TY - INPR A1 - Egger, Herbert A1 - Kugler, Thomas A1 - Liljegren-Sailer, Björn A1 - Marheineke, Nicole A1 - Mehrmann, Volker T1 - On structure preserving model reduction for damped wave propagation in transport networks N2 - We consider the discretization and subsequent model reduction of a system of partial differential-algebraic equations describing the propagation of pressure waves in a pipeline network. Important properties like conservation of mass, dissipation of energy, passivity, existence of steady states, and exponential stability can be preserved by an appropriate semi- discretization in space via a mixed finite element method and also during the further dimension reduction by structure preserving Galerkin projection which is the main focus of this paper. Krylov subspace methods are employed for the construction of the reduced models and we discuss modifications needed to satisfy certain algebraic compatibility conditions; these are required to ensure the well-posedness of the reduced models and the preservation of the key properties. Our analysis is based on the underlying infinite dimensional problem and its Galerkin approximations. The proposed algorithms therefore have a direct interpretation in function spaces; in principle, they are even applicable directly to the original system of partial differential-algebraic equations while the intermediate discretization by finite elements is only required for the actual computations. The performance of the proposed methods is illustrated with numerical tests and the necessity for the compatibility conditions is demonstrated by examples. KW - partial differential-algebraic equations KW - port-Hamiltonian systems KW - Galerkin projection Y1 - 2017 ER - TY - INPR A1 - Burlacu, Robert A1 - Geißler, Björn A1 - Schewe, Lars T1 - Solving Mixed-Integer Nonlinear Programs using Adaptively Refined Mixed-Integer Linear Programs N2 - We propose a method for solving mixed-integer nonlinear programs (MINLPs) to global optimality by discretization of occuring nonlinearities. The main idea is based on using piecewise linear functions to construct mixed-integer linear program (MIP) relaxations of the underlying MINLP. In order to find a global optimum of the given MINLP we develope an iterative algorithm which solves MIP relaxations that are adaptively refined. We are able to give convergence results for a wide range of MINLPs requiring only continuous nonlinearities with bounded domains and an oracle computing maxima of the nonlinearities on their domain. Moreover, the practicalness of our approach is shown numerically by an application from the field of gas network optimization. KW - Mixed-Integer Nonlinear Programming KW - Piecewise Linearization 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 - JOUR A1 - Martin, Gugat 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 - Gugat, Martin A1 - Zuazua, Enrique ED - Grimble, Mike J. T1 - Exact penalization of terminal constraints for optimal control problems JF - OPTIMAL CONTROL APPLICATIONS AND METHODS N2 - We study optimal control problems for linear systems with prescribed initial and terminal states. We analyze the exact penalization of the terminal constraints. We show that for systems that are exactly controllable, the norm-minimal exact control can be computed as the solution of an optimization problem without terminal constraint but with a nonsmooth penalization of the end conditions in the objective function, if the penalty parameter is sufficiently large. We describe the application of the method for hyperbolic and parabolic systems of partial differential equations, considering the wave and heat equations as particular examples. Copyright © 2016 John Wiley & Sons, Ltd. Y1 - 2016 U6 - https://doi.org/10.1002/oca.2238 VL - 37 IS - 6 SP - 1329 EP - 1354 ER - TY - JOUR A1 - Hante, Falk A1 - Leugering, Günter A1 - Martin, Alexander A1 - Schewe, Lars A1 - Schmidt, Martin T1 - Challenges in optimal control problems for gas and fluid flow in networks of pipes and canals: From modeling to industrial applications N2 - We consider optimal control problems for the flow of gas or fresh water in pipe networks as well as drainage or sewer systems in open canals. The equations of motion are taken to be represented by the nonlinear isothermal Euler gas equations, the water hammer equations, or the St.~Venant equations for flow. We formulate model hierarchies and derive an abstract model for such network flow problems including pipes, junctions, and controllable elements such as valves, weirs, pumps, as well as compressors. We use the abstract model to give an overview of the known results and challenges concerning equilibria, well-posedness, controllability, and optimal control. A major challenge concerning the optimization is to deal with switching on-off states that are inherent to controllable devices in such applications combined with continuous simulation and optimization of the gas flow. We formulate the corresponding mixed-integer nonlinear optimal control problems and outline a decomposition approach as a solution technique. KW - Networks KW - pipes KW - optimal control KW - Euler and St. Venant equations KW - hierarchy of models Y1 - 2016 ER - TY - JOUR A1 - Schewe, Lars A1 - Schmidt, Martin T1 - Computing Feasible Points for Binary MINLPs with MPECs JF - Mathematical Programming Computation N2 - Nonconvex mixed-binary nonlinear optimization problems frequently appear in practice and are typically extremely hard to solve. In this paper we discuss a class of primal heuristics that are based on a reformulation of the problem as a mathematical program with equilibrium constraints. We then use different regularization schemes for this class of problems and use an iterative solution procedure for solving series of regularized problems. In the case of success, these procedures result in a feasible solution of the original mixed-binary nonlinear problem. Since we rely on local nonlinear programming solvers the resulting method is fast and we further improve its reliability by additional algorithmic techniques. We show the strength of our method by an extensive computational study on 662 MINLPLib2 instances, where our methods are able to produce feasible solutions for 60% of all instances in at most 10s. KW - Mixed-Integer Nonlinear Optimization KW - MINLP KW - MPEC KW - Complementarity Constraints KW - Primal Heuristic Y1 - 2016 IS - 11(1) SP - 95 EP - 118 ER - TY - JOUR A1 - Gugat, Martin A1 - Hante, Falk T1 - Lipschitz Continuity of the Value Function in Mixed-Integer Optimal Control Problems JF - Mathematics of Control, Signals, and Systems Y1 - 2017 U6 - https://doi.org/10.1007/s00498-016-0183-4 VL - 29 IS - 1 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 - 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 - 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 - 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 - 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 - 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 - 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 - 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 - 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 - 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 - 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 - 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 - 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 - Hante, Falk A1 - Mommer, Mario A1 - Potschka, Andreas T1 - Newton-Picard preconditioners for time-periodic, parabolic optimal control problems JF - SIAM Journal on Numerical Analysis Y1 - 2016 U6 - https://doi.org/10.1137/140967969 VL - 53 IS - 5 SP - 2206 EP - 2225 ER - TY - JOUR A1 - Domschke, Pia A1 - Groß, Martin A1 - Hiller, Benjamin A1 - Hante, Falk A1 - Schewe, Lars A1 - Schmidt, Martin T1 - Mathematische Modellierung, Simulation und Optimierung von Gastransportnetzwerken JF - gwf-gas/erdgas Y1 - 2015 VL - 11 SP - 880 EP - 885 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 - 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 - 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 - 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 - 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 - 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 - Schweiger, Jonas A1 - Liers, Frauke T1 - A Decomposition Approach for Optimum Gas Network Extension with a Finite Set of Demand Scenarios N2 - Today's gas markets demand more flexibility from the network operators which in turn have to invest into their network infrastructure. As these investments are very cost-intensive and long-living, network extensions should not only focus on a single bottleneck scenario, but should increase the flexibility to fulfill different demand scenarios. In this work, we formulate a model for the network extension problem for multiple demand scenarios and propose a scenario decomposition in order to solve the arising challenging optimization tasks. In fact, euch subproblem consists of a mixed-integer nonlinear optimization problem (MINLP). Valid bounds are derived even without solving the subproblems to optimality. Furthermore, we develop heuristics that prove capable of improving the initial solutions substantially. Results of computational experiments on realistic network topologies are presented. It turns out that our method is able to solve these challenging instances to optimality within a reasonable amount of time. Y1 - 2016 ER - TY - JOUR A1 - Geißler, Björn A1 - Morsi, Antonio A1 - Schewe, Lars A1 - Schmidt, Martin T1 - Solving Highly Detailed Gas Transport MINLPs: Block Separability and Penalty Alternating Direction Methods JF - INFORMS Journal on Computing N2 - Detailed modeling of gas transport problems leads to nonlinear and nonconvex mixed-integer optimization or feasibility models (MINLPs) because both the incorporation of discrete controls of the network as well as accurate physical and technical modeling is required in order to achieve practical solutions. Hence, ignoring certain parts of the physics model is not valid for practice. In the present contribution we extend an approach based on linear relaxations of the underlying nonlinearities by tailored model reformulation techniques yielding block-separable MINLPs. This combination of techniques allows us to apply a penalty alternating direction method and thus to solve highly detailed MINLPs for large-scale real-world instances. The practical strength of the proposed method is demonstrated by a computational study in which we apply the method to instances from steady-state gas transport including both pooling effects with respect to the mixing of gases of different composition and a highly detailed compressor station model. Y1 - 2016 IS - 30(2) SP - 309 EP - 323 ER - TY - JOUR A1 - Geißler, Björn A1 - Morsi, Antonio A1 - Schewe, Lars A1 - Schmidt, Martin T1 - Penalty Alternating Direction Methods for Mixed-Integer Optimization: A New View on Feasibility Pumps JF - SIAM Journal on Optimization N2 - Feasibility pumps are highly effective primal heuristics for mixed-integer linear and nonlinear optimization. However, despite their success in practice there are only few works considering their theoretical properties. We show that feasibility pumps can be seen as alternating direction methods applied to special reformulations of the original problem, inheriting the convergence theory of these methods. Moreover, we propose a novel penalty framework that encompasses this alternating direction method, which allows us to refrain from random perturbations that are applied in standard versions of feasibility pumps in case of failure. We present a convergence theory for the new penalty based alternating direction method and compare the new variant of the feasibility pump with existing versions in an extensive numerical study for mixed-integer linear and nonlinear problems. Y1 - 2017 U6 - https://doi.org/10.1137/16M1069687 VL - 27 IS - 3 SP - 1611 EP - 1636 ER - TY - JOUR A1 - Grimm, Veronika A1 - Martin, Alexander A1 - Schmidt, Martin A1 - Weibelzahl, Martin A1 - Zöttl, Gregor T1 - Transmission and generation investment in electricity markets: The effects of market splitting and network fee regimes JF - European Journal of Operational Research N2 - We propose an equilibrium model that allows to analyze the long-run impact of the electricity market design on transmission line expansion by the regulator and investment in generation capacity by private firms in liberalized electricity markets. The model incorporates investment decisions of the transmission system operator and private firms in expectation of an energy-only market and cost-based redispatch. In different specifications we consider the cases of one vs. multiple price zones (market splitting) and analyze different approaches to recover network cost—in particular lump sum, generation capacity based, and energy based fees. In order to compare the outcomes of our multilevel market model with a first best benchmark, we also solve the corresponding integrated planner problem. Using two test networks we illustrate that energy-only markets can lead to suboptimal locational decisions for generation capacity and thus imply excessive network expansion. Market splitting heals these problems only partially. These results are valid for all considered types of network tariffs, although investment slightly differs across those regimes. KW - Electricity market modeling KW - Mixed-integer nonlinear optimization KW - Multilevel programming KW - Network expansion KW - Transmission management Y1 - 2016 U6 - https://doi.org/10.1016/j.ejor.2016.03.044 VL - 254 IS - 2 SP - 493 EP - 509 ER - TY - JOUR A1 - Grimm, Veronika A1 - Schewe, Lars A1 - Schmidt, Martin A1 - Zöttl, Gregor T1 - Uniqueness of Market Equilibrium on a Network: A Peak-Load Pricing Approach JF - European Journal of Operational Research N2 - In this paper we analyze peak-load pricing in the presence of network constraints. In our setup, firms facing fluctuating demand decide on the size and location of production facilities. They make production decisions constrained by the invested capacities, taking into account that market prices reflect scarce transmission capacities. We state general conditions for existence and uniqueness of the market equilibrium and provide a characterization of equilibrium investment and production. The presented analysis covers the cases of perfect competition and monopoly - the case of strategic firms is approximated by a conjectural variations approach. Our result is a prerequisite for analyzing regulatory policy options with computational multilevel equilibrium models, since uniqueness of the equilibrium at lower levels is of key importance when solving these models. Thus, our paper contributes to an evolving strand of literature that analyzes regulatory policy based on computational multilevel equilibrium models and aims at taking into account individual objectives of various agents, among them not only generators and customers but also, e.g., the regulator deciding on network expansion. KW - Pricing KW - Peak-Load Pricing KW - Networks KW - Uniqueness Y1 - 2017 U6 - https://doi.org/10.1016/j.ejor.2017.03.036 VL - 261 IS - 3 SP - 971 EP - 983 ER - TY - JOUR A1 - Gugat, Martin A1 - Trelat, Emmanuel A1 - Zuazua, Enrique ED - Sepulchre, Rodolphe T1 - Optimal Neumann control for the 1D wave equation: Finite horizon, infinite horizon, boundary tracking terms and the turnpike property JF - Systems & Control Letters N2 - We consider a vibrating string that is fixed at one end with Neumann control action at the other end. We investigate the optimal control problem of steering this system from given initial data to rest, in time TT, by minimizing an objective functional that is the convex sum of the L2L2-norm of the control and of a boundary Neumann tracking term. We provide an explicit solution of this optimal control problem, showing that if the weight of the tracking term is positive, then the optimal control action is concentrated at the beginning and at the end of the time interval, and in-between it decays exponentially. We show that the optimal control can actually be written in that case as the sum of an exponentially decaying term and of an exponentially increasing term. This implies that, if the time TT is large, then the optimal trajectory approximately consists of three arcs, where the first and the third short-time arcs are transient arcs, and in the middle arc the optimal control and the corresponding state are exponentially close to 00. This is an example of a turnpike phenomenon for a problem of optimal boundary control. If T=+∞T=+∞ (infinite time horizon problem), then only the exponentially decaying component of the control remains, and the norms of the optimal control action and of the optimal state decay exponentially in time. In contrast to this situation, if the weight of the tracking term is zero and only the control cost is minimized, then the optimal control is distributed uniformly along the whole interval [0,T][0,T] and coincides with the control given by the Hilbert Uniqueness Method. In addition, we establish a similarity theorem stating that, for every T>0T>0, there exists an appropriate weight λ<1λ<1 for which the optimal solutions of the corresponding finite horizon optimal control problem and of the infinite horizon optimal control problem coincide along the first part of the time interval [0,2][0,2]. We also discuss the turnpike phenomenon from the perspective of a general framework with a strongly continuous semi-group. KW - Neumann boundary control KW - Turnpike phenomenon KW - Exact control Y1 - 2016 U6 - https://doi.org/10.1016/j.sysconle.2016.02.001 VL - 90 SP - 61 EP - 70 ER - TY - CHAP A1 - Hante, Falk T1 - On the relaxation gap for PDE mixed-integer optimal control problems T2 - Proceedings in Applied Mathematics and Mechanics Y1 - 2016 U6 - https://doi.org/10.1002/pamm.201610380 VL - 16 SP - 783 EP - 784 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 - 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 - 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 - 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 - 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 - 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 - 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 - 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 - Geshkovski, B A1 - Zuazua, E T1 - Controllability of one-dimensional viscous free boundary flows N2 - In this work, we address the local controllability of a one-dimensional free boundary problem for a fluid governed by the viscous Burgers equation. The free boundary manifests itself as one moving end of the interval, and its evolution is given by the value of the fluid velocity at this endpoint. We prove that, by means of a control actuating along the fixed boundary, we may steer the fluid to constant velocity in addition to prescribing the free boundary’s position, provided the initial velocities and interface positions are close enough. Y1 - 2021 U6 - https://doi.org/https://doi.org/10.1137/19M1285354 VL - 59 IS - 3 SP - 1830 EP - 1850 ER - TY - INPR A1 - Esteve, C A1 - Kouhkouh, H A1 - Pighin, D A1 - Zuazua, E T1 - The Turnpike property and the long-time behavior of the Hamilton-Jacobi equation N2 - In this work, we analyze the consequences that the so-called turnpike property has on the long-time behavior of the value function corresponding to a finite-dimensional linear-quadratic optimal control problem with general terminal cost and constrained controls. We prove that, when the time horizon TTT tends to infinity, the value function asymptotically behaves as W(x)+c T+λW(x) + c\, T + \lambda W(x)+cT+λ, and we provide a control interpretation of each of these three terms, making clear the link with the turnpike property. As a by-product, we obtain the long-time behavior of the solution to the associated Hamilton-Jacobi-Bellman equation in a case where the Hamiltonian is not coercive in the momentum variable. As a result of independent interest, we provide a new turnpike result for the linear-quadratic optimal control problem with constrained control. As a main feature, our turnpike result applies to the case when the steady optimum may saturate the control constraints. This prevented us from proving the turnpike property with an exponential rate, which is well-known to hold for the unconstrained case. Y1 - 2021 ER -