1 Introduction

Optimal control of gas transport networks has become increasingly important in recent years. From a mathematical point of view, this problem turns out to be hard even in simplified settings because it combines nonlinear and discrete aspects. On the one hand, modeling the gas physics derived from the Euler equations results in a coupled system of nonlinear parabolic partial differential equations (\({\text{PDEs}}\)). On the other hand, switching active elements such as valves and compressors involves discrete decisions.

In this paper, we consider the particular problem of maximizing the storage capacity of the gas network, which is very important for transmission system operators (\({\text{TSO}}\)). Especially with regard to Power-to-Gas this problem becomes essential. In this context, the gas network is used to store energy by converting electrical power into gas, e.g., by generating hydrogen or methane, and feeding it into the gas network. In a typical Power-to-Gas scenario, the generated gas is only fed into the network during a certain period of time, for example when solar or wind energy is available, and later discharged when demand is high. To handle such scenarios, a transient model of the gas physics is needed, which makes the problem much more complex compared to the stationary case.

In our setting, the problem of maximizing the storage capacity of a gas network is as follows: Maximize the amount of gas that can be fed into the network such that there is an admissible time-dependent control of the active elements satisfying all physical and technical constraints. Furthermore, a concrete control has to be computed. In this context, we focus on global optimal solutions while discrete decisions are involved. We tackle this global optimization problem by a first-discretize-then-optimize approach. First, we present a new discretization of a system of nonlinear parabolic \({\text{PDEs}}\) that describe the gas physics. We prove well-posedness for the resulting discretized system. Incorporating active elements such as valves and compressors, we subsequently obtain a non-convex mixed-integer nonlinear problem (\({\text{MINLP}}\)). In order to solve this \({\text{MINLP}}\) to global optimality, we algorithmically extend the method proposed by Burlacu et al. (2017), Geißler et al. (2012), Geißler (2011), which is based on mixed-integer programming (\({\text{MIP}}\)) relaxations of the \({\text{MINLP}}\) and which has already been used successfully in the context of gas network optimization. Finally, two case studies illustrate the applicability of our approach to storage capacity maximization problems. To the best of our knowledge, no global optimization approach has been investigated in the literature so far that is able to maximize the storage capacity of a gas network with active elements to proven optimality.

The main contributions of this paper are the following. We consider the discretization of a well-established friction-dominated model for gas flow by a numerical scheme that can be interpreted as a spatial discretization by a finite volume method on a staggered grid together with an implicit time discretization. By derivation, the resulting scheme is consistent with the flow equations. It yields an approximation that is formally second order in space and first order in time. We show that the discretized system to be solved in each time step corresponds to the Euler–Lagrange equations for a convex minimization problem, which ensures the correctness of the discretization, i.e., the existence of a unique solution for each time step and by recursion for all time steps. Moreover, the proposed discretization scheme has the advantage that the nonlinear functions involved are univariate, i.e., only depend on one variable. This is particularly advantageous for the optimization algorithm of Burlacu et al. (2017), Geißler (2011), Geißler et al. (2012), which strongly relies on the linearization of these nonlinearities. Finally, we algorithmically extend the method in these references by two ideas that are both straightforward and quite powerful and have not yet been incorporated into their approach.

1.1 Literature review

Several general approaches for optimal control with discrete decisions have been studied in the literature. In the works of Lee et al. (1999), Gerdts (2006), variable time transformation methods that result in a continuous formulation are proposed. However, these are limited to ordinary differential equations (\({\text{ODEs}}\)). Other approaches switch at discrete time points between different systems of \({\text{ODEs}}\). Recently, a generalization to \({\text{PDEs}}\) was analyzed (Rüffler and Hante 2016), whereby only local optimality can be guaranteed. In addition, methods have been developed that use complementarity-based reformulations, see for example the papers by Baumrucker and Biegler (2009), Baumrucker and Biegler (2010), Schmidt et al. (2013), which use special nonlinear solvers or supplementary relaxation techniques. Recently, Buchheim et al. (2015) presented a global solution method for certain semi-linear elliptic mixed-integer \({\text{PDE}}\) problems using outer approximation. A first-discretize-then-optimize approach has been used in the following articles. Sager et al. (2009) developed the so-called convexification method, in which discrete decisions are used to derive a convex relaxation of mixed-integer optimal control problems. This method is limited to \({\text{ODEs}}\) only and is extended to \({\text{PDEs}}\) by Hante and Sager (2013). Moreover, Sager et al. (2011), Jung et al. (2015) applied this convexification method to handle discrete decisions over time and propose an efficient way to compute feasible solutions. Bock et al. (2018) studied cases in which discrete decisions depend on the state variables and studied a reformulation as well as solution method for such problems. Another direction that has been intensively investigated, especially in the chemical engineering community, is mixed-integer dynamic optimization. The dynamic system is typically described by a series of differential-algebraic equations (\({\text{DAEs}}\)). Allgor and Barton (1999) propose a general decomposition-based approach for the problems that arise in this regard. For further surveys in this field of research, we refer to the references contained therein.

In recent years, a lot of literature has been published on optimal control in the context of gas network optimization. The book by Koch et al. (2015) provides a comprehensive survey in case of a stationary gas physics. Recently, alternating direction methods have been used (Geißler et al. 2015b, 2018) to combine \({\text{MIP}}\) and nonlinear programming (\({\text{NLP}}\)) techniques in order to solve stationary gas optimization problems for large-scale real-world instances. Moreover, Ríos-Mercado and Borraz-Sánchez (2015) as well as Hante et al. (2017) present general information on modeling and solution methods for gas transport.

An important strand of literature deals with an discretize-then-optimize approach for these control problems; see, for instance, Devine et al. (2014), Ehrhardt and Steinbach (2005), Furey (1993), Gopalakrishnan and Biegler (2013), Osiadacz (1994), Rachford Jr et al. (2000), Steinbach (2007), Zlotnik et al. (2015) . The important difference to our work is that the resulting \({\text{NLPs}}\) are solved using local solvers, leading in turn to local optima. This allows for fast running times and high physical accuracy of the resulting solutions. The drawback is, however, that one cannot make claims about the quality of the resulting solution as the problem is highly nonconvex. To work with the integer decisions, there is also a strand of literature that uses metaheuristics to optimize the operation of a gas network, e. g. , Mahlke et al. (2007) uses a simulated annealing approach for the transient case. For an overview, both in the stationary and instationary case, we refer to Ríos-Mercado (2018).

The global optimization of transient mixed-integer gas transport has been tackled with related methods by Mahlke et al. (2010) and Domschke et al. (2011). Therein, the authors focus on minimizing the fuel gas consumption of the compressors while gas injection and discharge are given a priori and fixed at each entry and exit. This problem is also tackled in Hahn et al. (2017), where the authors develop a specialized spatial branching algorithm for this problem. In contrast, we maximize the amount of gas that can be fed into the network, where some entries and exits have a variable gas injection and discharge. Furthermore, our discretization scheme allows for a rigorous proof of well-posedness, i.e., existence of unique solutions for every time step, via a variational argument. The method of Domschke et al. (2011) is based on a different \({\text{PDE}}\) model for the gas flow, which does not allow for such an analysis. Recently, Gugat et al. (2017) presented an instantaneous control approach for solving transient gas transport problems, where an \({\text{MIP}}\) needs to be solved for each time step. Global optimality, however, is only guaranteed for each time step and not for the entire time horizon.

2 Mathematical model of gas transport

In this section, we present the basic equations describing the gas transport in a network of pipes and active elements. We start with a description of the topology and geometry of the network and then introduce the partial differential and algebraic equations modeling the conservation of mass and momentum in pipes, active elements, and across junctions.

2.1 Topology and geometry

The topology of the gas network is described by a finite directed graph \(\mathcal {G}=(\mathcal {V},\mathcal {A})\). Every arc \(a \in \mathcal {A}\) models a specific segment of the network, i.e., a pipe or an active element like a compressor or a valve. Correspondingly, we split \(\mathcal {A}=\mathcal {A}_{ pi }\cup \mathcal {A}_{ ae }\) into subsets of pipes and active elements. The vertices \(v \in \mathcal {V}\), on the other hand, describe the end points of segments and correspond to junctions of several segments or to terminal vertices of the network, where gas can be injected or discharged.

For any vertex \(v \in \mathcal {V}\), we denote by \(\delta ^{ in }(v) :=\{ a = (v_1, v_2) \in \mathcal {A}: v_2 = v \}\) the set of ingoing arcs and by \(\delta ^{ out }(v) :=\{ a = (v_1, v_2) \in \mathcal {A}: v_1 = v \}\) the set of outgoing arcs, and we denote by \(\mathcal {A}(v) :=\delta ^{ in }(v) \cup \delta ^{ out }(v)\) the set of arcs that are incident on v. We then split the set of vertices \(\mathcal {V}= \mathcal {V}_0 \cup \mathcal {V}_\partial \) into a set of interior vertices \(\mathcal {V}_0 :=\{v \in \mathcal {V}: |\mathcal {A}(v)| > 1\}\) and a set of boundary vertices \(\mathcal {V}_\partial = \{ v \in \mathcal {V}: |\mathcal {A}(v)| = 1\}\). We further partition \(\mathcal {V}_\partial = \mathcal {V}_q \cup \mathcal {V}_p\) into boundary vertices where either the mass flow or the pressure is prescribed.

To every pipe a, we associate parameters \(\ell _a\), \(D_a\), and \(A_a\) describing the length, diameter, and cross-sectional area of the pipe, and we denote by \(v_a\) the midpoint of the pipe corresponding to the arc. We will tacitly identify the pipe a with the interval \([0, \ell _a]\), which allows us to define differentiation for functions defined on a. In addition, we associate to each vertex \(v\in \mathcal {V}\) a control volume \(\text {vol}_v\) made up of the pipes \(a \in \mathcal {A}(v)\) cut to half length, see Fig. 1 for an illustration. We refer to the physical volume of these control volumes as \(|\text {vol}_v| = \sum _{a \in \mathcal {A}(v)} A_a \ell _a/2\). We will set \(\ell _a > 0\) for pipes and \(\ell _a = 0\) for active elements \(a \in \mathcal {A}_{ ae }\). Moreover, we require that \(\text {vol}_{v} > 0\) for all \(v \in \mathcal {V}\), i.e., every vertex is end point of at least one pipe \(a \in \mathcal {A}_{ pi }\). These topological conditions will be utilized in Sect. 3. As a next step, we describe the mathematical models for describing the gas flow through pipes and active elements.

Fig. 1
figure 1

Graph \(\mathcal {G}=(\mathcal {V},\mathcal {A})\) with vertices \(\mathcal {V}=\{v_1,v_2,v_3,v_4,v_5\}\) and arcs \(\mathcal {A}=\{a_1,a_2,a_3,a_4\}\) defined by \(a_1=(v_1,v_2)\), \(a_2=(v_2,v_3)\), \(a_3=(v_3,v_4)\), and \(a_4=(v_3,v_5)\). Here, \(\mathcal {V}_0=\{v_2,v_3\}\) and \(\mathcal {V}_\partial =\{v_1,v_4,v_5\}\). Furthermore, we have \(\mathcal {A}(v_1)=\{a_1\}\), \(\mathcal {A}(v_2)=\{a_1,a_2\}\), \(\mathcal {A}(v_3)=\{a_2,a_3,a_4\}\), \(\mathcal {A}(v_4)=\{a_3\}\), and \(\mathcal {A}(v_5)=\{a_4\}\). Additionally, \(\delta ^{ in }_{v_1}=\emptyset \), \(\delta ^{ in }_{v_2}=\{a_1\}\), \(\delta ^{ in }_{v_3}=\{a_2\}\),\(\delta ^{ in }_{v_4}=\{a_3\}\), \(\delta ^{ in }_{v_5}=\{a_4\}\), and \(\delta ^{ out }_{v_1}=\{a_1\}\), \(\delta ^{ out }_{v_2}=\{a_2\}\), \(\delta ^{ out }_{v_3}=\{a_3,a_4\}\), \(\delta ^{ out }_{v_4}=\emptyset \), \(\delta ^{ out }_{v_5}=\emptyset \). The control volumes \(\text {vol}_v\) are shown in gray

Full size image

2.2 Gas flow through pipes

On the length and time scales that are relevant for the operation of a gas network, the gas transport in a one-dimensional pipe \(a \in \mathcal {A}_{ pi }\) is described by the Euler equations, which are given as a system of nonlinear hyperbolic \({\text{PDEs}}\); see for example the works of Brouwer et al. (2011) and Osiadacz (1996):

$$ \partial _t\rho + \partial _x(\rho v)= 0, $$
(1a)
$$ \partial _t(\rho v) + \partial _x(p + \rho v^2)= -\frac{\lambda }{2D} \rho v \mathchoice{\left|v \right|}{|v|}{|v|}{|v|} - g \rho h', $$
(1b)
$$ \partial _t\Big ( \rho \big (\tfrac{1}{2} v^2 + e \big ) \Big ) + \partial _x\Big ( \rho v \big (\tfrac{1}{2} v^2 + e \big ) + pv\Big )= - \frac{k_w}{D}\left( T-T_w\right) . $$
(1c)

The three Eqs. (1a)–(1c) describe the conservation of mass, momentum, and energy, respectively. Here, \(\rho \), v, p, and T are the unknown density, velocity, pressure, and temperature, respectively. The constants \(\lambda \), g, and \(k_w\) are the friction coefficient, the gravitational constant, and the heat coefficient. Furthermore, we denote the slope of the pipe by \(h'\), the diameter by D, and the temperature at the pipe wall surface by \(T_w\). The internal energy is given by the variable \(e = c_v T + g h\) with the specific heat constant \(c_v\) and height h of the pipe. System (1) consists of three equations with four unknowns. In order to complete the system, an additional fourth equation is needed. To this end, we use the equation of state for real gases

$$ p = R_s \rho T z(p, T), $$
(2)

where z(p, T) is the compressibility factor and \(R_s\) the specific gas constant.

As already mentioned, we put particular emphasis on global optimal solutions of the underlying mathematical optimization problems. As a trade-off, we have to simplify system (1), as is often done in practice. First, we assume that the temperature T is constant, which allows us to neglect the energy equation (1c). The resulting system is often referred to as the isothermal Euler equations. We further assume that the compressibility factor z is constant as well. As a consequence, the speed of sound c can be computed by \(c^2 = R_s T z\), which transforms the equation of state (2) to

$$ p = c^2 \rho . $$
(3)

Using this, we can rewrite \(p + \rho v^2\) as \(p \left( 1 + v^2 / c^2 \right) \). In practice, the velocity of the gas is usually significantly lower than the speed of sound in the gas. Typically this is explicitly enforced to prevent noise and vibrations in the pipe. This entails that \(v^2 / c^2\) is very small and can therefore be neglected in our model. In addition, we assume that \(\partial _t(\rho v)\) is very small as well, see (Koch et al. 2015, Chapter 2). This assumption leads to a model comparable to the friction-dominated models discussed by Brouwer et al. (2011), which are widely used in the engineering literature (for references, see the work of, Brouwer et al. 2011). For ease of notation, we finally assume that the pipes are horizontal and that the diameter D is constant along pipes. Moreover, we define \(q :=A \rho v\) as the mass flow, where \(A = D^2 \pi /4\) is the cross-sectional area of the pipe. Consequently, the continuity eq. (1a) and the balance of moments (1b) simplify to:

$$ A \partial _t\rho + \partial _xq= 0, $$
(4)
$$ \partial _xp= -\frac{\lambda }{2D} \frac{|q|q}{A^2 \rho }. $$
(5)

In summary, the system (3)–(5) of nonlinear parabolic \({\text{PDEs}}\) is a friction-dominated approximation of the isothermal Euler equations and the equation of state (2); see (Domschke et al. 2017) for additional details. In the following, we use system (3)–(5) to represent gas physics.

2.3 Active elements

All active elements in our case are either valves or compressors and can be switched on or off. They denote pipe segments \(a = (v_1,v_2) \in \mathcal {A}_{ ae }\) of length \(\ell _a = 0\), in which the pressures \(p_a(v_1)\), \(p_a(v_2)\) and mass flows \(q_a(v_1)\), \(q_a(v_2)\) at the pipe ends \(v_1\) and \(v_2\) are related in a particular algebraic manner that can be switched between different states. A closed valve or compressor on an arc \(a=(v_1, v_2)\) blocks gas from passing, which can be expressed as \(q_a(v_2) = q_a(v_1) = 0\). For open valves or compressors in bypass mode, one has \(q_a(v_2) = q_a(v_1)\) and \(p_a(v_2) = p_a(v_1)\). For an operating compressor, one may assume \(q_a(v_2) = q_a(v_1)\) and \(p_a(v_2) = p_a(v_1) + \triangle \hat{p}_a\), where \(\triangle \hat{p}_a\) is the pressure increase produced by the compressor.

The individual cases mentioned above can be formulated in a unified manner. For an active element \(a = (v_1, v_2) \in \mathcal {A}_{ ae }\), the mass and momentum balance is described by

$$ q_a(v_1)- q_a(v_2)= 0, $$
(6)
$$ {\hat{s}}_{a}\, (p_a(v_1) - p_a(v_2)) + (1 - {\hat{s}}_{a})\, q_a(v_1)= {\hat{s}}_{a}\, \triangle \hat{p}_a, $$
(7)

where \({\hat{s}}_{a} \in \{0, 1\}\) and the pressure increment \(\triangle \hat{p}_a\) have to be prescribed. From now on, we use hat symbols to indicate that the corresponding variable is considered as a control or an input data for the gas transport model. Setting \({\hat{s}}_{a} = 1\) and choosing \(\triangle \hat{p}_a\) appropriately amounts to an open valve or a compressor that is in operating or bypass mode. Choosing \({\hat{s}}_{a} = 0\), on the other hand, describes a closed valve or compressor.

After having defined the models for gas transport in pipes and active elements, we now turn to the mathematical models for pipe junctions and terminal vertices.

2.4 Coupling conditions

In order to satisfy the basic conservation principles for mass and momentum also at the interior vertices \(v \in \mathcal {V}_0\) of the network, we require that

$$ \sum _{a \in \delta ^{ out }(v)} q_a(v) - \sum _{a \in \delta ^{ in }(v)} q_a(v)= \hat{q}_v, $$
(8)
$$ p_a(v)= p_v \qquad \text {for all } a \in \mathcal {A}(v). $$
(9)

Here \(q_a\) denotes the mass flow in the segment a and \(\hat{q}_v\) is a prescribed mass flow entering or leaving the system at the vertex v. The mass flows \(\hat{q}_v\) at interior vertices \(v \in \mathcal {V}_0\) can be interpreted as internal sources/sinks of mass on the network. The variable \(p_v\) denotes the value of the pressure at the vertex v which will be automatically determined when solving the system.

At the boundary vertices \(v \in \mathcal {V}_\partial =\mathcal {V}_p \cup \mathcal {V}_q\), we describe either the pressure or mass flow. This can be stated as

$$ \sum _{a \in \delta ^{ out }(v)} q_a(v) - \sum _{a \in \delta ^{ in }(v)} q_a(v)= \hat{q}_v \qquad \text {for all } v \in \mathcal {V}_q, $$
(10)
$$ p(v)= \hat{p}_v \qquad \text {for all } v \in \mathcal {V}_p. $$
(11)

Note that by definition of the boundary vertices, the two sums in (10) only involve one summand. Moreover, the corresponding equations amount to exactly one of the coupling conditions (8) or (9), while the other one is dropped. Again, the hat symbol denotes prescribed data for the gas transport model.

2.5 Initial data

The differential-algebraic system (4)–(11) can formally be reduced to a nonlinear degenerate parabolic system (Brouwer et al. 2011). In order to completely describe the evolution of the gas network, one therefore has to additionally prescribe the initial density distribution on all elements \(a \in \mathcal {A}\) by

$$ \rho _{a}|_{t=0} = \hat{\rho }_{a,0}. $$
(12)

The model (3)–(12) is our complete mathematical model for gas transport on the network and will be the starting point for all further considerations.

3 Discretization

In this section, we will derive a discretization method for the gas transport model discussed in the previous section. We will start with introducing a new variable and a reformulation of the governing equations, which is better suited for a systematic discretization. We then discuss the discretization in space by a finite volume approach on staggered grids and an implicit Euler method. The resulting nonlinear algebraic problem to be solved in each time step can be formulated as a convex minimization problem. This allows to prove the existence and uniqueness of the discretized gas transport problem for a rather general choice of the discrete and continuous controls that serve as input data.

3.1 Change of variables

The Eqs. (3)–(5), which model the gas transport for a single pipe \(a \in \mathcal {A}_{ pi }\) can be reformulated equivalently as

$$ A_a \partial _t\rho _a + \partial _xq_a= 0, $$
(13)
$$ \partial _x\pi _a= -\frac{\lambda _a}{D_a} \frac{c^2}{A_a^2} |q_a| q_a, $$
(14)
$$ \pi _a= c^4 \rho _a^2. $$
(15)

Note that, up to scaling, the new variable \(\pi _a\) amounts to the square of the pressure \(p_a\).

Since we only have to consider the cases \({\hat{s}}_{a} = 0\) and \({\hat{s}}_{a} = 1\), the algebraic equations (6)–(7) modeling the gas transport through active elements \(a \in \mathcal {A}_{ ae }\), can be rewritten equivalently as

$$ q_a(v_1) = q_a(v_2), $$
(16)
$$ {\hat{s}}_{a}\, (\pi _a(v_1) - \pi _a(v_2)) + (1 - {\hat{s}}_{a}) q_a(v_1) = {\hat{s}}_{a}\, \triangle \hat{\pi }_a, $$
(17)

where for ease of notation, we now assume that \(\triangle \hat{\pi }_a\) is prescribed instead of \(\triangle \hat{p}_a\) in Eq. (7).

In a similar manner, we rewrite the coupling conditions (8)–(9) at the interior vertices \(v \in \mathcal {V}_0\) as

$$ \sum _{a \in \delta ^{ out }(v)} q_a(v) - \sum _{a \in \delta ^{ in }(v)} q_a(v)= \hat{q}_v, $$
(18)
$$ \pi _a(v)= \pi _v \qquad \text {for all } a \in \mathcal {A}(v). $$
(19)

Again, the value \(\pi _v\) of the squared pressure at the junction v is a variable of the system that has to be determined during the solution process.

Using (3), the boundary conditions (10)–(11) may also be reformulated as

$$ \sum _{a \in \delta ^{ out }(v)} q_a(v) - \sum _{a \in \delta ^{ in }(v)} q_a(v)= \hat{q}_v \qquad \text {for all } v \in \mathcal {V}_q, $$
(20)
$$ \rho _v= \hat{\rho }_v \qquad \text {for all } v \in \mathcal {V}_p, $$
(21)

where \(\hat{\rho }_v\) can again be obtained from the prescribed pressure \(\hat{p}_v\) via (3). For ease of notation, let us also recall the initial condition

$$ \rho _{a}|_{t=0} = \hat{\rho }_{a,0}. $$
(22)

The system (13)–(22) in the three variables \(\rho \), q, and \(\pi \) will be the starting point for the discretization approach outlined in the following.

3.2 Local integral balances

Let us recall that \(\ell _a\), \(v_a\), and \(A_a\) denote the length, midpoint, and cross-sectional area of the arc \(a = (v_1, v_2)\), and that \(\text {vol}_v\) represents the control volume around a vertex v with \(|\text {vol}_v| = \sum _{a \in \mathcal {A}(v)} A_a\, \ell _a/2\) denoting the physical volume; see again Fig. 1 for an illustration.

By integration of Eq. (13) over the control volume \(\text {vol}_v\) and use of the coupling condition (18) at the vertex v, we obtain

$$ \int _{\text {vol}_v} \partial _t\rho \, d x+ \sum _{a \in \delta ^{ out }(v)} q_a(v_a) - \sum _{a \in \delta ^{ in }(v)} q_a(v_a) = \hat{q}_v. $$
(23)

Note that the cross-sectional area \(A_a\) from (13) appears implicitly in the definition of the control volume \(\text {vol}_v\). Equation (23) expresses the conservation of mass on the control volume \(\text {vol}_v\) and incorporates the differential equation (13) and the coupling condition (18).

Integration of the momentum equation (14) over a pipe \(a = (v_1, v_2)\) leads to

$$ \pi _a(v_2) - \pi _a(v_1) = -\frac{\lambda _a}{D_a} \frac{c^2}{A_a^2} \int _a |q_a| q_a \, d x, $$
(24)

which expresses the integral balance of pressure forces and friction over a pipe segment.

For an active element \(a = (v_1, v_2)\), we can directly use equation (17), which results in

$$ {\hat{s}}_{a}\, (\pi _a(v_1) - \pi _a(v_2)) + (1 - {\hat{s}}_{a}) q_a(v_1) = {\hat{s}}_{a}\, \triangle \hat{\pi }_a. $$
(25)

This equations resembles the balance of momentum for an active element \(a \in \mathcal {A}_{ ae }\).

3.3 Space discretization

We now replace \(\rho \) and q by their respective averages over the control volume spaces \(\text {vol}_v\) and arcs a using piecewise constant functions. By some abuse of notation, we denote the averages again by \(\rho _v\) and \(q_a\). Note that numerical integration by the mid-point rule is not used in the derivation of the method.

As approximation for integral balance (23) for the conservation of mass over the control volumes \(\text {vol}_v\), we then obtain

$$ |\text {vol}_v|\, \partial _t\rho _v + \sum _{a \in \delta ^{ out }(v)} q_a - \sum _{a \in \delta ^{ in }(v)} q_a = \hat{q}_v \qquad \text {for all } v \in \mathcal {V}_0 \cup \mathcal {V}_q. $$
(26)

For the boundary vertices \(v \in \mathcal {V}_p\), where the pressure is prescribed, we instead require that

$$ \rho _v = \hat{p}_v / c^2. $$
(27)

On every pipe \(a = (v_1,v_2) \in \mathcal {A}_{ pi }\), the balance of momentum is approximately described by

$$ \pi _{v_1} - \pi _{v_2} = \ell _a \frac{\lambda _a}{D_a} \frac{c^2}{A_a^2} |q_a| q_a, $$
(28)

where the integral in (24) is replaced by \(\ell _a |q_a| q_a\), since \(q_a\) was approximated by a constant value. In case of active elements \(a = (v_1, v_2) \in \mathcal {A}_{ ae }\), we set \(\ell _a = 0\) for the calculation of the volume \(|\text {vol}_v|\) assigned to the vertex v and replace (28) by

$$ {\hat{s}}_{a} (\pi _{v_1} - \pi _{v_2}) + (1 - {\hat{s}}_{a}) q_a = {\hat{s}}_{a} \triangle \hat{\pi }_a. $$

To complete the system, we finally require that

$$ \pi _v = c^4 \rho _v^2 \qquad \text {for all } v \in \mathcal {V}. $$
(29)

Further, we prescribe the initial density distribution on every control volume \(\text {vol}_v\) by

$$ \rho _v|_{t=0} = \hat{\rho }_{v,0}, $$
(30)

where \(\hat{\rho }_{v,0}\) may be defined as the average of the initial density distribution \(\hat{\rho }_{a,0}\) in (22) over the control volume \(\text {vol}_v\). The system (26)–(30) is the numerical model for the gas transport after semi-discretization in space. To obtain a computational model, we still need to discretize in time.

3.4 Time discretization

For the discretization in time, we utilize the implicit Euler method. Let \(\tau > 0\) be the time step and let \(t_n = n \tau \) with \(n=0, \ldots , N\) denote the discrete time points. For a function u of time, we denote by \(u_n\) the approximation for \(u(t_n)\) and we use the backward difference quotient \(\bar{\partial }_\tau u_n = (u_n - u_{n-1}) / \tau \) to approximate the time derivative term \(\partial _tu(t_n)\) appearing in Eq. (26). For ease of notation, let us further define for all \(v \in \mathcal {V}\) and all \(a \in \mathcal {A}\) the parameters

$$ \alpha _v :=\frac{|\text {vol}_v|}{\tau } \qquad \text {and} \qquad \beta _a :=\frac{\ell _a \lambda _a c^2}{D_a A_a^2}. $$
(31)

We further assume that \({\hat{s}}_{a,n}\), \({\hat{\rho }}_{v,0}\), \(\hat{p}_{v,n}\), \(\hat{q}_{v,n}\), and \(\triangle \hat{\pi }_{a,n}\) are prescribed. The fully discrete approximation for the gas transport problem (4)–(12) on the network is then given as follows.

Problem 1

(Fully discrete problem) Set \(\rho _{v,0} = \hat{\rho }_{v,0}\) for \(v \in \mathcal {V}\). Then, for \(n = 1, \ldots , N\), find solution vectors \(\rho _n=(\rho _{v,n})_{v \in \mathcal {V}}\), \(q_n=(q_{a,n})_{a \in \mathcal {A}}\), and \(\pi _n=(\pi _{v,n})_{v \in \mathcal {V}}\) such that

$$ \alpha _v \rho _{v,n} + \sum _{a \in \delta ^{ out }(v)} q_{a,n} - \sum _{a \in \delta ^{ in }(v)} q_{a,n}= \alpha _v \rho _{v,n-1} + \hat{q}_{v,n}\quad \text {for all } v \in \mathcal {V}_0 \cup \mathcal {V}_q, $$
(32)
$$ \alpha _v \rho _{v,n}= \alpha _v \hat{p}_{v,n}/c^2 \quad \text {for all } v \in \mathcal {V}_p, $$
(33)
$$ \pi _{v_1,n} - \pi _{v_2,n}= \beta _a |q_{a,n}| q_{a,n} \quad \text {for all } a = (v_1,v_2) \in \mathcal {A}_{ pi }, $$
(34)
$$ {\hat{s}}_{a,n} (\pi _{v_1,n} - \pi _{v_2,n}) + (1-{\hat{s}}_{a,n}) q_{a,n}= {\hat{s}}_{a,n} \triangle \hat{\pi }_{a,n}\quad \text {for all } a = (v_1,v_2) \in \mathcal {A}_{ ae }, $$
(35)
$$ \pi _{v,n}= c^4 \rho _{v,n}^2\quad \text {for all } v \in \mathcal {V}. $$
(36)

Let us note that this problem is a simulation problem that does not involve integer variables, since the controls \({\hat{s}}_{a,n}\) and \(\triangle \hat{\pi }_a\) are assumed to be prescribed here. Moreover, we keep \(\alpha _v\) on both sides of (33) since it appears naturally in the derivation of the Euler–Lagrange equations (38) in the following section. In the further course of our first-discretize-then-optimize approach, we will deal with optimal control problems where \({\hat{s}}_{a,n}\) and \(\triangle \hat{\pi }_{a}\) are included as free variables in Sect. 4. It is not difficult to see that the number of unknowns and equations match, so we can hope for a unique solution once the input and control variables are set appropriately.

3.5 Well-posedness of the fully discrete scheme

Before we proceed to the optimal control problems, let us briefly discuss the well-posedness of Problem 1. To do so, it suffices to show that for any \(1 \le n \le N\) and given density vector \(\rho _{n-1}=(\rho _{v,n-1})_{v \in \mathcal {V}}\), the system (32)–(36) admits a unique solution \((\rho _n,q_n,\pi _n)\). Recall that the three solution components \(\rho _n=(\rho _{v,n})_{v \in \mathcal {V}}\), \(q_n=(q_{a,n})_{a \in \mathcal {A}}\), and \(\pi _n=(\pi _{v,n})_{v \in \mathcal {V}}\) are vectors containing the respective function values.

3.5.1 A related minimization problem

For investigation of the solvability of (32)–(36), we consider the minimization problem

$$\begin{aligned} \min _{\rho _n,q_n,\pi _n} & \sum _{v \in \mathcal {V}} \tfrac{c^4 \alpha _v}{3} |\rho _{v,n}|^3 + \sum _{a \in \mathcal {A}_{ pi }} \left( \tfrac{\beta _a}{3} |q_{a,n}|^3 - \triangle \hat{\pi }_{a,n} q_{a,n}\right) \nonumber \\&+ \sum _{a \in \mathcal {A}_{ ae }} \left( \tfrac{1-{\hat{s}}_{a,n}}{2} |q_{a,n}|^2 - {\hat{s}}_{a,n} q_{a,n} \triangle \hat{\pi }_{a,n}\right) \end{aligned}$$
(37a)
$$\ {\text{s.t.}} \ \alpha _v \rho _{v,n} + \sum _{a \in \delta ^{ out }(v)} q_{a,n} - \sum _{a \in \delta ^{ in }(v)} q_{a,n} = \alpha _v \rho _{v,n-1} + \hat{q}_{v,n} \qquad \text {for all } v \in \mathcal {V}_0 \cup \mathcal {V}_q, $$
(37b)
$$\alpha _v \rho _{v,n} = \alpha _v \hat{p}_{v,n}/c^2 \qquad \text {for all } v \in \mathcal {V}_p. $$
(37c)

The Lagrangian for this constrained optimization problem reads

$$\begin{aligned} L(\rho _n,q_n,\pi _n)= \sum _{v \in \mathcal {V}} \tfrac{c^4 \alpha _v}{3} |\rho _{v,n}|^3 + \sum _{a \in \mathcal {A}_{ pi }} \left( \tfrac{\beta _a}{3} |q_{a,n}|^3 - \triangle \hat{\pi }_{a,n} q_{a,n}\right) \\&\quad + \sum _{a \in \mathcal {A}_{ ae }} \left( \tfrac{1-{\hat{s}}_{a,n}}{2} |q_{a,n}|^2 - {\hat{s}}_{a,n} q_{a,n} \triangle \hat{\pi }_{a,n}\right) \\&\quad - \sum _{v \in \mathcal {V}_0 \cup \mathcal {V}_q} \pi _{v,n} \left[ \alpha _v \rho _{v,n} + \sum _{a \in \delta ^{ out }(v)} q_{a,n} - \sum _{a \in \delta ^{ in }(v)} q_{a,n} - \alpha _v \rho _{v,n-1} - \hat{q}_{v,n}\right] \\&\quad - \sum _{v \in \mathcal {V}_p} \pi _{v,n} \alpha _v [\rho _{v,n} - \hat{p}_{v,n} / c^2]. \end{aligned}$$

The optimality conditions for the constrained optimization problem are thus given by

$$\begin{aligned}&0\,{\mathop {=}\limits ^{!}}\,\partial _{\rho _{v,n}} L(\rho _n,q_n,\pi _n) = c^4 \alpha _v |\rho _{v,n}| \rho _{v,n} - \alpha _v \pi _{v,n} \qquad \text {for all } v \in \mathcal {V},\nonumber \\&0\,{\mathop {=}\limits ^{!}}\,\partial _{q_{a,n}} L(\rho _n,q_n,\pi _n) = \beta _a |q_{a,n}| q_{a,n} + \pi _{v_2,n} - \pi _{v_1,n} \qquad \text {for all } a = (v_1,v_2) \in \mathcal {A}_{ pi },\nonumber \\&0\,{\mathop {=}\limits ^{!}}\,\partial _{q_{a,n}} L(\rho _n,q_n,\pi _n) = (1-{\hat{s}}_{a,n}) q_{a,n} - {\hat{s}}_{a,n}\triangle \hat{\pi }_{a,n} + \pi _{v_2,n} - \pi _{v_1,n} \qquad \text {for all } a = (v_1,v_2) \in \mathcal {A}_{ ae },\nonumber \\&\!0\,{\mathop {=}\limits ^{!}}\,\partial _{\pi _{v,n}} L(\rho _n,q_n,\pi _n) = \alpha _v \rho _{v,n} + \sum _{a \in \delta ^{ out }(v)} q_{a,n} - \sum _{a \in \delta ^{ in }(v)} q_{a,n} \nonumber \\&\quad \! - \alpha _v \rho _{v,n-1} - \hat{q}_{v,n} \qquad \text {for all } v \in \mathcal {V}_0 \cup \mathcal {V}_q, \nonumber \\&0\,{\mathop {=}\limits ^{!}}\,\partial _{\pi _{v,n}} L(\rho _n,q_n,\pi _n) = -\alpha _v [\rho _{v,n} - \hat{p}_{v,n}/c^2] \qquad \text {for all } v \in \mathcal {V}_p. \end{aligned}$$
(38)

It is easy to see that these equations are equivalent to the system (32)–(36), provided that \(\rho _v \ge 0\) for all \(v \in \mathcal {V}\). Also note that the role of the square pressure \(\pi _{v,n}\) is simply that of the Lagrange multiplier of the corresponding constraints (37b) and (37c).

Under some reasonable conditions on the properties of the network, we can now guarantee the existence of a unique solution of the minimization problem (37) for time step \(n \in [N] :=\{1, \ldots , N\}\).

Theorem 1

Let\(c>0\), \(\alpha _v>0\)for all\(v \in \mathcal {V}\), \(\beta _a>0\)for all\(a \in \mathcal {A}_{ pi }\). Furthermore, let\(\rho _{v,n-1}\)and\({\hat{s}}_{a,n} \in [0,1]\)be given for all\(v \in \mathcal {V}\)and\(a \in \mathcal {A}_{ ae }\). Then, the problem (37) admits a unique solution.

Proof

Let us first assume that \({\hat{s}}_{a,n} \in [0,1)\) for all \(a \in \mathcal {A}_{ ae }\). Then the first term of the objective function of the above optimization problem (37) is strictly convex in \(\rho =(\rho _v)_{v \in \mathcal {V}}\). The sum of the second and third term is strictly convex in \((q_a)_{a \in \mathcal {A}}\). The constraints (37b)–(37c), on the other hand, are linear and feasible, since \(\rho _v \ge 0\) for all \(v \in \mathcal {V}\). This already implies the existence of a unique minimizer in the case \({\hat{s}}_{a,n} \in [0,1)\) for all \(a \in \mathcal {A}_{ ae }\).

Now assume that \({\hat{s}}_{a,n} = 1\) for one arc \(a \in \mathcal {A}_{ ae }\). Then from the assumption that \(|\text {vol}_v|>0\), we deduce that one of the vertices v of the active element is connected to a pipe \(a' \in \mathcal {A}_{ pi }\). This allows us to formally eliminate the corresponding flow \(q_a\) via the linear equation (37b) for v in a pre-processing step, which also makes the Lagrange multiplier \(\pi _v\) superfluous; compare with Eq. (38). We are then back in the situation that \({\hat{s}}_{a,n} < 1\) for all (remaining) \(a \in \mathcal {A}_{ ae }{\setminus}\{a\}\). The case that \({\hat{s}}_{a,n} = 1\) for several arcs \(a \in \mathcal {A}_{ ae }\) can be treated by recursion of the argument. \(\square \)

3.5.2 Well-posedness of Problem 1

As mentioned above, as long as \(\rho _{v,n} \ge 0\) for all \(v \in \mathcal {V}\), the unique solution of the minimization problem (37), which always exists, corresponds to the unique solution of problem (32)–(36). If this is not the case, then problem (32)–(36) does not have a solution. By recursion over n, one can obtain a corresponding statement for the unique solvability of Problem 1.

4 The MINLP model

Endowed with the discretization from Sect. 3, we continue in this section with our first-discretize-then-optimize approach and show how to model the problem of maximizing the storage capacity of gas networks as an \({\text{MINLP}}\). To obtain a more intuitional modeling, we use a time-expanded graph that can be used equivalently to the fully discretized problem 1. Moreover, we incorporate active elements \(a \in \mathcal {A}_{ ae }= \mathcal {A}_{ vl }\cup \mathcal {A}_{ cm }\), where \(\mathcal {A}_{ vl }\) corresponds to the set of all valves and \(\mathcal {A}_{ cm }\) to the set of all compressors, into our model. As mentioned in Sect. 3.4, the control variables \({\hat{s}}_{a,n}\) and \(\triangle \hat{\pi }_a\) are now free and to optimize. We will then consider the solution of this \({\text{MINLP}}\) to global optimality in the succeeding section.

4.1 Pipes

Fig. 2
figure 2

A time-expanded graph of a gas network consisting of 4 vertices N1–N4 and 3 pipes. Each copy of a vertex is linked to the previous and subsequent copies by corresponding arcs (dark gray)

Full size image

The discretization from Sect. 3 is a time-expansion technique in which time-dependent properties change only at discrete times. It can therefore be modeled by a time-expanded graph. For this purpose, we copy the gas network for each time point and introduce for each vertex \(v \in \mathcal {V}\) an arc \((v_{n},v_{n+1})\) connecting the copy \(v_{n}\) of the vertex v in time step n with the one in time step \(n+1\). See Fig. 2 for an illustration.

For each vertex \(v \in \mathcal {V}\) and time step n we assume lower and upper bounds \(p_{v,n}^-\) and \(p_{v,n}^+\) for the pressure variable \(p_{v,n}\) and lower and upper bounds \(q_{a,n}^-\) and \(q_{a,n}^+\) for the flow variable \(q_{a,n}\) for each arc \(a \in \mathcal {A}\) and time step n. With the variable \(q_{(v_{n},v_{n+1})} :=\alpha _v \rho _{v,n}\) and using (32), we now obtain

$$ q_{(v_{n},v_{n+1})} + \sum _{a \in \delta ^{ out }(v)} q_{a,n} - \sum _{a \in \delta ^{ in }(v)} q_{a,n} = q_{(v_{n-1},v_{n})} + \hat{q}_{v,n} \qquad \text {for all } v \in \mathcal {V}, n \in [N], $$
(39)

for the flow conservation, where again \([N] = \{1, \ldots , N\}\). Since \(\pi _{v,n} = p_{v,n}^2\), we can incorporate the pressure loss equation (34) for each pipe \(a \in \mathcal {A}_{ pi }\) as

$$ p_{v_1(a),n}^2 - p_{v_2(a),n}^2 = \beta _a\, |q_{a,n}|\, q_{a,n} \qquad \text {for all } n \in [N] $$
(40)

into our model. Additionally, we have the following equations coupling (39) and (40):

$$ q_{(v_{n},v_{n+1})} = \alpha _v\, p_{v,n}/c^2 \qquad \text {for all } v \in \mathcal {V}, n \in [N]. $$
(41)

We point out that the bounds for \(q_{(v_{n},v_{n+1})}\) are determined by the bounds for \(p_{v,n}\) due to (41). It is also worth noting that this time-expanded graph can be considered as an extension of a stationary pipe model, e. g. , as specified by Fügenschuh et al. (2015), to a transient pipe model.

4.2 Valves

A valve corresponding to arc \(a = (v_1,v_2) \in \mathcal {A}_{ vl }\) is modeled using binary variables \(s_{a,n} \in \{0, 1\}\) for each time step n, whereby \(s_{a,n}\) is equal to one, if and only if the valve is open in time step n and equal to zero for a closed valve. A closed valve blocks gas from passing, which leads to decoupled pressures at vertices \(v_1\) and \(v_2\). For open valves, we have \(p_{v_1,n}= p_{v_2,n}\) and thus no pressure loss. This is described by

$$ q_{a,n}^- s_{a,n} \le q_{a,n} \le q_{a,n}^+ s_{a,n}, $$
(42a)
$$ ( p_{v_2,n}^+ - p_{v_1,n}^- ) s_{a,n} + p_{v_2,n}- p_{v_1,n} \le p_{v_2,n}^+ - p_{v_1,n}^-, $$
(42b)
$$ ( p_{v_1,n}^+ - p_{v_2,n}^- ) s_{a,n} + p_{v_1,n}- p_{v_2,n} \le p_{v_1,n}^+ - p_{v_2,n}^-. $$
(42c)

4.3 Compressors

Like a valve, a compressor corresponding to arc \(a = (v_1,v_2) \in \mathcal {A}_{ cm }\) is modeled via binary variables \(s_{a,n} \in \{0, 1\}\) for each time step n, whereby \(s_{a,n}\) is equal to one, if and only if the compressor is operating, i.e., increasing the pressure \(p_{v_1,n}\), in time step n. In the following, we restrict ourselves to a simplified compressor model, where an operating compressor may increase the pressure \(p_{v_1,n}\) such that

$$ 1 < r_a^- \le \frac{{p_{v_2,n}}}{{p_{v_1,n}}} \le r_a^+ $$
(43)

holds for given lower and upper bounds \(r_a^-\) and \(r_a^+\) of the compression ratio. Note that the flow is only allowed in arc direction (from \(v_1\) to \(v_2\)) for an operating compressor with \(0 \le (q_{a.n}^ {\text{op}} )^- \le (q_{a.n}^ {\text{op}} )^+\) as the corresponding bounds. Otherwise, if \(s_{a,n}\) is equal to zero, the compressor is in bypass mode, i.e., we have \(p_{v_1,n}= p_{v_2,n}\) while flow in both directions is allowed with the bounds \((q_{a.n}^ {\text{by}} )^- \le (q_{a.n}^ {\text{by}} )^+\). Similar to the paper by Geißler et al. (2015a), we can model this by

$$ (q_{a.n}^ {\text{by}} )^- (1 - s_{a,n}) + (q_{a.n}^ {\text{op}} )^-\, s_{a,n}\le q_{a,n}, $$
(44a)
$$ (q_{a.n}^ {\text{by}} )^+ (1 - s_{a,n}) + (q_{a.n}^ {\text{op}} )^+\, s_{a,n}\ge q_{a,n}, $$
(44b)
$$ \triangle _a^-\, s_{a,n} \le p_{v_2,n} - p_{v_1,n}, $$
(44c)
$$ \triangle _a^+\, s_{a,n} \ge p_{v_2,n} - p_{v_1,n}, $$
(44d)
$$ r_a^-\, p_{v_1,n}- (r_a^-\, p_{v_1,n}^+ - p_{v_2,n}^-) (1 - s_{a,n}) \le p_{v_2,n}, $$
(44e)
$$ r_a^+\, p_{v_1,n}- (r_a^+\, p_{v_1,n}^- - p_{v_2,n}^+) (1 - s_{a,n}) \ge p_{v_2,n}, $$
(44f)

where \(\triangle _a^-\) and \(\triangle _a^+\) are the bounds for the pressure increase. We point out that, unlike the modeling in Sect. 2, we limit ourselves to compressors that are only in either operating or bypass mode. The possibility to close a compressor can be modeled with an inlet or outlet valve.

4.4 Switching restrictions

Finally, we add constraints to limit switching operations of active elements to predetermined time intervals. These constraints imply that if the status of an active element is changed, then it must stay in this status for a specific time. This is motivated by the practice where the time between changing the settings of the active elements is usually long. In case of a valve, we require that a valve stays closed for \(S_{ vl }\) seconds if the status is changed from open to closed, and vice versa. We model this for all \(a \in \mathcal {A}_{ vl }\) by

$$ \sum _{i=n}^{n+M_n-1} s_{a,i} \ge M_n (s_{a,n} - s_{a,n-1})\quad \text {for all } n \in [N], $$
(45a)
$$ \sum _{i=n}^{n+M_n-1} s_{a,i} \le M_n + M_n (s_{a,n} - s_{a,n-1}) \quad \text{for all } n \in [N], $$
(45b)

where \(M_n = \min \{\lceil S_{ vl }/ \tau \rceil ,\; N - n +1 \}\) considering that the size of a time step \(\tau \) is given in seconds. In case of a compressor, we require that a compressor stays in bypass mode for \(S_{ cm }\) seconds if the status changes from operating to bypass, and vice versa. Analogously to a valve, we add (45a) and (45b) with \(M_n = \min \{\lceil S_{ cm }/ \tau \rceil ,\; N - n +1 \}\) for all \(a \in \mathcal {A}_{ cm }\) to the model.

4.5 Objective function

We now describe the objective of maximizing the storage capacity of a gas network more formally. To this end, we consider the following situation: Let a nomination \(\hat{q}^{\mathrm {nom}} \in \mathbb {R}^{N |\mathcal {V}_\partial |}\) be given, i.e., supply and demand for each time step n and each terminal vertex \(v \in \mathcal {V}_\partial \). We assume that the supply and demand vector consisting of the elements of \(\hat{q}^{\mathrm {nom}}\) that correspond only to the first time step \(n=1\) are feasible for the stationary case, i.e., there exists an admissible configuration of the active elements satisfying all physical and technical constraints for \(n=1\); see again (Koch et al. 2015) for more details on this topic. We further assume that such a feasible solution is available, which we will use as a starting solution for the first time step of our optimization problem.

Moreover, there are time windows \(1 \le k^- \le k \le k^+ \le N\) and \(1 \le l^- \le l \le l^+ \le N\) in which, additionally to the nomination, a positive amount of gas \({q}^{{\rm extra}}\in \mathbb {R}^{N |\mathcal {V}_{st}|}\) can be injected at selected entries \(\mathcal {V}_{s}\) and withdrawn at selected exits \(\mathcal {V}_{t}\), respectively. Lower and upper bounds \(({q}^{{\rm extra}}_{v,n})^-\) and \(({q}^{{\rm extra}}_{v,n})^+\) for each vertex \(v \in \mathcal {V}_{st}\) and time step n are also given. We balance \({q}^{{\rm extra}}\) by

$$ \sum _{v \in \mathcal {V}_{s}, n \in [N]} {q}^{{\rm extra}}_{v,n} \; - \sum _{v \in \mathcal {V}_{t}, n \in [N]} {q}^{{\rm extra}}_{v,n} \,=\, 0. $$
(46)

Our goal is to maximize this additional amount of gas that can be stored in the network.

This optimization problem can have different globally optimal solutions. We therefore take a simplified version of the minimization of the compressor energy into account, however, with such low costs that it is almost negligible. This gives us optimal solutions that tend to switch on compressors only when necessary. A possible simple formulation of the compressor energy minimization is

$$\begin{aligned} \min \ \sum \limits _{\begin{array}{c} a \in \mathcal {A}_{ cm } \end{array}} \gamma _1\, \int p_{v_2(a)}(t) - p_{v_1(a)}(t) \, d t+ \gamma _2\, |\partial _t(p_{v_2(a)}(t) - p_{v_1(a)}(t))|, \end{aligned}$$
(47)

where \(\gamma _1\), \(\gamma _2 > 0\) can be considered as costs and are small in our case. With the pressure increase \(\triangle p_{a,n} :=p_{v_2(a),n} - p_{v_1(a),n}\) for all compressors \(a = (v_1,v_2) \in \mathcal {A}_{ cm }\) and the change of the pressure increase over time \(|\triangle p_{a,n} - \triangle p_{a,n-1}|\), the formulation (47) corresponds to

$$\begin{aligned} \min \ \sum \limits _{\begin{array}{c} a \in \mathcal {A}_{ cm },\\ n \in [N] \end{array}} \gamma _1\, \triangle p_{a,n} + \gamma _2\, |\triangle p_{a,n} - \triangle p_{a,n-1}| \end{aligned}$$
(48)

in our \({\text{MINLP}}\) setting. We note that the absolute values in (48) can be eliminated by applying common \({\text{LP}}\) techniques.

Incorporating (48) into the objective function, we are now able to provide the complete problem of maximizing the storage capacity of a gas network as:

$$\begin{aligned} \max \sum \limits _{\begin{array}{c} v \in \mathcal {V}_{s},\\ n \in [N] \end{array}} {q}^{{\rm extra}}_{v,n} - \sum \limits _{\begin{array}{c} a \in \mathcal {A}_{ cm },\\ n \in [N] \end{array}} \gamma _1\, \triangle p_{a,n} + \gamma _2\, |\triangle p_{a,n} - \triangle p_{a,n-1}| \end{aligned}$$
(49a)
$$ \text{s.t.} \quad \text {pipe model constraints~(39)--(41)}, $$
(49b)
$$\text {active elements constraints~(42) and (44)}, $$
(49c)
$$\text {switching conditions~(45)}, $$
(49d)
$$\text {flow balance constraint~(46)}, $$
(49e)
$$p_{v,n}^- \le p_{v,n} \le p_{v,n}^+ \qquad \text {for all } v \in V,\; n \in [N], $$
(49f)
$$q_{a,n}^- \le q_{a,n} \le q_{a,n}^+ \qquad \text {for all } a \in \mathcal {A},\; n \in [N], $$
(49g)
$$({q}^{{\rm extra}}_{v,n})^- \le {q}^{{\rm extra}}_{v,n} \le ({q}^{{\rm extra}}_{v,n})^+ \qquad \text {for all } v \in \mathcal {V}_{st},\; n \in [N], $$
(49h)
$$s_{a,n} \in \{0,1\} \qquad \text {for all } a \in \mathcal {A}_{ ae },\; n \in [N].$$
(49i)

The nonlinear parts of the \({\text{MINLP}}\) model (49) are given by the pressure loss equations (40) for all \(n \in [N]\). Due to these equations this \({\text{MINLP}}\) problem is non-convex. However, these nonlinear functions are univariate and therefore only depend one a single variable, which simplifies the linearization in Sect. 5. For each \(n \in [N]\), the control variables are the binary variables \(s_{a,n}\) for all \(a \in \mathcal {A}_{ cm }\cup \mathcal {A}_{ vl }\) and the pressure increase \(\triangle p_{a,n} :=p_{v_2(a),n} - p_{v_1(a),n}\) for all \(a \in \mathcal {A}_{ cm }\).

5 Computational results

We now illustrate the applicability of our approach to storage capacity maximization problems by presenting two case studies based on the GasLib-11 (see Fig. 3) network (see Schmidt et al. 2017).

Fig. 3
figure 3

The GasLib-11 network

Full size image

The GasLib-11 network depicted in Fig. 3 consists of three entries S1–S3, five interior vertices N1–N5, and three exits T1–T3. Two compressors Cm1 and Cm2 are installed between S3 and N1, and N4 and N5, respectively. We have lower and upper bounds \(r_a^- = 1.0895\) and \(r_a^+ = 1.6009\) for the compression ratio of both compressors. All eight pipes have a length \(\ell _a\) of 55 km, a diameter \(D_a\) of 0.5m, and a roughness of 0.1mm resulting in a friction factor \(\lambda _a = 0.0137\). The two vertices T1 and T2 have a lower pressure bound of 40 bar and an upper pressure bound of 60 bar. All other vertices have lower and upper pressure bounds of 40 bar and 70 bar. In addition, a valve Vl1 between N1 and N3 is included.

5.1 Solving MINLP by MIP relaxations

As previously shown, we can model the problem of maximizing the storage capacity of gas networks as an \({\text{MINLP}}\) using (49). There is a wide variety of algorithms to solve \({\text{MINLP}s}\), for an overview see, e. g. , the works of Belotti et al. (2013), Lee and Leyffer (2012).

In this paper, we consider the method proposed by Burlacu et al. (2017), Geißler (2011) and Geißler et al. (2012), where \({\text{MINLP}s}\) are solved to global optimality by solving a series of mixed-integer linear programs (\({\text{MIP}s}\)). The main idea is to use piecewise linear functions to construct \({\text{MIP}}\) relaxations of the underlying \({\text{MINLP}}\). In order to find a global optimum, an iterative algorithm is developed that solves \({\text{MIP}}\) relaxations, which are refined adaptively. Additionally, whenever a feasible solution of an \({\text{MIP}}\) relaxation is found, all discrete variables of the \({\text{MINLP}}\) are fixed according to the corresponding solution of the \({\text{MIP}}\) relaxation. Solving the resulting \({\text{NLP}}\) to local optimality often delivers feasible solutions for the \({\text{MINLP}}\).

The motivation for using this method is as follows. As mentioned in Sect. 4, we can treat the instationary pipe model derived in the first sections as an extension of a stationary pipe model by a time-expanded graph. Burlacu et al. (2017) present promising numerical results for stationary gas transport optimization, where the \({\text{MIP}}\) relaxation approach outperforms state-of-the-art \({\text{MINLP}}\) solvers like Baron  (Tawarmalani and Sahinidis 2005) and SCIP  (Gamrath et al. 2016).

We give some insight into the chosen parameters and refer to the references already mentioned for further details on the algorithm. We use 50bar as error bound for the pressure loss equation (41) in the initial \({\text{MIP}}\) relaxation. Moreover, only those relaxations of the pressure loss equations (41) are chosen for refinement that have a relaxation error larger than \(0.85 \eta \), where \(\eta \) is the maximum of all relaxation errors.

We highlight two algorithmic extensions to the \({\text{MIP}}\)-based solution method. First, whenever a feasible solution of the \({\text{MINLP}}\) is obtained, we can obviously transform it into a feasible starting solution of the \({\text{MIP}}\) relaxation. This can sometimes reduce the runtime needed to solve the \({\text{MIP}}\). Furthermore, any objective value of a solution of an \({\text{MIP}}\) relaxation provides a dual bound for the \({\text{MINLP}}\) problem. At the same time, the dual bounds that we obtain while solving an \({\text{MIP}}\) relaxation are also dual bounds for the \({\text{MINLP}}\). We exploit this by solving a very fine \({\text{MIP}}\) relaxation. Although the \({\text{MIP}}\) solver is unlikely to solve the fine \({\text{MIP}}\) relaxation within reasonable time limits, if a tighter dual bound is found, we can use it as dual bound for the \({\text{MINLP}}\). In our computations, the extension of the algorithm by these two ideas leads to better results than the original solver proposed in Burlacu et al. (2017). Additionally, empirical studies in the context of gas network optimization problems show that the augmented solver is preferable to the original one. A detailed analysis, however, is beyond the scope of this paper and we have to leave it for future research.

We note that we do not use any problem specific heuristics to speed up the solution process. A possible heuristic would be to use an NLP relaxation of the problem, where the binary variables are reformulated as complementarity constraints and try to obtain a feasible solution via rounding (see e. g. Baumrucker and Biegler 2010 or Schewe and Schmidt 2018).

All computations are carried out utilizing this \({\text{MIP}}\)-based approach within the C++ software framework LaMaTTO++ (2015), on a cluster using 12 cores of a machine with two Xeon 5650 Westmere chips running at 2.66GHz with 24GB of RAM. Furthermore, we use Gurobi  (version 6.0.4 Gu et al. 2015) as \({\text{MIP}}\) solver and CONOPT3, provided by GAMS  (version 24.8.3 GAMS 2017), as the local \({\text{NLP}}\) solver both within LaMaTTO++.

5.2 Pressure and flow waves within pipes

As as first case study, we investigate the propagation of pressure and flow waves within pipes. For this purpose, we consider three consecutive pipes from the GasLib-11 network, e. g., S2–N3–N4–N2, resulting in a total length of 165 km. Initially, we assume a stationary state, where \(150\,\hbox {m}^{3}\hbox {h}^{-1}\) are injected in S2 and discharged at N2. We immediately increase the supply at S2 to \(450\,\hbox {m}^{3}\,\hbox {h}^{-1}\) and inject this amount up to minute 60. From minute 60 on, \(150\,\hbox {m}^{3}\,\hbox {h}^{-1}\) are injected again. We choose a time discretization of 5 s and a spatial discretization of 500 m. Please note that in the following, as is often the case for computational results in the literature, all flow values are given as volumetric flow values (\(\hbox {m}^{3}\,\hbox {h}^{-1}\)) instead of mass flow values. The volumetric flow Q and the mass flow q are related by \(q = \rho _0 Q\), where \(\rho _0 \approx 0.8304\,\hbox{kg\,m}^{-3}\) is the normal density, i.e., the density under normal conditions.

Fig. 4
figure 4

Pressure values (y-axis) for a fine (above) and coarse (below) discretization in three consecutive pipes of the GasLib-11 network over their accumulated length (x-axis) for different time points

Full size image
Fig. 5
figure 5

Flow values (y-axis) for a fine (above) and coarse (below) discretization in three consecutive pipes of the GasLib-11 network over their accumulated length (x-axis) for different time points

Full size image

The Figs. 4a and 5a show that our time-expanded graph model is capable of detecting parabolic pressure and flow waves and their propagation within pipes. Furthermore, we notice that although our model is not designed to accurately represent rapid flow changes in time, they are quickly smoothed. This behavior is typical for parabolic equations.

We now give some insight into the discretization of Sect. 5.3. Therein, we consider a time discretization of 10min and a two point space discretization of 55 km for the pipes. This coarse discretization is due to the fact that non-convex \({\text{MINLP}s}\) as in (49) are hard to solve in general. Hence, we are forced to use a coarse discretization in order to keep the \({\text{MINLP}}\) computationally tractable.

We run the same simulation as before, albeit with the coarse discretization. Analogously, we depict the result for the coarse discretization at different time points in the Figs. 4b and 5b. Please note that flow values between two discretization points in space are given by a piecewise constant function; see Sect. 3.3. In Fig. 5b, we therefore use the midpoint between two space discretization points to represent the respective flow values. Thus, we obtain points at lengths of 27.5 km, 82.5 km, and 137.5 km. Pressure values, however, are given for single discretization points in space, leading to points at lengths of 0 km, 55 km, 110 km, and 165 km in Fig. 4b. Comparing both discretizations, we can observe that the characteristic behavior of the fine discretization is maintained by the coarser one. In addition, the difference between the two discretizations vanishes with large time horizons. With the goal of global optimization, we are therefore confident to use the coarse discretization on time horizons of several hours.

5.3 Storage capacity maximization

As a second case study, we solve the storage capacity maximization problem (49) using the GasLib-11 network shown in Fig. 3. We choose the parameters \(\gamma _1 = 0.0015\), \(\gamma _2 = 0.02\), \(S_{ cm }= 7200\), and \(S_{ vl }= 3600\), which are introduced in Sect. 4. For the prescribed nomination \(\hat{q}^{\mathrm {nom}} \in \mathbb {R}^{N |\mathcal {V}_\partial |}\), we use the values that are given in Table 1 for all time steps.

Table 1 The prescribed nomination \(\hat{q}^{\mathrm {nom}}\) (given in \(\hbox {m}^{3}\,\hbox {h}^{-1}\)) for one time step and all entries and exits of the GasLib-11 network
Full size table

Both compressors Cm1 and Cm2 run in bypass mode at the beginning while the valve Vl1 is closed, which results in a tree structured network. Thus, we can compute an initial stationary solution by fixing the pressure for S1 to 58bar and propagation of the flow throughout the network. The resulting initial pressure values for all eleven vertices are given in Table 2.

Table 2 Initial pressure values (given in bar) for all eleven vertices of the GasLib-11 network as in Fig. 3
Full size table
Fig. 6
figure 6

Given volumetric flow rate profiles for the additional amount of gas that can be injected at S3 (left) and must be discharged accordingly at T3 (right). Based on \({q}^{{\rm extra}}\) in (49), the dashed lines indicate the additional amount of gas that can be injected at S3 (green lines) and must be discharged accordingly at T3 (red lines) with corresponding upper and lower bounds. (Color figure online)

Full size image

We now consider a time horizon of 8 h, with a time discretization of 10 min leading to a total amount of 48 time steps and a two point space discretization for the pipes. From minute 20 on, a positive amount of gas can be injected for two hours, in addition to the nomination, at S3. We allow a maximal additional amount that corresponds to  500 \(\hbox {m}^{3}\,\hbox {h}^{-1}\) . Moreover, we stipulate a linear increase (and decrease) in the additionally injectable gas amount up to (and from) the maximum within 20 min. From the fourth hour, the same additional amount of gas must be discharged at T3 within two hours, whereby the same conditions apply as in the case of the additional supply. See Fig. 6 for an illustration.

Fig. 7
figure 7

Profile for the pressure increase of compressor Cm1 (left) and compressor Cm2 (right) corresponding to the best solution for the storage capacity maximization problem (49) found after a total runtime of 4 h

Full size image
Fig. 8
figure 8

Profiles for the pressures of all eleven vertices of the GasLib-11 network in Fig. 3. The values correspond to the best solution for the storage capacity maximization problem (49) found after a total runtime of 4 h

Full size image
Fig. 9
figure 9

Volumetric flow rate profile for the valve Vl1 showing the amount of gas passing through the valve in case that it is open. The values correspond to the best solution for the storage capacity maximization problem (49) found after a total runtime of 4 h

Full size image
Fig. 10
figure 10

Volumetric flow rate profiles for the entry S1  (left) and the exit T2 (right) showing the additional amount of gas \({q}^{{\rm extra}}\) (orange) that is injected (S1) and discharged (T3). The values correspond to the best solution for the storage capacity maximization problem (49) found after a total runtime of 4 h

Full size image

The resulting \({\text{MINLP}}\) problem consists of 2311 variables, of which 2164 are continuous and 147 are binary, and 2785 constraints, of which 2393 are linear and 392 are nonlinear.

After a total runtime limit of 4 h, the \({\text{MIP}}\)-based approach delivers a feasible solution for the storage capacity maximization problem (49) that is globally optimal within a relative gap of almost 5%. The corresponding profiles of the solution are shown in Fig. 7 for the compressors Cm1 and Cm2, in Fig. 8 for the pressures of all eleven vertices, in Fig. 9 for the valve Vl1, and in Fig. 10 for the additional amount of gas \({q}^{{\rm extra}}\).

The compressor Cm1 is immediately switched on and operates throughout the whole time horizon. From minute 50 onwards, almost as much additional Gas \({q}^{{\rm extra}}\) is injected at S3 as possible. As a consequence, all pressure values rise with a higher amount of gas until no additional gas is injected in S3 anymore. Moreover, the valve Vl1 is opened, with approximately half of \({q}^{{\rm extra}}\) passing through it. About an hour before the additionally injected amount of gas is discharged at T3, the Compressor Cm2 is also switched on. At the same time, a small amount of gas passes through the valve again before it is closed. Due to the coincident compression of both compressors, the pressure at T3 remains within the pressure bounds while discharging the additional amount of gas.

Returning to the objective of maximizing the storage capacity, around 74.17% of the possible additional amount of gas in \({q}^{{\rm extra}}\) is attainable according to our solution; see Fig. 10. Due to the chosen parameters \(\gamma _1\) and \(\gamma _2\), the cost of compression is almost negligible in our \({\text{MINLP}}\) problem. Furthermore, our solution is globally optimal within a gap of less than 6%. Hence, we conclude that taking into account the model from above, no more than approximately 78.62% of the possible additional amount of gas in \({q}^{{\rm extra}}\) can be injected at S3.

Table 3 Iteration log of LaMaTTO++ for the storage capacity maximization problem (49) using the gas network in Fig. 3 with a total runtime limit of 4 h
Full size table

Finally, we show an iteration log of LaMaTTO++ for the storage capacity maximization problem (49) in Table 3. After a total runtime of less than 3 h, LaMaTTO++ is able to find a solution that is feasible for the storage capacity maximization problem (49) and globally optimal within a relative gap of almost 5%.

As mentioned before, the \({\text{MIP}}\) relaxation approach we utilize to solve our \({\text{MINLP}}\), adaptively refines \({\text{MIP}}\) relaxations of the \({\text{MINLP}}\). The first column in Table 3 indicates the corresponding \({\text{MIP}}\) relaxation. The best dual bound d of the \({\text{MINLP}}\) and the objective value z of the incumbent (feasible) solution are given in column two and three, respectively. The next column contains the relative gap \(|(z - d) / z|\), which is given in percent. The last column presents the runtime in seconds that LaMaTTO++ spent until the current iteration. We see that even with shorter runtime, LaMaTTO++ is able to find solutions with small relative gaps.

For the sake of comparison, the state-of-the-art global \({\text{MINLP}}\) solvers Baron and SCIP have the same \({\text{MINLP}}\) solved on the same cluster using 12 cores and a runtime limit of 4 h. After the time limit has been reached, the best feasible solution Baron finds has an objective value of 332.991, while the best dual bound is 630.965. This translates into a relative gap of about 89%. The best feasible solution SCIP finds has an objective value of 296.724, where the best dual bound is 622.838. This corresponds to a relative gap of about 109%. The extended \({\text{MIP}}\)-based approach of Burlacu et al. (2017), Geißler (2011), Geißler et al. (2012) thus delivers significantly better results in this case. Sometimes, in the case of application-related problems, a good feasible solution that is obtained in a short time is also useful. To this end, we solved the same \({\text{MINLP}}\) with the local \({\text{MINLP}}\) solvers AlphaECP  (Westerlund and Pörn 2002), Bonmin  (Bonami et al. 2008), and Knitro  (Byrd et al. 2006). Within a running time of 30 min Bonmin and Knitro were not able to find any feasible solution. AlphaECP, however, was able to find a feasible solution with an objective value of 464.885, which is slightly better than our solution found after 38.36 s and comparable to our best feasible solution, within only 2 m. AlphaECP is a local \({\text{MINLP}}\) solver and thus unable to provide a dual bound. Moreover, it could only confirm the feasibility of the solution, but no local optimality. With regard to global optimality, the approach of Burlacu et al. (2017), Geißler (2011), Geißler et al. (2012) is therefore preferable, as it provides feasible solutions of high quality and tight dual bounds.

In conclusion, we see that our time-expanded graph method can be successfully applied in the context of the storage capacity maximization of gas networks. In addition, the approach delivers solutions within reasonable runtime that are both physically plausible and near-global optimal.

6 Conclusion

In this paper, we presented a first-discretize-then-optimize approach for the maximization of the storage capacity of gas networks that are described by a coupled system of parabolic \({\text{PDEs}}\) and include active elements like valves and compressors. The main focus of our work is on global optimal solutions, including discrete decisions that result from switching active elements. To this end, we proposed a new discretization of the system of parabolic \({\text{PDEs}}\) and proved well-posedness for the resulting nonlinear discretized system. Endowed with this discretization, we used a time-expanded graph method to model the problem of maximizing the storage capacity as a non-convex \({\text{MINLP}}\).

Moreover, we algorithmically extended the \({\text{MINLP}}\) solver proposed by Burlacu et al. (2017), Geißler et al. (2012), Geißler (2011), which has so far been used successfully for stationary gas transport optimization. We utilized this augmented \({\text{MINLP}}\) solver to illustrate the applicability of our approach in a case study yielding both physically plausible and near-global optimal solutions. In addition, our method was able to find high-quality solutions even at short runtime. We therefore believe that our time-expanded graph approach is also suitable for the global optimization of other difficult problems in the field of transient gas transport optimization, which involve discrete decisions. Examples include problems with more realistic compressor models or large-scale time horizons of several days, which is part of our future work.