arXiv:1106.3977v3 [] 23 Jun 2011

Models, Calculation and Optimization of Gas
Networks, Equipment and Contracts for Design,
Operation, Booking and Accounting
L. A. Ostromuhov

∗†

Abstract
There are proposed models of contracts, technological equipment
and gas networks and methods of their optimization. The flow in network
undergoes restrictions of contracts and equipment to be operated. The
values of sources and sinks are provided by contracts. The contract models
represent (sub-) networks. The simplest contracts represent either nodes
or edges. Equipment is modeled by edges. More sophisticated equipment
is represented by sub-networks. Examples of such equipment are multipoles and compressor stations with many entries and exits. The edges
can be of different types corresponding to equipment and contracts. On
such edges, there are given systems of equation and inequalities simulating
the contracts and equipment. On this base, the methods proposed that
allow: calculation and control of contract values for booking on future days
and for accounting of sales and purchases; simulation and optimization of
design and of operation of gas networks. These models and methods are
implemented in software systems ACCORD and Graphicord as well as in
the distributed control system GAMOS used by Wingas, Germany. As
numerical example, the industrial computations are presented.

Contents
1 Introduction

2

2 Models and problems
2.1 Analysis of models used in gas supply companies . . . . . . . . .
2.2 Contract and client station models . . . . . . . . . . . . . . . . .
2.2.1 Contract models for planning and control of gas networks
and for invoicing. . . . . . . . . . . . . . . . . . . . . . . .
2.2.2 Models of client and shut-off stations. . . . . . . . . . . .

5
5
7
7
8

∗ Dr. L. A. Ostromuhov, Wingas Transport GmbH, Baumbachstr. 1, 34119 Kassel, Germany. E-mail: leonid.ostromuhov@wingas-transport.de
† The paper is presented on the World Symposium on Computing in the Gas Industry,
26-28.04.1999 in Florence, Italy.

1

2.3

2.4
2.5
2.6

Network models . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.3.1 Network models for hydraulic simulation and optimization.
2.3.2 Using the optimization based on hydraulic simulation by
planning. . . . . . . . . . . . . . . . . . . . . . . . . . . .
Flow network models . . . . . . . . . . . . . . . . . . . . . . . . .
Mathematical model and problem formulation . . . . . . . . . . .
Merits and demerits of different optimization problems . . . . . .
2.6.1 The network optimization based on hydraulic simulation.
2.6.2 The network optimization based only on flow models. . .

8
8
9
9
10
13
13
13

3 Method of continuous - discrete nonlinear optimization on a
network
14
4 Numerical example and experience: optimal operation of a gas
network
15
5 Quality, supply, and cost tracking

16

6 Conclusions

17

7 Notation

19

8 Figures

21

9 Tables

31

1

Introduction

In the paper, the contract models are proposed, which represent (sub-) networks.
These contract models are used for booking, accounting, estimation of contract
values, for control and operation of contracts, and for network optimization.
In addition, equipment is modeled by edges and sub-networks. The edges can
be of different types. A type of an edge correspond to a type of equipment and
contracts. On such edges, there are given systems of equation and inequalities
simulating the operation of equipment and contracts. In case of a gas network,
an edge might have a type of a pipe, compressor, compressor station, control
valve, shut-off valve, and so on.
The models of contracts and equipment construct a base for methods for
balancing and optimization both of contracts and of gas networks for design,
planning, control, operation, booking and accounting.
These models, methods and functions describing contracts and equipment
are realized in the software systems ACCORD and GRAPHICORD.
The proposed here contract models are implemented in the distributed control system GAMOS used by Wingas, Germany. The program implementation
in GAMOS is provided by Dr. Kaemmerling.

2

The software ACCORD has been developed as application of economic and
operational steady state simulation and optimization of gas pipeline networks.
Any network topology and in principle almost any objectives are available.
Minimization of fuel gas and purchased electricity, minimization of cost of purchased gas, injection and withdrawal optimization for storage facilities within
the network, profit maximization with cost consideration are provided for any
network. Both the quality and supply tracking are available. It makes possible
to produce the cost tracking, to estimate and to establish the optimal selling
prices. Compressors can be considered both with and without description of
their operating ranges or characteristics.
ACCORD has graphical user interface and interface to the third party programs e.g. to the distributed control systems. The programs providing these
types of interface construct a family named GRAPHICORD Suite. The software
GRAPHICORD provides Graphical user interface; database support; interface
with Geographic information system; interface to Distributed control systems
as well as to the third party systems; call of the third party programs; flie
management; scenario management; means to the search of information in the
networks saved; etc. The interface to the third party programs has input and
output in the form of text files. It allows to connect ACCORD with a graphic
editor; with geographic information system; with Distributed control systems;
with spreadsheet such as MS Excel. These connections are used to create a
network; to receive initial values of supplies, demands, and gas parameters; to
produce and present a graphic output. GRAPHICORD supports such databases
as MS Access, Microsoft SQL Server, Oracle. Selection of the type of database
is provided by the user.
Steady state optimization by ACCORD had been connected with programs
that perform a dynamic simulation of gas networks.
ACCORD is integrated in the distributed control system such as GAMOS
that consists of SCADA and various high level functions.
As numerical examples, the industrial computations are presented.
ACCORD is an abbreviation for Algorithmic and software Complex of Constructive nonlinear Optimization with Restriction on Discrete-Continuous network variables. It is intended for economic and operational steady state optimization of gas pipeline networks. There is no restriction on network topology
in ACCORD.
The general objectives of optimization include the following:
– to plan the installation of a network;
– to optimize the route plan of pipelines and location of equipment;
– to select pipe diameters;
– to specify facilities;
– to minimize the expenditure;
– to select supplies and demands;
– to optimize network operation, etc.
There are available in ACCORD such objective functions as:
– operational expenditure minimization;
3

– network flow maximization;
– set-point deviation minimization;
– profit maximization;
– minimization of weighted average cost of gas;
– specific transport cost minimization;
– injection and withdrawal optimization for storage facilities in pipeline
network, etc.
There are available such searching variables as:
– pressure ratio of compressor stations;
– output pressure of control valves;
– equipment of compressor stations;
– flow values of user-chosen supplies and demands;
– pressure in a user-chosen node.
A network state is a distribution of flow and pressure. The feasible network
state is received by ACCORD automatically as a result of optimization problem.
Both the quality and supply tracking are available. It makes possible to
produce the cost tracking and to establish the optimal selling prices.
Compressors can be considered in ACCORD both with and without description of their operating ranges and characteristics of macnines.
By computation of pressure drop, the modelling procedures are used which
simulate the operation of technical equipment. Therefore computation of pressure drop can be sophisticated.
The problems solved in ACCORD are to find the optimal set-points for
supplies, demands, and pressures and to make the optimal choice of equipment
on compressor stations to optimize both operational transport costs and costs for
purchased gas in order to optimize profit. In this class of problems the objective
functions depend on both flow and pressure. Minimal cost and maximal flow
problems are generalized. The typical problem consists in the optimal choice of:
– dependencies between flow and pressure from the given families;
– node intensities, i.e. values of supplies and demands;
– flow;
– pressure.
This is a class of problems belonging to the area of large scale nonlinear
mixed integer programming or constrained discrete-continuous optimization on
general networks. The developed optimization method represents a branching
multi-level computational process. It is based on nonlinear and integer programming and on graph theory. Its main characteristic feature consists in obtaining
of dominant solutions on the subnetworks, which represent the specially constructed fragments of the network.
ACCORD has an input and output interface in the form of text files. It
allows to connect ACCORD with a graphic editor or geographic system to create
a network; to receive initial values of supplies, demands, and gas parameters; to
monitor the runs of optimization; to produce and present a graphic output. Due
to its interface, ACCORD can be connected with any other simulation program
and SCADA system to provide steady state optimization of gas networks with
economic, business or operational objectives.
4

The paper consists of 6 significant sections and supplemented sections containg notations, figures, and tables.
Section 1 is an introduction while section 6 presents conclusions.
In section 2, mathematical model and problem formulation are presented.
In section 3, the developed methods of the continuous - discrete nonlinear
optimization on networks are briefly described.
Section 4 contains a numerical example as a result of industrial computational experience. For optimal operation, a gas network was optimized that
consist of a central distributed ring with large - scale supply and transport
pipelines containing ten - th compressor stations .
Section 5 presents the quality, supply and cost tracking computed by ACCORD in consequence of optimization. The graphic presentation of the tracking
is made on a path between two nodes in a gas network.
Section 6 contains conclusions.

2
2.1

Models and problems
Analysis of models used in gas supply companies

Let us consider a set of models and functions which are widespread in gas
transport, distribution and gas supply companies:
1) gas demand forecast for every client;
2) definition of set of gas suppliers and corresponding purchase quantities;
3) definition of gas injection and withdrawal quantities for every gas
storage;
4) optimization of contracts for gas sale and purchase, including both
gas exchange with adjacent companies and injection or withdrawal for different
gas storage;
5) contract optimization with restrictions arising due to gas network;
6) gas price investigation, calculation and definition for sale and purchase for long and short term planning;
7) determination of sold and purchased gas quantities in order to prepare
billing;
8) settlement and confirmation of accounts for sold and purchased gas
for every supplier and consumer and for every client station;
9) SCADA functions both for sale and purchase and for gas network
(SCADA is abbreviation for supervision, control and data acquisition);
10) supervision of actual contract fulfilment;
11) optimization of gas network state;
12) simulation and optimization of development of gas network.
The above functions allow to conclude that the following models play a
central role:
1) contract;
2) contract partner: supplier, consumer, gas storage, etc.;

5

3) client station;
4) gas network;
5) flow network.
At present, these models have different development degrees.
The network modelling went through several development steps. It derives
its sources from Kirchhoff. It follows the development periods of graph theory,
flow networks, dynamic hydraulic simulation of networks, and network steady
state optimization. It should be pointed out that models for network dynamic
optimization are not developed yet so that they could be used industrially.
There are various contract models. They have a common feature that they
are not connected with a model of gas network. It could seem that contract
models are significantly simpler than network models. More detailed consideration shows this is not the case.
A contract model source is the contract text. To originate a model, the
text must accept a formalization. Then a degree of detailed elaboration of the
formalization depends on the function wherein the model is used. Hence a contract model depends on functions wherein the contract or contract restrictions
are used. Therefore there is a contract model family corresponding to family of
functions of planning, control, invoicing, etc.
Questions arise, how these models are connected with each other; could they
be connected formally and therefore automatically; do they accept a uniform
representation. In the paper, there is proposed a contract model which represents an object consisting of:
– a graph;
– an ordered set of feasible intervals of gas parameters such as gas
demand, pressure, calorific value;
– price calculation procedures corresponding usually to the above intervals of gas parameters;
– integral quantities of gas.
The paragraphs of a contract or of an operational agreement could be represented by elements attributed to edges of the contract network, i.e. to the
connections between contract partners.
In the simplest case, the contract network consists of a node, with which
the feasible intervals of gas parameters and the procedures for calculation of gas
prices and transport expenses correspond.
Let us remark that an edge can be taken instead of node equally in that case.
Moreover, it can be taken more than one edge or node, e.g. one edge for actual
booking, the second one for communication, the third for accounting, and the
force for operation. In particularly, this approach can be useful for the so called
entry-exit economic models of contracts.
Such a contract model in form of a network causes different merits. It enables
a simple, visualizable, structured and unified representation of contracts. It
admits an automatic choice of degree of detailed elaboration of a contract model,
i.e. auto-modelling due to automation of procedures of reduction or expansion
(re-reduction) of contract network.

6

A comparison of planning and invoicing functions allows to find a lot of
similarities. In both cases, it handles with a gas distribution between the sources
or targets correspondingly. But direction of time as well as of cumulative or decumulative operation is opposite by planning and invoicing.
It is sufficient to compare a planning function of definition of purchase quantities covering an expected demand with an invoicing function of distribution
of gas quantities metered on a client station over the contracts and contract
conditions.
By planning function such as demand coverage, the client demands are accumulated to define a total demand and to distribute demand through suppliers.
The delivery ways from supplier to customer could be considered either implicitly by restrictions of maximal delivered gas quantities or explicitly by explicit
representation of gas network structure. Time is directed forwards, in the future.
By invoicing, the metered gas quantities have to be distributed i.e. decumulated on a client station in accordance with contracts, contract partners
and prices. For the most contracts, the gas flow ways from measurement places
to contract partners could be considered explicitly by explicit representation
of client station structure. The graph theory gives a suitable means for that.
Time is directed backwards since information about the earlier purchased gas
is processed.
Thus, the uniform modelling of pipelines, client stations and contracts by
means of networks allows to represent their relations and producible operations
explicitly, to visualize models, and it establishes a base for strict mathematical
problem formulation.

2.2
2.2.1

Contract and client station models
Contract models for planning and control of gas networks and
for invoicing.

The simplest representation of a contract is an object consisting of:
1) a node;
2) an interval of feasible demand;
3) an interval of feasible pressure;
4) values of demand and pressure;
5) a procedure for payment calculation.
A more complicated contract having an ordered set of feasible intervals of
demand and pressure with corresponding procedures for invoicing shall be represented by a (sub-) network.
Such a model causes different merits. It enables a simple, visualizable, structural and unified representation of contracts.
The unified contract representation is used for the following purposes and
by the following implementations:
– both for technical and economical objectives;
– for technical and contractual supervision of gas network in dispatcher
center;

7

–
–
balance;
–
–
–
2.2.2

for short and long term planning;
by gas balancing for automation of checking and achievement of gas
by data acquisition from client stations, i.e. gas meter stations;
by data preparation for settlement of accounts;
to construct the data base of gas company.

Models of client and shut-off stations.

A client station is a gas meter station. It consists of:
– shutting-off devices;
– means providing measuring of gas flow, pressure, temperature, and
other;
– valves;
– control valves;
– service pipes.
A shut-off station has the same structure as a client station. A difference is
only that the flow meter and control valves are used rather seldom by shut-off
stations. So the client and shut-off stations can be modelled in the same way.
A gas meter station has a technical structure plotting as a scheme. A configuration scheme is represented by a (sub-) network. Model of a gas meter station
shall be a (sub-) network.
Station modelling by networks causes the same merits as contract modelling
by networks.
Hence networks are used as models for gas networks, contracts, client and
shut-off stations.

2.3
2.3.1

Network models
Network models for hydraulic simulation and optimization.

A network is modelled as a graph that is equiped with flow and which nodes
and edges possess parameters. Nodes and edges possess technical parameters.
Pressure is considered explicitly. It is a nodal parameter. Restrictions are
formulated in terms of both pressure and flow.
Technical equipment as pipeline sections, compressor stations, control valves
and valves are represented by edges of the network. The complicated compressor
stations can be represented by sub-networks of the network.
Client and shut-off stations are represented by nodes of the network. The
complicated client and shut-off stations can be represented by sub-networks of
the network. If a contract is connected with only one client station and this
station is represented by a node of the network then the contract is represented
by the same node too. More complicated contracts can be represented by subnetworks of the network.
By computation of pressure drop, the modelling procedures are used which
simulate the operating of technical equipment. Therefore computation of pressure drop can be very sophisticated.
8

Exactly as in network operation, a pipeline capacity is represented implicitly.
This means that pipeline capacities are given due to maximal and minimal
pressure limits in nodes of network. Pressure limits arise owing to technical and
contractual restrictions.
There are two types of hydraulic simulation: a dynamic simulation and a
steady state simulation.
In the dynamic simulation, the partial differential equations are used to
model hydraulic. The network parameters such as flow and pressure depend on
time.
In the steady state simulation, the algebraic equations are used. The network parameters such as flow and pressure are taken at a certain moment or in
average.
A network optimization based on the hydraulic simulation considers restrictions and objective functions which are formulated in terms of both pressure
and flow. As a result of optimization, the feasible and optimal hydraulic state
of the whole network must be found and simulated.
A network dynamic optimization, i.e. the network optimization based on the
dynamic hydraulic simulation is not developed anywhere yet. A network steady
state optimization, i.e. the network optimization based on the steady state
hydraulic simulation is provided in Wingas by methods and software ACCORD
developed there.
2.3.2

Using the optimization based on hydraulic simulation by planning.

For short term planning, the network steady state optimization by ACCORD
is a useful tool. When planning for serial time periods, the network steady
state optimization can be used. For this purpose it must run several times
sequentially for sequential moments. Practically for long term planning it is
possible rather often. But, for some cases, it can be expensive if not prohibited
due to complexity of problem.
For example, a feasibility of the network state must be checked every year
for an extremely cold winter and for a summer which follows after the extremely
cold winter. Hence a planning for e.g. 25 years requires at least 50 feasibility
checking of the network state. Every feasibility checking of the network state is
reduced to the solution of a network optimization problem based on the steady
state hydraulic simulation. It means that ACCORD must run 50 times. For
complex networks represented in detail, it requires such user efforts that cannot
be completed in a very short time.

2.4

Flow network models

A network is modelled as a graph that is equiped with flow. Edges dispose of
flow. For nodes the value of demand or supply are considered. Simulation of
operation of technical equipment is not used. Hydraulic simulation is not used
either.

9

Pressure is considered implicitly. Restrictions are formulated in terms of
maximal flow that is capacity for every edge. Pipeline capacities must be given
as input data. Capacity is an idealization that is not met by network operation.
Capacities simulate technical and contractual restrictions such as maximal and
minimal pressure limits. A capacity does model implicitly the pressure limits.
Any client station and any contract is represented by a node. If necessary, a
station and a contract can be represented by a sub-network of the network.
To optimize gas network without hydraulic simulation, flow models are use
such as in the minimal cost network flow problem.
Let G = (V, E) be a network with a node set V and an edge set E. The
minimal cost network flow problem consists in:
X
minimize
fik (qik )
(1)
(i,k)∈E

subject to:
X

qji −

j

X

qk = Qi ,

i ∈ V,

(2)

k

min
max
qik
< qik < qik
,

(i, k) ∈ E,

(3)

where: qik is flow in arc (i, k); fik (qik ) is cost of flow qik ; Qi is supply or demand
in node i .
The minimal cost network flow problem is much easier as a network optimization with hydraulic simulation. There are efficient methods delivering a
solution of this problem.
For long term planning for serial time periods, it is worthwhile to use a
minimal cost network flow problem as a compromise simplification. It must
run several times sequentially for sequential moments for this purpose. Due to
efficient solution methods, a planning for 25 years requiring 50 - 100 solutions
of minimal cost network flow problem seems realistic.
The correct investigation of capacities can turn out as a weakest point in such
a simplified approach. Here is useful a method for precise definition of pressure
limits in a gas network. This method we have developed in [11]. Normally by
long term planning, the supplies and demands are considered as constant in
every time period. Hence it is allowed to use the said method for sub-networks
that are defined by connected subsets of nodes which include terminal nodes
and nodes of compressor stations.

2.5

Mathematical model and problem formulation

Let be given a connected undirected network G = (V, E) with a set of nodes V
and a set of edges E. Let qik be the flow in the edge (i, k) and Qi be the supply
or demand called intensity of node i, which satisfies the next conservation law:
X
qik + Qi = 0,
(4)
k

10

qik = −qki ,

i, k ∈ V,

(i, k) ∈ E.

(5)

The minimal cost network flow problem consists in
X
minimize F =
Fik (qik )

(6)

(i,k)∈E

subject to
X

qik −

X

qmi = Qi , qik = −qki ,

i, k ∈ V,

(i, k) ∈ E,

(7)

m

k

−
+
qik
≤ qik ≤ qik
,

(i, k) ∈ E.

(8)

In the dual problem, the objective function depends on the differences of potentials pi , pk , i.e. on tension vectors tik = pi − pk . The necessary and sufficient
optimality conditions for the minimum cost network flow problems with linear
or nonlinear objective functions are well known [3], [12]. . They include the
connection between pressures pi , pk and flow qik in the form of equality and
inequality system between the pressure differences and the left and right derivatives of the cost at the flow. They satisfy the following complementary slackness
condition [5], [13] in the necessary and sufficient optimality conditions

0
qik = qik

−
qik = qik

if and only if

pi − pk <

∂Fik
−
| qik
,
∂qik

(9)

+
qik = qik

if and only if

pi − pk >

∂Fik
+
| qik
,
∂qik

(10)

if and only if

pi − pk =

∂Fik
0
| qik
∂qik

for

−
+
0
qik
≤ qik
≤ qik
. (11)

While the edge (i, k) represents the equipment with input node i and output
node k, the equality (11)
∂Fik
(12)
pi − pk =
∂qik
represents the model of equipment, i.e. Ohm’s law, Bernoulli’s law etc. Really,
if Fik is linear,
Fik (qik ) = cik qik

then

pi − pk = cik

that corresponds cost problem,

for quadratic Fik
2
Fik (qik ) = cik qik

then

pi − pk ∼ qik
11

that corresponds Ohm’s law,

for cubic Fik
3
Fik (qik ) = cik qik

2
pi − pk ∼ qik

then

that corresponds Bernoulli’s law.

Let us generalize equipment models so that together with equations (12)
connecting potential difference with a function of flow there can be considerable
any function of flow and both potentials
(i, k) ∈ E.

fik (pi , pk , qik ) = 0,

(13)

To give a possibility to select the equipment, we come to the necessity to select
the model, i.e. to choice the best equation from the equation set, we suppose
that there are given the families of functional dependencies between flow and
pressures:
fdik (pi , pk , qik , cik ) = 0,

(i, k) ∈ E,

dik ∈ {1, ..., Nik }.

(14)
(15)

Here cik is a vector of continuous parameters (coefficients), and dik is a
discrete parameter on the edge (i, k). We suppose that there are given the
+
−
+
−
+
limitations Q−
i , Qi , pi , pi , cik , cik :
+
Q−
i ≤ Qi ≤ Qi ,
+
p−
i ≤ pi ≤ pi ,
+
c−
ik ≤ cik ≤ cik ,

i ∈ V,

(16)

i ∈ V,

(17)

(i, k) ∈ E,

(18)
a−
ik ,

and the other restrictions can be represented by inequalities with given
a+
ik
for the vector-functions aik (pi , pk , qik , cik , dik ) which have to be calculated:
+
a−
ik ≤ aik (pi , pk , qik , cik , dik ) ≤ aik ,

(i, k) ∈ E.

(19)

Because the roles of input and output and the flow direction could be
changed, there is considered an undirected network.
The considered objective function depends both on flow qik and on pressures
pi , pk , intensities Qi , continuous cik and discrete parameters dik . Then the
problem is:
X (1)
X (2)
minimize F =
Fik (pi , pk , qik , cik , dik ) +
Fi (pi , Qi )
(20)
i

ik

subject to (4),(5),(14)-(19).

(21)

We may interpret (19) as restrictions on the power, temperature, dissipation
and other characteristics of the equipment that is represented by the edge (i, k).
12

The set of available values of discrete parameters dik in (15) means that the
family of functions fdik can act on the edge (i, k), and we have to select the best
function fdik for an equation (14). Thus, we have to select such equation (14),
which is the best for the objective function (20). We may interpret this as a
selection of the most profitable equipment, which is installed or can be installed
on the place (i, k).
The continuous parameters cik in (14) can be interpreted as parameters that
smoothly regulate the work of equipment dik in bounds (18).
The inequalities (16) and the dependence of objective function on intensities
Qi mean that the most profitable values of supplies and demands have to be
chosen.
Without concentration on the conditions of existence and uniqueness of the
solution and on the proving of convergence to it, we describe the methods that
work in practice and bring the solution of the formulated problem in the general
case.

2.6

Merits and demerits of different optimization problems

2.6.1

The network optimization based on hydraulic simulation.

Advantages:
1) The network optimization with hydraulic simulation could be useful
for both operational and economic optimization;
2) The very broad range of technological restrictions can be considered;
3) The broad range of objective functions can be considered, multiobjective problem can be modelled;
4) Steady state network simulation is provided;
5) Pressure is considered explicitly. Restrictions and objective functions
are formulated in terms of both pressure and flow;
6) Exactly as in network operation, capacity of pipelines are represented
implicitly. This means that pipeline capacities are given due to maximal and
minimal pressure limits in nodes of network. Pressure limits arise owing to
technical and contractual restrictions;
7) In comparison with optimization based only on flow models, the network optimization based on hydraulic simulation has a high technical reliability
and exactness of results.
Demerits:
1) Complication of models and methods;
2) In comparison with optimization based only on flow models, the
network optimization based on hydraulic simulation usually needs more computational time and more efforts of user to get final results.
2.6.2

The network optimization based only on flow models.

Merits:

13

1) Simplicity of models;
2) In comparison with network optimization based on hydraulic simulation, the optimization based only on flow models usually needs not so much
computational time and less efforts of user to get final results
Demerits:
1) Pressure is considered implicitly;
2) Pipeline capacities must be given as input data. They simulate technical and contractual restrictions such as maximal and minimal pressure limits
only indirectly;
3) The optimization based only on flow models has rather low technical
reliability of results.

3

Method of continuous - discrete nonlinear optimization on a network

The formulated problem (4) - (20) is a problem of constrained nonlinear mixed
integer optimization, i.e. a problem of a search for an extremum for a function,
which has continuous - discrete parameters of optimization and which undergoes
nonlinear constraints. The objective function, constraints and parameters of optimization here are given on a network.. According to the mixing character of
variables, the combination of the continuous and discrete optimization methods
is used to solve the problem. The graph theory, integer programming, nonlinear
programming with and without constraints and the methods of solving the nonlinear systems of equations and inequality are the basis of the offered method.
Its main characteristic feature consists in obtaining the dominant solutions on
the specially constructed subnetworks.
The discrete variable is e.g. the configuration of a compressor station, i.e.
how much compressors have to be in operation and what scheme of their connection has to be used there. To manage the discrete variables, there are at least
two methods in ACCORD. The first one is a special modification of branch-andbound method. Another procedure for searching an integer-feasible solution is
connected with a possibility to check whether there is a realization of equation
tjk = pj − pk in the equation family (14). The complementary variable tjk will
be penalized if it cannot be represented by one of equations (14).
The difference between this method and the branch-and-bound approach is
clear for the cases of pure discrete problems on a tree. Such class of problems
means that the network has no cycles and there are no continuous variables at
all. Then the second method can fall in a local optimum. To avoid it, a restart
can be useful. For the same problem on a tree, the branch- and-bound method
can be very efficient. It brings a global optimum as a solution. However, for
a network with complicated topology the branch-and-bound method could be
expensive if not prohibited. This is valid especially for the networks with a
lot of cycles. Then the second procedure consisting of searching the discrete
variables djk by penalizing non-realizable continuous complementary variable

14

tjk is available there.
In practice, the method avoids the local optima.

4

Numerical example and experience: optimal
operation of a gas network

The graph of a tested gas network is presented on Fig. 1. The network consists
of a central distributed ring with large - scale supply and transport pipelines.
Every edge is either a pipeline section or a compressor station. The input data
for nodes are given in Table 1, for pipeline sections in Table 2, for compressor
stations in Table 3. The main benefits of optimization are collected in Table 4.
As a first approximation for pressure drop on a pipeline, there is used the
simple formula for pressure drop on an aligned pipeline section
2
Pi2 − Pe2 = kD lqie
sign (qie ) ,

(22)

where: Pi , Pe - pressures respectively in inlet node i and outlet (”exit”) node
e, [bar]; qie - flow rate [Mm3 /d], i.e. gas flow volume per day reduced to the
standard temperature T = 273K and pressure P = 1.013 bar; l - pipeline length,
[km]; kD - coefficient defined by formula

X
2 
5/2
2
−1
2
kD = Ra da 10 λzGT / E (π/4)
Di
,
(23)
where: E - efficiency factor that is a relation between real and theoretical flow
such that E < 1 and E = 0.92 for average operating conditions; Ra = 287 J/kgK
- gas constant for air, da = 1.293 kg/m3 - air normal density; λ - hydraulic
resistance coefficient defined e.g. after Colebrook - White formula [14], p. 286,
[1]; z - average gas compressibility, [1]; G - gas specific density on air (for air,
Gair = 1); T - average gas temperature, [K]; Di - inside diameter of the i-th
parallel pipe, [m]; here [1] means a dimensionless value.
.Finally, for pressure drop on (unaligned) pipelines, the more complicated
formula [14] is used.
The simulation of a compressor station cannot be reduced to a formula like it
has been made for a pipeline section. However, as a result of the simulating algorithm, the exhaust pressure Pe can be computed as a function of inlet pressure
Pi , flow rate qie , gas characteristics, and operating equipment of compressor
station aie and die :
pe = fei (Pi , qie , Ti , ..., aie , die ),

(24)

where aie are continuous characteristics of equipment and die are discrete characteristics, i.e. compressor types and connection schemes of compressors.
For our example, two problems have been solved:
1) Reproduction of initial operating conditions by means of optimization
with criterion of minimal deviation from set points;

15

2) Minimization of expenditure in the power expression.
It was required to support the set points of pressure in nodes of pipeline
joints. For this purpose, the narrow intervals of feasible pressure were taken in
these nodes. These intervals are presented in Table 1. The intervals in other
nodes are equal (0; 56 bar). The node 48 is taken as a root with the root
pressure P48 = 55 bar.
The value E = 0.9 of efficiency factor has been used in formula (23) for most
of the pipeline sections. Efficiencies of other pipeline sections were varied to
reach the feasible pressure area and to reproduce the initial operating conditions
(column ”kD initial” of Table 2). On compressor stations, the reproduction of
initial operating conditions has been provided by using efficiency factor E and
with schemes of connection of equipment which are presented in Table 3 in the
columns ”Efficiency factor” and ”Initial schemes” respectively. For compressor,
efficiency E is a relation between real and theoretical productivity like it is for
pipeline section. With the help of it, the real characteristics of compressors are
taken into account.
In a lot of practical implementations the simplified sub-optimal way can be
sufficient. It consists of dividing the initial discrete-continuous problem to the
pure discrete problem on a spanning tree with computed flow and to the prefix
and postfix network continuous problems which could be solved interactively.
However, we solved the full optimization problem for the test network.
In the central distributed ring two chords have been distinguished: the
pipeline sections 29 = (14, 17) and 35 = (22, 24). The pressure errors in nodes
17 and 24 are corresponding to flows in these chords. The found flows and the
pressure errors are:
q14,17 = 22.654 Mm3 /d,
dP17 = 0.01 bar.
q24,22 = 5.906 Mm3 /d,
dP24 = 0.33 bar.
The optimal connection of equipment on compressor stations has been found.
The results are presented in Table 3 in the column ”Optimal schemes”. The
power expenditure is reduced from 260.765 MW to 234.432 MW that means
11.2 % decreasing.
From the presented data we can see that the solution of the optimization
problem enables to find the feasible operating network conditions and to reduce
the transport expenditure by 11.2 % as a result of selection of optimal equipment
on the compressor stations No. 1, 6, 12 and 18.

5

Quality, supply, and cost tracking

We present the quality, supply and cost tracking computed by ACCORD in
consequence of optimization (Fig. 2 - 9). The graphic presentation of the
tracking is made on a path between two nodes in a pipeline network. To choice
a path, user clicks on two end-nodes - on the origin and terminus of the path.
If the path between these nodes is unique, it will be selected by ACCORD.
Otherwise it should be necessary to click on one or a few additional nodes.

16

Figures (i) 2 and 3, (ii) 4 and 5, (iii) 6 and 7, (iv) 8 and 9 can be considered
as four pairs of diagrams. In each of these pairs, the first diagram shows the
parameters distributed along the path: In Fig. 2, there are distance from origin
in km as axis x, pressure as axis y1 , and flow as axis y2 . In the second
diagram, i.e. here in Fig. 3, the parameters concerning nodes are shown: There
are supplies and demands situated on the selected path and flows located in
the pipelines branched off the path. In Fig. 4, supply tracking is shown, while
quality tracking as gas calorific value is shown in Fig. 5.
The computed data presented in Figs. 2 and 3 and then in Figs. 4 and 5
are basis for the supply cost tracking presented in Figs. 6 and 7. We can see
how the money for purchased gas is flowing along the pipeline per supply and in
total, and how much the normalized costs of purchased gas and the addendum
per supply for every consumer are. The operating expenses are depending on
the fuel costs. The flows of operating expenses and fix (investment) cost are
shown in Fig. 8. As a result, the normalized costs per consumer are presented
in Fig. 9.

6

Conclusions

The optimization methods and program ACCORD are developed for network
optimization. There are used steady state models of equipment. The equipment
such as pipelines, compressor stations, controlled valves, valves, etc. are represented by the edges of the network. Supplies and demands, inlets and outlets
of equipment are represented by the nodes of the network. The economic and
operational problems solved in ACCORD are formulated as continuous, discrete
and discrete-continuous optimization on general network with given family of
functional connections between flow and pressure. The continuous variables can
be acted both in nodes and edges. Pressures, flow and parameters of simulating models are examples of them. The discrete parameters correspond to edges.
Examples of them are internal structure of edges and types of simulating models
of edges, i. e. of concrete functional dependencies between flow and pressure.
The optimal equipment to operate can be selected. The generalization of the
discrete characteristic of nodes such as ”the node is a source (a sink)” is possible.
During optimization, the methods adapt themselves to the concrete network
and the features of both object function and variables.
There is proposed a model of contracts having a set of feasible intervals of
demand and pressure with corresponding procedures for payment calculation.
Every contract is represented by a (sub-) network. Such a model causes different
merits. It enables a simple, visualizable, structural and unified representation
of contracts.
For short term planning, the steady state optimization of gas network is
a useful tool. For long term planning for serial time periods, it is worthwhile
to use the minimal cost network flow problem as a compromise simplification.
The correct investigation of capacities can turn out as a weakest point in such
a simplified approach. Here a method [11] is useful; which we developed for

17

precise definition of pressure margin in gas networks.
Steady state optimization by ACCORD has been connected with dynamic
simulation programs and has been integrated in the distributed control system
GAMOS that consists of SCADA and various high level functions. ACCORD
possesses a clear and simple interface in the form of text files. Due to this
interface, ACCORD can be connected with any other simulation program, distributed control system and SCADA system to provide steady state optimization
of gas networks with economic, business or operational objectives.

18

7

Notation

Letters
A = area or cross section, [m2 ]
Ak = k−1
k , [−]
An = n−1
n , [−]
a = speed of sound, [m/s]
b = outlet width of impeller, [m]
C = conversion factor , [−]
D = outlet diameter of impeller, [m]
E = efficiency, [−]
H = mass-specific enthalpy, [kJ/kg]
Hp = specific polytropic work of compression i.e. specific polytropic head,
[kJ/kg]
k = isentropic exponent, [−]
m0 = mass flow, [kg/s]
M a = Mach number, [−]
M ix = gas composition as a list of components, [%]
n = polytropic exponent i.e. polytropic volume exponent, [−]
N = speed of rotation, [1/s] (sometimes [rps/rpm])
P = absolute pressure, [bar]
R, Rg = specific gas constant, [J/(kg · K)]
R0 = universal gas constant, [J/(kmol · K)]
Re = Reynolds number, [−]
S = pressure ratio, [−]
T = absolute temperature, [K]
u = velocity; linear tip speed, referred to D of impeller, [m/s]
v = velocity, [m/s]
V = volume, [m3 ]
V 0 = V̇ = volume flow, [m3 /s]
W = power, [W ]
Y = specific work of compression i.e. specific head, [kJ/kg]
Z = compressibility factor, [−]
µ = molar mass, [kg/kmol]
ν = kinematic viscosity, [m2 /s]
ρ = density, [kg/m3 ]
ϕ = flow coefficient, [−]
ψ = head coefficient i.e. process work coefficient, [−]
Indexes
1 = inlet
2 = outlet
a = actual i.e. operating point of compressor
e = expected value read from manufacturer characteristics
c - converted point i.e. result of conversion of operating point of compressor
to the reference gas and the reference inlet conditions
19

n = standard state i.e. standard condition for temperature and pressure
(STP)
p = polytropic
r - the reference gas composition and the reference state i.e. the reference
condition for temperature and pressure (RT P )

20

8

Figures

21

Figure 1: A gas pipeline network
22

Figure 2: Pressure, flow, and the compressor power over the selected path of
the considered gas network

23

Figure 3: Supplies, demands, and flow in the off-branched egdes over the selected
path of the considered gas network

24

Figure 4: Supply portions in Tracking of supplies, gas composition, thermodynamic properties, and quality parameters of the flow over the selected path of
the considered gas network

25

Figure 5: Heating value in Tracking of supplies, gas composition, thermodynamic properties, and quality parameters of the flow over the selected path of
the considered gas network

26

Figure 6: Costs of supplies in costs of flow as a part of Tracking of supplies,
gas composition, thermodynamic properties, and quality parameters of the flow
over the selected path of the considered gas network

27

Figure 7: Tracking of the normed operating expenses: Costs of supplies in costs
of demands as a part of Tracking of supplies, gas composition, thermodynamic
properties, and quality parameters of the flow over the selected path of the
considered gas network

28

Figure 8: Costs of fuel gas, electro energy, and fix expenses in costs of flow
as a part of Tracking of supplies, gas composition, thermodynamic properties,
and quality parameters of the flow over the selected path of the considered gas
network

29

Figure 9: Transport and fix expenses: Costs of fuel gas, electro energy, and fix
expenses in costs of demands as a part of Tracking of supplies, gas composition,
thermodynamic properties, and quality parameters of the flow over the selected
path of the considered gas network

30

9

Tables

Table 1. Sub-table 1.1. Data in end-nodes of the gas network
Cons.
No

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

Node

100
3
8
12
21
22
24
28
31
33
34
36
37
38
39
40
41
42
43
44

+, if
supply

+

+

+

Supply or
Demand,

P

Pmin

Pmax

Mm3/d

bar

bar

bar

2.3
3.55
1.9
43.4
9.83
46.07
8.14
12.06

41
46

40
45

41
40
28.3
33.4
31.3
42.5
37.5
37.5

40
38
27
29

42
47
56
56
56
56
56
56
56
56
56
56
42
40.5
29
34
56
56
56
56

10.76
13.5

11.3
19.9
1.6
0.1
10.1

31

Table 1. Sub-table 1.2. Data in end-nodes of the gas network
Cons.
No.

Node

21
22
23
24
25

45
46
47
48
59

26
27
28
29
30
31
32
33
34
35
36
37
38

60
62
63
64
65
67
68
69
70
71
72
73
74

+, if
supply

+

Supply or
Demand,

P

Pmin

Pmax

Mm3/d

bar

bar

bar

0.1
7.4
65.2
77.4
16.3

33.5
41.1
37.4
55
43

56
56
56
56
56

5.7

47.7
33.7
49.6
38.4
33.9
51
34.3
53.4
36.4
52.5
35.2
52.5
41

56
56
56
56
56
56
56
56
56
56
56
56
40

+

35.4

+

0.4
0.4
0.2
2.6
0.4
0.2
0.2
84.5

32

30

Table 2. Sub-table 2.1. Data of pipeline sections of the gas network
1
No

2
Section

3
Endnodes

4
L
Subsection

5
Inter-.
mediate
Node

6
Intermediate
Demand

7
Ko
initial

8
Ko
result

9
∆Ko

–

–

km

–

Mm3/d

–

–

%

1

23

100 – 3

36
25
38

1
2

0.5
2.5

0.083258

0.005263

-93.7%

2

24

3–8

28
23
19
16
21

4
5
6
7

0.6
1
2
3.9

0.011032

0.011032

–

3

25

8 – 31

9
14
8

29
30

1.2

0.011032

0.011032

–

4

26

8 – 12

28
13
31
1

9
10
11

2.7
1
1.2

0.83258

0.715182

-14.1%

5

27

12 – 14

9
38

13

0.3

0.005899

0.005899

–

33

Table 2. Sub-table 2.2. Data of pipeline sections of the gas network
1
No

2
Section

3
Endnodes

4
L
Subsection

5
Inter-.
mediate
Node

6
Intermediate
Demand

7
Ko
initial

8
Ko
result

9
∆Ko

–

–

km

–

Mm3/d

–

–

%

6

28

14 – 33

28
5

32

2.1

0.083258

0.083258

–

7

29

14 – 17

9
15
18

15
16

3.8
1.4

0.005899

0.005899

–

8

30

17 – 34

16

0.16232

0.16232

–

9

31

17 – 100

7
22
35
38

18
19
20

0.07
0.07
0.05

0.083258

0.083258

–

10

32

100 – 22

68
11

23

4.3

0.792462

0.792462

–

34

Table 2. Sub-table 2.3. Data of pipeline sections of the gas network
1
No

2
Section

3
Endnodes

4
L
Subsection

5
Inter-.
mediate
Node

6
Intermediate
Demand

7
Ko
initial

8
Ko
result

9
∆Ko

–

–

km

–

Mm3/d

–

–

%

11

33

22 – 21

6

0.792462

0.792462

–

12

34

21 – 36

75

0.872981

0.872981

–

13

35

22 – 24

12

0.16232

0.16232

–

14

36

24 – 3

106.3

0.027284

0.027284

–

15

37

100 – 28

13
80

0.083258

0.083258

–

16

43

47 – 46

12

17

44

44 – 45

100

0.00673

0.00673

–

18

45

42 – 43

100

0.311

0.311

–

19

46

40 – 41

100

0.0102

0.011

7.8%

20

47

38 – 39

100

0.00448

0.0166

270.5%

35
27

1.2
3

0.00673

35

Table 2. Sub-table 2.4. Data of pipeline sections of the gas network
1
No

2
Section

3
Endnodes

4
L
Subsection

5
Inter-.
mediate
Node

6
Intermediate
Demand

7
Ko
initial

8
Ko
result

9
∆Ko

–

–

km

–

Mm3/d

–

–

%

21

48

38 – 37

100

0.00918

0.00262

-71.5%

22

49

59 – 38

100

0.00282

0.00282

–

23

50

60 – 59

100

0.00483

0.00483

–

24

52

63 – 62

100

0.00786

0.00786

–

25

56

66 – 65

100

0.00037

0.00037

–

26

57

67 – 66

100

0.00189

0.00189

–

27

58

69 – 68

100

0.00255

0.00255

–

28

59

71 – 70

100

0.00204

0.00204

–

29

60

73 – 72

100

0.0213

0.0213

–

30

86

61 – 64

462.08

0.01636

0.01636

–

36

Table 3. Sub-table 3.1. Data of compressor stations belonging to the subsystem No. 1 of the considered gas network
1
No

2
Compressor
Station
No

3
Efficiency
of
Station

4
T
gas
inlet

5
Shops
Number

6
Type
of
Machines
Drivers

C

7
Power
of
Compressors

8
Number
of
Machines
Total

9
Machine
Configuration
Initial

10
Machine
Configuration
Optimal

11
Change

12
Benefit,
∆
machines

changed
changed
changed

−3
−1
−4

changed

+2

changed

−2

MW

1

6

0.69

13

3

turbine
turbine
electro

4
6
4

8
3
8

3x2
1x2
3x2

3x1
1x1
2x1

2

7

0.91

9

3

turbine
electro
turbine

4
4
5

5
8
3

2x1

2x1

3

1

0.91

8

1

electro

4

16

–

2x1

4

8

0.91

11

2

electro
turbine

4
4

8
5

1x2
2x2

1x2
2x2

5

9

0.91

2

2

electro
electro

4
4.5

7
5

2x1

–

6

10

0.91

3

1

electro

4

8

37

Table 3. Sub-table 3.2. Data of compressor stations belonging to the subsystem No. 2 of the considered gas network
1
No

2
Compressor
Station
No

3
Efficiency
of
Station

4
T
gas
inlet

5
Shops
Number

6
Type
of
Machines
Drivers

C

7
Power
of
Compressors

8
Number
of
Machines
Total

9
Machine
Configuration
Initial

10
Machine
Configuration
Optimal

11
Change

12
Benefit,
∆
machines

changed

−3

MW

7

11

0.98

13

1

electro

4

7

3x2

3x1

8

12

0.98

13

1

electro

4

7

3x1

3x1

38

Table 3. Sub-table 3.3. Data of compressor stations belonging to the subsystem No. 3 of the considered gas network
1
No

2
Compressor
Station
No

3
Efficiency
of
Station

4
T
gas
inlet

5
Shops
Number

6
Type
of
Machines
Drivers

C

7
Power
of
Compressors

8
Number
of
Machines
Total

9
Machine
Configuration
Initial

10
Machine
Configuration
Optimal

11
Change

12
Benefit,
∆
machines

changed
changed

+2
−4

MW

9

15

0.91

16

2

electro
turbine

4
10

10
3

4x2
1x2

4x2
1x2

10

16

0.83

20

2

turbine
turbine

10
6

6
6

2x2
2x2

2x2
2x2

11

17

0.83

14

2

turbine
electro

10
4

3
10

1x2
4x2

1x2
4x2

12

18

0.8

9

2

turbine
electro

6
4

6
10

2x2
4x2

3x2
2x2

13

19

0.98

6

2

turbine
turbine

5
6

5
6

2x2
2x2

2x2
2x2

39

Table 4. Benefits in the energy expended on compressor stations of the gas
network
1
Initial
Total
Compressor
Power

2
Optimal
Total
Compressor
Power

3
Savings
in
Compressor
Power

4
Benefits
∆machines

MW

MW

%

–

260.8

234.4

-11.2%

-13

References
[1] D. Ahlfeld, R. S. Dembo, J. S. Mulvey and S. A. Zenios: Nonlinear programming on generalized networks, Journal ACM Transactions on Mathematical Software (TOMS), Volume 13 Issue 4, Dec. 1987, 350 - 367.
[2] A. V. Aho, J. E. Hopcroft, J. D. Ullman: The design and analysis of
computer algorithms (Addison - Wesley, 1976)
[3] D. M. Himmelblau: Applied Nonlinear Programming (McGraw - Hill, NY,
1972)
[4] T. C. Hu. Integer programming and network flows (Addison - Wesley, 1970).
[5] Ju. M. Ermoljev, I. M. Melnik. Extremal problems on graphs (Nauk.
dumka, Kiev, 1968 (Russian)).
[6] E. M. Livshits, L. A. Ostromuhov: Continuous - discrete optimal control
problems of gas transient networks in ACCORD complex, VINITI 6707-84,
6708-84, 6709-84, (1984) 1 - 18, 1 - 22, 1 - 32 (Russian)
[7] E. M. Livshits, L. A. Ostromuhov: Solution methods for nonlinear discretecontinuous network optimization, Rep. on 3rd World Congr. on industrial
and appl. math. ICIAM-95, Hamburg (1995)
[8] L. A. Ostromuhov: Economic and operational network optimization by
ACCORD, - Proc. SIMONE Congress-95, Helsinki (1995).
[9] L. A. Ostromuhov: Economic and operational pressure and flow gas network optimization, Erdoel-Erdgas-Kohle 114 (1998, 7/8) 373 - 377
[10] L. A. Ostromuhov: Nonlinear programming on networks with discretecontinuous variables, in: Advances in Nonlinear Programming, Ya-xiang
Yuan (ed.), Kluwer Acad., 1998, pp. 299 - 310
40

[11] L. A. Ostromuhov: Precise definition of dictated points and pressure margin
in gas networks, Preprint (1993)
[12] H. Mawengkang, B. A. Murtagh: Solving nonlinear integer programs with
large - scale optimization software, Ann. Op. Res. 5 (1985/6) 425 - 437.
[13] S. A. Zenios, J. M. Mulvey, Relaxation techniques for strictly convex network problems, Ann. Op. Res. 5 (1985/6) 517 - 538.
[14] J. Kralik, P. Stiegler, Z. Vostry, J. Zavorka: Dynamic modeling of large
scale networks with application to gas distribution (Elsevier, 1988)
[15] E. M. Livshits, L. A. Ostromuhov, Continuous-discrete nonlinear optimization in networks with flow and pressure, 1246gz-90 (1990) 1 - 106 (Russian).
[16] E. M. Livshits, L. A. Ostromuhov: Flow with Nonlinear Potential in General Networks – Simulation, Optimization, Control, Risk and Stability
Analysis, 2011, arXiv:1103.3726

41

