Mathematical models
Natural gas is considered by many to be the most important energy source for the future. The objectives of energy commodities strategic problems can 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 locations. Needless to say these problems involve amount of money of the order of magnitude of the tens of billions € and often these problems can be a multi-countries problem. From the economic side, the natural gas consumption is expected to continue to grow linearly to approximately 153 trillion 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 only way to transport it from the production sites to the demanding places, before the concept of Liquefied Natural Gas (LNG). The transportation of natural 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;
Modeling and algorithmic considerations:
Typically, the mathematical programming formulations of these optimization problems contain a lot of nonlinear/nonconvex and even nonsmooth constraints and objective functions because of the underlying physic of the gas flows 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 divide et impera principium is applied. Therefore the problems 1 and 2 are somehow determined via simulations and normally there are - in the first 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 stations 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 which is an integer variable, the pipeline length between two compressor stations, and the suction and discharge gas pressures at compressor stations. This problem is computationally very challenging since it includes not only nonlinear 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 increasing the diameter. On the other hand, for the exploitation of new gas fields or off-shore transportation, pipeline systems are designed from scratch with no predetermined topology. Capacity planning and rollout has a time horizon of several years. Accordingly, some optimization models consider multiple stages of network expansion. Many of the planning problems are formulated as MINLP, with integer variables and nonconvex constraints. To solve these models directly, solvers apply outer approximation and spatial branching. Alternatively, the problem functions can be approximated piece-wise linearly, yielding a MIP formulation. A survey paper concerned with water networks is also relevant here (1). Specialized algorithms make use of the fact that certain subproblems with fixed integer variables have a convex reformulation, which can be solved efficiently and used for pruning (2-3). The design of pipeline topologies from scratch is solved with a decomposition, where first a topology is fixed heuristically, and improved by local search. The design of pipeline topologies from scratch is solved 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 has 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 Network Optimization, European Journal of Operational Research, 2015
(2) A. Raghunathan, Global Optimization of Nonlinear Network Design, SIAM 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 \& Industrial Engineering, 2011
Contributors:
Dr Robert Schwarz, ZIB
Dr. Fabrizio Lacalandra, Quantek
Dr. Lars Schewe, Universität Erlangen-Nürnberg