Abstract
When considering cost-optimal operation of gas transport networks, compressor stations play the most important role. Proper modeling of these stations leads to nonconvex mixed-integer nonlinear optimization problems. In this article, we give an isothermal and stationary description of compressor stations, state MINLP and GDP models for operating a single station, and discuss several continuous reformulations of the problem. The applicability and relevance of different model formulations, especially of those without discrete variables, is demonstrated by a computational study on both academic examples and real-world instances. In addition, we provide preliminary computational results for an entire network.
Similar content being viewed by others
Avoid common mistakes on your manuscript.
1 Introduction
Natural gas is one of the most important energy sources. In 2013, it accounted for 25 % of the fossil energy used in Europe (Eurostat 2013). It is used in industrial processes, for heating, and, more recently, for natural gas vehicles. Especially in Germany, its low price leads to its role as a “bridging energy” during the transition to a future energy mix based primarily on regenerative energy. In Europe, natural gas is transported through pipeline networks with a total length of 100,000 km. Gas transport in pipeline networks is pressure-driven, i.e., the gas flows from higher to lower pressure. Thus, pipeline-based gas transport requires compressor stations. The power required to compress the gas is delivered by drives that use either electrical power or gas from the network itself. The energy consumption of compressors is responsible for a large fraction of the variable operating costs of a gas network.
In this article we focus on the stationary optimization of a single compressor station. More specifically, we consider fixed boundary conditions, i.e., fixed inflow and outflow pressures together with a fixed throughput, and ask the following questions:
-
Can the station be operated in a way that satisfies the given boundary conditions? In other words: are those boundary conditions feasible?
-
If the boundary conditions are feasible: What is a minimum cost operation that satisfies the boundary condition?
Transport of natural gas has been a rich source of mathematical optimization problems for roughly half a century. The first publications on optimization in gas networks address tree-like or gun-barrel topologies with dynamic programming as a solution technique (Wong and Larson 1968a, b); see Carter (1998) for a later survey. In the following, we give a brief overview on mathematical optimization in this field. More extensive reviews can be found in Koch et al. (2015).
One main branch of research investigates the problems of minimum cost operation and feasibility testing for the stationary as well as the transient case. These problems require models of complete gas networks comprising various types of elements like pipes, compressors, (control) valves, etc. The combination of nonlinear gas physics with the switching of controllable network elements typically leads to mixed-integer nonlinear optimization models (MINLPs); see, e.g., Cobos-Zaleta et al. (2002) and Domschke et al. (2011). One standard approach for tackling these MINLPs is the application of (piecewise) linearizations of the nonlinearities in order to reduce the problems to mixed-integer linear models (MILPs) (Geißler 2011; Geißler et al. 2013; Martin et al. 2006, 2007; Martin and Möller 2005). Other investigations focus on the nonlinear aspects under fixed discrete controls (Ehrhardt and Steinbach 2004, 2005; Schmidt et al. 2015a, c; Steinbach 2007), or attempt to approximate discrete aspects by continuous reformulations (Schmidt 2013; Schmidt et al. 2013, 2015b). For more references and reviews in the areas of cost minimization and feasibility testing we refer to Koch et al. (2015) and, especially, the chapter Schewe et al. (2015) therein.
The second major research branch that we want to highlight considers selected types of network elements and studies them in more detail. For pipes, theoretical studies include the controllability and stabilization of the governing system of partial differential equations, the Euler equations (cf. Banda and Herty 2008; Banda et al. 2006; Brouwer et al. 2011; Gugat et al. 2015). The best-investigated problem for compressor stations is the one considered in this paper, which is of nonconvex MINLP type: minimum cost operation under given boundary conditions (Carter 1996; Carter et al. 1994; Jeníček and Králik 1993; Osiadacz 1980; Wright et al. 1998). See also Králik (1993) for a simulation based model of compressor stations and Odom and Muster (2009) for a recent survey on modeling centrifugal gas compressors. As already mentioned, the compressor stations are the dominant variable cost factor in gas network operation.
In this article we study discrete-continuous models for the problem of minimum cost compressor station operation. We give an almost complete isothermal description of all relevant devices and their interplay. This description is comparable in accuracy with isothermal simulation models. However, we neglect some minor model aspects that would only complicate the presentation without influencing the solutions significantly. We explicitly mention these simplifications later in the description of the considered problem. The specific structure of the resulting MINLP allows for a large variety of continuous reformulations that will be discussed in detail and that are applied to the problem under consideration. The approach of continuous reformulation is in line with recent publications that develop techniques based on mathematical programs with equilibrium constraints (MPECs) for reformulating other discrete aspects of network optimization models (Pfetsch et al. 2015; Schmidt 2013; Schmidt et al. 2013, 2015b). Thus, by combining the MPEC techniques from the cited publications with the reformulation schemes discussed in this paper, it is possible to state purely continuous NLP type models of the genuinely discrete-continuous problems of minimum cost operation or feasibility testing. The outcome of this achievement is twofold. First, it allows us to state highly detailed models of gas networks. This in particular is not viable with approaches based on linearizations since the resulting MILP models tend to be very hard for state-of-the-art MILP solvers. Second, it allows us to solve the resulting models with local NLP solvers, which are typically faster than global MI(N)LP solvers. Obviously, this comes at the price of finding only locally optimal solutions. For further applications of continuous reformulations of discrete-continuous optimization problems, especially in the field of process engineering, see Baumrucker et al. (2008), Kraemer et al. (2007), Kraemer and Marquardt (2010), and Stein et al. (2004). We remark that, despite the fact that continuous reformulations are being used in practice, an extensive numerical study like ours is yet missing in the literature.
The paper is organized as follows. The problem of optimizing a gas compressor station under steady-state boundary conditions is presented in Sect. 2. Afterwards, Sect. 3 introduces a mixed-integer nonlinear formulation of the problem and briefly discusses an equivalent general disjunctive programming formulation. Then, in Sect. 4, the concept of pseudo NCP (nonlinear complementarity problem) functions is introduced and a collection of continuous reformulation techniques is discussed that can be applied to the MINLP model of Sect. 3. These reformulations are applied to artificial and real-world compressor stations in Sect. 5 and the solutions are compared. In addition, this section also provides preliminary results for an entire large-scale network that is fully reformulated using continuous variables and smooth constraints. Finally, Sect. 6 gives some remarks on further work and open questions.
2 Problem description
A compressor station hosts a fixed number of compressor machines called units. It can operate in finitely many discrete states that arise from the three operation modes (closed, bypass mode, and active) and a certain number of configurations in the active mode. Every configuration consists of a serial combination of parallel arrangements of compressor units, see Fig. 2. Every compressor unit has an associated drive that provides the power for compressing the gas. For ease of exposition we assume that every drive powers just a single compressor unit. We also neglect the frictional pressure loss caused by station piping, measurement devices, etc., which is usually modeled by fictitious elements called resistors.
In this section we present the required models of all types of compressor machines and drives and then describe their interplay. Full details can be found in Schmidt et al. (2015c) where models of all network elements have been developed. For later reference, the models are presented in constraint form, with constraint functions being denoted by \(c\) and super-indexed with an abbreviated name indicating the semantics of the constraint.
2.1 Physical quantities
The dynamics of natural gas is modeled in terms of the mass flow \(q\), pressure \(p\), temperature \(T\), and density \(\rho \), where \(p, T, \rho \) are coupled by an equation of state. In specific, we use the thermodynamical standard equation,
Here the compressibility factor \(z\) models the deviation between real and ideal gas, for which we use an empirical formula of the American Gas Association (AGA),
We will later formulate certain constraints using \(\rho (p, T, z)\) and \(z(p, T)\) with fixed \(T\).
Finally we need the volumetric flow \(Q\), given by the constraint
See Table 1 (or Schmidt et al. 2015c) for explanations of the physical quantities and constants.
2.2 Boundary conditions
We are interested in feasibility testing and in computing cost optimal controls of a compressor station for given boundary values. In accordance with our general network models (Schmidt et al. 2015c), a compressor station is seen as an arc \(a= (u, v)\) of a directed network graph \(G =(\mathbb {V}, \mathbb {A})\). The boundary conditions at which the compressor station \(a\) has to operate consist of a mass flow range,
and of inlet and outlet pressure ranges,
Each of the values \(q_a, p_u, p_v\) can be fixed by setting its bounds to identical values.
2.3 Compressor machines
We distinguish turbo compressors and piston compressors and start with the common parts of their models. For an overview of relevant compressor quantities see Table 2.
The compression of a gas stream from \(p_\text {in}\) to \(p_\text {out}\) results in a specific change in adiabatic enthalpy, \(H_{\text {ad}}\):
Here \(z_\text {in}= z(p_\text {in}, T_\text {in})\), and we assume that the isentropic exponent \(\kappa \) is constant. The power \(P\) required for compressing the mass flow \(q\) is given by
Its upper limit is the maximal power \(P^{+}\) that the associated drive can deliver:
2.4 Turbo compressors
Turbo compressors are modeled by characteristic diagrams in \((Q, H_{\text {ad}})\)-space, see Fig. 1 (left). The curves are defined using biquadratic and quadratic polynomials \(F_2(x, y; A)\) and \(F_1(z; b)\) whose coefficients A and b are obtained from least-squares fits for given measurements of the compressor:
and
The isolines of speed \(n\) (solid) and adiabatic efficiency \(\eta _{\text {ad}}\) (dashed) are given by
The compressor’s operating range (gray area) is bounded by the isolines of minimal and maximal speeds \(n^\pm \), by the surgeline (left), and by the chokeline (right),
2.5 Piston compressors
Piston compressors are modeled by characteristic diagrams in \((Q, M)\)-space, see Fig. 1 (right). The volumetric flow \(Q\) satisfies
and the shaft torque \(M\) (with constant efficiency \(\eta _{\text {ad}}\)) is given by
The speed bounds \(n\in [n^{-},n^{+}]\) induce left and right bounds of the operating range, \(Q\in [V_{\text{ op }}n^{-}, V_{\text{ op }}n^{+}]\). The upper limit can be given in one of three forms depending on the specific compressor: either by a maximum compression ratio \(\varepsilon ^{+}\),
by a maximum pressure increase \(\varDelta p^{+}\),
or by a maximum shaft torque \(M^{+}\),
2.6 Drives
The four most frequently used drive types are gas turbines, gas driven motors, electric motors, and steam turbines. Here we focus on the common model aspects and consider a generic “catchall” drive model that incorporates the two main aspects: the maximal power \(P^{+}\) that the drive can deliver (cf. (1)),
and its specific energy consumption \(b\),
Here, \(T_{\text {amb}}\) denotes the ambient temperature at the compressor station and \(A_{P^{+}}\) as well as \(a_{b}\) are the coefficients of the fitted (bi)quadratic polynomials. For specific drive types, (2) or (3) may simplify or vanish completely. The fuel consumption of a gas-powered drive is the mass flow \(q^{\text{ fc }}\),
The fuel consumption of an electric drive is zero, \(0 = c_{}^{\text {fuel-cons}}(q^{\text{ fc }}, b) = q^{\text{ fc }}\).
2.7 Configurations
Recall that a compressor station can be closed, in bypass mode, or active. We denote the set of configurations of an active compressor station by \(\mathscr {C}= \{1, \dots , n_\mathscr {C}\}\), the set of serial stages of configuration \(i\in \mathscr {C}\) by \(\mathscr {S}_i= \{1, \dots , n_{\mathscr {S}_i}\}\), and the set of parallel units of stage \(j\in \mathscr {S}_i\) by \(\mathscr {P}_{ij} = \{1, \dots , n_{\mathscr {P}_{ij}}\}\). For instance, in Fig. 2 we have \(\mathscr {C}= \{1, \dots , 4\}\) and
In what follows, we refer to individual compressor units by the index triple \(ijk\).
Given a triple \((q_a, p_u, p_v)\) of boundary values, the selected configuration \(i\) must satisfy the following: the flow \(q_j\) of every serial stage \(j\in \mathscr {S}_i\) equals \(q_a\) and is distributed over the \(n_{\mathscr {P}_{ij}}\) parallel units:
Moreover, all parallel units in stage \(j\in \mathscr {S}_i\) have to increase the gas pressure to a common outflow value \(p_{i, j+1}\), which becomes the inflow pressure of stage \(j+1\). The first and last stages must satisfy \(p_{i1} = p_u\) and \(p_{i, n_{\mathscr {S}_i} + 1} = p_v\), respectively.
2.8 Objective function
There are various reasonable objective functions in our context, which can mainly be categorized as feasibility or optimization goals. If one merely wishes to know whether given boundary conditions are feasible, it suffices to use a zero objective, \(f\equiv 0\). If the boundary conditions are infeasible, it may be useful to add slack variables to a certain set of constraints and minimize the total infeasibility, measured by a suitable norm of the vector of slack variables. The reader interested in problem-specific slack variable formulations for gas network planning is referred to Schmidt et al. (2015a).
If one is convinced of having feasible boundary conditions, it is straightforward to minimize operating costs, power, or fuel consumption. Specific objective functions will be formulated after stating the optimization models in the following section.
3 Mixed-integer and general disjunctive programming models
One generic way to model the problem described in the previous section is presented in Sect. 3.1: a mixed-integer nonlinear program (MINLP) that incorporates binary variables for the discrete states of the compressor station. An equivalent general disjunctive programming (GDP) formulation of the problem is given in Sect. 3.2. Continuous reformulations of the MINLP and GDP models are discussed later in Sect. 4.
One further possibility of tackling the problem is to enumerate all states of the compressor station and solve all the resulting (continuous) problems by a local or global method. However, this is only suitable when single compressor stations are considered, whereas continuous reformulations can also be used for models of the entire transport network; cf. Sect. 5.5. Another way is to apply suitable heuristics, see, e.g., Schmidt et al. (2015b).
We denote individual continuous variables by \(x\) and discrete ones by \(s\). Variable vectors are written with bold letters, like \(\mathbf {x}\) or \(\mathbf {s}\). Sub-indices refer to corresponding elements of the compressor station or to sets of elements. In the constraint notation of Sect. 2, we now also use sub-indices with the same meaning as for variables. Additional sub-indices \(\mathscr {E}\) or \(\mathscr {I}\) distinguish equality and inequality constraints.
3.1 MINLP formulation
With \(\mathbf {x}\in \mathbb {R}^n\) and \(\mathbf {s}\in \{0,1\}^m\), the optimization problem under consideration takes the general MINLP form
The boundary conditions correspond to the variable sub-vector \(\mathbf {x}_\mathscr {B}= (q_a, p_u, p_v)\).
For a suitable formulation of the discrete decisions and their implications on other parts of the model, we review the concept of indicator constraints.
3.1.1 Indicator constraints
Indicator constraints use a binary indicator variable to control whether a certain constraint is enabled or disabled. If \(c(\mathbf {x})\) is any equality or inequality constraint with indicator variable \(s\), we denote the associated indicator constraints generically by
The formulation (4) is chosen in such a way that the original constraint \(c(\mathbf {x}) = 0\) or \(c(\mathbf {x}) \ge 0\) must hold if \(s= 1\) whereas it becomes irrelevant if \(s= 0\). In this article we use two specific types: big-M and bilinear indicator constraints. The big-M indicator constraints of the equality constraint \(c(\mathbf {x}) = 0\) take the form
For the inequality constraint \(c(\mathbf {x}) \ge 0\) we obtain the single inequality
Bilinear indicator constraints for equality and inequality constraints, respectively, are given by
The big-\(M\) formulation offers the advantage that convex constraints yield convex indicator constraints. However, the big-M constants must be chosen sufficiently large to ensure that the constraint is properly enabled or disabled: \(M_c^- \ge |\min _\mathbf {x}c(\mathbf {x})|\) and \(M_c^+ \ge |\max _\mathbf {x}c(\mathbf {x})|\) in (5), and \(M_c^- \ge |\min _\mathbf {x}c(\mathbf {x})|\) in (6). Numerical difficulties are to be expected if \(M_c^\pm \) are very large. The bilinear formulation avoids this but has the disadvantage that even convex constraints yield nonconvex indicator constraints. We later review these issues when discussing the numerical results of different problem formulations in Sect. 5.
Finally we need two more notions: an indicator expression y is a term whose value is \(y \ge 1\) if the associated state is enabled and zero otherwise, like \(s\) in (7). Conversely, a negation expression is a term whose value is \(y \ge 1\) if the associated state is disabled and zero otherwise, like \(1 - s\) in (5), (6).
3.1.2 Discrete states
To represent the set of states of a compressor station, we introduce the binary variable vector
with the following interpretation:
-
the station is active in configuration \(i\in \mathscr {C}\) if and only if \(s_i= 1\);
-
the station is in bypass mode if and only if \(s_\text {bp}= 1\);
-
the station is closed if and only if \(s_\text {cl}= 1\).
Since precisely one state must be selected, we add the special-ordered-set-1 (SOS-1) constraint
In bypass mode, the inflow and outflow pressures have to be identical,
yielding indicator constraints
Note that only equality constraints are required if bilinear indicator constraints (7) are used, whereas only inequality constraints are needed in the case of big-\(M\) constraints; cf. (5). That is, in the former case the vector \(c_{\mathscr {I}}^{\text {bypass-ind}}\) is empty and in the latter case the vector \(c_{\mathscr {E}}^{\text {bypass-ind}}\) is empty. Likewise, if the compressor station is closed, we have
yielding
3.1.3 Configurations
Now we turn to the details of individual configurations. The continuous variable vector of configuration \(i\in \mathscr {C}\) reads
Here \(q^{\text{ fc }}_{i}\) is the total fuel consumption, \(p_{ij}\) and \(p_{i,n_{\mathscr {S}_i}+1}\) denote the inflow pressure of stage \(j\) and the outflow pressure of the last stage, respectively, and \(z_{ij}\), \(\rho _{ij}\) represent the inflow compressibility factor and inflow gas density of stage \(j\). Finally, \(\mathbf {x}_{ijk}\) is the variable vector of compressor unit \(ijk\) and its associated drive, see Sect. 3.1.4.
The inflow quantities \(z_{ij}\) and \(\rho _{ij}\) are coupled to the physical inflow conditions by the constraints
The total fuel consumption \(q^{\text{ fc }}_{i}\) is the sum over all compressor units:
This constraint must be enabled if and only if configuration \(i\) is active:
Otherwise configuration \(i\) is inactive,
where \((q^{\text{ fc }}_{i})^+\) is a suitable upper bound of \(q^{\text{ fc }}_{i}\). Next, the inflow and outflow pressures of the active configuration must equal the inflow and outflow pressures of the station:
where
The flow distribution over the parallel units of every stage \(j\) finally completes the configuration model:
In summary, the equality constraints of configuration \(i\) read
and the inequality constraints are given by
3.1.4 Compressor units and drives
Lastly, we formulate MINLP models of turbo and piston compressors within a configuration. The continuous variable vector of a turbo compressor \(\nu = ijk\) with its associated drive reads
and for a piston compressor \(\nu \) with associated drive it reads
The equality constraints of a turbo compressor are then given by
and its inequality constraints read
Here we introduce indicator constraints to disable the associated limits of physical and technical quantities of inactive configurations: otherwise irrelevant infeasible values of those inactive configurations would render the entire compressor model infeasible.
The equality constraints of a piston compressor are given by
and the inequality constraints read
Here the indicator constraints are introduced for the same reason as for turbo compressors.
3.1.5 Model summary
As already mentioned, we may choose the objective \(f\equiv 0\) if we are only interested in feasibility testing. If we aim at minimum cost operation, a suitable objective is
where \(\mathscr {U}^\text {fuel}\) and \(\mathscr {U}^\text {el}\) are the sets of fuel gas and electricity driven compressor units, respectively, and \(\omega ^\text {fuel}\) and \(\omega ^\text {el}\) represent fuel gas and electricity costs. The complete MINLP model is then obtained with the variable vector
and the constraints
3.2 General disjunctive programming formulation
The shortest and possibly most natural way to model the cost minimization problem presented in Sect. 2 is a general disjunctive programming (GDP) formulation (Grossmann 2002; Raman and Grossmann 1994). Since it is a convenient form that is often used in engineering, we also state this model here for completeness. Using the notation from the preceding section, the GDP model reads
GDP models like this are generally built from separate sets of “local” constraints and objective terms that are combined in a logical disjunction. Every part of the disjunction is controlled by a decision variable (here \(s_\text {bp}\), \(s_\text {cl}\), or \(s_i\), \(i\in \mathscr {C}\)): the local constraints are enabled if and only if the associated decision variable is true (\(s_i= 1\)), and the local objective terms \(\gamma _i\) are set to zero otherwise. The SOS-1 constraint (9d) ensures that precisely one decision variable is true. In a general GDP, any set of feasible combinations of decision variables could be defined by a suitable logical expression. Moreover, “global” constraints and objective terms might be added.
4 Continuous reformulations
As discussed in Sect. 1, it is reasonable to study continuous reformulations of the MINLP and GDP models of Sects. 3.1 and 3.2 in order to tackle optimization problems for compressor stations or entire gas networks with continuous (local) optimization methods, which tend to be faster than global methods for mixed-integer nonlinear and nonconvex problems.
This section discusses five model reformulation schemes from the literature that can be applied to any model with binary variables that exhibit the structure of a logical disjunction, such as the problem under consideration.
First we introduce the concepts of NCP and pseudo NCP functions in Sect. 4.1. Then we present all reformulation schemes and discuss their feasible sets and regularity properties with a view towards solving them by local algorithms.
4.1 Pseudo NCP functions
NCP functions are bivariate functions: \(\varphi :\, \mathbb {R}^2 \rightarrow \mathbb {R}\) with the property that
Classical NCP functions include, e.g., the minimum function \(\varphi _{\min }(a, b) = \min (a, b)\) and the Fischer–Burmeister function (Fischer 1992),
See Sun and Qi (1999) and the references therein for an overview of NCP functions. NCP functions can be used to replace binary variables with continuous variables. However, the right-hand side of (10) introduces some difficulties if it is considered from an NLP perspective. The constraints \(a, b \ge 0\), \(a b = 0\) lead to mathematical programs with equilibrium constraints (MPECs). The problem is that standard NLP regularity concepts like the linear independence constraint qualification (LICQ) or the Mangasarian–Fromovitz constraint qualification (MFCQ) are violated at every feasible point of an MPEC (Ye and Zhu 1995); see Luo et al. (1996) for an overview of the theory and applications of MPECs. However, the nonnegativity constraints in (10) are not needed for the reformulations discussed below. This leads us to extend the class of NCP functions: We call a function \(\phi :\, \mathbb {R}^2 \rightarrow \mathbb {R}\) a pseudo NCP function if
In the remainder of this article we use the following two pseudo NCP functions:
Note that the Fischer–Burmeister \(\phi _{\text {FB}}\) function has a lack of regularity, whereas the product formulation \(\phi _{\text {prod}}\) is favorable since we do not have to impose nonnegativity constraints here as in the classical NCP setting.
4.2 Reformulation schemes
It is well-known that local solvers tend to be very sensitive to the specific formulation of a nonlinear model. This is the reason why it is often useful in practice to have different equivalent formulations to evaluate which formulation is best suited for the used solver. In this section we discuss five schemes that allow to reformulate the MINLP and GDP models of Sects. 3.1 and 3.2 with continuous variables and additional smooth constraints. Since the geometry of the feasible regions of the resulting continuous models and their regularity properties also have a strong influence on the solution process, we analyze these aspects for every reformulation.
To be applicable in the context of the model of Sect. 3.1, the reformulations have to possess the following properties:
-
1.
Every feasible solution of the reformulation has to be uniquely translatable into a feasible solution of the original MINLP (or GDP). This means that there exists a mapping (a left-total right-unique relation) from the feasible set of the reformulation to the feasible set of the original model.
-
2.
For every binary variable \(s\in \{0,1\}\), the reformulation has variables from which indicator and negation expressions can be constructed (cf. Sect. 3.1.1).
-
3.
The reformulation has variables from which the SOS-1 constraint can be constructed.
In what follows, we only present the representations of a set of binary variables \(s_1, \dots , s_m \in \{0,1\}\) together with the SOS-1 constraint \(\sum _{i = 1}^m s_i = 1\), rather than stating complete reformulated models. The latter can easily be reproduced from Sect. 3.1. We frequently use the sets \(\mathscr {M}\mathrel {{\mathop :}{=}}\{1, \dots , m\}\) and \(\mathscr {M}_i \mathrel {{\mathop :}{=}}\mathscr {M}\setminus \{i\}\).
As already stated in Sect. 1, all reformulation schemes below can be found in the existing literature—in particular, see Baumrucker et al. (2008), Kraemer and Marquardt (2010), and Stein et al. (2004)—except that we use pseudo NCP functions rather than NCP functions.
4.2.1 Exact bivariate reformulation
The first reformulation requires two continuous variables \((\sigma _i, \tau _i) \in \mathbb {R}^2\) per binary variable \(s_i\) together with the constraints
where \(\phi \) is an arbitrary pseudo NCP function. Clearly, the constraints (11) imply \((\sigma _i, \tau _i) \in \{(1,0), (0,1)\}\), giving the required mapping:
An indicator expression is \(\sigma _i\) and valid negation expressions are \(\tau _i\) or \((1 - \sigma _i)\). The feasible region of (11) is illustrated in Fig. 3 (left).
Since this scheme adds 2 m continuous variables and \(2 m + 1\) equality constraints, it introduces a lack of regularity (in the LICQ and MFCQ sense) in the \((\sigma _i, \tau _i)\)-space. However, (11) can be equivalently reformulated by replacing (11a) with
For \(\phi \in \{\phi _\text {prod}, \phi _\text {FB}\}\), it can be shown that the latter formulation satisfies the LICQ if and only if \(\sigma _1 \ne 0\). Of course, \(\mathscr {M}_1\) can be replaced with every other \(\mathscr {M}_j\).
4.2.2 Approximate bivariate reformulation
The second reformulation works like the first one but relaxes (11b):
The feasible set is illustrated in Fig. 3 (right): it is readily seen that \((\sigma _i, \tau _i) \in (\{0\} \times [1, \infty )) \cup ([1, \infty ) \times \{0\})\), and that exactly one \(i \in \mathscr {M}\) exists with \(\sigma _i = 1\) and \(\sigma _j = 0\) for all \(j \ne i\). Here we have added 2 m variables with \(m + 1\) equality and m inequality constraints. Depending on the activity status of inequalities, the LICQ might be satisfied or again be violated. An indicator expression is \(\sigma _i\) and a valid negation expression is given by \(\tau _i\). This scheme cannot be reformulated again like the exact bivariate reformulation since one would lose the property of being able to formulate indicator and negation expressions.
4.2.3 Exact univariate reformulation
This scheme requires only one continuous variable \(\sigma _i\) per binary variable \(s_i\) and adds the following constraints:
The feasible set is shown in Fig. 4 (left). Clearly we have \(\sigma _i \in \{0,1\}\) for all \(i \in \mathscr {M}\). An indicator expression is \(\sigma _i\) and a negation expression is \((1 - \sigma _i)\). The number of equality constraints exceeds the number of variables again by one (\(m + 1\) vs. m), but (13) can be equivalently replaced with
satisfying the LICQ for \(\phi \in \{\phi _\text {prod}, \phi _\text {FB}\}\) if and only if \(\sigma _1 \ne 0\).
4.2.4 Alternative exact univariate reformulation
Here, the set of constraints reads
These constraints imply \(\phi (\sigma _i, 1 - \sigma _i) = 0\), yielding \(\sigma _i \in \{0,1\}\) for all i. As before, there is one more equality constraint than variables (\(m + 1\) vs. m), and we have the equivalent reformulation
In both cases, an indicator expression is \(\sigma _i\) and a negation expression is \((1 - \sigma _i)\) or, equivalently, \(\sum _{j \in \mathscr {M}_i} \sigma _j\). The feasible set is the same as before, see Fig. 4 (left). Again, the LICQ is satisfied for \(\phi \in \{\phi _\text {prod}, \phi _\text {FB}\}\) if and only if \(\sigma _1 \ne 0\).
4.2.5 Approximate univariate reformulation
The set of constraints for the final scheme is given by
The feasible set is illustrated in Fig. 4 (right). Clearly we have \(\sigma _i \in \{0\} \cup [1, \infty )\) for all i. An indicator expression is \(\sigma _i\), and a negation expression is \(\sum _{j \in \mathscr {M}_i} \sigma _j\). This reformulation has the disadvantage that it always violates the LICQ for both \(\phi _{\text {prod}}\) and \(\phi _{\text {FB}}\), even if the inequality constraint (15b) is not active. Again, (15) can be equivalently reformulated by replacing (15a) with
This formulation satisfies the LICQ for \(\phi \in \{\phi _\text {prod}, \phi _\text {FB}\}\) if and only if \(\sigma _1 \ne 0\).
Table 3 lists the main properties of the five reformulation schemes.
5 Computational study
In the preceding sections we have discussed the problem of compressor station optimization and we have presented several model formulations. With these formulations at hand, the question arises whether all models are comparably well suited for numerical computations, or whether there are benefits or disadvantages for any of them. In this section we present an extensive computational study and compare the results of local and global solvers applied to different model formulations. We will see that the continuous reformulations work quite well in comparison to MINLP approaches.
As mentioned in the introduction, one main contribution of this paper is that—in combination with techniques presented in Pfetsch et al. (2015), Schmidt (2013), Schmidt et al. (2013) and Schmidt et al. (2015b)—our approach allows the purely continuous reformulation of genuinely discrete-continuous models of entire gas networks. In order to demonstrate that this is also viable in practice, in the sense that one can compute locally optimal values of the corresponding MINLPs, we present some promising first results.
Section 5.1 introduces two compressor stations with boundary conditions as test instances and describes the hardware and software used in the study. Section 5.2 then discusses performance profiles for measuring performance and robustness of different model formulations and solvers. Next, Sects. 5.3 and 5.4 present the numerical results for single compressor stations while Sect. 5.5 presents a preliminary computational study on entire gas networks. Finally, Sect. 5.6 gives a summary of the results.
5.1 Test instances and computational setup
We consider minimum cost problems using the objective (8) with cost coefficients and , and feasibility testing using the objective \(f\equiv 0\). These objectives are combined with all presented models for two different compressor stations. The first station, called GasLib-582 station in the following, is compressorStation_5 from the network GasLib-582 (Humpola et al. 2015). It contains one turbo compressor and one piston compressor and can be operated in three configurations. This station is comparatively small and serves as a proof of concept for the applicability of the continuous reformulations. Moreover, the data of this test set are publicly available, so that other researchers can compare their models or algorithms on the same data. The second station, called HG station in the following, is a real-world compressor station of our former industry partner Open Grid EuropeFootnote 1 (OGE). It is one of OGE’s largest compressor stations, containing five turbo compressors that can be operated in 14 configurations in our model. The results on this station illustrate the applicability of the presented models on real-world data.
The boundary values for our test instances are constructed as follows. We always prescribe the in- and outflow pressures as well as the flow through the station. For both stations, the set of inflow pressures (in bar) is \(\mathscr {P}_\text {in}= \{20,50,80\}\). For every inflow pressure \(p_\text {in}\in \mathscr {P}_\text {in}\), we then construct a set of outflow pressures \(\mathscr {P}_{\text {out},i}(p_\text {in}) = \{p_\text {in}+ k \varDelta p_i:k = 0, \dots , 3\}\), \(i = 1, 2\), where \(\varDelta p_1 = 13.3 \hbox { bar}\) (GasLib-582 station) and \(\varDelta p_2 = 20\hbox { bar}\) (HG station). The sets of flows (in \(10^3\hbox { Nm}^{3}\hbox {h}^{-1}\)) are \(\mathscr {Q}_1 = \{0, 375, 750, \dots , 2250\}\) (GasLib-582 station) and \(\mathscr {Q}_2 = \{0, 800, 1600, \dots , 4800\}\) (HG station). Thus, the complete set of boundary conditions for the GasLib-582 station is
and the corresponding set for the HG station is
All values are chosen based on our experience with the technical capabilities of the stations and with typical values in gas networks. Note that the flow values for the test sets are given as volumetric flow under normal conditions, \(Q_{0}\), measured in 1000 normal cubic meters per hour, as this is the standard technical unit in gas transportation. It can easily be converted to mass flow via \(q= c Q_{0}\rho _0\), where \(c = 1000/3600\), and \(\rho _0\) is the gas density under normal conditions. The sizes of the test sets are \(|\mathscr {T}_1| = |\mathscr {T}_2| = 84\).
All models are implemented using the modeling language GAMS (McCarl 2009) and the C software framework LaMaTTO (LaMaTTO++ 2015). As global solvers for the MINLP model and its continuous (NLP type) reformulations we use BARON 12.3.3 (Tawarmalani and Sahinidis 2002, 2004, 2005) and SCIP 3.0 (SCIP 2015; Vigerske 2012). Additionally, we use the convex MINLP solver KNITRO 8.1.1 (Byrd et al. 2006) as a heuristic for the nonconvex MINLPs and as NLP solver for the continuous reformulations. As local solvers for the continuous reformulations we use the interior-point code Ipopt 3.11 (Wächter and Biegler 2006) and the reduced-gradient code CONOPT4 (Drud 1994, 1995, 1996) as well as the three MINLP solvers. The solvers are run with default settings throughout, even for solution tolerances, as it is virtually impossible to find settings that make the results comparable in a strict mathematical sense.
All computations are executed on a six-core AMD Opteron Processor 2435 with 2600 MHz and 64 GB RAM. The operating system is Debian 7.5.
5.2 Measuring performance and robustness
To compare the computing times of different combinations of model formulations and solvers, we use standard performance profiles (Dolan and Moré 2002). To this end, let us define the performance measure
where the set \(\mathscr {S}\) contains all 106 combinations of model formulations and solvers: the MINLP model in big-\(M\) and bilinear product formulation combined with BARON, SCIP, and KNITRO (\(1 \times 2 \times 3 = 6\)), and each of the five continuous reformulations in four variants (big-\(M\) and bilinear product with both pseudo NCP functions each) combined with all five solvers (\(5 \times 4 \times 5 = 100\)). We consider only the subsets of feasible boundary values, \(\mathscr {F}_i \subset \mathscr {T}_i\), defined to contain those instances for which at least one combination \(s\in \mathscr {S}\) produces a feasible solution. Now the performance ratio \(r_{p,s}\) associated with \(t_{p,s}\) is
Moreover, we set \(r_{p,s} = r_M \mathrel {{\mathop :}{=}}\max \{r_{p',s'}:p' \in \mathscr {F}_i, \, s' \in \mathscr {S}_i\}\) for those instances p that cannot be solved by s. The logarithmically scaled performance profile is finally given by
Finally, we remark that we use two different objective functions depending on the goal of our analysis: If we consider the performance of the solution process, we minimize costs using objective (8). For this case we also discuss the different solution qualities obtained by the local solvers. If we consider the robustness of the solution process, we use the empty objective \(f\equiv 0\) since we are only interested in whether a feasible point can be found or not. In the latter case, the time used for the performance profiles thus equals the time required to find the first feasible point.
5.3 The GasLib-582 test set
The set \(\mathscr {F}_1\) contains 48 instances of \(\mathscr {T}_1\), hence 36 of the 84 instances are infeasible. The computing times are up to 62 s in cases where solutions are found and up to 59 s in cases where a solver detects infeasibility. Some of the instances are solved in fractions of a second. This can happen, for instance, in the preprocessing of BARON due to bound strengthening. As one would expect, the largest differences of computing times are observed for the global solvers.
First we discuss the objective values that are obtained by the different formulations and solvers. In theory, the global solvers BARON and SCIP should produce identical objective values whereas the local optima found by the local solvers can be larger by arbitrary amounts. However, our results show that the values of BARON and SCIP slightly differ in some cases and that all model formulations and solvers produce almost identical values on the current test set.
For every problem \(p \in \mathscr {F}_1\), we compute the minimum and maximum objective values \(f^*_{p,\min }\) and \(f^*_{p,\max }\) as well as the maximal absolute gap \(g^*_p = f^*_{p,\max } - f^*_{p,\min }\). The minimal values \(f^*_{p,\min }\) range from 0 to 0.008735 (operating cost in €/s), with maximal gaps ranging from 0 to 0.008765. The average maximal gap over \(p \in \mathscr {F}_1\) is approximately 0.0012, but most of the individual gaps are actually zero. We assume that differing objective values are mainly caused by different numerical properties of the solvers. We also compared the discrete states of the compressor stations in the optimal solutions for every instance. Different active states are found for 9 of the 48 feasible instances, 3 of which have boundary values of the form \(Q_{0}= 0\) and \(p_u= p_v\), where the bypass mode and the closed mode are both feasible and globally optimal with zero cost. The remaining 6 instances have different active configurations. Thus, we have the surprising observation that on the current test set the local solvers always yield optimal values close to the global minima. A possible reason could be that many instances admit just one feasible discrete configuration. Unfortunately we cannot find out whether this is true since it would require the huge effort of testing feasibility for all discrete configurations.
Next, we turn to the issue of infeasibility detection. A substantial fraction of the boundary values of our test set are infeasible: 36 out of 84. In theory, if a global solver detects infeasibility of an instance, this is considered as an infeasibility proof. However, due to numerical inaccuracy, this is not always true in practice. To give a more detailed overview, we also list the numbers of feasible instances that are not solved (i.e., infeasibility is reported or the solver simply fails) in Table 4. Among the solvers, BARON clearly shows the most reliable results: for every feasible instance there is at least one model formulation for which BARON produces a solution. All other solvers report false infeasible results or fail in 7 or 8 cases. Surprisingly, this is also true for the global solver SCIP. Regarding the different continuous reformulations, the approximate bivariate and exact univariate reformulations are solved for every feasible instance (at least by one solver). The worst result is obtained for the MINLP model (7 failures). However, this result has to be carefully interpreted because the MINLP is handled by only 3 solvers whereas all 5 solvers can handle the continuous reformulations. Within the set of reformulations, the approximate univariate reformulation has by far the largest number of false infeasibility reports and solver failures.
Let us now investigate the performance (measured in computing time) of all combinations \(s \in \mathscr {S}\). We define the fastest combination to be the one that has the largest number of instances that it solves at least as fast as all other combinations, i.e., the combination s with the largest value \(\rho _s(0)\) in the corresponding logarithmically scaled performance profile. We use this value because it is a generally accepted quality measure. Of course, one might also be interested in other measures such as the total runtime of a model/solver combination s on all instances. To give a visual illustration, we need some aggregation and compare the 106 combinations in two stages: in the first stage we determine the best combination of a solver with indicator constraint type and pseudo NCP function for each of the 6 basic models: MINLP and 5 reformulations. In the second stage, only the 6 best combinations of the first stage are compared. Table 5 lists the fastest solvers for the MINLP model and the 5 reformulations. The solver printed in bold is the fastest solver of the entire row, i.e., over all combinations of indicator constraint types and pseudo NCP functions. Note that the MINLP model does not involve any pseudo NCP functions, hence the first row has only two entries (big-\(M\) and BP).
First, it can be seen that the global solver BARON is the fastest solver for 18 of the 22 model formulations. The local solvers Ipopt or CONOPT4 are faster in only three cases. CONOPT4 is the overall fastest solver for the alternative exact and approximate univariate reformulations. Second, it is apparent that the bilinear product used as pseudo NCP function yields clearly faster runs than the Fischer–Burmeister function: all the bold model/solver combinations use the bilinear product. Third, a best choice of the type of indicator constraints (big-\(M\) vs. bilinear product) is not apparent by this criterion. The full data set actually shows that the choice does not have a significant impact here.
Figure 5 shows the 6 performance profiles of the fastest model/solver combinations (bold) for each row of Table 5. Although BARON is faster than all other solvers on the largest number of model formulations, it turns out that the preferable model/solver combination does not use BARON. In order to determine the overall fastest combination, we again compare the values \(\rho _s(0)\). It can be seen that the local solver CONOPT4 (applied to the alternative exact and approximate univariate reformulations) produces the shortest solution times for approximately 40 % of all feasible instances. Notice that both formulations solved with CONOPT4 are faster than all other combinations if an instance can be solved by CONOPT4 at all (the “horizontal” lines of the performance profiles of AEUR and AUR in Fig. 5 extend almost to the left boundary). This is to be expected since local solvers typically tend to be faster than global solvers. The global solver BARON applied to the other continuous reformulations yields significantly slower solution times and is the fastest combination for 15 to 25 % of the feasible instances. Finally, BARON applied to the original MINLP model is distinctly the slowest combination of solver and model formulation.
We now turn to robustness. The most robust combination is defined as the one that solves the largest fraction of instances to optimality, i.e., the combination s with the largest value
As in the performance comparison, we list the most robust solver for every combination of model reformulation, indicator constraint type, and pseudo NCP function in Table 6.
Here BARON appears even more often than in the case of computing times: It is always the most robust solver, except for the single case where SCIP is applied to the MINLP model with bilinear products as indicator constraints. In contrast to the case of computing times, the choice of pseudo NCP functions does not seem to have a significant impact here.
Again we compare the 6 performance profiles of the best combinations (bold) for each row of Table 6, see Fig. 6.
Overall, the results look more “homogeneous” than in Fig. 5. All combinations produce comparatively good values \(\rho _s^*\) from 85 to 98 % of solved instances. The two bivariate reformulations produce the best values (significantly above 90 %). Note further that these model formulations use big-\(M\) indicator constraints. The good robustness is probably caused by the convexity conserving property of the big-\(M\) formulation, which contrasts with the inherently nonconvex bilinear products.
5.4 The HG test set
The set \(\mathscr {F}_2\) contains 41 instances of \(\mathscr {T}_2\), hence 43 of the 84 instances are infeasible. The computing times are up to 67 s in cases where solutions are found and up to 45 s in cases where a solver detects infeasibility.
The minimal objective values (in €/s) now range from 0 to 0.069505 and the maximal gaps from 0 to 0.022102. The average maximal gap over all \(p \in \mathscr {F}_2\) is significantly smaller than for \(\mathscr {F}_1\) at approximately 0.0006778 and most of the individual gaps are again zero. Except for one case, the active states in the optimal solutions for a given set of boundary values are identical for all \(s \in \mathscr {S}\) or consist of different sets of identical compressor units yielding the same objective value.Footnote 2 The exceptional case is exactly the one leading to the maximal gap. Excluding this case reduces the maximal gap over all instances by one order of magnitude.
In Table 7 we list the numbers of feasible instances for which a model could not be solved to optimality (i.e., infeasibility is reported or the solver fails). As it was the case for the GasLib-582 station, BARON yields the smallest number of false infeasibility reports (just one). Moreover, the choice of the class of solver (global vs. local) seems to be more crucial than the choice of the specific model formulation: the MINLP solvers report false infeasibility in 1 to 3 cases whereas the local solvers have significantly larger numbers of failure of 5 and 8.
Turning to the performance investigation, we follow the same two-stage approach as before. Table 8 lists the fastest solvers for the MINLP model and all tested continuous reformulations. It can be seen that BARON is the fastest solver for the MINLP model (to which only global solvers can be applied) and that local solvers (CONOPT4 and Ipopt) are the fastest for all continuous reformulations, where both global and local solvers are applied. This is in line with our expectations since local solvers typically tend to be faster than global solvers. Moreover, it is noticeable that the pseudo NCP function \(\phi _\text {prod}\) yields better results than the Fischer–Burmeister function \(\phi _\text {FB}\), and that global solvers outperform local solvers when applied to big-\(M\) indicator constraints while the converse behavior is observed for bilinear indicator constraints (except for the case of BARON applied to the exact bivariate reformulation using bilinear indicator constraints and \(\phi = \phi _\text {prod}\)).
Figure 7 shows the performance profiles for every bold combination of Table 8. The approximate bivariate reformulation (ABR) solved with CONOPT4 is the overall fastest combination, performing best on more than 30 % of all instances. The approximate univariate (AUR), exact bivariate (EBR), and alternative exact univariate (AEUR) reformulations combined with CONOPT4 come next, each performing best on roughly 20 % of all instances. Since the approximate univariate formulation shows better results than EBR and AEUR for small values \(\tau > 0\), we may summarize that the approximate reformulations (combined with \(\phi = \phi _\text {prod}\)) tend to be the fastest combinations. A possible reason might be that for local solvers the enlarged feasible set is preferable to the feasible sets of lower dimension of the exact reformulations. In addition, the overall preferable approximate bivariate scheme is also the “most regular” formulation with respect to the LICQ (cf. Sect. 4.2). Finally we note that in terms of solution times both the exact univariate reformulation and the MINLP model cannot compete with the other reformulations.
Regarding robustness, the situation changes completely. We list the most robust solver (the one with largest \(\rho _s^*\)) for every combination of model reformulation, indicator constraint type, and pseudo NCP function in Table 9. For the original MINLP model, KNITRO (with big-\(M\) indicator constraints) and SCIP (with bilinear indicator constraints) are equally robust. BARON is the most robust solver in 80 % of all continuous reformulations. The bilinear product indicator constraints always yield better results than the big-\(M\) ones. Except for KNITRO applied to the approximate univariate reformulation using bilinear indicator constraints and \(\phi = \phi _\text {FB}\), no local solver is more robust than one of the global solvers.
The performance profiles of the most robust combinations of Table 9 are given in Fig. 8. All models yield comparable results, solving 85 to 93 % of all instances. The highest percentages are obtained by the original MINLP and the exact bivariate reformulation (EBR). The fastest continuous reformulations, i.e., the approximate bivariate and the alternative approximate univariate reformulation, yield the smallest values at approximately 85 %. Thus, we have exactly the opposite situation as for the performance comparison.
5.5 Continuous reformulations of entire networks
Let us now extend our approach of continuous reformulations to MINLP models of entire gas networks. To this end, we combine the reformulations presented in this paper with suitable MPEC based reformulations of all controllable network devices (except compressor stations) (Pfetsch et al. 2015; Schmidt 2013; Schmidt et al. 2013, 2015b). In our computational study, we combine the MPEC based model of the network with all combinations of pseudo NCP functions, indicator constraints, continuous reformulations, and local solvers discussed in the previous sections. Each of these combinations is applied to 50 randomly chosen instances of the GasLib-582 network.Footnote 3 All instances are solved with the goal of feasibility testing, i.e., with objective function \(f \equiv 0\); cf. Sect. 5.2. The time limit of all computations is set to 2 min, and we use the same hardware and software as in the preceding sections.
The results for embedding continuous reformulations of compressor stations in entire network models are of interest for, at least, two reasons. First, they give insight into the situation where boundary values are restricted to nontrivial ranges, rather than being fixed as in the study presented so far. Second, they provide a first impression on the robustness of solving purely continuous network models.
Table 10 lists the number of feasible solutions found by the individual reformulations. It turns out that the choice of the pseudo NCP function (Fischer–Burmeister vs. product) is not crucial here: 51 combinations using \(\phi _\text {FB}\) and 57 combinations using \(\phi _\text {prod}\) are solved to feasibility. Similarly, the choice of the specific indicator constraint type does not appear to be of great importance for entire networks (61 feasible solutions for big-\(M\) constraints and 47 for bilinear product constraints).
In contrast, the choices of reformulation scheme and local solver have a strong influence. All univariate reformulation schemes (EUR, AEUR, and AAUR) yield feasible solutions significantly less often (9, 13, and 8 times) than the exact bivariate (EBR; 45 feasible solutions) and the approximate bivariate reformulation scheme (ABR; 33 feasible solutions). Concerning the tested local solvers, Ipopt (70 feasible solutions) clearly outperforms both CONOPT4 (37) and KNITRO (1).
In total, 38 instances (76 %) are solved to feasibility. The most successful combination (printed bold in Table 10) combines the Fischer–Burmeister pseudo NCP function with big-\(M\) indicator constraints, the exact bivariate reformulation scheme, and the local solver CONOPT4.
The analysis of the results shows that feasibility testing for entire gas networks is possible with purely continuous models in principle. However, the used combinations of MPEC models and continuous compressor station reformulations have to be tested in more detail in order to increase the robustness of the formulations. This is a subject of future research.
5.6 Summary
A major result of our study is that local solvers applied to continuous reformulations tend be faster than global solvers applied to the mixed-integer model and its continuous reformulations. This was to be expected. Moreover, our numerical results suggest that this tendency becomes more evident for larger instances. When comparing only the continuous reformulations, the results for the larger compressor station HG indicate that reformulations with larger feasible sets are preferable and that the regularity of the formulation has a strong impact on the performance of the solution process. (Recall that the “most regular” approximate bivariate reformulation yields the best solution times on the large test set.) Finally, global solvers (especially BARON) produce more robust results, independent of the choice of model formulation.
Our results also indicate which types of indicator constraints work well with a given solver. Especially for larger instances, global solvers tend to be faster on big-\(M\) formulations while local solvers perform better with bilinear products. A probable reason for this is that the behavior of global solvers is stronger influenced by nonconvexity than it is the case for local solvers. The situation changes with regard to robustness of the solution process, where the bilinear indicator constraint is clearly preferable to the big-\(M\) formulation.
A second observation concerns the preferable type of pseudo NCP functions: The product formulation \(\phi _\text {prod}\) distinctly outperforms Fischer–Burmeister functions. Although the latter are quite prominent in the literature, the simple formulation using products usually produces faster and more robust formulations in practice.
Finally we can state that, for the models considered in this paper, there are no significant drawbacks concerning the quality of solutions when local solvers are used. These results are perhaps not entirely surprising for the considered class of real-world problems. However, no systematic study exists in the literature up to now.
The tendencies observed above might change when fixed boundary values are replaced with nontrivial feasible ranges. This happens, e.g., when the tested continuous reformulations of compressor stations are used in continuous models of entire networks. As expected, the resulting instances are hard, but we have seen in Sect. 5.5 that in principle they can be solved by local solvers. Nevertheless, more extensive testing of model combinations and possibly the development of further model variants are required in order to obtain more robust formulations. Both issues are subjects of future research.
6 Conclusion
In this article we have presented MINLP and GDP models for cost optimization and feasibility testing of gas compressor stations. Moreover, we have considered different types of continuous reformulation techniques from the literature and applied them to the application problem. Our computational study shows that local solvers applied to continuous reformulations can be used to replace MINLP formulations that can only be tackled by global solvers. The continuous reformulations yield comparably robust results, optimal values of almost the same quality on our test set, and tend to be solvable within shorter solution times. Together with the techniques developed in Pfetsch et al. (2015), Schmidt (2013), Schmidt et al. (2013), and Schmidt et al. (2015b), this article provides a complete continuous reformulation of the discrete-continuous problem of stationary gas transport optimization. Additionally, first promising numerical results on a large-scale network underpin the practical usability of continuous reformulations for entire networks.
However, some questions remain open. We have considered a stationary and isothermal variant of the problem of compressor station optimization. Since including gas temperature as a dynamic variable mainly leads to increased nonlinearity and nonconvexity in the model, we expect that continuous reformulations tend to be even more favorable for these models. In contrast, the consideration of the transient case will also increase the amount of discrete aspects so that it is unclear which formulation will be favorable in this case. Finally, more extensive testing of suitable continuous models for entire networks is a subject of future research.
Notes
The detection of mathematical symmetry in this situation could be used to reduce the complexity of the corresponding station model.
The 50 randomly chosen instances are cold_1461, cold_1466, cold_1689, cold_2311, cold_2406, cold_2763, cold_3824, cold_4105, cold_712, cool_122, cool_1500, cool_1586, cool_1766, cool_1770, cool_1929, cool_2045, cool_2208, cool_2270, cool_2859, cool_3400, cool_3409, cool_3885, cool_3929, cool_4031, cool_416, cool_4192, cool_526, cool_543, cool_821, freezing_1106, freezing_1416, freezing_1599, freezing_164, freezing_2206, freezing_3078, freezing_3853, freezing_402, freezing_728, mild_1203, mild_1344, mild_1459, mild_3124, mild_92, warm_1215, warm_2356, warm_2689, warm_2718, warm_3048, warm_3235, warm_916.
References
Banda MK, Herty M (2008) Multiscale modeling for gas flow in pipe networks. Math Methods Appl Sci 31:915–936. doi:10.1002/mma.948
Banda MK, Herty M, Klar A (2006) Gas flow in pipeline networks. Netw Heterog Media 1(1):41–56. doi:10.3934/nhm.2006.1.41
Baumrucker BT, Renfro JG, Biegler LT (2008) MPEC problem formulations and solution strategies with chemical engineering applications. Comput Chem Eng 32:2903–2913. doi:10.1016/j.compchemeng.2008.02.010
Bock HG, Kostina E, Phu HX, Rannacher R (eds) (2005) Modeling, simulation and optimization of complex processes. Springer, Berlin
Brouwer J, Gasser I, Herty M (2011) Gas pipeline models revisited: model hierarchies, nonisothermal models, and simulations of networks. Multiscale Model Simul 9(2):601–623. doi:10.1137/100813580
Byrd RH, Nocedal J, Waltz RA (2006) KNITRO: An integrated package for nonlinear optimization. In: Large scale nonlinear optimization, Springer Verlag, pp 35–59. doi:10.1007/0-387-30065-1_4
Carter RG (1996) Compressor station optimization: computational accuracy and speed. In: 28th annual meeting, Pipeline Simulation Interest Group. Paper 9605
Carter RG (1998) Pipeline optimization: dynamic programming after 30 years. In: PSIG 30th annual meeting, Denver, Colorado. Paper 9803
Carter RG, Schroeder DW, Harbick TD (1994) Some causes and effects of discontinuities in modeling and optimizing gas transmission networks. Tech. rep, Stoner Associates, Carlisle, PA, USA
Cobos-Zaleta D, Ríos-Mercado RZ (2002) A MINLP model for a problem of minimizing fuel consumption on natural gas pipeline networks. In: Proceedings of XI Latin-Ibero-American conference on operations research, pp 1–9. Paper A48–01
Dolan ED, Moré JJ (2002) Benchmarking optimization software with performance profiles. Math Program 91(2):201–213. doi:10.1007/s101070100263
Domschke P, Geißler B, Kolb O, Lang J, Martin A, Morsi A (2011) Combination of nonlinear and linear optimization of transient gas networks. INFORMS J Comput 23(4):605–617. doi:10.1287/ijoc.1100.0429
Drud AS (1994) CONOPT—a large-scale GRG code. INFORMS J Comput 6(2):207–216. doi:10.1287/ijoc.6.2.207
Drud AS (1995) CONOPT: a system for large scale nonlinear optimization, tutorial for CONOPT subroutine library. Tech. rep, ARKI Consulting and Development A/S, Bagsvaerd, Denmark
Drud AS (1996) CONOPT: a system for large scale nonlinear optimization, reference manual for CONOPT subroutine library. Tech. rep, ARKI Consulting and Development A/S, Bagsvaerd, Denmark
Ehrhardt K, Steinbach MC (2004) KKT systems in operative planning for gas distribution networks. Proc Appl Math Mech 4(1):606–607. doi:10.1002/pamm.200410284
Ehrhardt K, Steinbach MC (2005) Nonlinear optimization in gas networks. In: Bock et al. (eds) Modeling, simulation and optimization of complex processes. Springer, Berlin, pp. 139–148. doi:10.1007/3-540-27170-8_11
Eurostat (2013) Gross inland energy consumption by fuel type. http://epp.eurostat.ec.europa.eu/tgm/refreshTableAction.do?tab=table&plugin=1&pcode=tsdcc320&language=en. Downloaded on 2 Oct 2015
Fischer A (1992) A special Newton-type optimization method. Optimization 24(3–4):269–284. doi:10.1080/02331939208843795
Geißler B, Morsi A, Schewe L (2013) A new algorithm for MINLP applied to gas transport energy cost minimization. In: Jünger M, Reinelt G (eds) Facets of combinatorial optimization, Springer, Berlin Heidelberg, pp 321–353. doi:10.1007/978-3-642-38189-8_14
Geißler B (2011) Towards globally optimal solutions for MINLPs by discretization techniques with applications in gas network optimization. Ph.D. thesis, Friedrich-Alexander Universität Erlangen-Nürnberg, Germany
Grossmann IE (2002) Review of nonlinear mixed-integer and disjunctive programming techniques. Optim Eng 3(3):227–252. doi:10.1023/A:1021039126272 Special issue on mixed-integer programming and its applications to engineering
Gugat M, Hante FM, Hirsch-Dick M, Leugering G (2015) Stationary states in gas networks. Netw Heterog Media 10(2):295–320. doi:10.3934/nhm.2015.10.295
Humpola J, Joormann I, Oucherif D, Pfetsch ME, Schewe L, Schmidt M, Schwarz R (2015) GasLib—a library of gas network instances. http://www.optimization-online.org/DB_HTML/2015/11/5216.html
Jeníček T, Králik J (1995) Optimized control of generalized compressor station. In: PSIG annual meeting
Koch T, Hiller B, Pfetsch ME, Schewe L (eds) (2015) Evaluating gas network capacities. SIAM-MOS series on optimization. SIAM. doi:10.1137/1.9781611973693
Kraemer K, Kossack S, Marquardt W (2007) An efficient solution method for the MINLP optimization of chemical processes. In: V Plesu, PS Agachi (eds) 17th European symposium on computer aided process engineering, computer aided chemical engineering, vol. 24, Elsevier, pp 105–110. doi:10.1016/S1570-7946(07)80041-1
Kraemer K, Marquardt W (2010) Continuous reformulation of MINLP problems. In: M Diehl, F Glineur, E Jarlebring, W Michiels (eds) Recent advances in optimization and its applications in engineering, Springer, Berlin Heidelberg, pp 83–92. doi:10.1007/978-3-642-12598-0_8
Králik J (1993) Compressor stations in SIMONE. In: Proceedings of 2nd international workshop SIMONE on innovative approaches to modeling and optimal control of large scale pipeline networks, Prague, pp 93–117
LaMaTTO++ (2015) A framework for modeling and solving mixed-integer nonlinear programming problems on networks. http://www.mso.math.fau.de/edom/projects/lamatto.html
Luo ZQ, Pang JS, Ralph D (1996) Mathematical programs with equilibrium constraints. Cambridge University Press, Cambridge
Martin A, Möller M (2005) Cutting planes for the optimization of gas networks. In: Bock et al. (eds) Modeling, simulation and optimization of complex processes. Springer, Berlin, pp. 307–329. doi:10.1007/3-540-27170-8_24
Martin A, Mahlke D, Moritz S (2007) A simulated annealing algorithm for transient optimization in gas networks. Math Methods Oper Res 66(1):99–115. doi:10.1007/s00186-006-0142-9
Martin A, Möller M, Moritz S (2006) Mixed integer models for the stationary case of gas network optimization. Math Program 105(2–3):563–582. doi:10.1007/s10107-005-0665-5
McCarl BA (2009) GAMS user guide. VERSION 23.0
Odom FM, Muster GL (2009) Tutorial on modeling of gas turbine driven centrifugal compressors. Tech. Rep. 09A4, Pipeline Simulation Interest Group
Osiadacz A (1980) Nonlinear programming applied to the optimum control of a gas compressor station. Int J Numer Methods Eng 15(9):1287–1301. doi:10.1002/nme.1620150902
Pfetsch ME, Fügenschuh A, Geißler B, Geißler N, Gollmer R, Hiller B, Humpola J, Koch T, Lehmann T, Martin A, Morsi A, Rövekamp J, Schewe L, Schmidt M, Schultz R, Schwarz R, Schweiger J, Stangl C, Steinbach MC, Vigerske S, Willert BM (2015) Validation of nominations in gas network optimization: models, methods, and solutions. Optim Methods Softw 30(1):15–53. doi:10.1080/10556788.2014.888426
Raman R, Grossmann IE (1994) Modeling and computational techniques for logic based integer programming. Comput Chem Eng 18(7):563–578. doi:10.1016/0098-1354(93)E0010-7
Schewe L, Koch T, Martin A, Pfetsch ME (2015) Mathematical optimization for evaluating gas network capacities. In: Koch et al. (eds) Evaluating gas network capacities, chap. 5, pp. 87–102. doi:10.1137/1.9781611973693.ch5
Schmidt M (2013) A generic interior-point framework for nonsmooth and complementarity constrained nonlinear optimization. Ph.D. thesis, Gottfried Wilhelm Leibniz Universität Hannover
Schmidt M, Steinbach MC, Willert BM (2013) A primal heuristic for nonsmooth mixed integer nonlinear optimization. In: M Jünger, G Reinelt (eds) Facets of combinatorial optimization, Springer, Berlin, Heidelberg, pp 295–320. doi:10.1007/978-3-642-38189-8_13
Schmidt M, Steinbach MC, Willert BM (2015a) High detail stationary optimizationmodels for gas networks: validation and results. Optim Eng. doi:10.1007/s11081-015-9300-3
Schmidt M, Steinbach MC, Willert BM (2015b) An MPEC based heuristic. In: Koch et al. (eds) Evaluating gas network capacities, chap. 9, pp. 163–179. doi:10.1137/1.9781611973693.ch9
Schmidt M, Steinbach MC, Willert BM (2015c) High detail stationary optimization models for gas networks. Optim Eng 16(1):131–164. doi:10.1007/s11081-014-9246-x
SCIP (2015) Solving constraint integer programs. http://scip.zib.de/
Stein O, Oldenburg J, Marquardt W (2004) Continuous reformulations of discrete-continuous optimization problems. Comput Chem Eng 28(10):1951–1966. doi:10.1016/j.compchemeng.2004.03.011
Steinbach MC (2007) On PDE solution in transient optimization of gas networks. J Comput Appl Math 203(2):345–361. doi:10.1016/j.cam.2006.04.018
Sun D, Qi L (1999) On NCP-functions. Comput. Optim. Appl. 13(1–3):201–220. doi:10.1023/A:1008669226453 Computational Optimization—a Tribute to Olvi Mangasarian, Part II
Tawarmalani M, Sahinidis NV (2002) Convexification and global optimization in continuous and mixed-integer nonlinear programming: theory software, and applications. Kluwer Academic Publishers, Algorithms
Tawarmalani M, Sahinidis NV (2004) Global optimization of mixed-integer nonlinear programs: a theoretical and computational study. Math Program 99(3):563–591. doi:10.1007/s10107-003-0467-6
Tawarmalani M, Sahinidis NV (2005) A polyhedral branch-and-cut approach to global optimization. Math Program 103(2):225–249. doi:10.1007/s10107-005-0581-8
Vigerske S (2012) Decomposition in multistage stochastic programming and a constraint integer programming approach to mixed-integer nonlinear programming. Ph.D. thesis, Humboldt-Universität zu Berlin
Wächter A, Biegler LT (2006) On the implementation of an interior-point filter line-search algorithm for large-scale nonlinear programming. Math Program 106(1):25–57. doi:10.1007/s10107-004-0559-y
Wong PJ, Larson RE (1968a) Optimization of natural-gas pipeline systems via dynamic programming. IEEE Trans Autom Control 13:475–481. doi:10.1109/TAC.1968.1098990
Wong PJ, Larson RE (1968b) Optimization of tree-structured natural-gas transmission networks. J Math Anal Appl 24:613–626. doi:10.1016/0022-247X(68)90014-0
Wright S, Somani M, Ditzel C (1998) Compressor station optimization. In: PSIG 30th annual meeting, Denver, Colorado. Paper 9805
Ye JJ, Zhu DL (1995) Optimality conditions for bilevel programming problems. Optimization 33:9–27. doi:10.1080/02331939508844060
Acknowledgments
This work has been supported by the German Federal Ministry of Economics and Technology owing to a decision of the German Bundestag. The responsibility for the content of this publication lies with the authors. This research has been conducted as part of the Energie Campus Nürnberg and supported by funding through the “Aufbruch Bayern (Bavaria on the move)” initiative of the state of Bavaria. We are also very grateful to Benjamin Hiller for his comments on an earlier version of this paper. Finally, we thank our former industry partner Open Grid Europe GmbH for their support.
Author information
Authors and Affiliations
Corresponding author
Ethics declarations
Conflicts of interest
The authors declare that they have no conflict of interest
Human and Animal Participants
This article does not contain any studies with human or animal subjects
Rights and permissions
Open Access This article is distributed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/), which permits unrestricted use, distribution, and reproduction in any medium, provided you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons license, and indicate if changes were made.
About this article
Cite this article
Rose, D., Schmidt, M., Steinbach, M.C. et al. Computational optimization of gas compressor stations: MINLP models versus continuous reformulations. Math Meth Oper Res 83, 409–444 (2016). https://doi.org/10.1007/s00186-016-0533-5
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00186-016-0533-5
Keywords
- Discrete-continuous nonlinear optimization
- Gas networks
- Gas compressor stations
- Mixed-integer optimization
- Continuous reformulations