}, author = {Krebs, Vanessa and Schmidt, Martin}, doi = {10.1016/j.orp.2018.05.002}, faupublication = {yes}, journal = {Operations Research Perspectives}, keywords = {Market Equilibria; Networks; Transport Costs; Uniqueness; Perfect Competition}, pages = {169-173}, peerreviewed = {Yes}, title = {{Uniqueness} of {Market} {Equilibria} on {Networks} with {Transport} {Costs}}, url = {http://www.sciencedirect.com/science/article/pii/S2214716018300319}, volume = {5}, year = {2018} } @masterthesis{faucris.123956624, author = {Schmidt, Martin}, faupublication = {no}, peerreviewed = {automatic}, school = {Friedrich-Alexander-Universität Erlangen-Nürnberg}, title = {{Über} {Aspekte} des {Designs} symmetrischer {Verschlüsselungsverfahren} mit einer {Anwendung} auf ein neues {Kryptosystem}}, year = {2008} } @incollection{faucris.124206104, abstract = {

This chapter describes the fundamentals of gas transport. This includes an introduction to the basic terminology and basic physical laws with respect to natural gas. Then the basic elements needed to represent gas networks are discussed: pipes, resistors, valves, control valves, and compressor machines and drives. These elements can be grouped into larger entities like compressor groups and subnetwork operation modes.

}, author = {Fügenschuh, Armin and Geißler, Björn and Gollmer, Ralf and Morsi, Antonio and Pfetsch, Marc E. and Rövekamp, Jessica and Schmidt, Martin and Spreckelsen, Klaus and Steinbach, Marc C.}, booktitle = {Evaluating Gas Network Capacities}, doi = {10.1137/1.9781611973693.ch2}, editor = {Koch T, Hiller B, Pfetsch ME, Schewe L}, faupublication = {yes}, pages = {17-44}, peerreviewed = {Yes}, publisher = {SIAM}, series = {SIAM-MOS series on Optimization}, title = {{Physical} and technical fundamentals of gas networks}, year = {2015} } @article{faucris.121780824, 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 network}, author = {Groß, Martin and Pfetsch, Marc E. and Schewe, Lars and Schmidt, Martin and Skutella, Martin}, doi = {10.1002/net.21865}, faupublication = {yes}, journal = {Networks}, keywords = {Maximum flow problem, Network reduction, Potential networks, Potential-based flows, Series-parallel graphs.}, peerreviewed = {Yes}, title = {{Algorithmic} {Results} for {Potential}-{Based} {Flows}: {Easy} and {Hard} {Cases}}, url = {http://www.optimization-online.org/DB_HTML/2017/08/6185.html}, year = {2018} } @misc{faucris.122404304, abstract = {In this paper we show how to use an old mathematical concept of diophantine analysis, the approximation theorem of Kronecker, in symmetric cryptography. As a rst practical application we propose and analyze the new symmetric 128-bit block cipher KronCrypt. The cipher is a 4-round Feistel network with a non-bijective round function f made up of a variable number of large key-dependent S-boxes, XORs and modular additions. Its key length is variable but not less than 128 bit. The main innovation of KronCrypt in the area of symmetric cryptography is the fact that the key-dependent S-boxes are based upon a constructive proof of the approximation theorem of Kronecker used as a boolean function. We prove the correctness of our concept in general and show how we designe the new cipher KronCrypt. Furthermore, results concerning statistical behaviour, i.e. confusion, diusion and completeness, and dierential cryptanalysis are presented.}, author = {Elsner, Carsten and Schmidt, Martin}, faupublication = {no}, peerreviewed = {automatic}, title = {{KronCrypt} - {A} {New} {Symmetric} {Cryptosystem} {Based} on {Kronecker}'s {Approximation} {Theorem}}, url = {http://eprint.iacr.org/}, year = {2009} } @article{faucris.119629444, abstract = {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 example}, author = {Mehrmann, Volker and Schmidt, Martin and Stolwijk, Jeroen}, doi = {10.1007/s10013-018-0303-1}, faupublication = {yes}, journal = {Vietnam Journal of Mathematics}, keywords = {Gas transport optimization; Isothermal stationary Euler equations; Model hierarchy; Adaptive error control; Marking strategy}, peerreviewed = {Yes}, title = {{Model} and {Discretization} {Error} {Adaptivity} within {Stationary} {Gas} {Transport} {Optimization}}, url = {http://www.optimization-online.org/DB_HTML/2017/12/6365.html}, year = {2018} } @article{faucris.204162733, abstract = {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 use}, author = {Schewe, Lars and Schmidt, Martin and Thürauf, Johannes}, doi = {10.1007/s10288-019-00411-3}, faupublication = {yes}, journal = {4OR-A Quarterly Journal of Operations Research}, keywords = {Gas networks; Booking; Entry-exit system; Convexity; Flow models}, peerreviewed = {Yes}, title = {{Structural} {Properties} of {Feasible} {Bookings} in the {European} {Entry}-{Exit} {Gas} {Market} {System}}, url = {http://www.optimization-online.org/DB_HTML/2018/09/6831.html}, year = {2019} } @article{faucris.123677664, 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 method}, author = {Schmidt, Martin and Sirvent, Mathias and Wollner, Winnifried}, doi = {10.1007/s10107-018-1309-x}, faupublication = {yes}, journal = {Mathematical Programming}, keywords = {Mixed-Integer Nonlinear Optimization, Lipschitz Optimization, Inexact Function Evaluations, Decomposition Methods, Gas Networks.}, peerreviewed = {Yes}, title = {{A} {Decomposition} {Method} for {MINLPs} with {Lipschitz} {Continuous} {Nonlinearities}}, url = {http://www.optimization-online.org/DB_HTML/2017/07/6130.html}, year = {2018} } @article{faucris.106480484, abstract = {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 vers}, author = {Grimm, Veronika and Grübel, Julia and Schewe, Lars and Schmidt, Martin and Zöttl, Gregor}, doi = {10.1016/j.ejor.2018.09.016}, faupublication = {yes}, journal = {European Journal of Operational Research}, keywords = {Fundamental Welfare Theorems; Multiplicity; Natural Gas Markets; Nonconvex Equilibrium Models; Uniqueness}, peerreviewed = {Yes}, title = {{Nonconvex} {Equilibrium} {Models} for {Gas} {Market} {Analysis}: {Failure} of {Standard} {Techniques} and {Alternative} {Modeling} {Approaches}}, url = {https://www.sciencedirect.com/science/article/abs/pii/S0377221718307768}, year = {2018} } @incollection{faucris.111139424, abstract = {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.}, address = {Singapore}, author = {Hante, Falk and Leugering, Günter and Martin, Alexander and Schewe, Lars and Schmidt, Martin}, booktitle = {Industrial Mathematics and Complex Systems: Emerging Mathematical Models, Methods and Algorithms}, doi = {10.1007/978-981-10-3758-0_5}, editor = {Manchanda, Pammy; Lozi, René; Siddiqi, Abul Hasan}, faupublication = {yes}, isbn = {978-981-10-3758-0}, keywords = {Networks, pipes, canals, Euler and St. Venant equations, hierarchy of models, domain decomposition, controllability, optimal control.}, pages = {77-122}, peerreviewed = {unknown}, publisher = {Springer Singapore}, series = {Industrial and Applied Mathematics}, title = {{Challenges} in {Optimal} {Control} {Problems} for {Gas} and {Fluid} {Flow} in {Networks} of {Pipes} and {Canals}: {From} {Modeling} to {Industrial} {Applications}}, url = {https://opus4.kobv.de/opus4-trr154/files/121/isiam-paper.pdf}, year = {2017} } @phdthesis{faucris.106579264, author = {Schmidt, Martin}, faupublication = {no}, peerreviewed = {automatic}, school = {Friedrich-Alexander-Universität Erlangen-Nürnberg}, title = {{A} {Generic} {Interior}-{Point} {Framework} for {Nonsmooth} and {Complementarity} {Constrained} {Nonlinear} {Optimization}}, year = {2013} } @misc{faucris.213204500, abstract = {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.}, author = {Kleinert, Thomas and Schmidt, Martin}, faupublication = {yes}, peerreviewed = {automatic}, title = {{Computing} {Feasible} {Points} of {Bilevel} {Problems} with a {Penalty} {Alternating} {Direction} {Method}}, url = {http://www.optimization-online.org/DB_HTML/2019/03/7117.html}, year = {2019} } @misc{faucris.120075604, abstract = {Robust model predictive control approaches and other applications lead to nonlinear optimization problems defined on (scenario) trees. We present structure-preserving Quasi-Newton update formulas as well as structured inertia correction techniques that allow to solve these problems by interior-point methods with specialized KKT solvers for tree-structured optimization problems. The same type of KKT solvers could be used in active-set based SQP methods. The viability of our approach is demonstrated by two robust control problems.}, author = {Hübner, Jens and Schmidt, Martin and Steinbach, Marc C.}, faupublication = {yes}, keywords = {Nonlinear stochastic optimization, Interior-point methods, Structured Quasi-Newton updates, Structured inertia correction, Robust model predictive control.}, peerreviewed = {automatic}, title = {{Optimization} {Techniques} for {Tree}-{Structured} {Nonlinear} {Problems}}, url = {http://www.optimization-online.org/DB_HTML/2017/02/5845.html}, year = {2017} } @incollection{faucris.110561704, abstract = {

In this chapter we discuss the problem of validation of nominations as a nonsmooth and nonconvex mixed-integer nonlinear feasibility problem. For this problem we present a primal heuristic that is based on reformulation techniques that smooth the appearing nonsmooth aspects and that reformulate discrete aspects with complementarity constraints and problem specific relaxations. The resulting mathematical program with equilibrium constraints (MPEC) model can be regularized by standard techniques leading to a nonlinear program (NLP) type model. Solutions to the latter can finally be used as approximative solutions to the underlying feasibility problem.

}, author = {Schmidt, Martin and Steinbach, Marc C. and Willert, Bernhard M.}, booktitle = {Evaluating Gas Network Capacities}, doi = {10.1137/1.9781611973693.ch9}, editor = {Koch T, Hiller B, Pfetsch ME, Schewe L}, faupublication = {yes}, pages = {163-180}, peerreviewed = {Yes}, publisher = {SIAM}, series = {SIAM-MOS series on Optimization}, title = {{An} {MPEC} based heuristic}, year = {2015} } @article{faucris.120013784, abstract = {We study the transient optimization of gas transport networks including both discrete controls due to switching of controllable elements and nonlinear fluid dynamics described by the system of isothermal Euler equations, which are partial differential equations in time and 1-dimensional space. This combination leads to mixed-integer optimization problems subject to nonlinear hyperbolic partial differential equations on a graph. We propose an instantaneous control approach in which suitable Euler discretizations yield systems of ordinary differential equations on a graph. This networked system of ordinary differential equations is shown to be well-posed and affine-linear solutions of these systems are derived analytically. As a consequence, finite-dimensional mixed-integer linear optimization problems are obtained for every time step that can be solved to global optimality using general-purpose solvers. We illustrate our approach in practice by presenting numerical results on a realistic gas transport network.}, author = {Gugat, Martin and Leugering, Günter and Martin, Alexander and Schmidt, Martin and Sirvent, Mathias and Wintergerst, David}, doi = {10.1007/s10589-017-9970-1}, faupublication = {yes}, journal = {Computational Optimization and Applications}, keywords = {Mixed-integer optimal control, Instantaneous control, Partial differential equations on graphs, Gas networks, Mixed-integer linear optimization.}, pages = {267-294}, peerreviewed = {Yes}, title = {{MIP}-based instantaneous control of mixed-integer {PDE}-constrained gas transport problems}, volume = {70}, year = {2018} } @misc{faucris.201727031, abstract = {This paper mainly studies two topics: linear complementarity problems (LCPs) for modeling electricity market equilibria and optimization under uncertainty. While there have been quite some attempts to deal with uncertain LCPs in a stochastic - i.e., distributional - sense, robust LCPs have only gained attention very recently. In this paper, 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 particularly means that the two classical welfare theorems also hold in both considered robust cases. 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.}, author = {Kramer, Anja and Krebs, Vanessa and Schmidt, Martin}, faupublication = {yes}, keywords = {Robust optimization; Linear complementarity problems; Electricity market equilibrium models; Perfect competition; Nash-Cournot competition}, peerreviewed = {automatic}, title = {{Strictly} and {Γ}-{Robust} {Counterparts} of {Electricity} {Market} {Models}: {Perfect} {Competition} and {Nash}--{Cournot} {Equilibria}}, url = {http://www.optimization-online.org/DB_HTML/2018/07/6709.html}, year = {2018} } @article{faucris.109534304, abstract = {We propose an equilibrium model that allows to analyze the long-run impact of the regulatory environment on transmission line expansion by the regulator and investment in generation capacity by private firms in liberalized electricity markets. The model incorporates investment decisions of the transmission operator and private firms in expectation of an energy-only market and cost-based redispatch. In different specifications we consider the cases of one vs. multiple price zones (market splitting) and analyze different approaches to recover network cost - in particular lump sum, generation capacity based, and energy based fees. In order to compare the outcomes of our multistage market model with a first-best benchmark, we also solve the corresponding integrated planner problem. Using two test networks we illustrate that energy-only markets can lead to suboptimal locational decisions for generation capacity and thus imply excessive network expansion. Market splitting heals these problems only partially. These results are valid for all considered types of network tariffs, although investment slightly differs across those regime}, author = {Grimm, Veronika and Martin, Alexander and Schmidt, Martin and Weibelzahl, Martin and Zöttl, Gregor}, doi = {10.1016/j.ejor.2016.03.044}, faupublication = {yes}, journal = {European Journal of Operational Research}, keywords = {Equilibrium Models, Mixed-Integer Nonlinear Optimization, Multilevel Programming, Electricity Markets, Network Expansion, Transmission Management}, pages = {493-509}, peerreviewed = {Yes}, title = {{Transmission} and generation investment in electricity markets: {The} effect of market splitting and network fee regimes}, url = {http://www.optimization-online.org/DB_HTML/2015/03/4803.html}, volume = {254}, year = {2016} } @article{faucris.117696524, abstract = {When considering cost-optimal operation of gas transport networks, compressor stations play the most important role. Proper modeling of these stations leads to nonconvex mixed-integer nonlinear optimization problems. In this article, we give an isothermal and stationary description of compressor stations, state MINLP and GDP models for operating a single station, and discuss several continuous reformulations of the problem. The applicability and relevance of different model formulations, especially of those without discrete variables, is demonstrated by a computational study on both academic examples and real-world instances. In addition, we provide preliminary computational results for an entire network.}, author = {Rose, Daniel and Schmidt, Martin and Steinbach, Marc C. and Willert, Bernhard M.}, doi = {10.1007/s00186-016-0533-5}, faupublication = {yes}, journal = {Mathematical Methods of Operations Research}, keywords = {Discrete-continuous nonlinear optimization; Gas networks; Gas compressor stations; Mixed-integer optimization; Continuous reformulations}, pages = {409--444}, peerreviewed = {Yes}, title = {{Computational} optimization of gas compressor stations: {MINLP} models versus continuous reformulations}, url = {http://www.optimization-online.org/DB_HTML/2h015/02/4793.html}, volume = {83}, year = {2016} } @incollection{faucris.122515844, abstract = {

We introduce the Inhomogeneous Simultaneous Approximation Problem (ISAP), an old problem from the field of analytic number theory. Although the Simultaneous Approximation Problem (SAP) is already known in cryptography, it has mainly been considered in its *homogeneous* instantiation for *attacking* schemes. We take a look at the hardness and applicability of ISAP, i.e., the *inhomogeneous* variant, for *designing* schemes.

More precisely, we define a decisional problem related to ISAP, called DISAP, and show that it is NP-complete. With respect to its hardness, we review existing approaches for solving related problems and give suggestions for the efficient generation of hard instances. Regarding the applicability, we describe as a proof of concept a bit commitment scheme where the hiding property is directly reducible to DISAP. An implementation confirms its usability in principle (e.g., size of one commitment is 6273 bits and execution time is in the milliseconds).

}, author = {Armknecht, Frederik and Elsner, Carsten and Schmidt, Martin}, booktitle = {Progress in Cryptology – AFRICACRYPT 2011}, doi = {10.1007/978-3-642-21969-6_15}, editor = {Nitaj A, Pointcheval D}, faupublication = {no}, isbn = {978-3-642-21968-9}, pages = {242-259}, peerreviewed = {Yes}, publisher = {Springer Berlin / Heidelberg}, series = {Lecture Notes in Computer Science}, title = {{Using} the {Inhomogeneous} {Simultaneous} {Approximation} {Problem} for {Cryptographic} {Design}}, volume = {6737}, year = {2011} } @misc{faucris.113664584, author = {Hiller, Benjamin and Koch, Thorsten and Pfetsch, Marc E. and Schmidt, Martin and Geißler, Björn and Henrion, René and Joormann, Imke and Martin, Alexander and Morsi, Antonio and Römisch, Werner and Schewe, Lars and Schultz, Rüdiger and Steinbach, Marc C.}, faupublication = {yes}, peerreviewed = {automatic}, title = {{Capacity} {Evaluation} for {Large}-{Scale} {Gas} {Networks}}, url = {http://www.mso.math.fau.de/fileadmin/wima/data_members/schmidt/forne-komso.pdf}, year = {2017} } @incollection{faucris.123593624, abstract = {Die mittel- und längerfristige Planung für den Gastransport hat sich durch Änderungen in den regulatorischen Rahmenbedingungen stark verkompliziert. Kernpunkt ist die Trennung von Gashandel und -transport. Dieser Artikel diskutiert die hieraus resultierenden mathematischen Planungsprobleme, welche als Validierung von Nominierungen und Buchungen, Bestimmung der technischen Kapazität und Topologieplanung bezeichnet werden. Diese mathematischen Optimierungsprobleme werden vorgestellt und Lösungsansätze skizziert.}, address = {Düsseldorf}, author = {Martin, Alexander and Geißler, Björn and Hayn, Christine and Morsi, Antonio and Schewe, Lars and Hiller, Benjamin and Humpola, Jesco and Koch, Thorsten and Lehmann, Thomas and Schwarz, Robert and Schweiger, Jonas and Pfetsch, Marc E. and Schmidt, Martin and Steinbach, Marc C. and Willert, Bernhard M. and Schultz, Rüdiger}, booktitle = {Optimierung in der Energiewirtschaft}, faupublication = {yes}, pages = {105-114}, peerreviewed = {Yes}, publisher = {VDI-Verlag}, series = {VDI-Berichte 2157}, title = {{Optimierung} {Technischer} {Kapazitäten} in {Gasnetzen}}, year = {2011} } @article{faucris.106529764, 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.}, 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}, doi = {10.3390/data2040040}, faupublication = {yes}, journal = {Data}, keywords = {Gas Transport; Networks; Problem Instances; Mixed-Integer Nonlinear Optimization; GasLib}, peerreviewed = {Yes}, title = {{GasLib} - {A} {Library} of {Gas} {Network} {Instances}}, url = {http://www.optimization-online.org/DB_HTML/2015/11/5216.html}, volume = {2}, year = {2017} } @incollection{faucris.122314984, abstract = {
The different approaches to solve the validation of nomination problem presented in the previous chapters are evaluated computationally in this chapter. Each approach is analyzed individually, as well as the complete solvers for these problems. We demonstrate that the presented approaches can successfully solve large-scale real-world instances.

}, author = {Hiller, Benjamin and Humpola, Jesco and Lehmann, Thomas and Lenz, Ralf and Morsi, Antonio and Pfetsch, Marc E. and Schewe, Lars and Schmidt, Martin and Schwarz, Robert and Schweiger, Jonas and Stangl, Claudia and Willert, Bernhard M.}, booktitle = {Evaluating Gas Network Capacities}, doi = {10.1137/1.9781611973693.ch12}, editor = {Koch T, Hiller B, Pfetsch ME, Schewe L}, faupublication = {yes}, pages = {233-270}, peerreviewed = {Yes}, publisher = {SIAM}, series = {SIAM-MOS series on Optimization}, title = {{Computational} results for validation of nominations}, year = {2015} } @incollection{faucris.122210264, abstract = {

The main goal of our efforts described in this book consists of solving the problem of validation of nominations in gas networks, i.e., deciding whether a feasible solution exists for a given set of boundary conditions represented by a nomination. However, it turns out that the meaning of “feasible” is not self-evident. This is due to a multitude of reasons, ranging from the accuracy of problem data over subtle differences between our models to tractability of optimization problems. In the current chapter we elaborate on these points and try to clarify precisely in what sense and how well the mathematical methodology presented can distinguish feasible from infeasible solutions.

}, author = {Joormann, Imke and Schmidt, Martin and Steinbach, Marc C. and Willert, Bernhard M.}, booktitle = {Evaluating Gas Network Capacities}, doi = {10.1137/1.9781611973693.ch11}, editor = {Koch T, Hiller B, Pfetsch ME, Schewe L}, faupublication = {yes}, pages = {211-232}, peerreviewed = {Yes}, publisher = {SIAM}, series = {SIAM-MOS series on Optimization}, title = {{What} does “feasible” mean?}, year = {2015} } @incollection{faucris.117699164, abstract = {Complex real-world optimization tasks often lead to mixed-integer nonlinear problems (MINLPs). However, current MINLP algorithms are not always able to solve the resulting large-scale problems. One remedy is to develop problem specific primal heuristics that quickly deliver feasible solutions. This paper presents such a primal heuristic for a certain class of MINLP models. Our approach features a clear distinction between nonsmooth but continuous and genuinely discrete aspects of the model. The former are handled by suitable smoothing techniques; for the latter we employ reformulations using complementarity constraints. The resulting mathematical programs with equilibrium constraints (MPEC) are finally regularized to obtain MINLP-feasible solutions with general purpose NLP solvers.}, author = {Schmidt, Martin and Steinbach, Marc C. and Willert, Bernhard M.}, booktitle = {Facets of Combinatorial Optimization}, doi = {10.1007/978-3-642-38189-8_13}, editor = {Jünger M, Reinelt G}, faupublication = {no}, isbn = {978-3-642-38188-1}, pages = {295-320}, peerreviewed = {Yes}, publisher = {Springer Berlin Heidelberg}, title = {{A} {Primal} {Heuristic} for {Nonsmooth} {Mixed} {Integer} {Nonlinear} {Optimization}}, year = {2013} } @article{faucris.117698284, abstract = {Many real-world optimization models comprise nonconvex and nonsmooth functions leading to very hard classes of optimization models. In this article, a new interior-point method for the special, but practically relevant class of optimization problems with locatable and separable nonsmooth aspects is presented. After motivating and formalizing the problems under consideration, modifications and extensions to a standard interior-point method for nonlinear programming are investigated to solve the introduced problem class. First theoretical results are given and a numerical study is presented that shows the applicability of the new method for real-world instances from gas network optimization.}, author = {Schmidt, Martin}, doi = {10.1007/s13675-015-0039-6}, faupublication = {yes}, journal = {EURO Journal on Computational Optimization}, keywords = {Interior-point methods; Barrier methods; Line-search methods; Nonlinear and nonsmooth optimization; Classification of optimization models; Gas network optimization; 90C30; 90C51; 90C90; 90C35; 90C56; 90B10}, pages = {309-348}, peerreviewed = {No}, title = {{An} interior-point method for nonlinear optimization problems with locatable and separable nonsmoothness}, volume = {3}, year = {2015} } @article{faucris.123620464, abstract = {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 mode}, author = {Geißler, Björn and Morsi, Antonio and Schewe, Lars and Schmidt, Martin}, doi = {10.1287/ijoc.2017.0780}, faupublication = {yes}, journal = {Informs Journal on Computing}, keywords = {Nonconvex Mixed-Integer Nonlinear Optimization; Penalty Methods; Alternating Direction Methods; Block Separability; Gas Transport}, peerreviewed = {Yes}, title = {{Solving} {Highly} {Detailed} {Gas} {Transport} {MINLPs}: {Block} {Separability} and {Penalty} {Alternating} {Direction} {Methods}}, volume = {20}, year = {2018} } @misc{faucris.200121582, abstract = {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 global optimal solutions in finite time and we also provide a worst-case iteration bound. However, first numerical experiences reveal 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 researc}, author = {Schmidt, Martin and Sirvent, Mathias and Wollner, Winnifried}, faupublication = {yes}, keywords = {Mixed-Integer Nonlinear Optimization; Global Optimization; Lipschitz Optimization; Gas Networks}, peerreviewed = {automatic}, title = {{The} {Cost} of {Not} {Knowing} {Enough}: {Mixed}-{Integer} {Optimization} with {Implicit} {Lipschitz} {Nonlinearities}}, url = {https://opus4.kobv.de/opus4-trr154/frontdoor/index/index/docId/235}, year = {2018} } @article{faucris.111112364, abstract = {We propose a decomposition based method for solving mixed-integer nonlinear optimization problems with "black-box" nonlinearities, where the latter, e.g., may arise due to differential equations or expensive simulation runs. The method alternatingly solves a mixed-integer linear master problem and a separation problem for iteratively refining the mixed-integer linear relaxation of the nonlinearity. We prove that our algorithm finitely terminates with an approximate feasible global optimal solution of the mixed-integer nonlinear problem. Additionally, we show the applicability of our approach by three case studies from mixed-integer optimal control, from the field of pressurized flows in pipes with elastic walls, and from steady-state gas transport. For the latter we also present promising numerical results of our method applied to real-world instance}, author = {Gugat, Martin and Leugering, Günter and Martin, Alexander and Schmidt, Martin and Sirvent, Mathias and Wintergerst, David}, doi = {10.1002/net.21812}, faupublication = {yes}, journal = {Networks}, keywords = {Mixed-Integer Optimization, Simulation Based Optimization, Optimization with Differential Equations, Decomposition Method, Gas Transport Networks.}, pages = {60-83}, peerreviewed = {Yes}, title = {{Towards} {Simulation} {Based} {Mixed}-{Integer} {Optimization} with {Differential} {Equations}}, url = {https://onlinelibrary.wiley.com/doi/abs/10.1002/net.21812}, volume = {72}, year = {2018} } @misc{faucris.202208666, abstract = {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}, author = {Hojny, Christopher and Joormann, Imke and Lüthen, Hendrik and Schmidt, Martin}, faupublication = {yes}, keywords = {Max-cut; Connectivity; Branch-and-cut; Mixed-integer programming}, peerreviewed = {automatic}, title = {{Mixed}-{Integer} {Programming} {Techniques} for the {Connected} {Max}-k-{Cut} {Problem}}, url = {http://www.optimization-online.org/DB_HTML/2018/07/6738.html}, year = {2018} } @incollection{faucris.122514964, abstract = {In this chapter we describe a highly detailed nonlinear program (NLP) of gas networks for the case of fixed discrete decisions. By including nonlinear physics and a detailed description of the technical network devices, a level of accuracy is reached that is comparable to current commercial simulation software. Our NLP model is used to validate the solutions of the previously described models. A successful validation provides a solution of the underlying mixed-integer nonlinear program (MINLP).}, author = {Schmidt, Martin and Steinbach, Marc C. and Willert, Bernhard M.}, booktitle = {Evaluating Gas Network Capacities}, doi = {10.1137/1.9781611973693.ch10}, editor = {Koch T, Hiller B, Pfetsch ME, Schewe L}, faupublication = {yes}, pages = {181-210}, peerreviewed = {Yes}, publisher = {SIAM}, series = {SIAM-MOS series on Optimization}, title = {{The} precise {NLP} model}, year = {2015} } @article{faucris.122777864, abstract = {Due to strict regulatory rules in combination with complex nonlinear physics, major gas network operators in Germany and Europe face hard planning problems that call for optimization. In part 1 of this paper we have developed a suitable model hierarchy for that purpose. Here we consider the more practical aspects of modeling. We validate individual model components against a trusted simulation tool, give a structural overview of the model hierarchy, and use its large variety of approximations to devise robust and efficient solution techniques. An extensive computational study demonstrates the suitability of our models and techniques for previously unsolvable problems in gas network planning.}, author = {Schmidt, Martin and Steinbach, Marc C. and Willert, Bernhard M.}, doi = {10.1007/s11081-015-9300-3}, faupublication = {yes}, journal = {Optimization and Engineering}, keywords = {Gas networks; Stationary flow; High-detail modeling; Nonsmooth nonlinear discrete-continuous optimization; Smoothing techniques; 90B10; 90C06; 90C30; 90C90}, pages = {437-472}, peerreviewed = {Yes}, title = {{High} detail stationary optimization models for gas networks: validation and results}, url = {http://www.optimization-online.org/DB_HTML/2014/10/4602.html}, volume = {17}, year = {2016} } @misc{faucris.213202067, abstract = {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 minute}, author = {Grübel, Julia and Kleinert, Thomas and Krebs, Vanessa and Orlinskaya, Galina and Schewe, Lars and Schmidt, Martin and Thürauf, Johannes}, faupublication = {yes}, keywords = {Electricity markets; Storage; Market equilibria; Uniqueness; ADMM; Parallel computing; Large-scale optimization}, peerreviewed = {automatic}, title = {{On} {Electricity} {Market} {Equilibria} with {Storages}: {Modeling}, {Uniqueness}, and a {Distributed} {ADMM}}, url = {http://www.optimization-online.org/DB_HTML/2019/03/7118.html}, year = {2019} } @article{faucris.117697404, abstract = {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.}, author = {Geißler, Björn and Morsi, Antonio and Schewe, Lars and Schmidt, Martin}, doi = {10.1016/j.compchemeng.2015.07.005}, faupublication = {yes}, journal = {Computers & Chemical Engineering}, keywords = {Nonconvex mixed-integer nonlinear optimization; Alternating direction methods; Piecewise linear relaxations; Gas transport networks; Heat power supply and demand}, pages = {303-317}, peerreviewed = {Yes}, title = {{Solving} power-constrained gas transportation problems using an {MIP}-based alternating direction method}, volume = {82}, year = {2015} } @article{faucris.119464224, 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.}, author = {Leugering, Günter and Martin, Alexander and Schmidt, Martin and Sirvent, Mathias}, faupublication = {yes}, journal = {Control and Cybernetics}, keywords = {Optimal control; Gas networks; Euler's equation; Semilinear PDE; Nonoverlapping domain decomposition}, pages = {191-225}, peerreviewed = {Yes}, title = {{Nonoverlapping} {Domain} {Decomposition} for {Optimal} {Control} {Problems} governed by {Semilinear} {Models} for {Gas} {Flow} in {Networks}}, volume = {46}, year = {2017} }