@article{GrossMarcEScheweetal.2019, author = {Groß, Martin and Marc E., Pfetsch and Schewe, Lars and Schmidt, Martin and Skutella, Martin}, title = {Algorithmic Results for Potential-Based Flows: Easy and Hard Cases}, volume = {73}, number = {3}, edition = {Networks}, doi = {10.1002/net.21865}, pages = {303 -- 324}, year = {2019}, abstract = {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.}, language = {en} } @article{SchmidtSirventWollner2017, author = {Schmidt, Martin and Sirvent, Mathias and Wollner, Winnifried}, title = {A Decomposition Method for MINLPs with Lipschitz Continuous Nonlinearities}, series = {Mathematical Programming}, journal = {Mathematical Programming}, number = {178(1)}, pages = {449 -- 483}, year = {2017}, abstract = {Many mixed-integer optimization problems are constrained by nonlinear functions that do not possess desirable analytical properties like convexity or factorability or cannot even be evaluated exactly. This is, e.g., the case for problems constrained by differential equations or for models that rely on black-box simulation runs. For these problem classes, we present, analyze, and test algorithms that solve mixed-integer problems with only Lipschitz continuous nonlinearities. Our theoretical results depend on the assumptions made on the (in)exactness of function evaluations and on the knowledge of Lipschitz constants. If Lipschitz constants are known, we prove finite termination at approximate globally optimal points both for the case of exact and inexact function evaluations. If only approximate Lipschitz constants are known, we prove finite termination and derive additional conditions under which infeasibility can be detected. A computational study for gas transport problems and an academic case study show the applicability of our algorithms to real-world problems and how different assumptions on the constraint functions up- or downgrade the practical performance of the methods.}, language = {en} } @article{SchmidtAssmannBurlacuetal.2017, author = {Schmidt, Martin and Aßmann, Denis and Burlacu, Robert and Humpola, Jesco and Joormann, Imke and Kanelakis, Nikolaos and Koch, Thorsten and Oucherif, Djamal and Pfetsch, Marc E. and Schewe, Lars and Schwarz, Robert and Sirvent, Mathias}, title = {GasLib - A Library of Gas Network Instances}, series = {Data}, volume = {4}, journal = {Data}, number = {2}, doi = {10.3390/data2040040}, pages = {18}, year = {2017}, abstract = {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.}, language = {en} } @article{HanteSchmidt2017, author = {Hante, Falk and Schmidt, Martin}, title = {Complementarity-Based Nonlinear Programming Techniques for Optimal Mixing in Gas Networks}, series = {EURO Journal on Computational Optimization}, journal = {EURO Journal on Computational Optimization}, number = {7(3)}, pages = {299 -- 323}, year = {2017}, abstract = {We consider nonlinear and nonsmooth mixing aspects in gas transport optimization problems. As mixed-integer reformulations of pooling-type mixing models already render small-size instances computationally intractable, we investigate the applicability of smooth nonlinear programming techniques for equivalent complementarity-based reformulations. Based on recent results for remodeling piecewise affine constraints using an inverse parametric quadratic programming approach, we show that classical stationarity concepts are meaningful for the resulting complementarity-based reformulation of the mixing equations. Further, we investigate in a numerical study the performance of this reformulation compared to a more compact complementarity-based one that does not feature such beneficial regularity properties. All computations are performed on publicly available data of real-world size problem instances from steady-state gas transport.}, language = {en} } @article{KrebsScheweSchmidt2017, author = {Krebs, Vanessa and Schewe, Lars and Schmidt, Martin}, title = {Uniqueness and Multiplicity of Market Equilibria on DC Power Flow Networks}, series = {European Journal on Operations Research}, journal = {European Journal on Operations Research}, number = {271(1)}, pages = {165 -- 178}, year = {2017}, abstract = {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.}, language = {en} } @article{LeugeringMartinSchmidtetal.2017, author = {Leugering, G{\"u}nter and Martin, Alexander and Schmidt, Martin and Sirvent, Mathias}, title = {Nonoverlapping Domain Decomposition for Optimal Control Problems governed by Semilinear Models for Gas Flow in Networks}, volume = {46}, number = {3}, publisher = {Control and Cybernetics}, pages = {191 -- 225}, year = {2017}, abstract = {We consider optimal control problems for gas flow in pipeline networks. The equations of motion are taken to be represented by a first-order system of hyperbolic semilinear equations derived from the fully nonlinear isothermal Euler gas equations. We formulate an optimal control problem on a network and introduce a tailored time discretization thereof. In order to further reduce the complexity, we consider an instantaneous control strategy. The main part of the paper is concerned with a nonoverlapping domain decomposition of the optimal control problem on the graph into local problems on smaller sub-graphs - ultimately on single edges. We prove convergence of the domain decomposition method on networks and study the wellposedness of the corresponding time-discrete optimal control problems. The point of the paper is that we establish virtual control problems on the decomposed subgraphs such that the corresponding optimality systems are in fact equal to the systems obtained via the domain decomposition of the entire optimality system.}, language = {en} } @article{GrimmScheweSchmidtetal.2017, author = {Grimm, Veronika and Schewe, Lars and Schmidt, Martin and Z{\"o}ttl, Gregor}, title = {Uniqueness of Market Equilibrium on a Network: A Peak-Load Pricing Approach}, series = {European Journal of Operational Research}, volume = {261}, journal = {European Journal of Operational Research}, number = {3}, doi = {10.1016/j.ejor.2017.03.036}, pages = {971 -- 983}, year = {2017}, abstract = {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.}, language = {en} } @article{GrimmKleinertLiersetal.2017, author = {Grimm, Veronika and Kleinert, Thomas and Liers, Frauke and Schmidt, Martin and Z{\"o}ttl, Gregor}, title = {Optimal Price Zones of Electricity Markets: A Mixed-Integer Multilevel Model and Global Solution Approaches}, series = {Optimization Methods and Software}, journal = {Optimization Methods and Software}, number = {34(2)}, pages = {406 -- 436}, year = {2017}, abstract = {Mathematical modeling of market design issues in liberalized electricity markets often leads to mixed-integer nonlinear multilevel optimization problems for which no general-purpose solvers exist and which are intractable in general. In this work, we consider the problem of splitting a market area into a given number of price zones such that the resulting market design yields welfare-optimal outcomes. This problem leads to a challenging multilevel model that contains a graph-partitioning problem with multi-commodity flow connectivity constraints and nonlinearities due to proper economic modeling. Furthermore, it has highly symmetric solutions. We develop different problem-tailored solution approaches. In particular, we present an extended KKT transformation approach as well as a generalized Benders approach that both yield globally optimal solutions. These methods, enhanced with techniques such as symmetry breaking and primal heuristics, are evaluated in detail on academic as well as on realistic instances. It turns out that our approaches lead to effective solution methods for the difficult optimization tasks presented here, where the problem-specific generalized Benders approach performs considerably better than the methods based on KKT transformation.}, language = {en} } @unpublished{HillerKochScheweetal.2017, author = {Hiller, Benjamin and Koch, Thorsten and Schewe, Lars and Schwarz, Robert and Schweiger, Jonas}, title = {A System to Evaluate Gas Network Capacities: Concepts and Implementation}, series = {EJOR}, journal = {EJOR}, year = {2017}, abstract = {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.}, language = {en} } @article{GrimmScheweSchmidtetal.2017, author = {Grimm, Veronika and Schewe, Lars and Schmidt, Martin and Z{\"o}ttl, Gregor}, title = {A Multilevel Model of the European Entry-Exit Gas Market}, series = {Mathematical Methods of Operations Research}, journal = {Mathematical Methods of Operations Research}, number = {89(2)}, pages = {223 -- 255}, year = {2017}, abstract = {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.}, language = {en} }