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 - Hiller, Benjamin A1 - Koch, Thorsten A1 - Schewe, Lars A1 - Schwarz, Robert A1 - Schweiger, Jonas T1 - A System to Evaluate Gas Network Capacities: Concepts and Implementation T2 - EJOR N2 - Since 2005, the gas market in the European Union is liberalized and the trading of natural gas is decoupled from its transport. The transport is done by so-called transmissions system operators (TSOs). The market model established by the European Union views the gas transmission network as a black box, providing shippers (gas traders and consumers) the opportunity to transport gas from any entry to any exit. TSOs are required to offer maximum independent capacities at each entry and exit such that the resulting gas flows can be realized by the network without compromising security of supply. Therefore, evaluating the available transport capacities is extremely important to the TSOs. This paper gives an overview of the toolset for evaluating gas network capacities that has been developed within the ForNe project, a joint research project of seven research partners initiated by Open Grid Europe, Germany's biggest TSO. While most of the relevant mathematics is described in the book "Evaluating Gas Network Capacities", this article sketches the system as a whole, describes some developments that have taken place recently, and gives some details about the current implementation. Y1 - 2017 ER - TY - JOUR A1 - Grimm, Veronika A1 - Schewe, Lars A1 - Schmidt, Martin A1 - Zöttl, Gregor T1 - A Multilevel Model of the European Entry-Exit Gas Market JF - Mathematical Methods of Operations Research N2 - In entry-exit gas markets as they are currently implemented in Europe, network constraints do not affect market interaction beyond the technical capacities determined by the TSO that restrict the quantities individual firms can trade at the market. It is an up to now unanswered question to what extent existing network capacity remains unused in an entry-exit design and to what extent feasible adjustments of the market design could alleviate inefficiencies. In this paper, we offer a four-level modeling framework that is capable of analyzing these issues and provide some first results on the model structure. In order to decouple gas trading from network congestion management, the TSO is required to determine technical capacities and corresponding booking fees at every entry and exit node up front. Firms book those capacities, which gives them the right to charge or discharge an amount of gas at a certain node up to this capacity in every scenario. Beyond these technical capacities and the resulting bookings, gas trade is unaffected by network constraints. The technical capacities have to ensure that transportation of traded quantities is always feasible. We assume that the TSO is regulated and determines technical capacities, fees, and transportation costs under a welfare objective. As a first step we moreover assume perfect competition among gas traders and show that the booking and nomination decisions can be analyzed in a single level. We prove that this aggregated model has a unique solution. We also show that the TSO's decisions can be subsumed in one level as well. If so, the model boils down to a mixed-integer nonlinear bilevel problem with robust aspects. In addition, we provide a first-best benchmark that allows to assess welfare losses that occur in an entry-exit system. Our approach provides a generic framework to analyze various aspects in the context of semi-liberalized gas markets. Therefore, we finally discuss and provide guidance on how to include several important aspects into the approach, such as network and production capacity investment, uncertain data, market power, and intra-day trading. KW - Entry-Exit System KW - Gas Market KW - Multilevel Modeling Y1 - 2017 IS - 89(2) SP - 223 EP - 255 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 - INPR A1 - Schmidt, Martin A1 - Hiller, Benjamin A1 - Koch, Thorsten A1 - Pfetsch, Marc A1 - Geißler, Björn A1 - Henrion, René A1 - Joormann, Imke A1 - Martin, Alexander A1 - Morsi, Antonio A1 - Römisch, Werner A1 - Schewe, Lars A1 - Schultz, Rüdiger A1 - Steinbach, Marc C. T1 - Capacity Evaluation for Large-Scale Gas Networks N2 - Natural gas is important for the energy turnaround in many countries like in Germany, where it serves as a "bridging energy" towards a fossil-free energy supply in the future. About 20% of the total German energy demand is provided by natural gas, which is transported through a complex pipeline network with a total length of about 30000 km and the efficient use of the given transport infrastructure for natural gas is of political, economic, and societal importance. As a consequence of the liberalization of the European gas market in the last decades, gas trading and transport have been decoupled. This has led to new challenges for gas transport companies, and mathematical optimization is perfectly suited for tackling many of these challenges. However, the underlying mathematical problems are by far too hard to be solved by today's general-purpose software so that novel mathematical theory and algorithms are needed. The industrial research project "ForNe: Research Cooperation Network Optimization" has been initiated and funded by Open Grid Europe in 2009 and brought together experts in mathematical optimization from seven German universities and research institutes, which cover almost the entire range of mathematical optimization: integer and nonlinear optimization as well as optimization under uncertainty. The mathematical research results have been put together in a software package that has been delivered to Open Grid Europe at the end of the project. Moreover, the research is still continuing - e.g., in the Collaborative Research Center/Transregio 154 "Mathematical Modelling, Simulation and Optimization using the Example of Gas Networks" funded by the German Research Foundation. Y1 - 2019 ER - TY - JOUR A1 - Schewe, Lars A1 - Schmidt, Martin A1 - Thürauf, Johannes T1 - Computing Technical Capacities in the European Entry-Exit Gas Market is NP-Hard JF - Annals of Operations Research N2 - As a result of its liberalization, the European gas market is organized as an entry-exit system in order to decouple the trading and transport of natural gas. Roughly summarized, the gas market organization consists of four subsequent stages. First, the transmission system operator (TSO) is obliged to allocate so-called maximal technical capacities for the nodes of the network. Second, the TSO and the gas traders sign mid- to long-term capacity-right contracts, where the capacity is bounded above by the allocated technical capacities. These contracts are called bookings. Third, on a day-ahead basis, gas traders can nominate the amount of gas that they inject or withdraw from the network at entry and exit nodes, where the nominated amount is bounded above by the respective booking. Fourth and finally, the TSO has to operate the network such that the nominated amounts of gas can be transported. By signing the booking contract, the TSO guarantees that all possibly resulting nominations can indeed be transported. Consequently, maximal technical capacities have to satisfy that all nominations that comply with these technical capacities can be transported through the network. This leads to a highly challenging mathematical optimization problem. We consider the specific instantiations of this problem in which we assume capacitated linear as well as potential-based flow models. In this contribution, we formally introduce the problem of Computing Technical Capacities (CTC) and prove that it is NP-complete on trees and NP-hard in general. To this end, we first reduce the Subset Sum problem to CTC for the case of capacitated linear flows in trees. Afterward, we extend this result to CTC with potential-based flows and show that this problem is also NP-complete on trees by reducing it to the case of capacitated linear flow. Since the hardness results are obtained for the easiest case, i.e., on tree-shaped networks with capacitated linear as well as potential-based flows, this implies the hardness of CTC for more general graph classes. KW - European Entry-Exit Gas Market KW - Technical Capacities KW - Potential-Based Flows KW - Computational Complexity KW - NP-Hardness Y1 - 2020 U6 - https://doi.org/10.1007/s10479-020-03725-2 IS - 295 SP - 337 EP - 362 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 - 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 - 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 - 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 -