**Introduction:**

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.