Natural gas is considered by many to be the most important energy source=
for the future. The objectives of energy commodities strategic problems ca=
n be mainly related to natural gas and deal with the definition of the *=
"optimal*" gas pipelines design which includes a number of related sub =
problems such as: Gas stations (compression) location and Gas storage locat=
ions. Needless to say these problems involve amount of money of the order o=
f magnitude of the tens of billions =E2=82=AC and often these problems can =
be a multi-countries problem. From the economic side, the natural gas consu=
mption is expected to continue to grow linearly to approximately 153 trilli=
on cubic feet in 2030, which is an average growth rate of about 1.6 percent=
per year. Because of the properties of natural gas, pipelines were the onl=
y way to transport it from the production sites to the demanding places, be=
fore the concept of Liquefied Natural Gas (LNG). The transportation of natu=
ral gas via pipelines remains still very economical.

From an optimization standpoint, the gas pipeline design problems can be= divided in the following main sub problems:

- how to setup the pipeline network, i.e. its topology;
- how to determine the optimal diameter of the pipelines;
- how to allocate compressor stations in the pipeline network;

Typically, the mathematical programming formulations of these optimizati=
on problems contain a lot of nonlinear/nonconvex and even nonsmooth constra=
ints and objective functions because of the underlying physic of the gas fl=
ows that needs to be considered. The classic constraints are the so-called =
Weymouth panhandle equations, which are a potential-type set of constraints=
and relate the pressure and flow rate through an arc (m,n) of the pipeline=
. As in many other situations problems 1-3 are a single problem but a *d=
ivide et impera* principium is applied. Therefore the problems 1 and 2 =
are somehow determined via simulations and normally there are - in the firs=
t but also in the 2 - a lot of economic drivers, and also political drivers=
when many countries are involved. From a technical point of view, instead =
probably the most challenging problem is the number 3, the compression stat=
ions allocation. Because of the high setup cost and high maintenance cost, =
it is desirable to have the best network design with the lowest cost. This =
problem concerns a lot of variables: the number of compressor stations whic=
h is an integer variable, the pipeline length between two compressor statio=
ns, and the suction and discharge gas pressures at compressor stations. Thi=
s problem is computationally very challenging since it includes not only no=
nlinear functions in both objective and constraints but, in addition, also =
integer variables.

In the case of transmission networks, existing infrastructure is already= available, but needs to be expanded to increase the capacity. To this end,= new pipelines are often built in parallel to existing ones, effectively in= creasing the diameter. On the other hand, for the exploitation of new gas f= ields or off-shore transportation, pipeline systems are designed from scrat= ch with no predetermined topology. Capacity planning and rollout has a time= horizon of several years. Accordingly, some optimization models consider m= ultiple stages of network expansion. Many of the planning problems are form= ulated as MINLP, with integer variables and nonconvex constraints. To solve= these models directly, solvers apply outer approximation and spatial branc= hing. Alternatively, the problem functions can be approximated piece-wise l= inearly, yielding a MIP formulation. A survey paper concerned with water ne= tworks is also relevant here (1). Specialized algorithms make use of the fa= ct that certain subproblems with fixed integer variables have a convex refo= rmulation, which can be solved efficiently and used for pruning (2-3). The = design of pipeline topologies from scratch is solved with a decomposi= tion, where first a topology is fixed heuristically, and improved by = local search. The design of pipeline topologies from scratch is solve= d with a decomposition, where first a topology is fixed heuristically, and = improved by local search. The pipeline diameters are then solved separately= (4). In the case that the network has tree topology, Dynamic Programming h= as been applied, both for the choice of suitable pipe diameters (4) as well= as compression ratios (5).

**References**

(1) C. D'Ambrosio et al., Mathematical Programming techniques in Water N= etwork Optimization, European Journal of Operational Research, 2015

(2) A. Raghunathan, Global Optimization of Nonlinear Network Design, SIA= M Journal on Optimization, 2013

(3) J. Humpola, Gas Network Optimization by MINLP, PhD thesis, TU Berlin= , 2014

(4) B. Rothfarb et al., Optimal design of offshore natural-gas pipeline = systems, Operations Research, 1970

(5) C. Borraz-Sanchez, Minimizing fuel cost in gas transmission networks= by dynamic programming and adaptive discretization, Computers \& Indus= trial Engineering, 2011

**Contributors**:

Dr Robert Schwarz, ZIB

Dr. Fabrizio Lacalandra, Quantek

Dr. Lars Schewe, Universit=C3=A4t = Erlangen-N=C3=BCrnberg