High detail stationary optimization models for gas networks: validation and results

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.

1 Introduction

In part one of this paper (Schmidt et al. 2014) we have presented detailed models for stationary optimization in gas transport networks, consisting of physical components that are mostly associated with network wide gas dynamics, and of technical components that are usually associated with specific types of network elements. We have also developed smoothing techniques for nonsmooth components in order to apply optimization algorithms that use first and second order derivatives, and we have presented simplifications and approximations of highly complex components to reduce the computational effort when a lower accuracy is acceptable. This leads to a complicated variety of possible combinations of the component models. In this paper we will first provide a structural overview of the possible combinations in Sect. 2. The components will then be checked for correctness and accuracy in Sect. 3 by comparing computational results with the results of a commercial gas network simulation software. In Sect. 4 we consider general optimization techniques for computing practically useful and reliable results efficiently. This includes penalty relaxations to obtain additional information when no feasible solutions can be found, and using the variety of simplified and approximated models to construct sequences of warm-started NLPs for tackling highly detailed and nonsmooth problems that cannot be solved without these techniques. Results will be presented in Sect. 5 for a set of hard problem instances on a real-world network, and for a large set of publicly available instances on an artificial but realistic network. In combination, the model validation and computational results demonstrate that our NLP models are indeed applicable and useful in practice. An extensive literature review has already been given in part one (cf. Schmidt et al. 2014); a broader review can be found in Koch et al. (2015).

In the following subsection we introduce a fundamental application problem that will be referred to throughout the paper.

1.1 Validation of nominations (NoVa)

The validation of nominations is one of the key problems in the day-to-day work of gas network planners. In a nutshell, the NoVa problem is this:

Given a transport network and a nomination of all entry and exit load flows, determine whether there is a technically and physically feasible operation of the network that satisfies this nomination.

The details are as follows. Consider a set of booking contracts with entry and exit customers. The booked capacities define maximal load flows that the customers may nominate for actual transport. Now, a nomination is defined as a complete set of balanced entry and exit load flows together with specific restrictions on gas pressures and with prescribed values for all quality parameters of the supplied gas, like calorific value, etc. The problem of validating such a nomination is to decide whether it is technically and physically feasible, i.e., whether all load flows can be realized. Throughout the paper we only consider the continuous feasibility problem that is obtained after fixing all discrete decisions. For more information on the NoVa problem and on our overall solution approach see, e.g., Koch et al. (2015), Pfetsch et al. (2015).

2 NLP model variants

In part one of this paper (cf. Schmidt et al. 2014), we have presented component models for the required element types of gas networks and for basic physical phenomena that are relevant to the entire network. The component models often consist of several sub-models describing different physical phenomena or technical processes that we refer to as model aspects, and many of these aspects admit a choice among several modeling variants that we refer to as model concretizations. This leads to a large variety of possible NLP models, each of which is determined by choosing a complete set of concretizations for all model aspects.

In this section we provide a structural description of the sets of component models, aspects and concretizations, to obtain an overview and better understanding of the complete set of NLP models and their interrelations. This is complicated by the fact that the selection of concretizations for certain global aspects determines the sets of choices of other aspects, whereas the remaining selections are mostly independent of each other, even for different network elements of the same type. To capture these interdependencies formally, we will arrange aspects and concretizations in a directed (meta-)graph so that every possible NLP model will ultimately correspond to a forest in the meta-graph: a set of trees that satisfy certain properties. These properties will now be determined.

To this end, let us first give an overview of the component models and some illustrative examples of model aspects and concretizations. The basic physical phenomena include: gas compressibility, the equation of state for real gas, the heat capacity of gas, the interdependence of changes in gas pressure and temperature (Joule–Thomson effect), and mixing of different gas compositions. The required element types include: nodes (entries, exits, junctions), passive arcs (pipes, resistors, short cuts), and active arcs (compressor groups, control valve stations, valves). Typical model aspects are the pressure drop along a pipe, the fuel consumption of a compressor, or the equation of state. For instance, the aspect “equation of state” has two concretizations, “thermodynamical standard equation” and “Redlich–Kwong”. The former depends on another model aspect, “compressibility”, which in turn has two concretizations, “AGA” and “Papay”; see Fig. 1. Here we consider only the concretizations that we use in our NLP models, with details given in part one; further variants can be added as needed.

Fig. 1

Model aspect graph of resistors. The nodes in shaded blocks exist only in non-isothermal models

There are two global aspects whose concretizations determine sets of choices of other aspects: gas temperature and gas composition, the latter being represented by seven gas quality parameters. In a coarse model we may fix the values of gas temperature and gas quality parameters globally, but if we decide to take into account changes at some network elements, then we must compute changes throughout the network. This is the case since both temperature and composition are globally coupled: fixing certain values at some network elements and computing changes at other elements would inevitably lead to model inconsistencies. Taking the changes into account is known as temperature tracking and gas quality tracking, respectively. Practitioners tend to use it only when necessary as it complicates the models and computations considerably. Note finally that the seven gas quality parameters (molar mass $m$, calorific value $H_{\mathrm{c}}$, pseudocritical pressure and temperature $p_{\mathrm{c}}, T_{\mathrm{c}},$ and the coefficients of isobaric molar heat capacity A, B, C) consist of four independent subsets that can be selected for tracking individually, namely $m$, $H_{\mathrm{c}}$, $(p_{\mathrm{c}}, T_{\mathrm{c}}),$ and (A, B, C). Tracking has to be enabled if at least one subset is selected, but only the selected subsets appear in the required mixing equations. The two global aspects thus have $2^5$ concretizations arising as combinations of “fixed” or “tracking” for the temperature and the four parameter groups.

Next, we start describing the above-mentioned meta-graph to formalize relations between model aspects and concretizations. As before, let the directed graph $G = ({\mathbb{V}}, {\mathbb{A}})$ model the gas network with node set ${\mathbb{V}}$ and arc set ${\mathbb{A}}$. We denote model aspect nodes of the meta-graph by $\alpha \in {\mathcal{A}}$ and concretization nodes by $\gamma \in {\mathcal{C}}$; their union ${\mathcal{A}}\cup {\mathcal{C}}$ defines the node set of the meta-graph. An arc $a = \alpha \gamma$ from $\alpha$ to $\gamma$ exists iff $\gamma$ is a concretization of the model aspect $\alpha$. These arcs in the set ${\mathcal{A}}\times {\mathcal{C}}$ are called “can-be-modeled-by”-arcs. For instance, there is an arc from the model aspect node $\alpha =$ “equation of state” to the concretization node $\gamma =$ “Redlich–Kwong”. In addition, the meta-graph also contains arcs from the set ${\mathcal{C}}\times {\mathcal{A}}$. These occur for concretizations that depend on other model aspects. For instance, the concretization “thermodynamical standard equation” depends on the sub-aspect “compressibility” (with concretizations “AGA” and “Papay”). We refer to these arcs in the set ${\mathcal{C}}\times {\mathcal{A}}$ as “contains-aspect”-arcs. In contrast, there are no arcs in ${\mathcal{C}}\times {\mathcal{C}}$ or in ${\mathcal{A}}\times {\mathcal{A}}$ since concretizations do not need to be concretized further and there is no need to consider aspects containing sub-aspects. (For instance, considering the specific change in adiabatic enthalpy $H_{\text{ad}}$ as an aspect with sub-aspects “compressibility” and “isentropic exponent” would be physically reasonable but would unnecessarily complicate the meta-graph, cf. Fig. 2).

Fig. 2

Model aspect graph of compressors. The nodes in the shaded block exist only in non-isothermal models

Thus, every aspect has at least one concretization and every concretization belongs to some aspect, implying that aspect nodes always have nonzero out-degree and concretization nodes always have nonzero in-degree. We define fundamental model aspects as aspects with in-degree zero, and terminal concretizations as concretizations with out-degree zero. Those form the respective sets $\bar{\mathcal{A}} \,{{:=}}\{\alpha \in {\mathcal{A}}:|\delta ^-_{\alpha }| = 0\}$ and $\bar{\mathcal{C}}\, {:=}\{\gamma \in {\mathcal{C}}:|\delta ^+_{\gamma }| = 0\}$.

In contrast to the two global model aspects, gas temperature and gas composition, we call all other model aspects local. The selection of concretizations of local aspects does not influence the sets of choices of other local aspects (except for sub-aspects of the concretizations, of course), and the selections are independent for all individual network elements. For instance, we may choose to concretize the compressibility factor model with the AGA formula at pipes in regional (low-pressure) sub-networks but choose to model the compressibility factor with the Papay formula on large (high-pressure) transport pipelines. Similar considerations may apply to the choice between “approximation” or “discretization” of the governing ODEs for pipes. We thus speak of global and local selections of concretizations.

To select a specific NLP model variant, we first have to fix the global selections and subsequently the local selections for all nodes and arcs of the network graph. Let us denote the global selections by $\sigma _g \in \Sigma _g$ where $\Sigma _g$ is the (finite) set of global choices. Then, for every network element $\ell \in {\mathbb{V}}\cup {\mathbb{A}}$, the global selections $\sigma _g$ determine a local model aspect graph ${\mathcal{M}}_\ell (\sigma _g)$ describing all possible aspects, concretizations, and sub-aspects of $\ell$; see, e.g., Figs. 1 and 2 for the local model aspect graphs of resistors and compressors. Fixing the local selections for $\ell$ means that, for every fundamental aspect node ${\bar{\alpha}}$ in ${\mathcal{M}}_\ell (\sigma _g)$, we select a tree $T_{\ell ,{\bar{\alpha}}}$ rooted in ${\bar{\alpha}}$ such that every aspect node $\alpha$ in $T_{\ell ,{\bar{\alpha}}}$ has out-degree one (select one concretization of $\alpha$) whereas every concretization node $\gamma$ in $T_{\ell ,{\bar{\alpha}}}$ has the same out-degree as in ${\mathcal{M}}_\ell (\sigma _g)$ (cover every sub-aspect of $\gamma$). Obtaining trees here requires that identical aspects reached from several concretizations are separate nodes in ${\mathcal{M}}_\ell (\sigma _g)$, such as “compressibility” in Figs. 1 and 2. Thus ${\mathcal{M}}_\ell (\sigma _g)$ is actually a forest, and every tree $T_{\ell ,{\bar{\alpha}}}$ is a subtree of the tree rooted in ${\bar{\alpha}}$. On the other hand, we always select identical concretizations for every instance of a “multiple” aspect, and we do not see any good reason to do otherwise. (Therefore we depict every such aspect as a single node with a visual indication of its multiplicity.) Now, the union $\bigcup _{{\bar{\alpha}}} T_{\ell ,{\bar{\alpha}}}$ is a forest in ${\mathcal{M}}_\ell (\sigma _g)$ representing a specific local model selection. We denote those local selections by $\sigma _\ell \in \Sigma _\ell (\sigma _g)$ where $\Sigma _\ell (\sigma _g)$ is the set of choices (local forests) at element $\ell$ determined by $\sigma _g$. Given network elements $\ell _1, \ell _2$ of the same type, the local model aspect graphs ${\mathcal{M}}_{\ell _1}(\sigma _g)$, ${\mathcal{M}}_{\ell _2}(\sigma _g)$ are clearly identical whereas the local selections $\sigma _{\ell _1}, \sigma _{\ell _2}$ may differ. A formal definition of the complete set of possible selections (or NLP model variants) thus reads

$$ \Sigma \,{:=}\bigcup _{\sigma _g \in \Sigma _g} \left[ \{\sigma _g\} \times {\prod _{\ell \in {\mathbb{V}}\cup {\mathbb{A}}}} \Sigma _\ell (\sigma _g) \right] . $$

The elements of $\Sigma$ will be denoted by $\sigma = (\sigma _g, \sigma_{\mathbb{V} \cup \mathbb{A}})$ with $\sigma _{\mathbb{V}\cup \mathbb{A}} = (\sigma _\ell )_{\ell \in \mathbb{V}\cup \mathbb{A}};$ each corresponds to a forest in the meta-graph constructed as a union of local forests. The respective subsets of global concretizations and of local concretizations at element $\ell \in {\mathbb{V}}\cup {\mathbb{A}}$ selected by $\sigma _g$ and $\sigma _\ell$ will be denoted by ${\mathcal{C}}_g, {\mathcal{C}}_\ell$.

With a selection $\sigma \in \Sigma$ at hand, we can now formulate the corresponding NLP model variant of the complete network. To this end, let ${\bar{\mathcal{E}}}_g, {\bar{\mathcal{I}}}_g$ and ${\bar{\mathcal{E}}}_\ell , {\bar{\mathcal{I}}}_\ell$ denote complete index sets of equality and inequality constraints that may appear in concretizations of the global aspects and of the aspects of element $\ell \in {\mathbb{V}}\cup {\mathbb{A}}$, respectively. Likewise, let ${\bar{\mathcal{V}}}_g, {\bar{\mathcal{V}}}_\ell$ denote the respective index sets of variables that appear in these concretizations. Here we require that corresponding constraint index sets of different elements $\ell _1, \ell _2 \in {\mathbb{V}}\cup {\mathbb{A}}$ are mutually disjoint, even if $\ell _1, \ell _2$ are elements of the same type,

$$ {\bar{\mathcal{E}}}_{\ell _1} \cap {\bar{\mathcal{E}}}_{\ell _2} = \emptyset , \quad {\bar{\mathcal{I}}}_{\ell _1} \cap {\bar{\mathcal{I}}}_{\ell _2} = \emptyset .$$

In addition, we require that every local variable index is associated with a unique network element $\ell$. This is possible since variables of arc $\ell \in {\mathbb{A}}$ can only appear in the constraints of arc $\ell$ and of its head and tail nodes whereas variables of node $\ell \in {\mathbb{V}}$ can only appear in the constraints of node $\ell$ and of its incident arcs. Thus, we obtain the following complete sets of constraints and variables that may appear in the NLP model:

$$ {\bar{\mathcal{E}}}= {\bar{\mathcal{E}}}_g \cup \bigcup _{\ell \in {\mathbb{V}}\cup {\mathbb{A}}} {\bar{\mathcal{E}}}_\ell , \quad {\bar{\mathcal{I}}}= {\bar{\mathcal{I}}}_g \cup \bigcup _{\ell \in {\mathbb{V}}\cup {\mathbb{A}}} {\bar{\mathcal{I}}}_\ell , \quad {\bar{\mathcal{V}}}= {\bar{\mathcal{V}}}_g \cup \bigcup _{\ell \in {\mathbb{V}}\cup {\mathbb{A}}} {\bar{\mathcal{V}}}_\ell .$$

Now, every model selection $\sigma$ determines certain global and local index subsets corresponding to the constraints and variables of the concretizations ${\mathcal{C}}_g, {\mathcal{C}}_\ell$,

$${\mathcal{E}}_{\sigma _g} \subseteq {\bar{\mathcal{E}}}_g, \quad {\mathcal{E}}_{\sigma _\ell } \subseteq {\bar{\mathcal{E}}}_\ell , \qquad {\mathcal{I}}_{\sigma _g} \subseteq {\bar{\mathcal{I}}}_g, \quad {\mathcal{I}}_{\sigma _\ell } \subseteq {\bar{\mathcal{I}}}_\ell , \quad {\mathcal{V}}_{\sigma _g} \subseteq {\bar{\mathcal{V}}}_g, \quad {\mathcal{V}}_{\sigma _\ell } \subseteq {\bar{\mathcal{V}}}_\ell . $$

The unions of these sets yield the complete index subsets associated with $\sigma \in \Sigma$,

$${\mathcal{E}}_\sigma = {\mathcal{E}}_{\sigma _g} \cup \bigcup _{\ell \in {\mathbb{V}}\cup {\mathbb{A}}} {\mathcal{E}}_{\sigma _\ell }, \quad {\mathcal{I}}_\sigma = {\mathcal{I}}_{\sigma _g} \cup \bigcup _{\ell \in {\mathbb{V}}\cup {\mathbb{A}}} {\mathcal{I}}_{\sigma _\ell }, \quad {\mathcal{V}}_\sigma = {\mathcal{V}}_{\sigma _g} \cup \bigcup _{\ell \in {\mathbb{V}}\cup {\mathbb{A}}} {\mathcal{V}}_{\sigma _\ell }.$$

The selected NLP variant finally reads

$$\min _{x_\sigma } \quad f(x_\sigma ) \quad {\text{s.t.}}\quad c_{{\mathcal{E}}_\sigma }(x_\sigma ) = 0, \quad c_{{\mathcal{I}}_\sigma }(x_\sigma ) \ge 0,$$

(1)

where

$$x_\sigma \,:=(x_i)_{i \in {\mathcal{V}}_\sigma }, \quad c_{{\mathcal{E}}_\sigma } \,:=(c_i)_{i \in {\mathcal{E}}_\sigma }, \quad c_{{\mathcal{I}}_\sigma } \,:=(c_i)_{i \in {\mathcal{I}}_\sigma }.$$

The objective function f, although not part of the model variant, is restricted by its set of variables: it can be any smooth function that depends only on $x_\sigma$.

We remark that some of the NLP model variants contain additional continuous choices that we will not formalize here. Those appear in concretizations that involve smoothing techniques or discretizations of differential equations, with smoothing parameters or grid parameters that vary in continuous sets. Examples of such concretizations include “Darcy–Weisbach smoothed” for resistors (see Fig. 1), or the concretization “discretization” of the model aspect “Momentum equation” for pipes (see Fig. 21 in Appendix 2).

Figures 1 and 2 and 17, 18, 19, 20, and 21 in Appendix 2 show the local model aspect graphs for resistors, compressors, nodes, control valves, and pipes. As already mentioned, the given sets of concretizations correspond to the model variants developed in part one of this paper (cf. Schmidt et al. 2014); further variants are conceivable and may be added as needed.

Let us finally remark that the occurrence of model aspects with several concretizations is not restricted to the case of gas network optimization. Our experience shows that other problems from engineering and physics share similar properties. The framework formalized in this section can thus be used in other fields of applied optimization as well.

3 Model validation

For a proper validation of the model components developed in the first part of this paper (cf. Schmidt et al. 2014), one would ideally set up inverse problems to perform parameter estimations based on measurements from a real gas network. Although possible in principle, this is prohibitively expensive in practice. Instead, we validate our model components against a commercial simulation software by a systematic comparison. This is a natural approach since our industrial partners rely on the same simulation software to check the results of the optimization methods.

For a stationary simulation, one generally has to prescribe a suitable set of quantities so that the resulting system of nonlinear differential and algebraic equations has a unique solution. In our case this includes discrete and continuous control settings of active network elements, flows at all but one entry and exit nodes in every connected component of the network, and in addition the pressure at one node in every hydraulically connected area. The simulation problem is typically solved by a Newton framework using numerical integrators. In practical planning applications, the solution is then manually checked against inequality constraints like pressure limits at nodes or the velocity limit on pipes.

Modern simulation methods can compute solutions with high accuracy. For increased computational speed, some simulation tools offer model simplifications, such as replacing heat dynamics by a constant temperature (see Záworka 1993) or deactivating the tracking of gas quality parameters like molar mass or calorific value.

To analyze the physical and technical accuracy of our NLP model components, we now carry out a consistency test against the commercial gas network simulation software SIMONE v5.73 (2004).¹ The relevant components are pipes, resistors, control valves, and compressors: entries, exits, junctions, valves, and short cuts have trivial models and are therefore excluded. For the comparison, each of the four element types is tested with several technical and physical settings, and possibly with several model variants. The variant offering the highest common level of detail between the NLP model and SIMONE is always included in the test set. In specific, we use a non-isothermal model of gas physics with gas mixing at nodes, discretized ODEs for the gas flow in pipes, and maximally detailed models of compressors and drives; see Sect. 3 in Schmidt et al. (2014) for the details of the NLP model.

When generating the test sets, we aim at choosing realistic parameters of network elements. Ideally, we would like to use the elements of a real-world network for the comparison, but due to limitations of the SIMONE API (2009), some parameters can only be entered manually via the graphical user interface, which is impractical for our large number of tests. The test set of every network element type is therefore designed as follows. For every technical parameter (except pipe inclination, which cannot be set with the SIMONE API) we take four quantiles from the distribution of values of a real-world gas network: the 10, 35, 65, and 90 % quantiles. The gas network considered is the northern high-calorific network of our industry partner Open Grid Europe (OGE)² (see Sect. 5 for more details of this network). All other parameters of our test sets like pressure or flow values are suitably chosen from typical ranges based on our experience. The Cartesian product of the resulting sets of parameters then defines the test set. Excluding the lower and upper 10 % of parameter values helps to avoid unrealistic parameter combinations that would otherwise distort the analysis. We also exclude those cases from the analysis where SIMONE or the NLP solver do not converge or where SIMONE yields a solution that violates the velocity limit on a pipe. The remaining successful cases will be referred to as valid tests.

As measures of deviation for a physical or technical quantity x (such as pressure or temperature) we will consider the absolute and relative deviations of x itself,

$$\begin{aligned} d_{\text{abs}}(x) = |x_{\text{NLP}} - x_{\text{Sim}}|, \qquad d_{\text{rel}}(x) = \frac{|x_{\text{NLP}} - x_{\text{Sim}}|}{|x_{\text{Sim}}|}, \end{aligned}$$

and, if applicable, the relative deviation of the change of x along a network arc,

$$\begin{aligned} d_{\text{rel}}(\Delta x), \quad \Delta x = x_{\text{in}}- x_{\text{out}}. \end{aligned}$$

Here, $x_{\text{Sim}}$ and $x_{\text{NLP}}$ denote the respective solution values of SIMONE and the NLP model. To obtain a meaningful comparison, the component parameters are always identical in the NLP and in SIMONE, similarly the transport situations (typically defined by $Q_{0}$, $p_{\text{in}}$, $T_{\text{in}}$), and the model variants are selected to agree as well as possible. To avoid that exceptional cases dominate the comparison, we will discuss arithmetic mean deviations rather than maximum deviations.

3.1 Pipes

For the validation of pipes we select four model variants: the combinations of two pressure loss models (quadratic approximation and ODE discretization) with two models of the compressibility factor (AGA formula and Papay’s formula). For each of these four variants, 12,288 test cases are obtained as combinations of the parameters given in Table 1. The geodesic height of the inflow node is fixed at 0 m, so that 8192 physically possible test cases remain (with $|h_{\text{out}}| < L$). The valid tests are used to calculate average deviations of $x \in \{p_{\text{out}}, T_{\text{out}}\}$. Here $d_{\text{rel}}(\Delta x)$ is only computed if the change $\Delta x$ is at least 1% of the inflow value, to avoid numerical noise dominating in cases where the change is insignificant and hence the denominator $\Delta x$ becomes very small, which could bias the comparison substantially. Table 2 shows the resulting deviations. As expected, the deviations between the discretized ODE model and SIMONE are smaller than in case of the quadratic approximation. Note that SIMONE always applies an implicit integration over time for the Euler equations of gas; dynamics; cf. Králik et al. (1988) and Záworka (1993). In the stationary case, the PDE solution approaches the solution of the spatial ODE asymptotically, and SIMONE simply uses a large time interval to obtain a highly accurate solution. Nevertheless, the absolute deviation of pressure with the quadratic approximation is only about 0.1 bar, which appears to be sufficiently small for practical purposes in mid- to long-term planning tasks. Figure 3 shows logarithmically scaled histograms of the absolute deviations of outflow pressure and temperature for the model using the discretized ODE and Papay’s formula. For the outflow pressure the leftmost bin contains 2574 of 2659 samples (97 %) and for outflow temperature the leftmost bin contains 2330 of 2659 samples (88 %).

Table 1 Parameters for test cases of pipes

Table 2 Deviations of outflow pressure ($p_{\text{out}}$, bar) and outflow temperature ($T_{\text{out}}$, K) of pipes

Fig. 3

Logarithmic histograms of outflow pressure and temperature for the model variants “ODE discretization” and “Papay’s formula”

Fig. 4

Outflow pressure profile of an exemplary pipe (L = 46 km, D = 1185 mm, k = 0.006 mm, s = 0.01, p _in = 74.44 bar, T _in = 318.15 K and T _soil = 284.15 K) computed using Papay’s formula in SIMONE v5.73 (), NLP with ODE discretization (- - -), and NLP with a quadratic approximation (···). Figure on the right is a zoom of the dashed frame in the left figure

Fig. 5

Outflow temperature profile for the pipe of Fig. 4

Let us now discuss a specific test instance in more detail. Figure 4 shows some exemplary pressure profiles (outflow pressure vs. flow) of SIMONE and two NLP model variants, each combined with Papay’s formula. As one would expect, the outflow pressure deviations between the models grow with increasing pressure loss. In fact, almost arbitrarily large deviations can be generated if the pipe parameters and boundary values are chosen such that huge pressure losses result: for instance, a gap of about 38.5 bar between SIMONE and the quadratic approximation is obtained for the example in Table 3.

Table 3 Extremal pipe example

In this (totally unrealistic) case, the pipe is rather long and its inner wall is extremely rough.

Turning to the outflow temperatures in Fig. 5, we observe that all three profiles are roughly comparable but visibly different. An interesting aspect is the difference between the NLP models based on approximation and ODE discretization. As can be seen in Fig. 5, the approximation model does not catch the convex curvature at small flows. Nevertheless, the average absolute deviation of 1 K (cf. Table 2) lies within the range of data accuracy: environmental forecasts, soil temperatures, and heat transfer coefficients of pipe walls are inherently inaccurate, and data imprecision is likely to introduce larger errors than 1 K.

Figure 5 also shows a strange behavior of SIMONE for flow values close to zero: there is a sharp peak in the outflow temperature profile that cannot actually represent physical behavior. Therefore we tested the example of Fig. 5 again with the more recent software release SIMONE v5.83. This version appears to fix the problem at small flows, see Fig. 6 (right). However, both versions exhibit a discontinuity of the outflow pressure at zero flow, see Fig. 6 (left).

Fig. 6

Differences between SIMONE v5.73 (${- - -}$) and SIMONE v5.83 (····) versions for small flows

Moreover, comparing both versions at large flows in the example of Fig. 6 yields deviations up to 1.5 bar for outflow pressure and up to 0.93 K for outflow temperature. These deviations are larger than most of the deviations between the NLP model and SIMONE v5.73. Thus, regarding temperature, the NLP model appears to match SIMONE as well as the two versions of SIMONE match each other.

Finally, although the quadratic pressure loss approximation is a substantial simplification of the PDE model solved by SIMONE, its results appear to be sufficiently accurate for practical use in mid- to long-term planning tasks: the deviations discussed above are mostly smaller than data inaccuracies caused by uncertainty of measurements and unknown network data. In any case, if higher physical accuracy is required, the approximation model can easily be replaced by the ODE model.

3.2 Control valves and resistors

In order to obtain unique solutions for control valves and resistors, the values of inflow pressure, inflow temperature, and flow are fixed, and in case of control valves also the pressure reduction. For the compressibility factor we consider again both the AGA formula and Papay’s formula. The temperature change in control valves and resistors is calculated by the same model, cf. Eq. (100) of Schmidt et al. (2014), hence similar behavior is to be expected in the comparisons. The definition of the test set is given in Tables 4 and 5 and the results can be seen in Tables 6 and 7.

Table 4 Parameters for test cases of control valves

Table 5 Parameters for test cases of resistors

Table 6 Outflow temperature ($T_{\text{out}}$) deviations of control valves

Table 7 Outflow pressure ($p_{\text{out}}$) and temperature ($T_{\text{out}}$) deviations of resistors: linear pressure loss model (above) and Darcy–Weisbach type model (below)

In one respect they are similar to the case of pipes: Papay’s formula yields very small deviations for the outflow temperature whereas the AGA formula yields deviations up to 8 times as large. However, the absolute deviations are always reasonably small at less than 1 K.

For control valves and for resistors with a linear pressure loss model, the outflow pressure depends linearly on the preset values by Eq. (99) of Schmidt et al. (2014) and Eq. (12) of Schmidt et al. (2014). Thus the NLP model and SIMONE should agree almost within machine precision, but actually the outflow pressures show an average absolute deviation of about 5 × 10⁻⁵ bar. Since the NLP results can be shown to be correct, the deviation possibly indicates an output precision of the SIMONE API of about 1 × 10⁻⁴. The precision of internal computations is not known for SIMONE.

For resistors with a Darcy–Weisbach type pressure loss model, the outflow pressure is determined by the nonlinear eq. (13) of Schmidt et al. (2014). Although all values in this equation are given (except for the outflow pressure), we observe again small but measurable deviations between the NLP and SIMONE. The mean absolute deviation is 0.006 bar with the AGA formula and 0.008 bar with Papay’s formula.

3.3 Compressors

Table 8 Parameters for test cases of piston and turbo compressors

For the examination of turbo and piston compressors, we fix the values of inflow pressure, inflow temperature, outflow pressure, and flow (see Table 8 for the specific values). The test set is constructed from 18 combinations of physical models of the compressibility factor, the isentropic exponent, and the temperature rise equations, yielding 1458 test cases both for turbo and piston compressors. We compare computed values of the specific change in adiabatic enthalpy $H_{\text{ad}}$ (kJ kg$^{-1}$), required compressor power $P$ (MW), and compressor outflow temperature $T_{\text{out}}$ (K). Table 9 shows the results for turbo and piston compressors.

Table 9 Results of the comparison of turbo compressors (above) and piston compressors (below) concerning specific change in adiabatic enthalpy ($H_{\text{ad}}$), power ($P$), and outflow temperature ($T_{\text{out}}$)

Since $H_{\text{ad}}$ and $P$ do not have inflow and outflow values, $d_{\text{rel}}(\Delta x)$ does not exist for these quantities. The results of the NLP model and SIMONE agree very well for the compressors: the relative deviations $d_{\text{rel}}(x)$ are no larger than 0.2 %, and even the relative deviations $d_{\text{rel}}(\Delta x)$ with respect to the temperature change are just about 2 %. A possible reason for the remaining small temperature difference may lie in the model of the isentropic exponent or in differences of the adiabatic efficiency. These two quantities cannot be accessed with the SIMONE API and are therefore not compared.

3.4 Conclusion

Of course, one cannot expect that computational results of any simulation software and of the NLP model agree with high precision. Differences in numerical algorithms, discretizations, and implementations make deviations almost inevitable. In addition, it is likely that there are differences in data handling and in the precision of data input and output. Obviously, these aspects may add to the deviations caused by the numerical schemes.

As we have seen, it is difficult to validate our highly accurate NLP model against a closed-source simulation package like SIMONE because the code of the latter cannot be inspected. This is the reason why in certain cases we can only observe but not analyze differences in the computational results. For instance, we have no clue why the outflow temperatures of several network element types show unexpectedly large deviations if we use the AGA formula for the compressibility factor, whereas deviations are very small with Papay’s formula. A possible reason might be that the correction term for the heat capacity (see Eq. (38) of Schmidt et al. 2014) is handled in different ways. As stated in part 1 of this paper, that term evaluates to zero with the AGA formula, so the value is exact in our NLP model. However, it is possible that SIMONE evaluates the integral numerically rather than simply dropping it. Differences like those may cause many of the unexplained deviations, but we have no way to tell.

In summary, the observed differences between the NLP model and SIMONE are surprisingly small. Thus, we view the comparison presented above as a successful validation of our model components for the intended use in optimization-based mid-term to long-term planning in gas networks.

4 Optimization techniques

This section addresses two types of techniques that are important when solving the problem of validation of nominations in practice: penalty-based relaxations in several standard and problem-specific variants and sequences of simplified NLPs that are used to obtain a good initial estimate for the NLP of interest.

As it is the case for the framework of model aspect graphs in Sect. 2, the techniques presented in this section are not restricted to the field of gas network optimization but can also be applied to other problems from engineering or physics.

4.1 Penalty formulations

Penalty formulations provide an essential tool for the modeler as well as for the practitioner who uses optimization software to solve real-world problems. For the modeler it is often difficult to find model errors or inconsistencies, particularly if he or she is not also a practitioner or an expert in the area of application. More importantly, the modeler (or practitioner) is often troubled with erroneous, incomplete, or inconsistent data. These data problems may lead to infeasible instantiations of the optimization model and are typically hard to detect. Sophisticated penalty formulations relax certain constraints of the optimization model, thus giving a chance to detect the area of the transport network in which a model or data problem may be located. For the practitioner, penalty formulations are also very useful in situations where he or she is not only interested in optimal solutions but also in other feasible solutions.

Furthermore, penalty formulations are often instrumental in speeding up the solution process by finding an (almost) feasible solution first. It is usually easier and faster to solve the original problem with such a near-feasible solution as initial estimate than solving it from scratch (cf. Sect. 4.2).

In what follows, we present some penalty-based relaxation schemes that are used in gas transport applications. The presented relaxation schemes will be used in Sect. 4.2, and numerical results are finally given in Sect. 5.

4.1.1 Relaxation schemes for gas network optimization models

Suppose that a specific instantiation of interest of the model hierarchy presented in Sect. 3 of Schmidt et al. (2014) is given in standard NLP form,

$$ \min _x \, f(x) \quad \text{s.t.}\quad c_{\mathcal{E}}(x) = 0, \quad c_{\mathcal{I}}(x) \ge 0.$$

(2)

Here and in what follows, ${\mathcal{E}}$ and ${\mathcal{I}}$ are the respective index sets of equality and inequality constraints. With slack variables $s = (s_{\mathcal{E}}^+, s_{\mathcal{E}}^-, s_{\mathcal{I}}^+)$, the associated standard $\ell _1$ penalty model is then defined as

$$\min _{x, s} \, ||s||_1 \quad \text{s.t.}\quad c_{\mathcal{E}}(x) + s_{\mathcal{E}}^+ - s_{\mathcal{E}}^- = 0, \quad c_{\mathcal{I}}(x) + s_{\mathcal{I}}^+ \ge 0, \quad s \ge 0. $$

(3)

Likewise, the standard $\ell _\infty$ penalty model reads

$$\min _{x, s} \, ||s||_\infty \quad \text{s.t.}\quad c_{\mathcal{E}}(x) + s_{\mathcal{E}}^+ - s_{\mathcal{E}}^- = 0, \quad c_{\mathcal{I}}(x) + s_{\mathcal{I}}^+ \ge 0, \quad s \ge 0.$$

(4)

Both models are full relaxations of (2) and hence feasible by construction. The $\ell _1$ penalty model (3) is actually smooth since $||s||_1$ is just the sum of the components of s, while the $\ell _\infty$ penalty model is easily converted to an equivalent smooth formulation by adding an extra variable z for $||s||_\infty$ and inequality constraints $z - s_i \ge 0$ for all components of s.

Minimizing the $\ell _1$ norm has the well-known property that it tends to generate sparse solutions, i.e., solutions with only a few nonzero entries in s (see Elad (2010), Wotao and Zhang (2008), and the references therein). This property is very useful in detecting and analyzing potential reasons of infeasibility.

Minimizing the $\ell _\infty$ norm is useful if one is interested in determining the smallest possible upper bound on the constraint violations. In contrast to (3), solutions of (4) tend to have the property that many components of s do not vanish but often have significantly smaller values than the nonzero components of solutions to the corresponding $\ell _1$ penalty model.

These two basic relaxation types are now used to develop problem-specific relaxation schemes. In practice, one often does not wish to relax all constraints but only certain classes. For instance, such a class may contain all pressure loss modeling equations on pipes or all constraints modeling the borders of characteristic diagrams of compressors. For handling selected classes of constraints, we introduce the index set ${\mathcal{R}}\subseteq {\mathcal{E}}\cup {\mathcal{I}}$ indicating which constraints are to be relaxed. The required slack variables are $s = (s_{\mathcal{E} \cap \mathcal{R}}^+, s_{\mathcal{E} \cap \mathcal{R}}^-, s_{\mathcal{I} \cap \mathcal{R}}^+)$. With this notation, the partly relaxed $\ell _1$ penalty model is given by

$$\begin{aligned}\min _{x, s} \, ||s||_1 \quad \text{s.t.}\quad&c_{\mathcal{E}\setminus \mathcal{R}}(x) = 0, \quad c_{\mathcal{E}\cap \mathcal{R}}(x) + s_{\mathcal{E}\cap \mathcal{R}}^+ - s_{\mathcal{E}\cap \mathcal{R}}^- = 0, \\&c_{\mathcal{I}\setminus \mathcal{R}}(x) \ge 0, \quad c_{\mathcal{I}\cap \mathcal{R}}(x) + s_{\mathcal{I}\cap \mathcal{R}}^+ \ge 0, \quad s \ge 0.\end{aligned}$$

(5)

The corresponding partly relaxed $\ell _\infty$ norm penalty model reads

$$\begin{aligned} \min _{x, s} \, ||s||_\infty \quad \text{s.t.}\quad&c_{\mathcal{E}\setminus \mathcal{R}}(x) = 0, \quad c_{\mathcal{E}\cap \mathcal{R}}(x) + s_{\mathcal{E}\cap \mathcal{R}}^+ - s_{\mathcal{E}\cap \mathcal{R}}^- = 0, \\&c_{\mathcal{I}\setminus \mathcal{R}}(x) \ge 0, \quad c_{\mathcal{I}\cap \mathcal{R}}(x) + s_{\mathcal{I}\cap \mathcal{R}}^+ \ge 0, \quad s \ge 0. \end{aligned}$$

(6)

Note that these two relaxations are not necessarily feasible, except of course with the choice ${\mathcal{R}}= {\mathcal{E}}\cup {\mathcal{I}}$ where they become identical to the standard penalty models.

The partly relaxed penalty models (5) and (6) are of special interest in practice, because a suitable choice of the index set ${\mathcal{R}}$ may allow to detect reasons of infeasibility. Of course, from the mathematical viewpoint, there is no such thing as a “reason” of infeasibility: infeasibility is simply caused by a set of incompatible constraints, and in general there may be a variety of possibilities to achieve feasibility by relaxing different subsets of those constraints. In practice, however, different constraints often have different relevance (depending on the specific situation). Then, if the violation of a lower-priority constraint makes the problem otherwise feasible, that lower-priority constraint may be interpreted as “the reason” of infeasibility, and a sufficiently small violation will be tolerated.

Suppose that a practitioner is confronted with an infeasible instance. If, say, a relaxation of compressor group constraints leads to feasibility, the reason might be that a lower pressure bound in a downstream part of the network is too tight. Another reason might be that the operating ranges of certain active compressor units are not sufficiently large for generating an outflow pressure that satisfies the pressure bounds in the downstream network. The opposite situation (too tight upper pressure bounds) may be detected by relaxing control valve constraints that limit the pressure decrease from below. Here, the “reason” depends on the interpretation of the situation by the practitioner, who may decide that the pressure bounds or the borders of the characteristic diagrams of the compressors are more important, respectively. Another relaxation that is often used in practice is to relax the supplied and discharged amounts of flow at entry and exit nodes. Given a solution to this relaxed model with non-vanishing slack variables, the practitioner obtains the information of how much the contracts with one or more entry or exit customers have to be modified in order to achieve a feasible flow situation.

Going further, it may be useful for practitioners to partition the index set ${\mathcal{R}}$ into several mutually disjoint constraint classes ${\mathcal{R}}_k$, $k \in {\mathcal{K}}$,

$${\mathcal{R}}= \bigcup _{k \in {\mathcal{K}}} {\mathcal{R}}_k \subseteq {\mathcal{E}}\cup {\mathcal{I}},$$

and allow a specific maximum constraint violation $\bar{s}_k$ for each constraint class under consideration. Letting $s_k = (s_{{\mathcal{E}}\cap {\mathcal{R}}_k}^+, s_{{\mathcal{E}}\cap {\mathcal{R}}_k}^-, s_{{\mathcal{I}}\cap {\mathcal{R}}_k}^+)$ and $s = (s_k)_{k \in {\mathcal{K}}}$, this leads to the modified $\ell _\infty$ feasibility problem

$$\begin{aligned} \begin{array}{lll} \text{Find} \quad (x, s) \quad \text{s.t.}\quad & c_{\mathcal{E}\setminus \mathcal{R}}(x) = 0, \quad c_{\mathcal{E}\cap \mathcal{R}}(x) + s_{\mathcal{E}\cap \mathcal{R}}^+ - s_{\mathcal{E}\cap \mathcal{R}}^- = 0, \\ &c_{\mathcal{I}\setminus \mathcal{R}}(x) \ge 0, \quad c_{\mathcal{I}\cap \mathcal{R}}(x) + s_{\mathcal{I}\cap \mathcal{R}}^+ \ge 0, \\ &s \ge 0, \quad \bar{s}_k - ||s_k||_\infty \ge 0 \quad \text{for } k \in {\mathcal{K}}. \end{array} \end{aligned}$$

(7)

This refined relaxation plays an important role in the presence of soft constraints (see Joormann et al. 2015 for a detailed discussion). For instance, the gas flow can excite vibrations of the pipes, which in turn may generate undesired noise in populated areas and, in serious cases, may even destroy the pipes. As there is no suitable quantitative model for these phenomena, a simple speed limit for the gas flow often serves as a crude practical measure to prevent vibrations. In this situation, the network operator may formulate the goal that the speed bound should be satisfied ($v\le v^+$), although he will accept small violations if necessary. So he can define the gas velocity constraints to be one of the sets ${\mathcal{R}}_k$ and can specify an additional quantity $\bar{s}_k$ that softens the former bound to $v\le v^+ + \bar{s}_k$. Soft constraints like these often play an important role in real-world problems and can be covered by penalty reformulations like (7).

4.2 Sequential NLP solving

As one might imagine, industrial users would always like to use the most accurate available model. Unfortunately but naturally, the most detailed and accurate model variants presented in Sect. 3 of Schmidt et al. (2014) are the most nonlinear and nonconvex ones. In addition, some of them are nonsmooth, i.e., the standard ${\mathcal{C}}^{2}$ assumption is violated unless one incorporates numerically challenging smoothing techniques. All these facts illustrate that it is an ambitious task to solve these models from scratch. Since it is impractical for industrial users of optimization methods to adapt the model or to tune the parameters of the solver for individual problem instances, there is a general need for numerically robust solution techniques.

The model hierarchy presented in Sect. 3 of Schmidt et al. (2014) suggests a natural way to achieve this goal. The large variety of NLP model variants allows us to set up sequences of NLPs that can be solved successively. The key aspect is to arrange each sequence in a way such that successive NLPs differ only slightly in terms of model size and in increase of nonlinearity and non-convexity, thus allowing for warm starts.

4.2.1 NLP sequences

We consider finite sequences $(\textsf{NLP}_k)$, $k \in {\mathcal{N}}$, that are chosen from the family of NLPs given in (1). Recall that ${\mathcal{A}}$ is the set of all model aspects where aspect $\alpha \in {\mathcal{A}}$ has concretizations $\gamma _\alpha \in {\mathcal{C}}_\alpha$. With this notation, we require that a sequence of NLPs has increasing accuracy order, defined by

$${\textsf{NLP}}_k \le {\textsf{NLP}}_{k+1}:\!\!\iff \gamma _\alpha ^k \le \gamma _\alpha ^{k+1} \quad {\text{for all}}\quad \alpha \in {\mathcal{A}}, \quad k, k + 1 \in {\mathcal{N}}.$$

Here, the notation “$\gamma _\alpha ^k \le \gamma _\alpha ^{k+1}$” means that the concretization $\gamma _\alpha ^k$ of model aspect $\alpha$ used in $\textsf{NLP}_k$ is no more accurate than the concretization $\gamma _\alpha ^{k+1}$ used in $\textsf{NLP}_{k+1}$. The notion of “more accurate” is not always defined in a strict mathematical sense (the Papay formula is considered more accurate than the AGA formula, for instance), but in any case we require that all variables of a model variant are also present in a “more accurate” variant. Thus, the numbers of NLP variables in a sequence satisfy $n_k \le n_{k+1}$.

4.2.2 Increasing robustness and convergence acceleration

When solving an NLP sequence we make use of three key ideas that improve the solution process by making it more robust and by accelerating convergence of the individual NLPs:

• 1. In most of the sequences used in practice, at least the first NLP is a penalty formulation of the target NLP that we actually want to solve; thus solving the first NLP is analogous to phase 1 of the simplex method. The benefit of this approach is twofold. First, solving a penalty model is much easier than solving the original model in many cases, according to our experience. Second, if a given instance is infeasible, the penalty formulation allows for a better analysis of possible reasons (cf. Sect. 4.1). In view of this, similar techniques have also been used in optimization for water networks; cf. Burgschweiger and Steinbach (2009).

• 2. Nonsmooth model aspects appear primarily in the model of gas parameter mixing, because flow directions in the network are initially unknown (cf. Eq. (9) of Schmidt et al. 2014). When solving an NLP of the sequence that incorporates mixing of gas parameters, we fix the flow directions on all network arcs based on the solution of the previous NLP, as follows. Let $q_a^{k} \in \left[ q_a^{-},q_a^{+}\right]$ denote the bounded flow variable of arc $a$ in $\textsf{NLP}_k$ and let $(q_a^{k})^*$ denote its optimal value in $\textsf{NLP}_k$. The flow direction for $\textsf{NLP}_{k+1}$ is then fixed by setting properly restricted bounds,

  $$\begin{aligned} q_a^{k+1} \in {\left\{ \begin{array}{lll} {\mathbb{R}}_{\ge 0} \cap \left[ q_a^{-},q_a^{+}\right] , &\quad (q_a^{k})^* > 0, \\ {\mathbb{R}}_{\le 0} \cap \left[ q_a^{-},q_a^{+}\right] , &\quad (q_a^{k})^* < 0, \\ \{0\}, &\quad (q_a^{k})^* = 0. \end{array}\right. } \end{aligned}$$

  (8)

  Similar ideas can be used for other nonsmooth aspects, like (de-)activating gas coolers (see Eq. (68) of Schmidt et al. 2014) and preheaters (see Eq. (103) of Schmidt et al. 2014). It would be reasonable to consider the optimal values of the dual variables of $\textsf{NLP}_k$ in order to relax the third case in (8), yielding restricted bounds ${\mathbb{R}}_{\ge 0} \cap \left[ q_a^{-},q_a^{+}\right]$ or ${\mathbb{R}}_{\le 0} \cap \left[ q_a^{-},q_a^{+}\right]$ instead of fixing the flow to zero. We have not done this in the current study because of the technical effort for accessing the dual variables from many NLP codes with different interfaces that we used, and because some solvers do not even provide dual variables.

• 3. We initialize the variables of $\textsf{NLP}_{k + 1}$, $x^{k+1} \in {\mathbb{R}}^{n_{k+1}}$, based on the optimal solution of $\textsf{NLP}_k$, $(x^k)^* \in {\mathbb{R}}^{n_k}$. This is done as follows. After some re-ordering we can write $x^{k+1} = (x^k, \tilde{x}^{k+1})$ with $\tilde{x}^{k+1} \in {\mathbb{R}}^{\tilde{n}}$, $\tilde{n} = n_{k+1} - n_k$. The key idea is to fix the $x^k$ part at $(x^k)^*$ and to determine $\tilde{x}^{k+1}$ by simple techniques so that $((x^k)^*, \tilde{x}^{k+1})$ satisfies the constraints of $\textsf{NLP}_{k+1}$ as well as possible. For instance, consider a constraint $c(x^k, \tilde{x}_i^{k+1}) = 0$ that can be solved explicitly for the “new” variable $\tilde{x}_i^{k+1}$ in terms of the “old” variables,

  $$0 = c(x^k, \tilde{x}_i^{k+1}) \iff \tilde{x}^{k+1}_i = \tilde{c}(x^k) {\mathrel{{=}{\mathop :}}}\,\tilde{x}_i^*. $$

  In this case we initialize $\tilde{x}^{k+1}_i$ with $\tilde{x}_i^*$. This technique is successively applied to new variables that depend on $x^k$ and already initialized components $\tilde{x}_i^{k+1}$. In other situations, we simply initialize the new variables with suitable constants.

4.2.3 Stopping criterion

In the finite sequences considered thus far, ${\textsf{NLP}}_{|\mathcal{N}|}$ is the most accurate model that we attempt to solve. It is also possible to extend the presented technique to infinite sequences of NLPs. For instance, one may wish to increase the physical accuracy of the model of gas dynamics in pipes by discretizing the ODEs on successively finer grids, which calls for a stopping criterion. Various criteria are possible, and a natural requirement is that they should be based on changes in variables that exist in every member $\textsf{NLP}_k$ of the sequence. Meaningful quantities of this type are pressures at nodes and mass flows on arcs of the network. With the vectors

$$p^{k}_{\mathbb{V}}{\mathrel{{\mathop :}{=}}}(p^{k}_i)_{i \in {\mathbb{V}}}, \quad q^{k}_{\mathbb{A}}{\mathrel {{\mathop :}{=}}}(q_a^{k})_{a\in {\mathbb{A}}}, $$

and tolerances $\varepsilon _p, \varepsilon _q> 0$, a suitable stopping criterion is given by

$$||p^{k}_{\mathbb{V}}- p^{k-1}_{\mathbb{V}}||_{\infty } < \varepsilon _p\quad {\text{and}}\quad ||q^{k}_{\mathbb{A}}- q^{k-1}_{\mathbb{A}}||_{\infty } < \varepsilon _q.$$

(9)

4.2.4 Specific NLP sequences

In this section we give three examples of sequences that are useful in gas network optimization. The first sequence mainly addresses the nonsmoothness of the gas quality parameter mixing model given in Sect. 3.3 of Schmidt et al. (2014). The second one deals with highly detailed isothermal modeling of gas dynamics in pipes and the last one can be used in order to incorporate heat dynamics in the problem. Computational results of the sequential NLP approach are presented in Sect. 5. For all sequences, we assume that all discrete decisions are given.

An NLP sequence for gas parameter tracking. The finite sequence for gas quality parameter tracking is informally defined as follows:

${\textsf{NLP}}_1$ :

Simple mass conservation model at nodes without gas parameter mixing (see Eq. (7) of Schmidt et al. 2014), isothermal quadratic approximation of gas dynamics in pipes (see Eq. (55) of Schmidt et al. 2014), full isothermal compressor group model with machine models as described in Sects. 3.4.10 and 3.4.15 of Schmidt et al. (2014), isothermal control valve model (see Eq. (99) of Schmidt et al. 2014), standard resistor, short cut, and valve models, arbitrary penalty formulation (see Sect. 4.1). Globally constant gas density under normal conditions.

$\textsf{NLP}_2$ :

Like $\textsf{NLP}_1$ but with an extended node model incorporating mixing of molar masses (see Eq. (9) of Schmidt et al. 2014).

$\textsf{NLP}_3$ :

Like $\textsf{NLP}_2$ but with an extended node model incorporating mixing of calorific values.

$\textsf{NLP}_4$ :

Like $\textsf{NLP}_3$ but with an extended node model incorporating mixing of pseudocritical pressures and temperatures.

$\textsf{NLP}_5$ :

Like $\textsf{NLP}_4$ but with gas density under normal conditions depending on the quality parameters.

To obtain smooth formulations of the mixing models it is necessary to fix the flow directions on all network arcs, as already discussed in the previous section.

An NLP sequence for highly detailed isothermal gas dynamics modeling. In this sequence the main focus is on highly detailed modeling of isothermal gas dynamics in pipes. The sequence is given as follows:

$\textsf{NLP}_1$ :

Identical to ${\textsf{NLP}}_1$ in the sequence above.

${\textsf{NLP}}_2$ :

Like ${\textsf{NLP}}_1$ but with the momentum equation discretized on initial grids $\Delta _a^{0}$ for all pipes $a\in {\mathbb{A}}_{\text{ pi }}$; cf. Sect. 3.4.7 of Schmidt et al. (2014).

$\textsf{NLP}_k, k > 2$ :

Like $\textsf{NLP}_{k-1}$ but with the momentum equation discretized on refined grids $\Delta _a^{k-2} \supset \Delta _a^{k-3}$ for all pipes $a\in {\mathbb{A}}_{\text{ pi }}$.

The canonical stopping criterion for this infinite sequence is (9). To reduce the numerical effort during iterative grid refinement ($k > 2$), one might also employ an adaptive discretization scheme. Here adaptive means that the discretization on pipe $a= ij \in {\mathbb{A}}_{\text{ pi }}$ is only refined in $\textsf{NLP}_k$ if

$$ \left\| \left(\begin{array}{*{20}c}p_{i}\\ p_{j}\end{array}\right)^k - \left(\begin{array}{*{20}c}p_{i}\\ p_{j}\end{array} \right)^{k-1}\right\|_{\infty } > \varepsilon _{p} \quad {\text{or}}\quad |q_{a}^{k} - q_{a}^{k - 1} | > \varepsilon _{q} . $$

(10)

Of course, it is also possible to use pipe-specific tolerances, i.e., to replace $\varepsilon _p$ and $\varepsilon _q$ in (10) by $\varepsilon _{p,a}$ and $\varepsilon _{q,a}$.

An NLP sequence for temperature dynamics modeling. Here we incorporate all temperature dynamics constraints in the model. The sequence is defined as follows:

$\textsf{NLP}_1$ :

Identical to $\textsf{NLP}_1$ in the sequences above.

$\textsf{NLP}_2$ :

Like $\textsf{NLP}_1$ but with an extended node model incorporating the mixing of the coefficients A, B, C of the molar heat capacity of ideal gas.

$\textsf{NLP}_3$ :

Like $\textsf{NLP}_{2}$ but with non-isothermal models of all elements of the network (including heat capacity models).

Notice that none of the three sequences above has a cost minimization objective: all of them solve $\ell _1$ penalty-based relaxation models in which we relax the flow balance constraint of all entry and exit nodes. However, all sequences can readily be extended or modified to incorporate a cost minimization objective.

5 Computational results

In order to show the practical relevance of our NLP models and solution techniques on large-scale real-world networks, we now present an extensive computational study for the problem of validation of nominations (NoVa). A complete NoVa model contains discrete aspects of controllable elements as well as detailed models of gas dynamics and technical devices of the network. This combination leads to hard mixed-integer nonlinear optimization (or feasibility) models that are intractable for state-of-the-art general-purpose MINLP solvers on real-world network sizes. In the research project ForNe we have developed custom solution approaches for NoVa. The main idea is to split up the solution process into two stages. The first stage solves a model containing all discrete aspects and simplified variants of the underlying gas physics and technical network elements. Afterwards, the resulting discrete controls are fixed throughout the network in order to obtain a purely continuous and highly detailed NLP model that “validates” the fixed decisions. In this stage, penalty formulations as described in Sect. 4.1 are used to prove ($\varepsilon$-)feasibility of the underlying MINLP, or to obtain information on possible reasons of infeasibility otherwise. Here we use the sequential NLP (SNLP) approach for solving NLP models with a high level of physical and technical accuracy.

This section deals with that second stage of the NoVa solution approach and presents detailed numerical results for it. We will indeed see that the NoVa problem is solvable even with high detail and accuracy, and that the SNLP approach is a key tool for increasing robustness. Additional information concerning the outcomes of the ForNe project and extensive computational studies of the overall approach are given in Fügenschuh et al. (2014), Martin et al. (2011), Pfetsch et al. (2015) and in the book Koch et al. (2015).

The remainder of this section is organized as follows. In Sect. 5.1 we present the computational setup including the description of used modeling languages, solvers, and other software and hardware issues. Sect. 5.2 then describes both the real-world network and the publicly available academic network that we used in our computational experiments. The following Sects. 5.3 and 5.4 present and discuss the respective numerical results on the real-world and the academic test set. Finally, Sect. 5.5 concludes with a discussion of the results.

For brevity, we only present the numerical results for the NLP sequences “parameter tracking” and “temperature dynamics” here. The SNLP approach has also been run successfully on the “ODE Discretization” sequence for highly detailed isothermal gas dynamics modeling (Sect. 4.2.4), with results that are qualitatively comparable to the results of both other sequences.

5.1 Computational setup

All models and algorithms are implemented using the framework LaMaTTO++ (2015) for modeling and solving mixed-integer nonlinear optimization problems on networks. The computational study of the NLP validation stage presented in this paper is run on a desktop PC with a six-core AMD Opteron Processor 2435 with 2600 MHz and 64 GB RAM. The operating system is Debian 7.5 and the C++ code LaMaTTO++ is compiled using GCC 4.7.2. All models are implemented in GAMS 24.1.3³, cf. Rosenthal (2008).

The computational results presented below are obtained using the NLP solver CONOPT 3.15L, because it performs best on the given problem class and on the networks considered in the ForNe project. The solvers we have tested include Ipopt by Wächter and Biegler (2006), CONOPT and CONOPT4 (1996), KNITRO (2006), SNOPT (2002), and MINOS (1993). Note that the comparison of these solvers is not a topic of this paper.

5.2 Test instances

We evaluate and test our models on two different test sets based on country-sized transport networks. The first test set, called HN, contains 30 difficult expert instances that arise at OGE. The corresponding network is the northern high-calorific gas network of OGE. The second test set, called GasLib-582, is publicly available (cf. Humpola et al. 2015) and is approximately of the same size as the HN network. These two test sets appear under the same names in other publications as well. Table 10 gives the numbers of elements of the two networks. In order to limit the computational effort to a reasonable amount, we randomly chose 500 out of the 4227 GasLib-582 nominations that are freely available at http://gaslib.zib.de. The first stage solvers of our NoVa approach obtained feasible solutions for 394 of the 500 random nominations. We perform the NLP validation on these 394 instances; see Table 13 in Appendix 3 for the complete list.

The results on the HN test set will demonstrate the practicability of our NLP models on hard instances that arise in the day-to-day work at German gas network planning departments whereas the GasLib-582 test set provides publicly available instances on which other researchers can test and compare their algorithms.

Table 10 Elements of the HN network and the GasLib-582 network

Table 11 Exit states of direct approach and of SNLP sequence (HN test set, both sequence types)

5.3 The HN test set

Here we present the computational results for the SNLP sequences “parameter tracking” and “temperature dynamics” (see Sect. 4.2) applied to the expert instances on the HN test set, and compare them with the direct approach, i.e., the attempt to solve the final NLP of each sequence (the target NLP) from scratch. SNLP results are determined by the target NLP (exit state, accuracy) or by the entire sequence (iteration count, computing time).

5.3.1 Parameter tracking problem

Recall that we expect that solving a sequence of NLPs while successively adding new gas parameters to the model leads to better convergence than the direct approach. This is indeed the case, as can be seen in Table 11: the exit states show that the direct approach solves only one third of all instances to local optimality whereas the SNLP approach solves every instance.

Since the NoVa problem is a feasibility problem, our objective is to minimize the constraint violation (using the relaxed NLP in Sect. 4.1). Figure 7 presents empirical distribution functions of the respective objective values for the SNLP sequence and the direct approach, giving for every constraint violation the percentage of instances not exceeding that value. The plot clearly shows that the direct approach is much less successful: it yields substantially larger constraint violations and in fact many “false infeasibles”. Moreover, only for 2 out of the 30 instances, it computes a zero constraint violation where the SNLP approach fails to do so.

Fig. 7

Constraint violations of direct approach and of SNLP sequence (HN test set, “parameter tracking”)

Fig. 8

Iteration counts and computing times (s) of direct approach and of SNLP sequence (HN test set, “parameter tracking”)

Figure 8 shows the empirical distribution functions for total iteration counts and computing times (i.e., accumulated over all NLPs in case of the SNLP sequence). Despite the fact that the SNLP approach solves five NLPs rather than just one, both approaches require roughly the same effort. While the SNLP approach needs a slightly larger number of iterations than the direct approach, it does not possess as extreme outliers as the latter. In summary, it can be clearly stated that the SNLP approach is much more effective than the direct approach in producing feasible solutions while the computational cost is comparable.

The above observations are confirmed by Fig. 9, which displays the distributions of iteration counts and computing times of individual NLPs in the sequence over the HN test set. Except for a few outliers, all iteration counts are below 100, which is approximately 1/5 of the average iteration count of the direct approach. Outliers above 100 are only present in the first, third, and fifth NLP of the sequence. Possible explanations are as follows. The first model does not contain any mixing aspects, and the outliers thus may arise from “correcting” the continuous part of the solution given by the first stage of the NoVa solution approach. The third NLP adds the calorific value as a new gas quality parameter to the model. Since the HN test set includes heat power bounds at the entries and exits (in addition to the mass flow bounds), activating the tracking of the calorific value plays a crucial role for the feasibility of the problem. Finally, the fifth and last NLP adds the gas density under normal conditions as a variable to the model. Since this quantity occurs in many constraints—especially in all flow conversion constraints—the worst-case difficulty of the model increases, which might be the reason for outliers in SNLP iteration 5. Turning to the computing times, we see that the majority are below 4 s, and we observe a similar qualitative behavior as for the iteration counts.

Fig. 9

Iteration counts (left) and computing times (s, right) of NLPs of the SNLP sequence (HN test set, “parameter tracking”)

Let us now consider some model statistics of the NLPs of the SNLP sequence. In all NLPs the number of variables is only slightly larger than the number of constraints: after fixing the discrete decisions only a few degrees of freedom remain, resulting from continuous control variables of active network elements. Both the numbers of variables and constraints strictly increase within the SNLP sequence, lying between 5000 and 15,000. The number of non-constant entries and the total number of entries in the constraints Jacobian also strictly increase, lying between 10,000 and 20,000 and between 20,000 and 40,000, respectively. The fraction of non-zero entries in the Jacobian is approximately 0.025 %.

5.3.2 Temperature dynamics problem

The results for “temperature dynamics” are similar to the results for “parameter tracking”. Again, the direct approach solves only an unsatisfactory share of instances to local optimality (26.67 %) whereas the SNLP approach solves all instances (see Table 11). Moreover, the SNLP approach reduces the constraint violation much stronger than the direct approach, as Fig. 10 clearly shows. Only two instances are solved with a smaller constraint violation by the direct approach than by the SNLP approach. Furthermore, the SNLP approach is substantially more efficient. Figure 11 compares iteration counts and computing times using empirical distribution functions. On average, the SNLP approach is faster and does not possess as strong outliers as the direct approach does.

Fig. 10

Constraint violations of direct approach and of SNLP sequence (HN test set, “temperature dynamics”)

Iteration counts of the individual NLPs of the SNLP sequence are displayed in Fig. 12. In particular, the first NLP (isothermal model) appears to be the problem with the hardest instances of the sequence, as in “parameter tracking”: the number of outliers of NLP 1 clearly exceeds the numbers of outliers of NLPs 2 and 3.

Fig. 11

Iteration counts and computing times (s) of direct approach and of SNLP sequence (HN test set, “temperature dynamics”)

Fig. 12

Iteration counts (left) and computing times (s, right) of NLPs of the SNLP sequence (HN test set, “temperature dynamics”)

5.4 The GasLib-582 test set: parameter tracking and temperature dynamics

Next we describe the results for the SNLP sequences “parameter tracking” and “temperature dynamics” on the random subset of all GasLib-582 instances given in Table 13 of Appendix 3.

The characteristics of the computational results for “parameter tracking” and “temperature dynamics” differ significantly from the corresponding results on the HN test set. While it is very hard to compute feasible solutions with the direct approach on the latter (cf. Sect. 5.3), this is not the case for the GasLib-582 test set. Table 12 shows the associated exit states for all sequences. The percentage of instances solved to local optimality by the direct approach is 96.4 % for “parameter tracking” and 95.7 % for “temperature dynamics”. By way of comparison, the SNLP approach solves 98.2 % and 98.5 % to local optimality, respectively. This shows that the SNLP approach is again more robust, but this time only by a small margin. In contrast to the HN test set there are now also a few instances (7 for “parameter tracking” and 6 for “temperature dynamics”) on which the SNLP approach fails completely because one NLP of the corresponding sequence cannot be solved at all (see the row “broken sequence” in Table 12). All other results of these two problems look very similar to the corresponding results on the HN test set. We only discuss the results for “parameter tracking”—all figures for “temperature dynamics” are given in Appendix 1. As Figs. 13 and 14 show, both approaches behave quite similar in terms of constraint violations, iteration counts, and computing times. The advantage of the SNLP approach is that it does not possess extreme outliers. However, these outliers of the direct approach are not as extreme as for the HN test set. The qualitative behavior of individual iteration counts and numbers of variables, constraints, etc., of the SNLP approach is similar to the behavior on the HN test set and therefore not further discussed here.

Table 12 Exit states of direct approach and of SNLP sequence (GasLib-582 test set, both sequence types)

Fig. 13

Constraint violations of direct approach and of SNLP sequence (GasLib-582 test set, “param. tracking”)

Fig. 14

Iteration counts and computing times of direct approach and SNLP sequence (GasLib-582 test set, “parameter tracking”)

5.5 Discussion

In this section we have presented an extensive computational study of our NLP models on two different test sets involving the solution of about 4500 NLPs. The NLP models under consideration are hard to solve due to their high degree of nonlinearity and non-convexity and because they possess only a small number of free variables.

It turns out that the expert instances of the HN test set are much harder than the instances of the GasLib-582 test set. The problems of both tested sequences (“parameter tracking” and “temperature dynamics”) are hardly solvable from scratch, whereas the SNLP approach proves robust and entirely practical: it solves all instances of the HN test set successfully, while iteration counts and solution times are comparable to the direct approach when the latter is successful.

6 Summary

In part 1 of this paper we describe detailed models for stationary optimization in gas transport networks. This paper provides an analysis of their structural interplay and possible combinations of these models and shows that their level of detail and accuracy is comparable with today’s commercial gas network simulation software. The former aspect is realized by the analysis of so-called model aspect graphs whereas the latter aspect is illustrated by a comparison with a state-of-the-art simulation software on single network elements. Finally, we present tailored optimization techniques and show that—using these techniques—it is possible to solve the resulting NLPs on real-world networks. In particular, by using NLP sequences we are able to include model aspects that are usually omitted or substantially simplified to obtain tractable problems or to reduce the solution effort: the mixing of different gas species and the heat dynamics. This demonstrates that optimization models and solvers can provide a valuable tool for gas network planners that adds new capabilities to existing simulation tools.

Appendices

Appendix 1: Computational results for temperature dynamics on the GasLib-582 test set

See Figs. 15 and 16.

Fig. 15

Constraint violations of direct approach and of SNLP sequence

Fig. 16

Iteration counts and computing times (s) of direct approach and of SNLP sequence

Appendix 2: Model aspect graphs

See Figs. 17, 18, 19, 20, and 21.

Fig. 17

Model aspect graph of nodes (global aspect: mixing of gas types). The nodes in the shaded block exist only in non-isothermal models

Fig. 18

Model aspect graph of nodes (global aspect: uniform gas composition). The nodes in the shaded block exist only in non-isothermal models

Fig. 19

Model aspect graph of control valves. The nodes in shaded blocks exist only in non-isothermal models

Fig. 20

Model aspect graph of pipes (isothermal). (*) If the exact solutions of the momentum equation are chosen as a concretization, not every choice of the compressibility factor is possible, cf.  Schmidt et al. (2014). In addition, not every combination of pipe slope and compressibility factor is possible. (o) To achieve a smooth NLP model, flow bound strengthening has to be applied. (+) Only possible for horizontal pipes

Fig. 21

Model aspect graph of pipes (non-isothermal)

Appendix 3: GasLib-582 instances

See Table 13.

Table 13 ID’s of GasLib-582 instances used in the computational study of Sect. 5.4. The set of instances can also be downloaded at www.ifam.uni-hannover.de/mcs