J Frédéric Bonnans
email: frederic.bonnans@inria.fr.

Jean André
email: jean-dr.andre@gdfsuez.com

Optimal structure of gas transmission trunklines

Keywords: gas network, pipeline system, network design, optimality conditions, generalized multipliers

In this paper, we consider the optimal design of a straight pipeline system. Suppose a gas pipeline is to be designed to transport a specified flowrate from the entry point to the gas demand point. Physical and contractual requirements at supply and delivery nodes are known as well as the costs to buy and lay a pipeline or build a compressor station. In order to minimize the overall cost of creation of this mainline, the following design variables need to be determined: the number of compressor stations, the lengths of pipeline segments between compressor stations, the diameters of the pipeline segments, the suction and discharge pressures at each compressor station. To facilitate the calculation of the design of a pipeline, gas engineers proposed, in several handbooks, to base their cost-assessments on some optimal properties from previous experiences and usual engineering practices: the distance between compressors is constant, all diameters are equal, and all inlet (resp. outlet) pressures are equal. The goals of this paper are (1) to state on which assumptions we can consider that the optimal properties are valid and (2) to propose a rigorous proof of the optimal properties (based on nonlinear programming optimality conditions) within a more general framework than before.

Structure optimale de gazoducs de grand transport

Résumé : Cet article traite le problème de la conception optimale d'un système de pipelines en ligne droite. Le pipeline doit transporter un débit donné d'un point d'entrée à un point de demande de gaz. Les contraintes physiques et contractuelles aux points d'entrée et de demande sont données ainsi que les coûts d'installation de pipelines et de construction des compresseurs. Pour minimiser le coût total de création, on doit déterminer les variables suivantes : le nombre de stations de compression, la longueur des segments, et les pressions d'aspiration et de refoulement de chaque station de compression. Pour faciliter le calcul de la conception du pipeline, des ingénieurs ont proposé, dans plusieurs manuels, de baser la conception sur certaines propriétés optimales issues d'expériences précédentes et de la pratique usuelle en ingénierie : distance constante entre compresseurs, égalité des diamètres, et égalité des pressions d'entrée (resp. de sortie). Le but de cet article est (1) d'énoncer sous quelles hypothèses on peut considérer que ces propriétés sont satisfaites, et (2) de donner une démonstration rigoureuse de ces propriétés (en se basant sur les conditions d'optimalité en programmation non linéaire), dans un cadre plus général que précédemment.

Mots-clés : Réseaux de gaz, pipelines, conception de réseaux, conditions d'optimalité, multiplicateurs généralisés.

Introduction

The gas trunkline system is a long-distance, wide-diameter pipeline system that generally links a major supply source (production area, natural gas processing plants...) with a market area. Between the producing area, or supply source, and the market area, a number of compressor stations are located along the transmission system. These stations contain one or more compressor units whose purpose is to receive the transmission flow (which has decreased in pressure since the previous compressor station) at an intake point, increase the pressure and rate of flow, and thus, maintain the circulation of natural gas along the pipeline.

Compressor units that are used on a natural gas mainline transmission system are usually of the centrifugal (turbine) or reciprocating (piston) type. Most compressor units operate on natural gas (extracted from the pipeline flow); but in recent years, and mainly for environmental reasons, the use of electricity driven compressor units has been growing! .

In the classical sense, the pipeline design problem can be addressed as follows. Suppose a gas pipeline is to be designed to transport a specified quantity of gas per time from the entry point to the gas demand point. Physical and contractual requirements at supply and delivery nodes (mainly minimal and maximal bounds on pressures) are known as well as the costs to buy and lay a pipeline or build a compressor station. In order to minimize the overall cost of creation of this mainline, the following design variables need to be determined: the number of compressor stations, the lengths of pipeline segments between compressor stations, the diameters of the pipeline segments, the suction and discharge pressures at each compressor station.

Therefore, the design of natural gas transmission involves a high number of alternatives.

Edgar et al. [START_REF] Himmelblau | Optimal Design of Gas Transmission Network[END_REF] were the first to apply mathematical programming techniques to such an open-ended problem. They considered the minimization of the total cost of operation per year including the capital cost in their objective function against which the above parameters are to be optimized. The capital cost of the compressor stations was either a linear function of the horsepower or a linear function of the horsepower with a fixed capital outlay for zero horsepower to account for installation, foundation, and other costs. The first cost relationship allowed direct application of non linear programming, but it did require the initial postulation of compressor location. The technique, when converged, indicated which compressor stations should be deleted. They solved the second scenario using the branch and bound technique to handle the integer variables which are the number of compressors. They applied their techniques not only to gunbarrel pipelines but also to branched systems (with fixed branch lengths).

Soliman and Murtagh [START_REF] Soliman | The solution of large-scale Gas Pipeline Design Problems[END_REF] showed that a commercial nonlinear solver (MI-NOS, [START_REF] Murtagh | MINOS 5.5 USERS GUIDE[END_REF]) could be used to solve large instance of the continuous pipeline design problem (without fixed installation outlay) within moderate computing times.

More recently, Babu, Angira, Chakole and Syed Mubeen [START_REF] Babu | Optimal Design of Gas Transmission Network Using Differential Evolution[END_REF] applied Differential Evolution, an evolutionary computation technique, to the same problem and example as Edgar et al. [START_REF] Himmelblau | Optimal Design of Gas Transmission Network[END_REF]. Both scenarios above mentioned have been solved by these population based-search algorithms. They found optimal costs closed to the cost of Edgar et al. but the optimal variables were less close to their bounds than with Edgar et al.

To facilitate the calculation of the design of a pipeline, gas engineers proposed to reduce the high number of alternatives by applying criteria based on previous experiences and/or usual engineering practices. A first class of procedures is a trial and error process among several candidate designs proposed beforehand (Mohitpour, Golshan and Murray [START_REF] Mohitpour | Pipeline Design and Construction -A Practical Approach[END_REF]). For that purpose, Lang [START_REF] Lang | Transmission-System Design[END_REF] highlights the usefulness of simulation softwares to assess what is the best trade-off between compressor costs and pipeline costs. A second approach is to establish some optimal properties to reduce the number of variables. Hence, Cheeseman [START_REF] Cheeseman | How to optimize Gas Pipeline Design by computer[END_REF] states that the compression ratios giving the minimum energy consumption should be equal for each station. Kabirian and Hemmati [START_REF] Kabirian | A strategic planning model for natural gas transmission networks[END_REF] assume that the new compressor stations are located in the middle of pipes.

In the French handbook of Chapon "Design and Construction of gas transportation networks" [START_REF] Chapon | Conception et Construction des réseaux de transport de gaz, Manuel pour le transport et la distribution du gaz[END_REF], the following assumptions are taken: the layout is horizontal, the flowrate Q is constant along the pipeline, the number of compressor stations is known.

Besides, the power is approximated by a specific logarithmic formulation. In this case, Chapon asserts, without proof, that the resolution of the pipeline design problem with differential calculation leads to the following optimal characteristics of the network: diameters are equal on each pipeline segments (including the terminal segments) discharge pressures for all compressor stations are equal to the maximum admissible operational pressure of the pipelines compressor stations are equidistant, and hence, compressor ratios are equal.

Thanks to these properties, the computation is strongly simplified with only two remaining variables to determine: one optimal diameter and one optimal compression ratio for the whole pipeline. Then, it is only necessary to select the right number of compressor station which minimizes the associated costs. Bouckly [START_REF] Boucly | Conception optimale d'un réseau de transport, Support de formation "Information sur le transport et le stockage du gaz naturel[END_REF] presents a partial proof of the above properties but the arguments were not very clear and always limited to the Chapon's framework. In his Ph degree, Hafner [START_REF] Hafner | Gaz naturel et production d'électricité : analyse technologique et économique de la génération d'électricité et du transport de gaz pour les pays du bassin méditerranéen[END_REF] does not discuss the validity of these assertions and only details the calculation steps of the two last remaining variables. More recently, Ainouche [START_REF] Ainouche | Economic Comparison of a number of Gas Supply Routes, 19th World Energy Congress[END_REF] based his cost analysis on the same properties.

As the best of our knowledge, no paper has been published to give a theoretical proof of these optimal properties. The goals of this paper are to state on which assumptions we can consider that the optimal properties are valid and to propose a solid proof of the optimal properties (based on nonlinear programming optimality conditions) within a more general framework than before.

Physical Background

A gas network is made of pipelines and compressor stations. In this part, physical rules are recalled as well as simplifications made for design purposes.

Pipes

Let us consider the physical parameters related to a single pipe: Q, the flowrate in a pipe, π i , the inlet square pressure (or inlet head) of the pipe, π o , the outlet square pressure (or outlet head) of the pipe, L, the length, D the internal diameter of the pipe.

Let us write the Weymouth equation [START_REF] Katz | Handbook of Natural Gas Engineering[END_REF], [START_REF] Mohitpour | Pipeline Design and Construction -A Practical Approach[END_REF] modeling the pressure loss on a pipe element:

π i -π o = K 1 .d.T.Z av (π i , π o ).λ(Q, D).Q 2 . L D 5 (1)
with K 1 (constant) function of P 0 , standard pressure, T 0 , standard temperature and ρ A , the mass density of dry air, d, the gas specific gravity compared with air, T , the gas temperature, Z av (π i , π o ), the average gas compressibility factor, function of the suction and discharge pressures. Its expression is as follows, where C < 0 is a constant and the average pressure P av , defined as P av = 2 3 [START_REF] Mohitpour | Pipeline Design and Construction -A Practical Approach[END_REF]:

P i P o P i +P o
Z av = 1 + C.P av (π i , π o ) (2)
λ(Q, D), the friction factor depending on the diameter and the flow regime (laminar flow, mixed or transition flow, or fully turbulent flow),

In this paper, β = K 1 .d.T.Z av (π i , π o ).λ(Q, D) will be considered as a constant regarding the inlet and outlet pressures and the diameter. this reasonable assumption for design purpose has been made in previous papers as Edgar et al. [START_REF] Himmelblau | Optimal Design of Gas Transmission Network[END_REF]. The drop pressure equation will be written as follows:

π i -π o = β.Q 2 . L D 5 (3)

Compression Power

Let us define π s , the suction square pressure and π d , the discharge square pressure. The power of an adiabatic compressor is given by this formula [START_REF] Katz | Handbook of Natural Gas Engineering[END_REF], [START_REF] Mohitpour | Pipeline Design and Construction -A Practical Approach[END_REF]:

Ŵ = 1 η ad .K 2 .T s .Z av (π s , π d ). γ γ -1 .Q. ( π d π s ) γ-1 2γ -1 , (4)
with Z av defined above (see (2)), and:

K 2 (constant) function of P 0 , standard pressure and T 0 , standard temperature, γ, the specific heat ratio, η ad , the efficiency constant and T s , the inlet temperature,

This power is adjusted to recover ISO conditions at 15 o C:

W = Ŵ pf 1 .pf 2 .pf 3 (5)
with pf 1 = 0.95, pf 2 = 0.97, pf 3 = 0.98. By setting average values for these factors, the compression horsepower can be written as follows:

W = γ 1 .Q. ( π d π s ) γ 2 2 -1 , (6)
Mandatory pressure drops at the entry and the exit of a compressor station are assumed to be negligible. If several compressors are available in a same compressor station, the total horsepower is the sum of the power of each compressor.

Mathematical Programming Background

Since our method consists in solving the first-order necessary optimality conditions, we will in this section give a brief account of them. Consider the following nonlinear programming problem with equality, inequality and bound constraints:

       min x∈R n f (x) g i (x) = 0, i = 1, . . . , p h i (x) ≤ 0, i = 1, . . . , q x j ≤ x j ≤ xj , j = 1, . . . , n, (7)
where f : R n → R and g : R n → R p are C 1 mappings, and x j < xj , j = 1, . . . , n.

The Lagrangian function in non-qualified form associated with this problem is

L(x, η, θ, u, v) := η 0 f (x) + p i=1 θ i g i (x) + + q i=1 η i h i (x)+ n j=1 (u i (x i -x i ) + v j (x i -xi )) . (8)
Its derivative w.r.t. the primal variable is

∇ x L(x, η, θ, u, v) = η 0 ∇f (x) + u p i=1 θ i ∇g i (x) + q i=1 η i ∇h i (x) -u + v. ( 9
)
We say that (θ, η, u, v) is a generalized Lagrange multiplier associated with x ⋆ ∈ R n is the following holds:

       η ≥ 0; u ≥ 0; v ≥ 0; |η| + |θ| + |u| + |v| > 0; ∇ x L(x ⋆ , η, θ, u, v) = 0; g(x ⋆ ) = 0; h i (x ⋆ ) ≤ 0; η i h i (x ⋆ ) = 0; i = 1, . . . , q; x j ≤ x ⋆ j ≤ xj ; u j (x ⋆ j -x j ) = v j (x j -x ⋆ j ) = 0, j = 1, . . . , n. (10)
The set Λ G (x ⋆ ) of generalized Lagrange multipliers associated with x ⋆ is a polyhedral convex cone; if η 0 = 0 then we say that (η, θ, u, v) is a singular multiplier; otherwise, when η 0 = 1 we say that (η, θ, u, v) is a Lagrange multiplier, the set of which is denoted Λ L (x ⋆ ). The Mangasarian-Fromovitz qualification hypothesis [START_REF] Mangasarian | The Fritz-John necessary optimality conditions in the presence of equality and inequality constraints[END_REF] is

   Dg(x ⋆
) is onto, and there exists d ∈ KerDg(x ⋆ );

∇h i (x ⋆ ) • d < 0, if h i (x ⋆ ) = 0, j = 1, . . . , q, d j > 0 if x j = x j ; d j < 0 if x j = xj , j = 1, . . . , n. (11)
This is desirable property, as shows the following well-known result, see [START_REF] John | Extremum problems with inequalities as subsidiary conditions[END_REF], [START_REF] Mangasarian | The Fritz-John necessary optimality conditions in the presence of equality and inequality constraints[END_REF] and [6, Section 5.2]. [START_REF] Gill | SNOPT:An SQP Algorithm for Large-Scale Constrained Optimization[END_REF] holds iff one of the following conditions holds: (a) the set Λ L (x ⋆ ) of Lagrange multiplier is nonempty and bounded, (b) the set of singular multipliers is empty.

Lemma 1. If x ⋆ is a local solution of (P ), then (i) Λ G (x ⋆ ) = ∅, and (ii) Con- dition (
It may be more effective to express the optimality conditions in term of the restricted Lagrangian function (in which the bound constraints are not dualized):

L R (x, η, θ) := η 0 f (x) + p i=1 θ i g i (x) + q i=1 η i h i (x). (12)
Denote by Λ RG (x ⋆ ) the set of reduced generalized multipliers, i.e., couples

(η, θ) ∈ R p × R q such that (η, θ, u, v) ∈ Λ L (x ⋆ ), for some (u, v) ∈ R n × R n . When η 0 = 1, we also call Lagrange multipliers the elements of Λ RG (x ⋆ ). It is easily checked that (η, θ) ∈ Λ RG (x ⋆ ) iff        g(x ⋆ ) = 0; h i (x ⋆ ) ≤ 0; η i h i (x ⋆ ) = 0; i = 1, . .

. , q;

For all 1 ≤ j ≤ n :

∂ ∂x j L R (x ⋆ , η, θ)    ≥ 0 if x ⋆ j = x j ; ≤ 0 if x ⋆ j = xj ; = 0 otherwise. ( 13
)
We will say that x ⋆ is a critical point of problem [START_REF] Boucly | Conception optimale d'un réseau de transport, Support de formation "Information sur le transport et le stockage du gaz naturel[END_REF]

if Λ G (x ⋆ ) = ∅, and that x ⋆ is a nondegenerate critical point of problem (7) if Λ L (x ⋆ ) = ∅.

Problem Formulation

Our goal is to determine the least-cost configuration of a pipeline (with compressors) linking one supply node to one delivery point without any withdrawals and assumptions on the compressor station location.

Let us define a "section" k, as the association of a pipe followed by a compressor station to offset the pressure drop. The compression occurs at the outlet of the section. There is no loss of generality in assuming such a structure, since either the compression ratio can be taken equal to 1, or the length of a section can be zero.

Objective function

The cost model will be equivalent to the model used by Edgar et al. [START_REF] Himmelblau | Optimal Design of Gas Transmission Network[END_REF], Boucly [START_REF] Boucly | Conception optimale d'un réseau de transport, Support de formation "Information sur le transport et le stockage du gaz naturel[END_REF] or Soliman et al. [START_REF] Soliman | The solution of large-scale Gas Pipeline Design Problems[END_REF]. The objective function comprises the sum of terms for each section consisting of the annualized capital cost of the pipe and compressor, and the operating cost of the compressor.

The annualized capital costs for each pipeline section depend linearly on the pipe diameter and length with a factor α p , the amortization factor reducing the capital cost to an annual cost.

C pipe = α p LD (14)
Operating and maintenance charges for a compressor station are directly related to the horsepower O c . The capital cost of a compressor station is divided into two parts: an initial fixed installation outlay B, a cost increasing with the power: C c W , where C c is the compressor capital cost per unit horsepower.

The function ϕ of compression costs yielded by the installation of a compressor station is then given by:

C comp = ϕ( π d π s ) = α c W ( π d π s ) + B, (15)
where α c = O c + C c represents both annualized capital cost and operating cost per unit horsepower. Let us note some generic properties:

ϕ : [1, ∞) → R; ϕ ′ (t) > 0, t ∈ [1, ∞). (16)
where by ϕ ′ we denote the derivative of ϕ. In particular, the cost of compression is increasing with the square compression ratio ρ := π d π s , and the latter is greater or equal to 1.

The problem is to find the number n of compressor stations, diameters D k , section length L, and suction and discharge pressures (π s k , π d k ) that to minimize the charges to lay pipes and/or build compressor stations:

φ(D, L, π s , π d ) := n k=1 α p L k D k + ϕ π s k π d k . (17)
Note that, for fixed n, the constant B plays no role in the minimization problem.

Constraints

We adopt the following notations:

π d k-1 :
inlet head of section k, equal to the discharge head of the previous upstream section k -1, π s k : outlet head of section k, is the suction head of the compressor station of that section.

β ′ := βQ 2 , a fixed coefficient.
With these notations, the pressure drop equation on section k is as follows:

π d k-1 -π s k = β ′ L k D σ k , k = 1, . . . , n, (18)
where the input head π d 0 and output head π d n are given, and σ ≈ 5 for gas networks. Since other values may be used for different fluids, and our results hold with an arbitrary value, we adopt this more general law. On every compressor station, the discharge pressure cannot be less than the suction pressure:

π s k ≤ π d k , k = 1, . . . , n. (19)
In this model the square compression ratio ρ k := π d k /π s k on section k has no other upper bound that the one deriving from pressure bounds. The sum of length of section must equal the distance ℓ between the supply node and the delivery point:

n k=1 L k = ℓ. (20)
In addition, upper and lower bounds are set on diameters and pressures:

0 < D min ≤ D k ≤ D max , π min ≤ π s k ≤ π max , π min ≤ π d k ≤ π max , k = 1, . . . , n (21)
with D max , the maximal commercial diameter proposed by the contractors of a gas transportation company, P 0 , standard pressure, and M OP , the maximum operational pressure of the pipes equal for every section. We denote π min := P 2 0 , π max := M OP 2 . Note that the lower bound D min must be upper than 0 to avoid division by zero in the pressure drop relationship.

As boundary conditions, we consider in this paper that the first inlet pressure and the last outlet pressure are given.

Program

The program to solve is then the following (writing first equality constraints, then bound constraints and ending by general inequality constraints):

                                 min D,L,π s ,π d φ := n k=1 α p L k D k + ϕ k π d k π s k β ′ L k D σ k -π d k-1 + π s k = 0, k = 1, . . . , n (a)
ℓ -

n k=1 L k = 0 (b) π d 0 = πd 0 π d n = πd n ; (c) π s k -π d k ≤ 0, k = 1, . . . , n (d) D min ≤ D k ≤ D max , k = 1, . . . , n (e) π min ≤ π s k ≤ π max , k = 1, . . . , n (f ) π min ≤ π d k ≤ π max , k = 1, . . . , n -1 (g) (22)
By taking a compression cost function ϕ k with minimal properties, this model is generic enough to be applied to any pipeline design problem.

Necessary optimality conditions

In the sequel, we consider π d 0 and π d n as data (and not optimization variables). Let us introduce the Lagrangian multipliers λ, µ and η respectively associated to pressure drop, total length and compression constraints.

Let us write the restricted Lagrangian function (without the bound constraints on the variables) of program (22):

L(D, L, π s , π d , λ, µ, η) = η 0 n k=1 α p L k D k + ϕ k π d k π s k + n k=1 λ k β ′ L k D σ k -π d k-1 + π s k +µ ℓ - n k=1 L k + n k=1 η k π s k -π d k . (23)
For later use, we note the expressions of the partial derivatives of the Lagrangian w.r.t. primal variables (reminding that

ρ k := π d k /π s k ): ∂L ∂L k = η 0 α p D k + λ k β ′ D σ k -µ, k = 1 . . . , n, (24)
∂L ∂D k = η 0 α p L k -σβ ′ L k λ k D σ+1 k = L k η 0 α p -σβ ′ λ k D σ+1 k , k = 1 . . . , n, (25)
∂L ∂π s k = -η 0 π d k (π s k ) 2 ϕ ′ k (ρ k ) + λ k + η k , k = 1 . . . , n, (26)
∂L ∂π d k = η 0 π s k ϕ ′ k (ρ k ) -λ k+1 -η k , k = 1 . . . , n -1. ( 27
)
Our analysis will be based on the first-order optimality system. In most cases it allows to compute the optimal design of the network. There are some singular situations, however, where the optimality system provides no much information Example 2 (Special case 1). Assume that π d 0 = π min . Then, in view of the drop equation, L 1 = 0 and π s 1 = π min . Take µ = 0 and all components of λ and η equal to zero, except for λ 1 > 0. Then the equation of a critical point are satisfied, but we get no useful information on the solution.

Example 3 (Special case 2). Assume that π d n = π min . Then, in view of the drop equation, π s n = π min . Take µ = 0 and all components of λ and η equal to zero, except for η n > 0. Again the equation of a critical point are satisfied, but we get no useful information on the solution.

The remedy for what we will call these two special cases is obvious:

In case 1, consider L 1 = 0 and π s 1 = π min as data, and take into account the equality (22)(a) for k = 2 to n -1 only. In addition we can assume that the first compressor is active, and hence,

π s 1 < π d 1 and η 1 = 0. ( 28
)
In case 2, consider π s n = π min as data, and take into account constraint (22)(d) for k = 1 to n -1 only.

Of course then the partial derivatives of the Lagrangian corresponding to deleted variables and multipliers associated to deleted constraints should not be taken into account.

We are going to prove the following properties of an optimal network. Denote the set of sections with positive lengths by

I L := {1 ≤ i ≤ n; L i > 0}. ( 29
)
Theorem 4. For the optimal number n of compressor stations, the only degenerate (with η 0 = 0) solution of the necessary optimality conditions, is when all diameters have their maximal value, all suction (resp. discharge) pressures have their minimal (resp. maximal) value (except of course for the given final discharge pressure), and if compressors are identical, all section lengths (except possibly for the first and last ones) are equal.

Theorem 5. For the optimal number n of compressor stations, the nondegenerate (with η 0 = 1) solutions of the necessary optimality conditions have the following structure:

Proof of the main results

The proof is based on a sequence of lemmas. We first eliminate a degenerate case. We give the proof for the general case, and indicate in brackets the modifications for the special cases.

Lemma 6. A degenerate critical point is such that µ = 0.

Proof. Assume on the contrary that

η 0 = µ = 0. For 1 ≤ k ≤ n [2 ≤ k ≤ n in case 1], by (24), λ k = 0 if L k > 0, and λ k ≥ 0 if L k = 0. Let us prove by contradiction that η k = 0, k = 1, . . . , n. Assume on the contrary that η k > 0, for some 1 ≤ k ≤ n [with k ≤ n -1 in case 2]. Since λ ≥ 0, (26)-(27) imply that π s k = π min , π d k = π max (the latter if k ≤ n -1). ( 30
)
Since π d n > π min , we deduce that π s k < π d k , k = 1, . . . , n, contradicting for η k > 0. So we have proved that η = 0.

We next prove that λ = 0. Assume on the contrary that λ k = 0, for some We have proved that (η, λ, µ) = 0, therefore we must also have (u, v) = 0, i.e., all multipliers associated with bound constraints also must be zero. But this contradicts the definition of a generalized multiplier. Lemma 7. For any critical point, over sections with positive length, all diameters D k (resp. multipliers λ k ) have a constant value D * (resp. λ * ), that satisfy

1 ≤ k ≤ n [2 ≤ k ≤ n in
-λ * β ′ (D * ) σ+1 = η 0 α p - µ D * . ( 31
)
Proof. Let k ∈ I L . Since L k has no upper bound, ∂L ∂L k = 0, and hence,

-λ k β ′ D σ+1 k = η 0 α p - µ D k . ( 32
)
Substituting this expression in (25), and setting δ(

D k ) := (L k ) -1 ∂L ∂D k , obtain δ(D k ) = η 0 α p (1 + σ) -σ µ D k . (33)
Note that this function does not depend on k, and cannot be identically zero since η 0 > 0 or µ = 0 by the previous lemma. If δ(D) is positive (negative) over (D min , D max ), then all diameters are equal to their lower (upper) bounds. If on the contrary δ(D) changes of sign over [D min , D max ], then η 0 > 0, and then we may take η 0 = 1, µ > 0, and δ(D) has a unique zero D η0,µ := σµ/(α p (1 + σ)).

In addition, δ(D) is an increasing function. In view of (13), it follows that D k = D ⋆ η0,µ , where

D ⋆ η0,µ = max(D min , min(D η0,µ , D max )), (34)
proving that all diameters are equal. That the same holds for the λ k follows from (32).

Remark 8. For all sections of positive length, since (24) equals zero, the multipliers λ k have the same value

λ * = (D ⋆ η0,µ ) σ β ′ (µ -η 0 α p D ⋆ η0,µ )). ( 35
)
In particular, if the diameters are out of bound, then

λ k = α p σβ ′ σµ (σ + 1)α p (σ+1) = λ, k ∈ I L . (36)
The previous result has an important consequence. We may, and will do in the sequel of the paper, set the diameters of zero length sections to the same value as the one of positive sections; this changes neither the solution, nor (in view of (25)) the associated set of generalized multipliers. If two sections are separated by one or several non active compressors, since these sections have equal diameters, they can be viewed as a single section. We have proved the following:

  
For the optimal n, we may assume without loss of generality that all diameters are equal and that all compressors, except perhaps for the last one, are active.

(37) So in the sequel we will assume that:

π s k < π d k and η k = 0, k = 1, . . . , n -1. ( 38
)
Proof of theorem 4. Assume that η 0 = 0. Then µ = 0 by lemma 6. For k ∈ I L , in view of (24), we have that λ k = 0, and by lemma 7 its value is a constant λ * over I L . If λ * < 0, then for k ∈ I L , k < n, (26) combined with (38) would imply that π s k attains its upper bound, which cannot happen since compressors are running. So λ * > 0, and also µ > 0 by (31). Consequently, for a section k of length zero, since ∂L ∂L k ≥ 0, we also have λ k > 0. Using (25)-( 27), we obtain that for k ∈ I L , ∂L ∂D k < 0, so that we may assume that diameters reach their maximal value in all sections, and for any k, ∂L ∂π s k > 0, and

(if k ≤ n -1) ∂L ∂π d k-1
< 0, so that all suction (resp. discharge) pressures have their minimal (resp. maximal) value. The latter proves that all sections have a positive length. If compressors are identical, then by the drop equation, for k < n, lengths are equal. The result follows.

So η 0 = 0 corresponds to the limiting case when, for fixed n, the maximum of resources must be used in order to comply with the constraints. In the sequel we will assume that η 0 = 1 in order to compute the nondegenerate solutions. Lemma 9. For any nondegenerate critical point, discharge pressures reach their maximal values for all sections of positive length (except perhaps for the last one):

π d k = π max , for all k ∈ I L , k < n. (39)
In addition, any section of positive length is followed by a section of positive length (except perhaps for the last one).

Proof. Adding (26) and ( 27), obtain for k < n

∂L ∂π s k + ∂L ∂π d k = 1 π s k ϕ ′ k (ρ k ) 1 - π d k π s k + λ k -λ k+1 . (40)
Since by (24), ∂L ∂L k in increasing w.r.t. λ k , we have that λ k = λ * ≤ λ k+1 , and hence, since ϕ ′ k (ρ k ) > 0 and π s k < π d k by (37), the r.h.s. of the above display is negative. Hence, at least one of the two partial derivatives is negative, which implies that one variable is at its upper bound. Since

π s k < π d k ≤ π max , we have that ∂L ∂π s k ≥ 0. Therefore ∂L ∂π d k < 0.
This proves (39). If, for 1 < k < n, section k -1 is of positive length and section k is of zero length, the latter has an active compressor with a maximal suction pressure, which is impossible. The result follows.

So it is possible that sections say 1 to k 0 have zero length. We now study this situation.

Lemma 10. Assume that sections 1 to k 0 have zero length. If the model of compressors satisfies (6) and (15), then the compression ratio is constant, for sections 1 to k 0 .

Proof. It suffices to check that, if k 0 ≥ 2, then ρ 1 = ρ 2 . Set a i = (ρ i ) γ2/2 and b = a 1 a 2 . Given b corresponding to the compression ration over the two first sections, the minimization of cost of compressors over these sections imply that (a 1 , a 2 ) are solution of the problem

min a a 1 + a 2 ; a 1 a 2 = b, ( 41
)
whose solution is a 1 = a 2 = √ b. The result follows.

Remark 11. Note that, if the constant B in ( 15) is equal to zero, in view of the identity

a 1 a 2 -1 ≥ (a 1 -1) + (a 2 -1) (42)
we see that it is more economical to use two compressors instead of one. For fixed B, this will remain true if the compression ratio is high. In the real world, the initial pressure usually has a high level, and zero length sections should not be expected.

Lemma 12. For any nondegenerate critical point, all components of λ are positive over sections with active compressors, and if compressors are identical (so we write ϕ instead of ϕ k ) and the following hypothesis holds:

π s k → π max (π s ) 2 ϕ ′ π max π s k is decreasing, (43)
then suction pressures are equal on sections of positive length, except perhaps for the last one:

π s k = π s k+1 , for all k = 1, .., n -1. ( 44
)
Proof. For sections with active compressors, η k = 0 and π s k does not reach its upper bound, and hence, by (26):

0 ≤ ∂L ∂π s k = - π d k (π s k ) 2 ϕ ′ k π d k π s k + λ k , (45)
implying λ k > 0. In addition, if k ∈ I L , and k < n, then (45) reduces to

0 ≤ ∂L ∂π s k = - π max (π s k ) 2 ϕ ′ k π max π s k + λ * , (46)
By (43) the r.h.s. is an increasing function of π s k , identical for all sections of positive length. By [START_REF] John | Extremum problems with inequalities as subsidiary conditions[END_REF] there is no more than one possible solution satisfying the sign conditions if a bound is active. The result follows.

Remark 13. Hypothesis (43) holds when the model of compressors satisfies [START_REF] Bonnans | Perturbation analysis of optimization problems[END_REF] and [START_REF] Katz | Handbook of Natural Gas Engineering[END_REF]. Indeed, we have that ϕ

′ k (ρ) = α c γ 1 .Q. γ2 2 .ρ γ 2 2 -1 = M 1 .ρ γ 2
2 -1 with M 1 > 0, and hence,

∂L ∂π s k = - π max (π s k ) 2 .M 1 .( π max π s k ) γ 2 2 -1 + λ = - M 2 (π s k ) 1+ γ 2 2 + λ (47)
with M 2 > 0 independent of the section k.

Proof of theorem 5. The information on the possibly first sections of zero length is provided by lemma 10. By lemma 7, all sections have the same diameter, and by lemma 9, discharge pressures reach their maximal values for all sections of positive length except perhaps for the last one. If compressors are identical and satisfy ( 6) and ( 15), then by lemma 12 and remark 13, suction pressures are equal over sections k 0 + 1 to n -1; by the drop equation, it follows that lengths are equal over sections k 0 + 2 to n -1. The result follows.

Optimal Values

We have proved that an optimal gas transmission mainline is as follows. Excluding the case of initial sections with zero length, and assuming compressors to follow the model ( 6) and ( 15), we have that:

(P 1 ) diameters are all equal and all compressors are running (except perhaps for the last one).

(P 2 ) discharge pressures are equal to their maximal values (except perhaps for the last one).

(P 3 ) suction pressures are equal.

(P 4 ) compressor stations are equidistant (except perhaps for the last one).

In particular, if both the input head and output head are equal to the maximal value:

π d 0 = π d n = M OP, (48)
we have the following:

(P ′ 1 ) diameters are all equal and all compressors are running.

(P ′ 2 ) discharge pressures are equal to their maximal values.

(P ′ 3 ) suction pressures are equal.

(P ′ 4 ) compressor stations are equidistant When (48) holds, a quick way for computing the solution of problem ( 22) is therefore to solve the following problem, that involves only two scalar variables ρ and D:

         min (D,ρ) φ := α p ℓD + nϕ(ρ) subject to: (a) 0 = β ′ ℓ D σ -nπ max (1 -1/ρ), (b) ρ > 1, (c) D min ≤ D ≤ D max . (49)
Consider the Lagrangian function of this program, where λ ∈ R is the multiplier associated with the pressure drop equation (49 a):

L(D, ρ, λ) := φ(D, ρ) + λ β ′ ℓ D σ -nπ max (1 -1/ρ) . ( 50
)
If D is out of bounds, the following first-order optimality conditions are:

           (i) ∂L ∂D = α p ℓ -σλ β ′ l D (σ+1) = 0, (ii) ∂L ∂ρ = nϕ ′ (ρ) -nλ π max ρ 2 = 0, (iii) ∂L ∂λ = β ′ ℓ D σ -nπ max (1 -1/ρ) = 0. (51)
The primal variables can be expressed as functions of the dual variable. Nevertheless, we have to detail the formulation of the compressor power to establish these relationships. In the case of ϕ = α c γ 1 Q(ρ γ2/2 -1) formulated with the classical manner (as mentioned in the part "Physical Background"), then conditions (i)-(ii) can be written as follows:

     (i) D(λ) = ( σβ ′ α p λ) 1/(σ+1) , (ii) ρ(λ) = ( π max α c γ 1 Q γ2 2 λ) 2 2+γ 2 . ( 52
)
By substituting these expressions into the constraint (iii), a nonlinear equation is to solve in λ:

β ′ l D(λ) σ -nπ max (1 -1/ρ(λ)) = 0 (53)
This one-dimensional equation can be computed numerically at low cost. Once λ is computed, the values of D and ρ follow by (52).

Numerical verifications

In order to check that the properties aforementioned are true, we propose in this section to run some tests on very simple networks by solving the program (22). Solving this program will be made with the continuous non linear solver SNOPT ( [START_REF] Gill | SNOPT:An SQP Algorithm for Large-Scale Constrained Optimization[END_REF]).

A gunbarrel network

Available cost data in the literature are scarce. We choose to take those from Edgar ( [START_REF] Himmelblau | Optimal Design of Gas Transmission Network[END_REF]) in Imperial Units. To stick to the notations from the modeling part of this paper, the values are the following:

C comp = α c W ( π d π s ) + B.
To be consistent with these cost data, we choose to use hereafter only imperial units. In that case, β = 10 12 871 2 and σ = 16/3 for the pressure drop equation and γ 1 = 214.98, γ 2 = 0.1939 for the compression power equation (that will be expressed in horsepower). Upper bounds on compression rates are set to 2.

Let us take the design of a trunkline of 150 miles (around 241 km) with a maximal operating pressure of 1000 psia (close to 68.7 bars) what is a very common MOP on the French Transmission Network. The expected flowrate is 600 Million Cubic Feet a Day (roughly 17 Million Cubic Meter a Day).

In the following tests we denote the inlet and outlet pressures by P in := π d 0 and P out := π d n . These tests will assess the use the methodology proposed in this paper.

Case 1 P in

= P out = M OP
Let us begin with the simplest framework with P in = P out = M OP . It is therefore assumed that one part of the compression work has been done at the upstream of the pipeline. In that case, thanks to equations (52) and (53), calculation of the unique diameter (P ′ 1 ) and the unique compression rate (consequence of (P ′

2 ) -(P ′ 3 )) are rather straightforward (with the use of function fzero of MATLAB finding the root of a continuous function of one variable) and results are given in Table 1. Then, by applying the optimal properties (P ′

2 ) -(P ′ 4 ), it is easy to build the pressure profile along the pipeline. Figure 1 shows the associated pressure evolution along the pipeline from 1 to 4 compressor stations. For one compressor, all the compression work is located at the very end of the pipeline. For more than one compressor, compressor stations are regularly placed and discharge pressures of in-between compression are equal to t! he MOP.

The output of the SNOPT solver are exactly matching with these "near analytical" results. Not to start from the optimal solution, initialization of the solver has been made with points rather far from the optimal value. For example, by taking the initial values of lengths at 20 % for the first section and the remaining sections equally located to fill the gap up to 100 % of the total length whatever the number of compressor stations is. Initial diameters are set to the maximal available commercial sizes of 50 inches. The solver always converged.

Evolution of costs with respect to the number of compressors can be seen in Figure 2. First, we can observe that, compression costs make up only 10% of the total investment cost. Second, while the number of compressor is increasing, the unit compression rate is decreasing and the compression cost is increasing. Third, although the cost of compression is increasing, the overall investment cost is slightly decreasing due to the savings yielded on the pipelines. The lesson learnt is the following: the more the number of compressors, the cheaper the cost. This phenomenon mainly comes from the lack of initial outlay in this example what gives incentives to investments in compression. In this case, we consider that the input pressure is equal to the output pressure but, on the contrary of the previous case, these pressures are lower than the MOP of the pipe. For example, let us take P in = P out = 750 psia. First of all, we solved this problem with SNOPT. Results are displayed on the figure 3. We can see that the properties (P 1 ) -(P 4 ) are satisfied. Especially, for the first section, the first decision is to compensate for the lack in pressure with a near-zero length section in order to reach the maximal operating pressure. All following discharge pressures behave in the same way except at the delivery point where compression does not occur. On table 2, the property of equal diameters is well observed with a same diameter proposed on every section. Eventually, the equal repartition of compressor stations does not appear with a concentration of the compressor stations in the first half of pipeline (where they are equidistant). The explanation lies in the condition P out < M OP which is not taken into account in the program (22). The special cases where the inlet and outlet pressures are at their minimal bounds have been discussed in part 5 and the proposed remedy was to consider that the first and the last sections have been previously designed to reach the maximal values of the inlet and outlet pressures. ¿From a practical point of view, we propose hereafter a method where we can apply the fast calculations proposed in part 7 and used for the previous case:

Number of

1. for the first section, we just have to compensate for the lack in pressure with a zero length section.

2. for the remaining sections, we have to determine the optimal location of the last active compressor. To approximate this location, we can take this length as the total length of a partial pipeline (bounded with the true total length) and find, for each length, on the upstream side, the optimal unique diameter and compressor ratio with the equations of part 7 and, on the downstream side, the corresponding diameter is directly determined from the knowledge of the remaining length, the inlet pressure and the outlet pressure.

3. place the compressor stations at equal distance from each other before the last compressor station location.

We can use this methodology for P out < P in = M OP , which is often the case in network design problems.

A tree network

A tree network has been particularly studied in the literature [START_REF] Babu | Optimal Design of Gas Transmission Network Using Differential Evolution[END_REF][START_REF] Himmelblau | Optimal Design of Gas Transmission Network[END_REF][START_REF] Soliman | The solution of large-scale Gas Pipeline Design Problems[END_REF]. The topology of this network is shown on Figure 4. This network is made of 3 branches (the first feeding the 2 downstream branches) and the lengths of each branch are respectively 163, 8, 33 miles. Demand on delivery nodes at the end of branches 2 and 3 are 300 MCFD. Cost data are the same as for the gunbarrel network.

We propose to apply the principles and methods described for gunbarrel networks to this tree network. The unknown variable of this problem is the pressure at the connection node located between the upstream branch and the 2 downstream branches (node 4 in this network). So, once this variable is set, we can split the design problem into 3 independent gunbarrel networks design problems for each branch and apply the methods previously shown. To double check the validity of the approach, we compute the local optimal solution with SNOPT as it has been made for the previous example.

On figures 5,6 and 7, we can see the results of the application of the methods with the pressure profile with respect to the variation of the connection pressure 4 from 500 psia (under the minimal pressure required at the end of branch 2) and 1000 psia (maximal operating pressure) with a step of 20 psia. On branch 1, we can see that compression is necessary to offset the pressure losses due to the length of this line. As for the case 2 of the previous example, properties 1,2,3 are fulfilled and property 4 is only visible when the pressure at node 4 reaches the maximal authorized pressure. On branches 2 and 3, compression facilities are not activated except for compression on node 4 for inlet pressures from upstream below 640 psia where compression is required to get pressures upper than 600 psia at the delivery node. Note that one of the main assumption to see properties 2, 3 and 4 was the activation of the compressor stations.! Therefore, these properties are not seen but property 1 appears with a same diameter for each branch.

On figure 8, we can track the cost evolution regarding the pressure at the connection node 4. First, we can note the continuous U-shape of this cost function. The first decreasing part of the function comes from the strong cost reduction on downstream branches 2 and 3 yielded by the increase of the inlet pressure number 4. But, above 640 psia, this reduction is not enough to counterbalance the cost increase on branch 1 where the required terminal pressure is always increasing. The total minimal cost is reached at 7.017 M°(for a pressure of 640 psia) what is slightly better than the best solution from [START_REF] Soliman | The solution of large-scale Gas Pipeline Design Problems[END_REF] of 7.038 M°. It could be explained with the use of 2 intermediate compressor stations on Branch 1 instead of only one considered in the previous papers. This choice has been made to show the equal repartition of the compressors (Property 4) along the pipeline.

The detailed optimal solution is given in Table 3. Note that, at this overall optimal point, the results of theorem 5 are verified on branches 2 and 3 with zero length sections located at the beginning of the branch (due to high enough pressure at the inlet of the section).

Conclusions

In this paper, thanks to the mathematical programming framework, we have proved on solid grounds that most of the usual practices of pipeline engineers (on supply and delivery given pressures) have to be carefully considered before applying these principles. Hence, an high enough pressure at the inlet of a pipeline can make compression unuseful and properties on compression will not appear (with apparition of zero length sections). In case of required delivery pressure lower than the maximal operating pressure, the equidistant location property can not be applied to the last section. These properties have been checked with numerical tests on small gas networks. On going works are focused on extending these properties to a more realistic problem (with fixed pipeline segments lengths or withdrawals along the pipelines) and to use the theoretical results on larger numerical examples.

( i )

 i Sections 1 to say k 0 have zero length (possibly with k 0 = 0, i.e., no section has zero length). If the model of compressors satisfies (6) and (15), then the compression ratios ρ k , for k = 1 to k 0 , have the same value ρ, (ii) All sections have the same diameter, and sections k 0 + 1 to n -1 have the same maximal discharge pressure.(iii) If the model of compressors satisfies (6) and (15), then sections k 0 + 1 to n -1 have the same suction pressure π s * , and sections k 0 + 2 to n -1 have the same positive length L * .

  case 1]. Since η = 0, by (24), L k = 0, and hence by the drop equation π s k = π d k-1 . We see that when k = 1, since π d 0 > π min , we have that π s 1 > π min , in contradiction with (26) for k = 1. when k > 1, since π s k = π d k-1 , these two variables cannot both reach their bounds, in contradiction with (26)-(27) (the latter at index k -1).

  the amortization factor α p =870 °per miles per inches (in C pipe = α p LD) operating and maintenance charges for a compressor station O c = 10 °per horsepower. the initial fixed installation outlay from a compressor station B = 0, the capital cost of a new installation C c = 70 °per horsepower. which gives α c = 80 °per horsepower in

Figure 1 :Figure 2 : 8 . 1 . 2

 12812 Figure 1: Gunbarrel Network-Case 1: Pressure evolution with P in = P out = M OP = 1000 psia

Figure 3 :

 3 Figure 3: Gunbarrel Network-Case 2: Pressure evolution with P in = P out = 750 psia < M OP = 1000 psia

Figure 4 :

 4 Figure 4: TREE NETWORK TOPOLOGY (example from [4, 10, 20])

Figure 5 :

 5 Figure 5: Tree Network: Pressure evolution on Branch 1 with variation of interconnection pressure 4 Branch Number

Figure 6 :

 6 Figure 6: Tree Network: Pressure evolution on Branch 2 with variation of interconnection pressure 4

Figure 7 :Figure 8 :

 78 Figure 7: Tree Network: Pressure evolution on Branch 3 with variation of interconnection pressure 4

Table 1 :

 1 Gunbarrel Network-Case 1: Optimal Characteristics with several compressors

		Diameter	Compression Costs (M°)
	Compres-	(inches)	rate
	sors
	1	34.55	1.34	5.11
	2	33.05	1.18	4.98
	3	32.48	1.12	4.93
	4	32.18	1.09	4.91
	5	32	1.07	4.89

Table 2 :

 2 Gunbarrel Network-Case 2: Optimal Characteristics with several compressors given by SNOPT

	Number of	Diameter	Compression Costs (M°)
	Compres-	(inches)	rates*
	sors
	1	34.55	1.79	5.112
	2	32.37	1.23	5.030
	3	31.91	1.13	5.014
	4	31.71	1.09	5.008
	5	31.6	1.07	5.004
	*(except the inlet compression for more than one compressor)

Table 3 :

 3 Tree Network: Detailed features of the optimal solution

RR n 6791