TY - INPR A1 - Krebs, Vanessa A1 - Müller, Michael A1 - Schmidt, Martin T1 - Γ-Robust Linear Complementarity Problems with Ellipsoidal Uncertainty Sets T2 - International Transactions in Operational Research N2 - We study uncertain linear complementarity problems (LCPs), i.e., problems in which the LCP vector q or the LCP matrix M may contain uncertain parameters. To this end, we use the concept of Γ-robust optimization applied to the gap function formulation of the LCP. Thus, this work builds upon [16]. There, we studied Γ-robustified LCPs for l1- and box-uncertainty sets, whereas we now focus on ellipsoidal uncertainty set. For uncertainty in q or M, we derive conditions for the tractability of the robust counterparts. For these counterparts, we also give conditions for the existence and uniqueness of their solutions. Finally, a case study for the uncertain traffic equilibrium problem is considered, which illustrates the effects of the values of Γ on the feasibility and quality of the respective robustified solutions. KW - Robust optimization KW - Linear complementarity problems KW - Ellipsoidal uncertainty sets KW - Traffic equilibrium problems Y1 - 2019 IS - 29(1) SP - 417 EP - 441 ER - TY - JOUR A1 - Krug, Richard A1 - Mehrmann, Volker A1 - Schmidt, Martin T1 - Nonlinear Optimization of District Heating Networks JF - Optimization and Engineering N2 - We develop a complementarity-constrained nonlinear optimization model for the time-dependent control of district heating networks. The main physical aspects of water and heat flow in these networks are governed by nonlinear and hyperbolic 1d partial differential equations. In addition, a pooling-type mixing model is required at the nodes of the network to treat the mixing of different water temperatures. This mixing model can be recast using suitable complementarity constraints. The resulting problem is a mathematical program with complementarity constraints subject to nonlinear partial differential equations describing the physics. In order to obtain a tractable problem, we apply suitable discretizations in space and time, resulting in a finite-dimensional optimization problem with complementarity constraints for which we develop a suitable reformulation with improved constraint regularity. Moreover, we propose an instantaneous control approach for the discretized problem, discuss practically relevant penalty formulations, and present preprocessing techniques that are used to simplify the mixing model at the nodes of the network. Finally, we use all these techniques to solve realistic instances. Our numerical results show the applicability of our techniques in practice. KW - District heating networks KW - Nonlinear optimization KW - Euler equations KW - Differential-algebraic equations KW - Complementarity constraints Y1 - 2019 IS - 22(2) SP - 783 EP - 819 ER - TY - JOUR A1 - Farshbaf Shaker, Mohammad Hassan A1 - Gugat, Martin A1 - Heitsch, Holger A1 - Henrion, René T1 - Optimal Neumann boundary control of a vibrating string with uncertain initial data and probabilistic terminal constraints N2 - In optimal control problems, often initial data are required that are not known exactly in practice. In order to take into account this uncertainty, we consider optimal control problems for a system with an uncertain initial state. A finite terminal time is given. On account of the uncertainty of the initial state, it is not possible to prescribe an exact terminal state. Instead, we are looking for controls that steer the system into a given neighborhood of the desired terminal state with sufficiently high probability. This neighborhood is described in terms of an inequality for the terminal energy. The probabilistic constraint in the considered optimal control problem leads to optimal controls that are robust against the inevitable uncertainties of the initial state. We show the existence of such optimal controls. Numerical examples with optimal Neumann control of the wave equation are presented. KW - PDE constrained optimization, probabilistic constraints, uncertain initial data Y1 - U6 - https://doi.org/10.1137/19M1269944 ER - TY - JOUR A1 - Heitsch, Holger T1 - On probabilistic capacity maximization in a stationary gas network JF - Optimization N2 - The question for the capacity of a given gas network, i.e., determining the maximal amount of gas that can be transported by a given network, appears as an essential question that network operators and political administrations are regularly faced with. In that context we present a novel mathematical approach in order to assist gas network operators in managing increasing uncertainty with respect to customers gas nominations and in exposing free network capacities while reliability of transmission and supply is taken into account. The approach is based on the rigorous examination of optimization problems with nonlinear probabilistic constraints. As consequence we deal with solving a problem belonging to the class of probabilistic/robust optimization problems, which can be formulated with some joint probabilistic constraint over an infinite system of random inequalities. We will show that the inequality system can be reduced to a finite one in the situation of considering a tree network topology. A detailed study of the problem of maximizing bookable capacities in a stationary gas network is presented that comes up with an algebraic model involving Kirchhoff's first and second laws. The focus will be on both the theoretical and numerical side. The analytical part consists in introducing and validating a generalized version of the known rank two constraint qualification implying the differentiability of the considered capacity problem. The results are important in order to solve the capacity problem numerically, where function and gradient evaluations of the probabilistic constraints are performed by an approach using spheric-radial decomposition applicable for multivariate Gaussian random variables and more general distributions. KW - stationary gas networks, booked capacities, probabilistic constraints, constraint qualification, spheric-radial decomposition Y1 - 2019 U6 - https://doi.org/10.1080/02331934.2019.1625353 ER - TY - JOUR A1 - Heitsch, Holger A1 - Strogies, Nikolai T1 - Consequences of uncertain friction for the transport of natural gas through passive networks of pipelines JF - Springer N2 - Assuming a pipe-wise constant structure of the friction coefficient in the modeling of natural gas transport through a passive network of pipes via semilinear systems of balance laws with associated linear coupling and boundary conditions, uncertainty in this parameter is quantified by a Markov chain Monte Carlo method. Information on the prior distribution is obtained from practitioners. The results are applied to the problem of validating technical feasibility under random exit demand in gas transport networks. The impact of quantified uncertainty to the probability level of technical feasible exit demand situations is studied by two example networks of small and medium size. The gas transport of the network is modeled by stationary solutions that are steady states of the time dependent semilinear problems. KW - uncertainty quantification, Markov chain Monte Carlo, reliability of gas networks, nomination validation, spheric-radial decomposition Y1 - 2019 SP - 211 EP - 238 ET - Topics in Applied Analysis and Optimisation ER - TY - INPR A1 - Hümbs, Lukas A1 - Martin, Alexander A1 - Schewe, Lars T1 - Exploiting complete linear descriptions for decentralized power market problems with integralities N2 - It is well known that linear prices supporting a competitive equilibrium exist in the case of convex markets, however, in the presence of integralities this is open and hard to decide in general. We present necessary and sufficient conditions for the existence of such prices for decentralized market problems where market participants have integral decision variables and their feasible sets are given in complete linear description. We utilize total unimodularity and the aforementioned conditions to show that such linear prices exist and present some applications. Furthermore, we compute competitive equilibria for two classes of decentralized market problems arising in energy markets and show that competitive equilibria may exist regardless of integralities. KW - Mixed-integer programming KW - Competitive equilibrium KW - Linear prices KW - Total unimodularity Y1 - 2019 N1 - Former title: "On the existence of solutions to market equilibrium problems with integralities" ER - TY - JOUR A1 - Hauschild, Sarah-Alexa A1 - Marheineke, Nicole A1 - Mehrmann, Volker A1 - Mohring, Jan A1 - Badlyan, Arbi Moses A1 - Rein, Markus A1 - Schmidt, Martin T1 - Port-Hamiltonian modeling of district heating networks JF - Progress in Differential Algebraic Equations II (edited by Reis T., Grundel S., and Schöps S). Differential-Algebraic Equations Forum N2 - This paper provides a first contribution to port-Hamiltonian modeling of district heating networks. By introducing a model hierarchy of flow equations on the network, this work aims at a thermodynamically consistent port-Hamiltonian embedding of the partial differential-algebraic systems. We show that a spatially discretized network model describing the advection of the internal energy density with respect to an underlying incompressible stationary Euler-type hydrodynamics can be considered as a parameter-dependent finite-dimensional port-Hamiltonian system. Moreover, we present an infinite-dimensional port-Hamiltonian formulation for a compressible instationary thermodynamic fluid flow in a pipe. Based on these first promising results, we raise open questions and point out research perspectives concerning structure-preserving discretization, model reduction, and optimization. KW - Partial differential equations on networks KW - Port-Hamiltonian model framework KW - Energy-based formulation KW - District heating network KW - Thermodynamic fluid flow Y1 - 2019 ER - TY - JOUR A1 - Grimm, Veronika A1 - Orlinskaya, Galina A1 - Schewe, Lars A1 - Schmidt, Martin A1 - Zöttl, Gregor T1 - Optimal Design of Retailer-Prosumer Electricity Tariffs Using Bilevel Optimization JF - Computers & Operations Research N2 - We compare various flexible tariffs that have been proposed to cost-effectively govern a prosumer's electricity management - in particular time-of-use (TOU), critical-peak-pricing (CPP), and a real-time-pricing tariff (RTP). As the outside option, we consider a fixed-price tariff (FP) that restricts the specific characteristics of TOU, CPP, and RTP, so that the flexible tariffs are at least as profitable for the prosumer as the fixed-price tariff. We propose bilevel models to determine the optimal interplay between the retailer's tariff design and the prosumer's decisions on using the storage, on consumption, and on electricity purchases from as well as electricity sales to the grid. The single-level reformulations of the considered bilevel models are computationally highly challenging optimization problems since they, e.g., combine bilinearities and mixed-integer aspects for modeling certain tariff structures. Based on a computational study using real-world data, we find that RTP increases retailer profits, however, leads to the largest price volatility for the prosumer. TOU and CPP only yield mild additional retailer profits and, due to the multiplicity of optimal plans on the part of the prosumer, imply uncertain revenues for the retailer. KW - Electricity tariffs KW - Pricing KW - Bilevel optimization KW - Mixed-integer optimization KW - Tariff design Y1 - 2019 IS - 114 ER - TY - JOUR A1 - Gatzert, Nadine A1 - Martin, Alexander A1 - Schmidt, Martin A1 - Seith, Benjamin A1 - Vogl, Nikolai T1 - Portfolio Optimization with Irreversible Long-Term Investments in Renewable Energy under Policy Risk: A Mixed-Integer Multistage Stochastic Model and a Moving-Horizon Approach JF - European Journal of Operational Research N2 - Portfolio optimization is an ongoing hot topic of mathematical optimization and management science. Due to the current financial market environment with low interest rates and volatile stock markets, it is getting more and more important to extend portfolio optimization models by other types of investments than classical assets. In this paper, we present a mixed-integer multistage stochastic model that includes investment opportunities in irreversible and long-term infrastructure projects in the context of renewable energies, which are also subject to policy risk. On realistic time scales for investment problems of this type, the resulting instances are by far too large to be solved with today's most evolved optimization software. Thus, we present a tailored moving-horizon approach together with suitable approximations and simplifications of the model. We evaluate these approximations and simplifications in a computational sensitivity analysis and derive a final model that can be tackled on a realistic instance by our moving-horizon approach. KW - Mixed-integer optimization KW - Multistage stochastic optimization KW - Portfolio optimization KW - Illiquid investments KW - Policy risk Y1 - 2019 ER - TY - JOUR A1 - Göttlich, Simone A1 - Hante, Falk A1 - Potschka, Andreas A1 - Schewe, Lars T1 - Penalty alternating direction methods for mixed-integer optimal control with combinatorial constraints JF - Mathematical Programming N2 - We consider mixed-integer optimal control problems with combinatorial constraints that couple over time such as minimum dwell times. We analyze a lifting and decomposition approach into a mixed-integer optimal control problem without combinatorial constraints and a mixed-integer problem for the combinatorial constraints in the control space. Both problems can be solved very efficiently with existing methods such as outer convexification with sum-up-rounding strategies and mixed-integer linear programming techniques. The coupling is handled using a penalty-approach. We provide an exactness result for the penalty which yields a solution approach that convergences to partial minima. We compare the quality of these dedicated points with those of other heuristics amongst an academic example and also for the optimization of electric transmission lines with switching of the network topology for flow reallocation in order to satisfy demands. Y1 - 2019 ER - TY - INPR A1 - Brodskyi, Yan A1 - Hante, Falk A1 - Seidel, Arno T1 - Stabilization of Partial Differential Equations by Sequential Action Control N2 - We extend the framework of sequential action control to systems of partial differential equations which can be posed as abstract linear control problems in a Hilbert space. We follow a late-lumping approach and show that the control action can be explicitly obtained from variational principles using adjoint information. Moreover, we analyze the closed-loop system obtained from the SAC feedback for quadratic stage costs. We apply this theory prototypically to an unstable heat equation and verify the results numerically. Y1 - 2019 ER - TY - INPR A1 - Liers, Frauke A1 - Schewe, Lars A1 - Thürauf, Johannes T1 - Radius of Robust Feasibility for Mixed-Integer Problems N2 - For a mixed-integer linear problem (MIP) with uncertain constraints, the radius of robust feasibility (RRF) determines a value for the maximal “size” of the uncertainty set such that robust feasibility of the MIP can be guaranteed. The approaches for the RRF in the literature are restricted to continuous optimization problems. We first analyze relations between the RRF of a MIP and its continuous linear (LP) relaxation. In particular, we derive conditions under which a MIP and its LP relaxation have the same RRF. Afterward, we extend the notion of the RRF such that it can be applied to a large variety of optimization problems and uncertainty sets. In contrast to the setting commonly used in the literature, we consider for every constraint a potentially different uncertainty set that is not necessarily full-dimensional. Thus, we generalize the RRF to MIPs as well as to include “safe” variables and constraints, i.e., where uncertainties do not affect certain variables or constraints. In the extended setting, we again analyze relations between the RRF for a MIP and its LP relaxation. Afterward, we present methods for computing the RRF of LPs as well as of MIPs with safe variables and constraints. Finally, we show that the new methodologies can be successfully applied to the instances in the MIPLIB 2017 for computing the RRF. KW - Robust Optimization, Mixed-integer programming, Uncertainty sets, Robust feasibility Y1 - 2019 U6 - https://doi.org/10.1287/ijoc.2020.1030 PB - Informs Journal on Computing ER - TY - JOUR A1 - Gugat, Martin A1 - Schuster, Michael ED - Weber, Gerhard-Wilhelm T1 - Stationary Gas Networks with Compressor Control and Random Loads: Optimization with Probabilistic Constraints JF - Mathematical Problems in Engineering N2 - We introduce a stationary model for gas flow based on simplified isothermal Euler equations in a non-cycled pipeline network. Especially the problem of the feasibility of a random load vector is analyzed. Feasibility in this context means the existence of a flow vectormeeting these loads, which satisfies the physical conservation laws with box constraints for the pressure. An important aspect of the model is the support of compressor stations, which counteract the pressure loss caused by friction in the pipes.The network is assumed to have only one influx node; all other nodes are efflux nodes.With these assumptions the set of feasible loads can be characterized analytically. In addition we show the existence of optimal solutions for some optimization problems with probabilistic constraints. A numerical example based on real data completes this paper. KW - Validation of nominations, Stationary states, Isothermal Euler equations, Ideal Gas, Gas network, Gas transport, Compressor control, Uncertainty, Chance Constraints, Spheric-radial decomposition Y1 - 2019 U6 - https://doi.org/https://doi.org/10.1155/2018/7984079 ER - TY - JOUR A1 - Gugat, Martin A1 - Schultz, Rüdiger A1 - Schuster, Michael T1 - Convexity and Starshapedness of Feasible Sets in Stationary Flow Networks JF - Networks and Heterogeneous Media N2 - We deal with a stationary model for flow through a network. The flows are determined by the values at the boundary nodes of the network that we call the loads of the network. In the applications , the feasible loads must satisfy some box constraints. We analyze the structure of the set of feasible loads. Our analysis is motivated by gas pipeline flows, where the box constraints are pressure bounds. We present sufficient conditions to show, that the feasible set is star-shaped with respect to special points. For stronger conditions, we prove the convexity of the set of feasible loads. All the results are given for active and passive networks, i.e. networks with and without inner control. This analysis is motivated by the aim to use the spheric-radial decomposition for stochastic boundary data in this model. This paper can be used for simplifying the algorithmic use of the spheric-radial decomposition. KW - Validation of nominations, Stationary states, Isothermal Euler equations, Gas networks, Convexity, Star-Shapedness, Spheric-radial decomposition Y1 - 2020 U6 - https://doi.org/10.3934/nhm.2020008 SP - 171 EP - 195 ER - TY - INPR A1 - Kleinert, Thomas A1 - Labbé, Martine A1 - Plein, Fränk A1 - Schmidt, Martin T1 - There's No Free Lunch: On the Hardness of Choosing a Correct Big-M in Bilevel Optimization T2 - Operations Research N2 - One of the most frequently used approaches to solve linear bilevel optimization problems consists in replacing the lower-level problem with its Karush-Kuhn-Tucker (KKT) conditions and by reformulating the KKT complementarity conditions using techniques from mixed-integer linear optimization. The latter step requires to determine some big-M constant in order to bound the lower level's dual feasible set such that no bilevel-optimal solution is cut off. In practice, heuristics are often used to find a big-M although it is known that these approaches may fail. In this paper, we consider the hardness of two proxies for the above mentioned concept of a bilevel-correct big-M. First, we prove that verifying that a given big-M does not cut off any feasible vertex of the lower level's dual polyhedron cannot be done in polynomial time unless P=NP. Second, we show that verifying that a given big-M does not cut off any optimal point of the lower level's dual problem (for any point in the projection of the high-point relaxation onto the leader's decision space) is as hard as solving the original bilevel problem. KW - Bilevel optimization KW - Mathematical programs with complementarity constraints (MPCC) KW - Bounding polyhedra KW - Big-M KW - Hardness Y1 - 2019 IS - 68(6) SP - 1716 EP - 1721 ER - TY - JOUR A1 - Ullmann, Sebastian A1 - Müller, Christopher A1 - Lang, Jens T1 - Stochastic Galerkin Reduced Basis Methods for Parametrized Linear Convection-Diffusion-Reaction Equations N2 - We consider the estimation of parameter-dependent statistics of functional outputs of steady-state convection–diffusion–reaction equations with parametrized random and deterministic inputs in the framework of linear elliptic partial differential equations. For a given value of the deterministic parameter, a stochastic Galerkin finite element (SGFE) method can estimate the statistical moments of interest of a linear output at the cost of solving a single, large, block-structured linear system of equations. We propose a stochastic Galerkin reduced basis (SGRB) method as a means to lower the computational burden when statistical outputs are required for a large number of deterministic parameter queries. Our working assumption is that we have access to the computational resources necessary to set up such a reduced-order model for a spatial-stochastic weak formulation of the parameter-dependent model equations. In this scenario, the complexity of evaluating the SGRB model for a new value of the deterministic parameter only depends on the reduced dimension. To derive an SGRB model, we project the spatial-stochastic weak solution of a parameter-dependent SGFE model onto a reduced basis generated by a proper orthogonal decomposition (POD) of snapshots of SGFE solutions at representative values of the parameter. We propose residual-corrected estimates of the parameter-dependent expectation and variance of linear functional outputs and provide respective computable error bounds.We test the SGRB method numerically for a convection–diffusion–reaction problem, choosing the convective velocity as a deterministic parameter and the parametrized reactivity or diffusivity field as a random input. Compared to a standard reduced basis model embedded in a Monte Carlo sampling procedure, the SGRB model requires a similar number of reduced basis functions to meet a given tolerance requirement. However, only a single run of the SGRB model suffices to estimate a statistical output for a new deterministic parameter value, while the standard reduced basis model must be solved for each Monte Carlo sample. Y1 - 2018 U6 - https://doi.org/doi:10.3390/fluids6080263 VL - Fluids IS - 6 SP - 263 ER - TY - JOUR A1 - Mindt, Pascal A1 - Lang, Jens A1 - Domschke, Pia T1 - Entropy-Preserving Coupling of Hierarchical Gas Models N2 - This paper is concerned with coupling conditions at junctions for transport models which differ in their fidelity to describe transient flow in gas pipelines. It also includes the integration of compressors between two pipes with possibly different models. A hierarchy of three one-dimensional gas transport models is built through the 3 × 3 polytropic Euler equations, the 2 × 2 isentropic Euler equations and a simplified version of it for small velocities. To ensure entropy preservation, we make use of the novel entropy-preserving coupling conditions recently proposed by Lang and Mindt [Netw. Heterog. Media, 13:177-190, 2018] and require the equality of the total enthalpy at the junction and that the specific entropy for pipes with outgoing flow equals the convex combination of all entropies that belong to pipes with incoming flow. We prove the existence and uniqueness of solutions to generalised Riemann problems at a junction in the neighbourhood of constant coupling functions and stationary states which belong to the subsonic region. This provides the basis for the well-posedness of certain Cauchy problems for initial data with sufficiently small total variation. Y1 - 2018 U6 - https://doi.org/doi:10.1137/19M1240034 VL - SIAM Journal on Mathematical Analysis IS - 51 SP - 4754 EP - 4775 ER - TY - JOUR A1 - Schneider, Moritz A1 - Lang, Jens A1 - Weiner, Rüdiger T1 - Super-Convergent Implicit-Explicit Peer Methods with Variable Step Sizes N2 - Dynamical systems with sub-processes evolving on many different time scales are ubiquitous in applications. Their efficient solution is greatly enhanced by automatic time step variation. This paper is concerned with the theory, construction and application of IMEX-Peer methods that are super-convergent for variable step sizes and A-stable in the implicit part. IMEX schemes combine the necessary stability of implicit and low computational costs of explicit methods to efficiently solve systems of ordinary differential equations with both stiff and non-stiff parts included in the source term. To construct super-convergent IMEX-Peer methods which keep their higher order for variable step sizes and exhibit favourable linear stability properties, we derive necessary and sufficient conditions on the nodes and coefficient matrices and apply an extrapolation approach based on already computed stage values. New super-convergent IMEX-Peer methods of order s + 1 for s = 2, 3, 4 stages are given as result of additional order conditions which maintain the super-convergence property independent of step size changes. Numerical experiments and a comparison to other super-convergent IMEX-Peer methods show the potential of the new methods when applied with local error control. Y1 - 2019 U6 - https://doi.org/doi:10.1016/j.cam.2019.112501 VL - J. Comput. Appl. Math. IS - 387 SP - 112501 ER - TY - INPR A1 - Schewe, Lars A1 - Schmidt, Martin A1 - Weninger, Dieter T1 - A Decomposition Heuristic for Mixed-Integer Supply Chain Problems T2 - Operations Research Letters N2 - Mixed-integer supply chain models typically are very large but are also very sparse and can be decomposed into loosely coupled blocks. In this paper, we use general-purpose techniques to obtain a block decomposition of supply chain instances and apply a tailored penalty alternating direction method, which exploits the structural properties of the decomposed instances. We further describe problem-specific enhancements of the algorithm and present numerical results on real-world instances that illustrate the applicability of the approach. KW - Supply chain KW - Mixed-integer optimization KW - Decomposition KW - Penalty method KW - Alternating direction methods Y1 - 2019 IS - 48(3) SP - 225 EP - 232 ER - TY - JOUR A1 - Grübel, Julia A1 - Kleinert, Thomas A1 - Krebs, Vanessa A1 - Orlinskaya, Galina A1 - Schewe, Lars A1 - Schmidt, Martin A1 - Thürauf, Johannes T1 - On Electricity Market Equilibria with Storage: Modeling, Uniqueness, and a Distributed ADMM JF - Computers & Operations Research N2 - We consider spot-market trading of electricity including storage operators as additional agents besides producers and consumers. Storages allow for shifting produced electricity from one time period to a later one. Due to this, multiple market equilibria may occur even if classical uniqueness assumptions for the case without storages are satisfied. For models containing storage operators, we derive sufficient conditions that ensure uniqueness of generation and demand. We also prove uniqueness of the market equilibrium for the special case of a single storage operator. Nevertheless, in case of multiple storage operators, uniqueness fails to hold in general, which we show by illustrative examples. We conclude the theoretical discussion with a general ex-post condition for proving the uniqueness of a given solution. In contrast to classical settings without storages, the computation of market equilibria is much more challenging since storage operations couple all trading events over time. For this reason, we propose a tailored parallel and distributed alternating direction method of multipliers (ADMM) for efficiently computing spot-market equilibria over long time horizons. We first analyze the parallel performance of the method itself. Finally, we show that the parallel ADMM clearly outperforms solving the respective problems directly and that it is capable of solving instances with more than 42 million variables in less than 13 minutes. Y1 - 2019 U6 - https://doi.org/10.1016/j.cor.2019.104783 IS - 114 ER - TY - JOUR A1 - Kleinert, Thomas A1 - Schmidt, Martin T1 - Computing Feasible Points of Bilevel Problems with a Penalty Alternating Direction Method JF - INFORMS Journal on Computing N2 - Bilevel problems are highly challenging optimization problems that appear in many applications of energy market design, critical infrastructure defense, transportation, pricing, etc. Often, these bilevel models are equipped with integer decisions, which makes the problems even harder to solve. Typically, in such a setting in mathematical optimization one develops primal heuristics in order to obtain feasible points of good quality quickly or to enhance the search process of exact global methods. However, there are comparably few heuristics for bilevel problems. In this paper, we develop such a primal heuristic for bilevel problems with mixed-integer linear or quadratic upper level and linear or quadratic lower level. The heuristic is based on a penalty alternating direction method, which allows for a theoretical analysis. We derive a convergence theory stating that the method converges to a stationary point of an equivalent single-level reformulation of the bilevel problem and extensively test the method on a test set of more than 2800 instances - which is one of the largest computational test sets ever used in bilevel programming. The study illustrates the very good performance of the proposed method, both in terms of running times and solution quality. This renders the method a suitable sub-routine in global bilevel solvers as well as a reasonable standalone approach. KW - Bilevel optimization KW - Mixed-integer bilevel optimization KW - Stationary points KW - Penalty methods KW - Alternating direction methods Y1 - 2019 U6 - https://doi.org/10.1287/ijoc.2019.0945 IS - 33 (1) SP - 198 EP - 215 ER - TY - JOUR A1 - Krebs, Vanessa A1 - Schmidt, Martin T1 - Γ-Robust Linear Complementarity Problems JF - Optimization Methods and Software N2 - Complementarity problems are often used to compute equilibria made up of specifically coordinated solutions of different optimization problems. Specific examples are game-theoretic settings like the bimatrix game or energy market models like for electricity or natural gas. While optimization under uncertainties is rather well-developed, the field of equilibrium models represented by complementarity problems under uncertainty - especially using the concepts of robust optimization - is still in its infancy. In this paper, we extend the theory of strictly robust linear complementarity problems (LCPs) to Γ-robust settings, where existence of worst-case-hedged equilibria cannot be guaranteed. Thus, we study the minimization of the worst-case gap function of Γ-robust counterparts of LCPs. For box and l1-norm uncertainty sets we derive tractable convex counterparts for monotone LCPs and study their feasibility as well as the existence and uniqueness of solutions. To this end, we consider uncertainties in the vector and in the matrix defining the LCP. We additionally study so-called ρ-robust solutions, i.e., solutions of relaxed uncertain LCPs. Finally, we illustrate the Γ-robust concept applied to LCPs in the light of the above mentioned classical examples of bimatrix games and market equilibrium modeling. KW - Linear complementarity problems KW - Robust optimization KW - Optimization under uncertainty KW - Γ-robustness KW - Tractable counterparts Y1 - 2019 ER - TY - JOUR A1 - Gonzalez Grandon, Tatiana A1 - Henrion, Rene A1 - Perez-Aros, Pedro T1 - Dynamic probabilistic constraints under continuous random distributions N2 - In this paper we address novel results on the theoretical structural analysis of dynamic joint probabilistic constraints under continuous random variables. This dynamic probabilistic function is important when decisions are time-dependent and when the modeler can react on past observations. We first study the continuity of dynamic probabilistic constraints and provide strong and weak semi-continuous results depending on whether the policies are supposed to be in the L^p or W^{1,p} spaces. Moreover, we prove the non-convexity of the feasible set of decisions induced by a dynamic probability function in the L^p space. Lastly, for a simple two-stage model, verifiable conditions for Lipschitz continuity and differentiability of this probability function are derived and endowed with explicit derivative formulae. Y1 - 2019 U6 - https://doi.org/10.1007/s10107-020-01593-z ER - TY - JOUR A1 - Gugat, Martin A1 - Hante, Falk T1 - On the turnpike phenomenon for optimal boundary control problems with hyperbolic systems JF - SIAM Journal on Control and Optimization N2 - We study problems of optimal boundary control with systems governed by linear hyperbolic partial differential equations. The objective function is quadratic and given by an integral over the finite time interval (0,T) that depends on the boundary traces of the solution. If the time horizon T is sufficiently large, the solution of the dynamic optimal boundary control problem can be approximated by the solution of a steady state optimization problem. We show that for T to infinity the approximation error converges to zero in the sense of the norm in L^2(0,1) with the rate 1/T, if the time interval (0,T) is transformed to the fixed interval (0,1). Moreover, we show that also for optimal boundary control problems with integer constraints for the controls the turnpike phenomenon occurs. In this case the steady state optimization problem also has the integer constraints. If T is sufficiently large, the integer part of each solution of the dynamic optimal boundary control problem with integer constraints is equal to the integer part of a solution of the static problem. A numerical verification is given for a control problem in gas pipeline operations. Y1 - 2019 U6 - https://doi.org/10.1137/17M1134470 VL - 57 IS - 1 SP - 264 EP - 289 ER - TY - JOUR A1 - Labbé, Martine A1 - Plein, Fränk A1 - Schmidt, Martin T1 - Bookings in the European Gas Market: Characterisation of Feasibility and Computational Complexity Results JF - Optimization and Engineering N2 - As a consequence of the liberalisation of the European gas market in the last decades, gas trading and transport have been decoupled. At the core of this decoupling are so-called bookings and nominations. Bookings are special capacity right contracts that guarantee that a specified amount of gas can be supplied or withdrawn at certain entry or exit nodes of the network. These supplies and withdrawals are nominated at the day-ahead. The special property of bookings then is that they need to be feasible, i.e., every nomination that complies with the given bookings can be transported. While checking the feasibility of a nomination can typically be done by solving a mixed-integer nonlinear feasibility problem, the verification of feasibility of a set of bookings is much harder. The reason is the robust nature of feasibility of bookings - namely that for a set of bookings to be feasible, all compliant nominations, i.e., infinitely many, need to be checked for feasibility. In this paper, we consider the question of how to verify the feasibility of given bookings for a number of special cases. For our physics model we impose a steady-state potential-based flow model and disregard controllable network elements. For this case we derive a characterisation of feasible bookings, which is then used to show that the problem is in coNP for the general case but can be solved in polynomial time for linear potential-based flow models. Moreover, we present a dynamic programming approach for deciding the feasibility of a booking in tree-shaped networks even for nonlinear flow models. It turns out that the hardness of the problem mainly depends on the combination of the chosen physics model as well as the specific network structure under consideration. Thus, we give an overview over all settings for which the hardness of the problem is known and finally present a list of open problems. KW - Gas networks KW - Booking KW - Nomination KW - Computational complexity KW - Trees Y1 - 2018 IS - 21(1) SP - 305 EP - 334 ER - TY - JOUR A1 - Hante, Falk M. A1 - Schmidt, Martin T1 - Convergence of Finite-Dimensional Approximations for Mixed-Integer Optimization with Differential Equations JF - Control and Cybernetics N2 - We consider a direct approach to solve mixed-integer nonlinear optimization problems with constraints depending on initial and terminal conditions of an ordinary differential equation. In order to obtain a finite-dimensional problem, the dynamics are approximated using discretization methods. In the framework of general one-step methods, we provide sufficient conditions for the convergence of this approach in the sense of the corresponding optimal values. The results are obtained by considering the discretized problem as a parametric mixed-integer nonlinear optimization problem in finite dimensions, where the maximum step size for discretizing the dynamics is the parameter. In this setting, we prove the continuity of the optimal value function under a stability assumption for the integer feasible set and second-order conditions from nonlinear optimization. We address the necessity of the conditions on the example of pipe sizing problems for gas networks. KW - Optimization with differential equations KW - Optimal value function KW - Lipschitz continuity KW - Parametric optimization KW - Mixed-integer nonlinear programming Y1 - 2018 ER - TY - JOUR A1 - Ambrosius, Mirjam A1 - Grimm, Veronika A1 - Kleinert, Thomas A1 - Liers, Frauke A1 - Schmidt, Martin A1 - Zöttl, Gregor T1 - Endogenous Price Zones and Investment Incentives in Electricity Markets: An Application of Multilevel Optimization with Graph Partitioning JF - Energy Economics N2 - In the course of the energy transition, load and supply centers are growing apart in electricity markets worldwide, rendering regional price signals even more important to provide adequate locational investment incentives. This paper focuses on electricity markets that operate under a zonal pricing market design. For a fixed number of zones, we endogenously derive the optimal configuration of price zones and available transfer capacities on a network in order to optimally govern investment and production decisions in the long run. In a multilevel mixed-integer nonlinear model that contains a graph partitioning problem on the first level, we determine welfare-maximizing price zones and available transfer capacities for a given electricity market and analyze their impact on market outcomes. Using a generalized Benders decomposition approach developed in Grimm et al. (2019) and a problem-tailored scenario clustering for reducing the input data size, we are able to solve the model to global optimality even for large instances. We apply the approach to the German electricity market as an example to examine the impact of optimal zoning on key performance indicators such as welfare, generation mix and locations, or electricity prices. It turns out that even for a small number of price zones, an optimal configuration of zones induces a welfare level that almost approaches the first best. KW - Electricity Markets KW - Price Zones KW - Investment Incentives KW - Multilevel Optimization KW - Graph Partitioning Y1 - 2018 IS - 92 ER - TY - JOUR A1 - Schewe, Lars A1 - Schmidt, Martin A1 - Thürauf, Johannes T1 - Structural Properties of Feasible Bookings in the European Entry-Exit Gas Market System JF - 4OR N2 - In this work we analyze the structural properties of the set of feasible bookings in the European entry-exit gas market system. We present formal definitions of feasible bookings and then analyze properties that are important if one wants to optimize over them. Thus, we study whether the sets of feasible nominations and bookings are bounded, convex, connected, conic, and star-shaped. The results depend on the specific model of gas flow in a network. Here, we discuss a simple linear flow model with arc capacities as well as nonlinear and mixed-integer nonlinear models of passive and active networks, respectively. It turns out that the set of feasible bookings has some unintuitive properties. For instance, we show that the set is nonconvex even though only a simple linear flow model is used. KW - Gas networks KW - Booking KW - Entry-exit system KW - Convexity KW - Flow models Y1 - 2018 U6 - https://doi.org/10.1007/s10288-019-00411-3 IS - 18 SP - 197 EP - 218 ER - TY - JOUR A1 - Hante, Falk T1 - Mixed-Integer Optimal Control for PDEs: Relaxation via Differential Inclusions and Applications to Gas Network Optimization JF - Mathematical Modelling, Optimization, Analytic and Numerical Solutions, Springer Series on Industrial and Applied Mathematics, 2020 N2 - We show that mixed-integer control problems for evolution type partial differential equations can be regarded as operator differential inclusions. This yields a relaxation result including a characterization of the optimal value for mixed-integer optimal control problems with control constraints. The theory is related to partial outer convexification and sum-up rounding methods. The results are applied to optimal valve switching control for gas pipeline operations. A numerical example illustrates the approach. Y1 - 2018 ER - TY - JOUR A1 - Hojny, Christopher A1 - Joormann, Imke A1 - Lüthen, Hendrik A1 - Schmidt, Martin T1 - Mixed-Integer Programming Techniques for the Connected Max-k-Cut Problem JF - Mathematical Programming Computation N2 - We consider an extended version of the classical Max-k-Cut problem in which we additionally require that the parts of the graph partition are connected. For this problem we study two alternative mixed-integer linear formulations and review existing as well as develop new branch-and-cut techniques like cuts, branching rules, propagation, primal heuristics, and symmetry breaking. The main focus of this paper is an extensive numerical study in which we analyze the impact of the different techniques for various test sets. It turns out that the techniques from the existing literature are not sufficient to solve an adequate fraction of the test sets. However, our novel techniques significantly outperform the existing ones both in terms of running times and the overall number of instances that can be solved. KW - Max-cut KW - Connectivity KW - Branch-and-cut KW - Mixed-integer programming Y1 - 2018 ER - TY - JOUR A1 - Kramer, Anja A1 - Krebs, Vanessa A1 - Schmidt, Martin T1 - Strictly and Γ-Robust Counterparts of Electricity Market Models: Perfect Competition and Nash-Cournot Equilibria JF - Operations Research Perspectives N2 - This paper mainly studies two topics: linear complementarity problems for modeling electricity market equilibria and optimization under uncertainty. We consider both perfectly competitive and Nash–Cournot models of electricity markets and study their robustifications using strict robustness and the Γ-approach. For three out of the four combinations of economic competition and robustification, we derive algorithmically tractable convex optimization counterparts that have a clear-cut economic interpretation. In the case of perfect competition, this result corresponds to the two classical welfare theorems, which also apply in both considered robust cases that again yield convex robustified problems. Using the mentioned counterparts, we can also prove the existence and, in some cases, uniqueness of robust equilibria. Surprisingly, it turns out that there is no such economic sensible counterpart for the case of Γ-robustifications of Nash–Cournot models. Thus, an analogue of the welfare theorems does not hold in this case. Finally, we provide a computational case study that illustrates the different effects of the combination of economic competition and uncertainty modeling. KW - Robust optimization KW - Linear complementarity problems KW - Electricity market equilibrium models KW - Perfect competition KW - Nash-Cournot competition Y1 - 2018 IS - 89(2) SP - 100197 ER - TY - JOUR A1 - Schewe, Lars A1 - Schmidt, Martin T1 - The Impact of Potential-Based Physics Models on Pricing in Energy Networks JF - Central European Journal of Operations Research N2 - Pricing of access to energy networks is an important issue in liberalized energy sectors because of the natural monopoly character of the underlying transport infrastructures. We introduce a general pricing framework for potential-based energy flows in arbitrarily structured transport networks. In different specifications of our general pricing model we discuss first- and second-best pricing results and compare different pricing outcomes of potential-free and potential-based energy flow models. Our results show that considering nonlinear laws of physics leads to significantly different pricing results on networks and that these differences can only be seen in sufficiently complex, e.g., cyclic, networks as they can be found in real-world situations. KW - Energy Networks KW - Pricing KW - Gas Networks KW - Electricity Networks Y1 - 2018 IS - 28(3) SP - 1003 EP - 1029 ER - TY - JOUR A1 - Gugat, Martin A1 - Rosier, Lionel A1 - Perrollaz, Vincent ED - Arendt, W. ED - Pierre, M. T1 - Boundary stabilization of quasilinear hyperbolic systems of balance laws: exponential decay for small source terms JF - Journal of Evolution Equations N2 - We investigate the long-time behaviour 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. The proof of the existence and uniqueness of a solution defined for all positive times is also provided in this paper. Y1 - 2018 U6 - https://doi.org/10.1007/s00028-018-0449-z ER - TY - JOUR A1 - Schmidt, Martin A1 - Sirvent, Mathias A1 - Wollner, Winnifried T1 - The Cost of Not Knowing Enough: Mixed-Integer Optimization with Implicit Lipschitz Nonlinearities JF - Optimization Letters N2 - It is folklore knowledge that nonconvex mixed-integer nonlinear optimization problems can be notoriously hard to solve in practice. In this paper we go one step further and drop analytical properties that are usually taken for granted in mixed-integer nonlinear optimization. First, we only assume Lipschitz continuity of the nonlinear functions and additionally consider multivariate implicit constraint functions that cannot be solved for any parameter analytically. For this class of mixed-integer problems we propose a novel algorithm based on an approximation of the feasible set in the domain of the nonlinear function---in contrast to an approximation of the graph of the function considered in prior work. This method is shown to compute approximate global optimal solutions in finite time and we also provide a worst-case iteration bound. In some first numerical experiments we show that the ``cost of not knowing enough'' is rather high by comparing our approach with the open-source global solver SCIP. This reveals that a lot of work is still to be done for this highly challenging class of problems and we thus finally propose some possible directions of future research. KW - Mixed-Integer Nonlinear Optimization, Global Optimization, Lipschitz Optimization, Gas Networks Y1 - 2018 ER - TY - JOUR A1 - Kleinert, Thomas A1 - Schmidt, Martin T1 - Global Optimization of Multilevel Electricity Market Models Including Network Design and Graph Partitioning JF - Discrete Optimization N2 - We consider the combination of a network design and graph partitioning model in a multilevel framework for determining the optimal network expansion and the optimal zonal configuration of zonal pricing electricity markets, which is an extension of the model discussed in [25] that does not include a network design problem. The two classical discrete optimization problems of network design and graph partitioning together with nonlinearities due to economic modeling yield extremely challenging mixed-integer nonlinear multilevel models for which we develop two problem-tailored solution techniques. The first approach relies on an equivalent bilevel formulation and a standard KKT transformation thereof including novel primal-dual bound tightening techniques, whereas the second is a tailored generalized Benders decomposition. For the latter, we strengthen the Benders cuts of [25] by using the structure of the newly introduced network design subproblem. We prove for both methods that they yield global optimal solutions. Afterward, we compare the approaches in a numerical study and show that the tailored Benders approach clearly outperforms the standard KKT transformation. Finally, we present a case study that illustrates the economic effects that are captured in our model. KW - Network design KW - Graph partitioning KW - Multilevel optimization KW - Mixed-integer optimization KW - Electricity market design Y1 - 2018 IS - 33 SP - 43 EP - 69 ER - TY - JOUR A1 - Robinius, Martin A1 - Schewe, Lars A1 - Schmidt, Martin A1 - Stolten, Detlef A1 - Thürauf, Johannes A1 - Welder, Lara T1 - Robust Optimal Discrete Arc Sizing for Tree-Shaped Potential Networks JF - Computational Optimization and Applications N2 - We consider the problem of discrete arc sizing for tree-shaped potential networks with respect to infinitely many demand scenarios. This means that the arc sizes need to be feasible for an infinite set of scenarios. The problem can be seen as a strictly robust counterpart of a single-scenario network design problem, which is shown to be NP-complete even on trees. In order to obtain a tractable problem, we introduce a method for generating a finite scenario set such that optimality of a sizing for this finite set implies the sizing's optimality for the originally given infinite set of scenarios. We further prove that the size of the finite scenario set is quadratically bounded above in the number of nodes of the underlying tree and that it can be computed in polynomial time. The resulting problem can then be solved as a standard mixed-integer linear optimization problem. Finally, we show the applicability of our theoretical results by computing globally optimal arc sizes for a realistic hydrogen transport network of Eastern Germany. KW - Discrete arc sizing KW - Mixed-integer linear optimization KW - Potential networks KW - Scenario generation KW - Robust optimization Y1 - 2018 U6 - https://doi.org/10.1007/s10589-019-00085-x IS - 73(3) SP - 791 EP - 819 ER - TY - JOUR A1 - Hajian, Soheil A1 - Hintermüller, Michael A1 - Schillings, Claudia A1 - Strogies, Nikolai T1 - A Bayesian approach to parameter identification in gas networks JF - Control and Cybernetics N2 - The inverse problem of identifying the friction coefficient in an isothermal semilinear Euler system is considered. Adopting a Bayesian approach, the goal is to identify the distribution of the quantity of interest based on a finite number of noisy measurements of the pressure at the boundaries of the domain. First well-posedness of the underlying non-linear PDE system is shown using semigroup theory, and then Lipschitz continuity of the solution operator with respect to the friction coefficient is established. Based on the Lipschitz property, well-posedness of the resulting Bayesian inverse problem for the identification of the friction coefficient is inferred. Numerical tests for scalar and distributed parameters are performed to validate the theoretical results. Y1 - 2018 VL - 48 SP - 377 EP - 402 ER - TY - JOUR A1 - Rüffler, Fabian A1 - Mehrmann, Volker A1 - Hante, Falk T1 - Optimal Model Switching for Gas Flow in Pipe Networks N2 - We consider model adaptivity for gas flow in pipeline networks. For each instant in time and for each pipe in the network a model for the gas flow is to be selected from a hierarchy of models in order to maximize a performance index that balances model accuracy and computational cost for a simulation of the entire network. This combinatorial problem involving partial differential equations is posed as an optimal switching control problem for abstract semilinear evolutions. We provide a theoretical and numerical framework for solving this problem using a two stage gradient descent approach based on switching time and mode insertion gradients. A numerical study demonstrates the practicability of the approach. Y1 - 2018 ER - TY - JOUR A1 - Gugat, Martin A1 - Steffensen, Sonja ED - Trelat, Emmanuel T1 - DYNAMIC BOUNDARY CONTROL GAMES WITH NETWORKS OF STRINGS JF - ESAIM: Control, Optimisation and Calculus of Variations (ESAIM: COCV) N2 - Consider a star-shaped network of strings. Each string is governed by the wave equation. At each boundary node of the network there is a player that performs Dirichlet boundary control action and in this way influences the system state. At the central node, the states are coupled by algebraic conditions in such a way that the energy is conserved. We consider the corresponding antagonistic game where each player minimizes a certain quadratic objective function that is given by the sum of a control cost and a tracking term for the final state. We prove that under suitable assumptions a unique Nash equilibrium exists and give an explicit representation of the equilibrium strategies. Y1 - 2018 U6 - https://doi.org/10.1051/cocv/2017082 ER - TY - JOUR A1 - Farshbaf-Shaker, M. Hassan A1 - Henrion, Rene A1 - Hömberg, Dietmar T1 - Properties of Chance Constraints in Infinite Dimensions with an Application to PDE Constrained Optimization JF - Set-Valued and Variational Analysis N2 - Chance constraints represent a popular tool for finding decisions that enforce the satisfaction of random inequality systems in terms of probability. They are widely used in optimization problems subject to uncertain parameters as they arise in many engineering applications. Most structural results of chance constraints (e.g., closedness, convexity, Lipschitz continuity, differentiability etc.) have been formulated in finite dimensions. The aim of this paper is to generalize some of these well-known semi-continuity and convexity properties as well as a stability result to an infinite dimensional setting. The abstract results are applied to a simple PDE constrained control problem subject to (uniform) state chance constraints. KW - Chance constraints KW - Probabilistic constraints KW - PDE constrained optimization Y1 - 2018 U6 - https://doi.org/doi:10.1007/s11228-017-0452-5 ER - TY - JOUR A1 - Hantoute, Abderrahim A1 - Henrion, Rene A1 - Perez-Aros, Pedro T1 - Subdifferential characterization of probability functions under Gaussian distribution N2 - Probability functions figure prominently in optimization problems of engineering. They may be nonsmooth even if all input data are smooth. This fact motivates the consideration of subdifferentials for such typically just continuous functions. The aim of this paper is to provide subdifferential formulae of such functions in the case of Gaussian distributions for possibly infinite-dimensional decision variables and nonsmooth (locally Lipschitzian) input data. These formulae are based on the spheric-radial decomposition of Gaussian random vectors on the one hand and on a cone of directions of moderate growth on the other. By successively adding additional hypotheses, conditions are satisfied under which the probability function is locally Lipschitzian or even differentiable. Y1 - 2018 U6 - https://doi.org/10.1007/s10107-018-1237-9 ER - TY - JOUR A1 - Hintermüller, Michael A1 - Strogies, Nikolai T1 - Identification of the friction function in a semilinear system for gas transport through a network JF - Optimization Methods and Software N2 - An identification problem for the friction parameter in a semilinear system of balance laws, describing the transport of gas through a passive network of pipelines, is considered. The existence of broad solutions to the state system is proven and sensitivity results for the corresponding solution operator are obtained. The existence of solutions to the output least squares formulation of the identification problem, based on noisy measurements over time at fixed spatial positions is established. Finally, numerical experiments validate the theoretical findings. Y1 - 2017 VL - 35 SP - 576 EP - 617 ER - TY - JOUR A1 - Mehrmann, Volker A1 - Schmidt, Martin A1 - Stolwijk, Jeroen J. T1 - Model and Discretization Error Adaptivity within Stationary Gas Transport Optimization JF - Vietnam Journal of Mathematics N2 - The minimization of operation costs for natural gas transport networks is studied. Based on a recently developed model hierarchy ranging from detailed models of instationary partial differential equations with temperature dependence to highly simplified algebraic equations, modeling and discretization error estimates are presented to control the overall error in an optimization method for stationary and isothermal gas flows. The error control is realized by switching to more detailed models or finer discretizations if necessary to guarantee that a prescribed model and discretization error tolerance is satisfied in the end. We prove convergence of the adaptively controlled optimization method and illustrate the new approach with numerical examples. KW - Gas network optimization KW - Isothermal stationary Euler equations KW - Model hierarchy KW - Adaptive error control KW - Marking strategy Y1 - 2017 IS - 46(4) SP - 779 EP - 801 ER - TY - JOUR A1 - Schneider, Moritz A1 - Lang, Jens A1 - Hundsdorfer, Willem T1 - Extrapolation-Based Super-Convergent Implicit-Explicit Peer Methods with A-stable Implicit Part N2 - In this paper we extend the implicit-explicit (IMEX) methods of Peer type recently developed in [Lang, Hundsdorfer, J. Comp. Phys., 337:203–215, 2017] to a broader class of two-step methods that allow the construction of super- convergent IMEX-Peer methods with A-stable implicit part. IMEX schemes combine the necessary stability of implicit and low computational costs of ex- plicit methods to efficiently solve systems of ordinary differential equations with both stiff and non-stiff parts included in the source term. To construct super- convergent IMEX-Peer methods with favourable stability properties, we derive necessary and sufficient conditions on the coefficient matrices and apply an extrapolation approach based on already computed stage values. Optimised super-convergent IMEX-Peer methods of order s + 1 for s = 2, 3, 4 stages are given as result of a search algorithm carefully designed to balance the size of the stability regions and the extrapolation errors. Numerical experiments and a comparison to other IMEX-Peer methods are included. Y1 - 2017 U6 - https://doi.org/10.1016/j.jcp.2018.04.006 VL - J. Comput. Physics IS - Vol. 367 SP - 121 EP - 133 ER - TY - JOUR A1 - Krebs, Vanessa A1 - Schmidt, Martin T1 - Uniqueness of Market Equilibria on Networks with Transport Costs JF - Operations Research Perspectives N2 - We study the existence and uniqueness of equilibria for perfectly competitive markets in capacitated transport networks. The model under consideration is rather general so that it captures basic aspects of related models in, e.g., gas or electricity networks. We formulate the market equilibrium model as a mixed complementarity problem and show the equivalence to a welfare maximization problem. Using the latter we prove uniqueness of the resulting equilibrium for piecewise linear and symmetric transport costs under additional mild assumptions. Moreover, we show the necessity of these assumptions by illustrating examples that possess multiple solutions if our assumptions are violated. KW - Market Equilibria KW - Networks KW - Transport Costs KW - Uniqueness KW - Perfect Competition Y1 - 2017 IS - 5 SP - 169 EP - 173 ER - TY - JOUR A1 - Burlacu, Robert A1 - Egger, Herbert A1 - Groß, Martin A1 - Martin, Alexander A1 - Pfetsch, Marc A1 - Schewe, Lars A1 - Sirvent, Mathias A1 - Skutella, Martin T1 - Maximizing the storage capacity of gas networks: a global MINLP approach N2 - In this paper, we study the transient optimization of gas networks, focusing in particular on maximizing the storage capacity of the network. We include nonlinear gas physics and active elements such as valves and compressors, which due to their switching lead to discrete decisions. The former is described by a model derived from the Euler equations that is given by a coupled system of nonlinear parabolic partial differential equations (PDEs). We tackle the resulting mathematical optimization problem by a first-discretize-then-optimize approach. To this end, we introduce a new discretization of the underlying system of parabolic PDEs and prove well-posedness for the resulting nonlinear discretized system. Endowed with this discretization, we model the problem of maximizing the storage capacity as a non-convex mixed-integer nonlinear problem (MINLP). For the numerical solution of the MINLP, we algorithmically extend a well-known relaxation approach that has already been used very successfully in the field of stationary gas network optimization. This method allows us to solve the problem to global optimality by iteratively solving a series of mixed-integer problems (MIPs). Finally, we present two case studies that illustrate the applicability of our approach. KW - Mixed-Integer Nonlinear Programming KW - Transient Gas Transport Optimization KW - Storage Capacity Maximization KW - Power-to-Gas KW - First-Discretize-Then-Optimize Y1 - 2019 U6 - https://doi.org/10.1007/s11081-018-9414-5 VL - 20 SP - 543 EP - 573 ET - Optimization and Engineering ER - TY - JOUR A1 - Grimm, Veronika A1 - Grübel, Julia A1 - Schewe, Lars A1 - Schmidt, Martin A1 - Zöttl, Gregor T1 - Nonconvex Equilibrium Models for Gas Market Analysis: Failure of Standard Techniques and Alternative Modeling Approaches JF - European Journal on Operational Research N2 - This paper provides a first approach to assess gas market interaction on a network with nonconvex flow models. In the simplest possible setup that adequately reflects gas transport and market interaction, we elaborate on the relation of the solution of a simultaneous competitive gas market game, its corresponding mixed nonlinear complementarity problem (MNCP), and a first-best benchmark. We provide conditions under which the solution of the simultaneous game is also the solution of the corresponding MNCP. However, equilibria cannot be determined by the MNCP as the transmission system operator's (TSO’s) first-order conditions are insufficient, which goes back to nonconvexities of the gas flow model. This also implies that the welfare maximization problem may have multiple solutions that sometimes do not even coincide with any of the market equilibria. Our analysis shows that, even in the absence of strategic firms, market interaction fails to implement desirable outcomes from a welfare perspective due to the TSO’s incentive structure. We conclude that the technical environment calls for a market design that commits the TSO to a welfare objective through regulation and propose a design where the market solution corresponds to a welfare maximum and vice versa. KW - Natural Gas Markets KW - Nonconvex Equilibrium Models KW - Uniqueness KW - Multiplicity KW - Fundamental Welfare Theorems Y1 - 2017 IS - 273(3) SP - 1097 EP - 1108 ER - TY - INPR A1 - Schmitt, Johann Michael A1 - Ulbrich, Stefan T1 - Optimal Boundary Control of Hyperbolic Balance Laws with State Constraints N2 - In this paper we analyze the optimal control of initial-boundary value problems for entropy solutions of scalar hyperbolic balance laws with pointwise state constraints. Hereby, we suppose that the initial and the boundary data switch between different C¹-functions at certain switching points, where the C¹ -functions and the switching points are considered as the control. For a class of cost functionals, we prove first order necessary optimality conditions for the corresponding optimal control problem with state constraints. Furthermore, we use a Moreau-Yosida type regularization to approximate the optimal control problem with state constraints. We derive optimality conditions for the regularized problems and finally prove convergence to the solution of the optimal control problem with state constraints. Y1 - 2021 ER - TY - RPRT A1 - Hiller, Benjamin A1 - Walther, Tom T1 - Improving branching for disjunctive polyhedral models using approximate convex decompositions N2 - Disjunctive sets arise in a variety of optimization models and much esearch has been devoted to obtain strong relaxations for them. This paper focuses on the evaluation of the relaxation during the branch-and-bound search process. We argue that the branching possibilities (\ie binary variables) of the usual formulations are unsuitable to obtain strong bounds early in the search process as they do not capture the overall shape of the the entire disjunctive set. To analyze and exploit the shape of the disjunctive set we propose to compute a hierarchy of approximate convex decompositions and show how to extend the known formulations to obtain improved branching behavior. KW - disjunctive set KW - convex hull reformulation KW - branch-and-bound KW - approximate convex decomposition Y1 - 2017 ER - TY - INPR A1 - Egger, Herbert A1 - Kugler, Thomas A1 - Wollner, Winnifried T1 - Numerical optimal control of instationary gas transport with control and state constraints N2 - We consider the optimal control of a nonlinear hyperbolic system of balance laws on a one-dimensional network which arises in the context of gas transport in pipeline systems. State constraints, which are required for the safe operation of the system, are incorporated by a barrier method. We discuss the well-posedness of the governing system of partial differential-algebraic equations and investigate the existence of minimizers. For the numerical solution, we then consider the approximation of the state equation by mixed finite elements in space and a particular linear implicit time integration scheme that can be interpreted as a discontinuous Galerkin approximation. We establish well- posedness of this discretization scheme and prove the existence of minimizers for the corresponding discretized optimal control problem and discuss its numerical solution by a projected Gauß-Newton method. The efficient realization of the Jacobian and Hessian of the quadratic approximations that have to be minimized in every iteration of the Gauß-Newton method can be obtained via the solution of discretized sensitivity and adjoint equations. These are obtained by formal differentiation and transposition of the Galerkin methods employed for the discretization of the state equations. All approximations obtained after discretization can thus be interpreted as functions on the continuous level and, since the functional analytic setting is not changed by the Galerkin discretization, we observe mesh independence of the resulting fully discrete methods. For illustration of our theoretical results and to demonstrate the efficiency of the proposed method, we present numerical results for two test problems that model typical situations that may arise in the daily operation of gas networks. Y1 - 2017 ER - TY - JOUR A1 - Adelhütte, Dennis A1 - Aßmann, Denis A1 - Gonzàlez Grandòn, Tatiana A1 - Gugat, Martin A1 - Heitsch, Holger A1 - Liers, Frauke A1 - Henrion, René A1 - Nitsche, Sabrina A1 - Schultz, Rüdiger A1 - Stingl, Michael A1 - Wintergerst, David T1 - Joint model of probabilistic/robust (probust) constraints applied to gas network optimization N2 - Optimization tasks under uncertain conditions abound in many real-life applications. Whereas solution approaches for probabilistic constraints are often developed in case the uncertainties can be assumed to follow a certain probability distribution, robust approaches are usually used in case solutions are sought that are feasible for all realizations of uncertainties within some pre-defined uncertainty set. As many applications contain different types of uncertainties that require robust as well as probabilistic treatments, we deal with a class of joint probabilistic/robust constraints as its appears in optimization problems under uncertainty. Focusing on complex uncertain gas network optimization problems, we show the relevance of this class of problems for the task of maximizing free booked capacities in an algebraic model for a stationary gas network. We furthermore present approaches for their solution. Finally, we study the problem of controlling a transient system that is governed by the wave equation. The task consists in determining controls such that a certain robustness measure remains below some given upper bound, with high probability. KW - robust optimization KW - chance constraints KW - optimal control KW - spheric-radial decomposition Y1 - 2017 U6 - https://doi.org/10.1007/s10013-020-00434-y ER -