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 - 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 - 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 - 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 - 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 - 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 - 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 - 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 - 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 - 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 - 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 - 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 - 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 - 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 - 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 - 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 - 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 - Geißler, Björn A1 - Morsi, Antonio A1 - Schewe, Lars A1 - Schmidt, Martin T1 - Solving Power-Constrained Gas Transportation Problems using an MIP-based Alternating Direction Method JF - Computers & Chemical Engineering N2 - We present a solution algorithm for problems from steady-state gas transport optimization. Due to nonlinear and nonconvex physics and engineering models as well as discrete controllability of active network devices, these problems lead to difficult nonconvex mixed-integer nonlinear optimization models. The proposed method is based on mixed-integer linear techniques using piecewise linear relaxations of the nonlinearities and a tailored alternating direction method. Most other publications in the field of gas transport optimization only consider pressure and flow as main physical quantities. In this work, we additionally incorporate heat power supplies and demands as well as a mixing model for different gas qualities. We demonstrate the capabilities of our method on Germany's largest transport networks and hereby present numerical results on the largest instances that were ever reported in the literature for this problem class. Y1 - 2016 U6 - https://doi.org/10.1016/j.compchemeng.2015.07.005 VL - 82 IS - 2 SP - 303 EP - 317 ER - TY - JOUR A1 - Reuß, Markus A1 - Welder, Lara A1 - Thürauf, Johannes A1 - Linßen, Jochen A1 - Grube, Thomas A1 - Schewe, Lars A1 - Schmidt, Martin A1 - Stolten, Detlef A1 - Robinius, Martin T1 - Modeling Hydrogen Networks for Future Energy Systems: A Comparison of Linear and Nonlinear Approaches JF - International Journal of Hydrogen Energy N2 - Common energy system models that integrate hydrogen transport in pipelines typically simplify fluid flow models and reduce the network size in order to achieve solutions quickly. This contribution analyzes two different types of pipeline network topologies (namely, star and tree networks) and two different fluid flow models (linear and nonlinear) for a given hydrogen capacity scenario of electrical reconversion in Germany to analyze the impact of these simplifications. For each network topology, robust demand and supply scenarios are generated. The results show that a simplified topology, as well as the consideration of detailed fluid flow, could heavily influence the total pipeline investment costs. For the given capacity scenario, an overall cost reduction of the pipeline costs of 37% is observed for the star network with linear cost compared to the tree network with nonlinear fluid flow. The impact of these improvements regarding the total electricity reconversion costs has led to a cost reduction of 1.4%, which is fairly small. Therefore, the integration of nonlinearities into energy system optimization models is not recommended due to their high computational burden. However, the applied method for generating robust demand and supply scenarios improved the credibility and robustness of the network topology, while the simplified fluid flow consideration can lead to infeasibilities. Thus, we suggest the utilization of the nonlinear model for post- processing to prove the feasibility of the results and strengthen their credibility, while retaining the computational performance of linear modeling. Y1 - 2019 U6 - https://doi.org/10.1016/j.ijhydene.2019.10.080 ER - TY - INPR A1 - Grimm, Veronika A1 - Hintermüller, Michael A1 - Huber, Olivier A1 - Schewe, Lars A1 - Schmidt, Martin A1 - Zöttl, Gregor T1 - A PDE-Constrained Generalized Nash Equilibrium Approach for Modeling Gas Markets with Transport N2 - We investigate a class of generalized Nash equilibrium problems (GNEPs) in which the objectives of the individuals are interdependent and the shared constraint consists of a system of partial differential equations. This setup is motivated by the modeling of strategic interactions of competing firms, which explicitly take into account the dynamics of transporting a commodity, such as natural gas, through a network. We establish the existence of a variational equilibrium of the GNEP. In the case of symmetric firms, we identify an equivalent optimization problem. We use this model to numerically explore the impact of linepacking, that is the use of the network as a temporary storage device. In particular, we study the firms' decisions under various linepacking abilities and analyze which market participants benefit from it. Y1 - ER - TY - INPR A1 - Halbig, Katrin A1 - Hümbs, Lukas A1 - Rösel, Florian A1 - Schewe, Lars A1 - Weninger, Dieter T1 - Computing optimality certificates for convex mixed-integer nonlinear problems N2 - Every optimization problem has a corresponding verification problem which verifies whether a given optimal solution is in fact optimal. In the literature there are a lot of such ways to verify optimality for a given solution, e.g., the branch-and-bound tree. To simplify this task, Baes et al. introduced optimality certificates for convex mixed-integer nonlinear programs and proved that these are bounded in the number of integer variables. We introduce an algorithm to compute the certificates and conduct computational experiments. Through the experiments we show that the optimality certificates can be surprisingly small. Y1 - 2021 ER -