A Linearized Model for the Optimization of the Coupled Electricity and Natural Gas System - Sirvent, Mathias; Kanelakis, Nikolaos; Geißler, Björn; Biskas, Pandelis (Journal of Modern Power Systems and Clean Energy, 2017)
In this paper a combined optimization of a coupled electricity and gas system is presented. For the electricity network a unit commitment problem with optimization of energy and reserves under a power pool, considering all system operational and unit technical constraints is solved. The gas network subproblem is a medium-scale mixed-integer nonconvex and nonlinear programming problem. The coupling constraints between the two networks are nonlinear as well. The resulting mixed-integer nonlinear program is linearized with the extended incremental method and an outer approximation technique. The resulting model is evaluated using the Greek power and gas system comprising fourteen gas-fired units under four different approximation accuracy levels. The results indicate the efficiency of the proposed mixed-integer linear program model and the interplay between computational requirements and accuracy.

A new algorithm for MINLP applied to gas transport energy cost minimization - Geißler, Björn; Morsi, Antonio; Schewe, Lars (Facets of Combinatorial Optimization, 2013)
In this article, we present a new algorithm for the solution of nonconvex mixed-integer nonlinear optimization problems together with an application from gas network optimization, the gas transport energy cost minimization problem. Here, the aim is to transport gas through the network at minimum operating cost. The proposed algorithm is based on the adaptive refinement of a new class of MIP-relaxations and has been developed within an industry project on gas network optimization. Since therefore the implementation is not as general as it could be, our computational results are restricted to instances from gas network optimization at this point of time. However, as these problems are real-world applications and turn out to be rather hard to solve with the aid of state-of-the-art MINLP-solvers we believe that our computational results reveal the potential of this new approach and motivate further research on the presented techniques.

Combination of Nonlinear and Linear Optimization of Transient Gas Networks - Domschke, Pia; Geißler, Björn; Kolb, Oliver; Lang, Jens; Martin, Alexander; Morsi, Antonio (Informs Journal on Computing, 2011)
In this paper, we study the problem of technical transient gas network optimization, which can be considered a minimum cost flow problem with a nonlinear objective function and additional nonlinear constraints on the network arcs. Applying an implicit box scheme to the isothermal Euler equation, we derive a mixed-integer nonlinear program. This is solved by means of a combination of (i) a novel mixed-integer linear programming approach based on piecewise linearization and (ii) a classical sequential quadratic program applied for given combinatorial constraints. Numerical experiments show that better approximations to the optimal control problem can be obtained by using solutions of the sequential quadratic programming algorithm to improve the mixed-integer linear program. Moreover, iteratively applying these two techniques improves the results even further.
Keywords: gas networks; optimal control; mixed-integer programming; nonlinear programming; sequential quadratic programming

Mathematical optimization for challenging network planning problems in unbundled liberalized gas markets - Fügenschuh, Armin; Geißler, Björn; Gollmer, Ralf; Hayn, Christine; Henrion, René; Hiller, Benjamin; Humpola, Jesco; Koch, Thorsten; Lehmann, Thomas; Martin, Alexander; Mirkov, Radoslava; Morsi, Antonio; et al. (Energy Systems, 2014)
The recently imposed new gas market liberalization rules in Germany lead to a change of business of gas network operators. While previously network operator and gas vendor were united, they were forced to split up into independent companies. The network has to be open to any other gas trader at the same conditions, and free network capacities have to be identified and publicly offered in a non-discriminatory way. We discuss how these changing paradigms lead to new and challenging mathematical optimization problems. This includes the validation of nominations, that asks for the decision if the network’s capacity is sufficient to transport a specific amount of flow, the verification of booked capacities and the detection of available freely allocable capacities, and the topological extension of the network with new pipelines or compressors in order to increase its capacity. In order to solve each of these problems and to provide meaningful results for the practice, a mixture of different mathematical aspects have to be addressed, such as combinatorics, stochasticity, uncertainty, and nonlinearity. Currently, no numerical solver is available that can deal with such blended problems out-of-the-box. The main goal of our research is to develop such a solver, that moreover is able to solve instances of realistic size. In this article, we describe the main ingredients of our prototypical software implementations.
Keywords: Gas market liberalization; Entry / exit model; Gas network access regulation; Mixed-integer nonlinear nonconvex stochastic optimization; 90B10; 90C11; 90C30; 90C90

Mixed Integer Linear Models for the Optimization of Dynamical Transport Networks - Geißler, Björn; Kolb, Oliver; Lang, Jens; Leugering, Günter; Martin, Alexander; Morsi, Antonio (2010)

Mixed integer linear models for the optimization of dynamical transport networks - Geißler, Björn; Kolb, Oliver; Lang, Jens; Leugering, Günter; Martin, Alexander; Morsi, Antonio (Mathematical Methods of Operations Research, 2011)
We introduce a mixed integer linear modeling approach for the optimization of dynamic transport networks based on the piecewise linearization of nonlinear constraints and we show how to apply this method by two examples, transient gas and water supply network optimization. We state the mixed integer linear programs for both cases and provide numerical evidence for their suitability.
Keywords: Mixed integer linear programming; Piecewise linear approximation; Gas network optimization; Water network optimization

Mixed Integer Optimization of Water Supply Networks - Morsi, Antonio; Geißler, Björn; Martin, Alexander (Mathematical Optimization of Water Networks, 2012)
We introduce a mixed integer linear modeling approach for the optimization of dynamic water supply networks based on the piecewise linearization of nonlinear constraints. One advantage of applying mixed integer linear techniques is that these methods are nowadays very mature, that is, they are fast, robust, and are able to solve problems with up to a huge number of variables. The other major point is that these methods have the potential of finding globally optimal solutions or at least to provide guarantees of the solution quality. We demonstrate the applicability of our approach on examples networks.

Optimale Schaltentscheidungen für Gasnetze - Geißler, Björn; Martin, Alexander; Morsi, Antonio; Schewe, Lars (Optimierung in der Energiewirtschaft, 2011)

Optimierung Technischer Kapazitäten in Gasnetzen - Martin, Alexander; Geißler, Björn; Hayn, Christine; Morsi, Antonio; Schewe, Lars; Hiller, Benjamin; Humpola, Jesco; Koch, Thorsten; Lehmann, Thomas; Schwarz, Robert; Schweiger, Jonas; Pfetsch, Marc E.; et al. (Optimierung in der Energiewirtschaft, 2011)
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.

Penalty Alternating Direction Methods for Mixed-Integer Optimization: A New View on Feasibility Pumps - Geißler, Björn; Morsi, Antonio; Schewe, Lars; Schmidt, Martin (SIAM Journal on Optimization, 2017)
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.
Keywords: Mixed-Integer Nonlinear Optimization; Mixed-Integer Linear Optimization; Feasibility Pump; Alternating Direction Methods; Penalty Methods

Physical and technical fundamentals of gas networks - Fügenschuh, Armin; Geißler, Björn; Gollmer, Ralf; Morsi, Antonio; Pfetsch, Marc E.; Rövekamp, Jessica; Schmidt, Martin; Spreckelsen, Klaus; Steinbach, Marc C. (Evaluating Gas Network Capacities, 2015)
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.

Solving Highly Detailed Gas Transport MINLPs: Block Separability and Penalty Alternating Direction Methods - Geißler, Björn; Morsi, Antonio; Schewe, Lars; Schmidt, Martin (Informs Journal on Computing, 2018)
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
Keywords: Nonconvex Mixed-Integer Nonlinear Optimization; Penalty Methods; Alternating Direction Methods; Block Separability; Gas Transport

Solving power-constrained gas transportation problems using an MIP-based alternating direction method - Geißler, Björn; Morsi, Antonio; Schewe, Lars; Schmidt, Martin (Computers & Chemical Engineering, 2015)
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.
Keywords: Nonconvex mixed-integer nonlinear optimization; Alternating direction methods; Piecewise linear relaxations; Gas transport networks; Heat power supply and demand

The MILP-relaxation approach - Geißler, Björn; Martin, Alexander; Morsi, Antonio; Schewe, Lars (Evaluating Gas Network Capacities, 2015)
We describe how to tackle the problem of validating nominations using mixed-integer programming methods. To this end we first give a mixed-integer nonlinear programming formulation of NoVa, from which we derive a mixed-integer linear relaxation. Our reformulation technique allows us to prescribe an a priori bound on the error we make when relaxing the nonlinear functions.

The Transport PDE and Mixed-Integer Linear Programming - Fügenschuh, Armin-René; Geißler, Björn; Martin, Alexander; Morsi, Antonio (Models and Algorithms for Optimization in Logistics, 2009)
Discrete, nonlinear and PDE constrained optimization are mostly considered as different fields of mathematical research. Nevertheless many real-life problems are most naturally modeled as PDE constrained mixed integer nonlinear programs. For example, nonlinear network flow problems where the flow dynamics are governed by a transport equation are of this type. We present four different applications together with the derivation of the associated transport equations and we show how to model these problems in terms of mixed integer linear constraints.
Keywords: Transport Equation; Partial Differential Equation; Mixed-Integer Linear Programming; Modeling; Nonlinear Constraints

Using Piecewise Linear Functions for Solving MINLPs - Geißler, Björn; Martin, Alexander; Morsi, Antonio; Schewe, Lars (Mixed Integer Nonlinear Programming, 2012)
In this chapter we want to demonstrate that in certain cases general mixed integer nonlinear programs (MINLPs) can be solved by just applying purely techniques from the mixed integer linear world. The way to achieve this is to approximate the nonlinearities by piecewise linear functions. The advantage of applying mixed integer lin- ear techniques are that these methods are nowadays very mature, that is, they are fast, robust, and are able to solve problems with up to millions of variables. In addition, these methods have the potential of finding globally optimal solutions or at least to provide solution guarantees. On the other hand, one tends to say at this point “If you have a hammer, everything is a nail.”[15], because one tries to reformulate or to approximate an ac- tual nonlinear problem until one obtains a model that is tractable by the methods one is common with. Besides the fact that this is a very typical approach in mathematics the question stays whether this is a reasonable approach for the solution of MINLPs or whether the nature of the nonlin- earities inherent to the problem gets lost and the solutions obtained from the mixed integer linear problem have no meaning for the MINLP. The purpose of this chapter is to discuss this question. We will see that the truth lies somewhere in between and that there are problems where this is indeed a reasonable way to go and others where it is not.

Validation of nominations in gas network optimization: Models, methods, and solutions - Pfetsch, Marc E.; Fügenschuh, Armin; Geißler, Björn; Geißler, Nina; Gollmer, Ralf; Hiller, Benjamin; Humpola, Jesco; Koch, Thorsten; Lehmann, Thomas; Martin, Alexander; Morsi, Antonio; Rövekamp, Jessica; et al. (Optimization Methods & Software, 2015)
In this article, we investigate methods to solve a fundamental task in gas transportation, namely the validation of nomination problem: given a gas transmission network consisting of passive pipelines and active, controllable elements and given an amount of gas at every entry and exit point of the network, find operational settings for all active elements such that there exists a network state meeting all physical, technical, and legal constraints. We describe a two-stage approach to solve the resulting complex and numerically difficult non-convex mixed-integer nonlinear feasibility problem. The first phase consists of four distinct algorithms applying mixed-integer linear, mixed-integer nonlinear, nonlinear, and methods for complementarity constraints to compute possible settings for the discrete decisions. The second phase employs a precise continuous nonlinear programming model of the gas network. Using this setup, we are able to compute high-quality solutions to real-world industrial instances that are significantly larger than networks that have appeared in the mathematical programming literature before.
Keywords: gas network optimization; gas transport optimization; mixed-integer nonlinear programming; nomination