Keywords

4.1 Introduction

There are different types of optimization algorithms that can be used in gas allocation optimization. Generally they can be classified into two categories: numerical algorithms and heuristic ones (Jacoud et al. 2015).

4.2 Numerical Algorithms

Until some years ago using numerical methods for finding an optimum point for a gas allocation problem was a common method. These methods require an initial guess of the solution, and then the process moves in search direction dk (see (4.1)).

$$ d^{k} = \left( {d_{1}^{k} \cdot d_{2}^{k}\cdot \, \ldots\, \cdot d_{n}^{k} } \right). $$
(4.1)

The general form of updating the gas injection rates is as follows (Nishikiori et al. 1989):

  1. (a)

    Set k = 0

  2. (b)

    If the \( {\text{Q}}_{\text{g}}^{\text{k}} \) is optimum terminate the computation otherwise determine dk for \( {\text{Q}}_{\text{g}}^{\text{k}} \)

  3. (c)

    Find the step length αk that maximizes \( {\text{f}}({\text{Q}}_{\text{g}}^{\text{k}} + \upalpha^{\text{k}} {\text{d}}^{\text{k}} ) \)

  4. (d)

    Set \( {\text{Q}}_{\text{g}}^{{{\text{k}} + 1}} = {\text{Q}}_{\text{g}}^{\text{k}} + \upalpha^{\text{k}} {\text{d}}^{\text{k}} \) and set k = k + 1

  5. (e)

    to (b)

There are various methods to find the search direction dk and αk in different steps until the optimum point is found.

4.2.1 Equal Slope Optimization

The equal slope optimization is a method for finding the best allocation. Kanu et al. (1981) expressed this in 8 steps:

  1. Step 1

    Analyze the wells and calculate the well performance for different gas liquid ratio in gas lift operation.

  2. Step 2

    Establish a relation for the production oil rate versus injection gas. These plots are called gas lift performance curve. Figure 4.1 shows a typical gas lift performance curve.

    Fig. 4.1
    figure 1

    A typical gas lift performance curve (Rashid et al. 2012)

    Full size image
  3. Step 3

    Plot the data of Step 2 for all wells in a unique graph.

  4. Step 4

    Draw lines with various slopes tangent to each curve (as Fig. 4.2).

    Fig. 4.2
    figure 2

    Economic slope (Rashid et al. 2012)

    Full size image
  5. Step 5

    At each point of Step 4 find the injection rate and production.

  6. Step 6

    Establish a relationship between slope and the injection and production rates for each well.

  7. Step 7

    Establish a relationship between slope and the injection and production rates for the whole field by calculating the equation of Step 6.

  8. Step 8

    Calculate the economic slope using Eq. (4.2):

    $$ {\text{m}} = \frac{{\vartriangle q_{L} }}{{\vartriangle q_{g} }} = \frac{{C_{g} }}{{f_{o } P}}. $$
    (4.2)
  9. Step 9

    Use this slope and use it in Step 6.

  10. Step 10

    Obtain the total injection rate by adding the optimum injection rates of individual wells, which are gained by slopes.

4.2.2 Gradient Optimization

One of the oldest methods that sometimes was also the most common one is the gradient or steepest ascent method (Fletcher 2013; Luenberger 1984). This function approximates the objective (fitness) function by a first degree Taylor polynomial (4.3):

$$ f\left( {Q_{g}^{k} + \delta } \right) = f\left( {Q_{g}^{k} } \right) + \delta^{T} g^{k}. $$
(4.3)

In which \( \delta = \upalpha\, {\text{d}}^{\text{k}} \;{\text{and}}\;{\text{g}}^{\text{k}} \) is the gradient of “f” at \( {\text{Q}}_{\text{g}}^{\text{k}} \).

For gk see (4.4):

$$ \nabla f\left( {Q_{g}^{k} } \right) = \left( {\frac{{\partial f\left( {Q_{g}^{k} } \right)}}{{\partial q_{g1} }} \cdot \frac{{\partial f\left( {Q_{g}^{k} } \right)}}{{\partial q_{g2} }}\cdot\, \ldots\, \cdot \frac{{\partial f\left( {Q_{g}^{k} } \right)}}{{\partial q_{gn} }}} \right)^{T} = g^{k}. $$
(4.4)

In this method, for increasing the total production oil rate, condition (4.5) should be satisfied:

$$ d^{{k^{T}}} g^{k} > 0. $$
(4.5)

This condition is called the ascent condition. In the gradient method, the search condition is specified as (4.6):

$$ d^{k} = g^{k} $$
(4.6)

This states that the gradient method searches in the steepest direction. This direction guarantees the finding of an optimum point for positive scalar α. However, further studies showed that this method searches linearly and thus frequently, it is slow in converging to the optimum point and this is its main disadvantage (Fletcher 2013; Luenberger 1984).

4.2.3 Newton Method

The Newton method is much faster than the gradient method. This method is derived from the second order Taylor polynomial approximation (see (4.7)).

$$ f\left( {Q_{g}^{k} + \delta } \right) = f\left( {Q_{g}^{k} } \right) + \delta^{T} \quad \nabla f\left( {Q_{g}^{k} } \right) + \frac{1}{2} \delta^{T} {\text{F}}\left( {Q_{g}^{k} } \right). $$
(4.7)

\( F( {Q_{g}^{k} } ) \) is the Hessian matrix of the second derivative. And \( \delta \) is defined as (4.8):

$$ \delta = - \left[ {F\left( {Q_{g}^{k} } \right)} \right]^{ - 1} \quad \nabla f\left( {Q_{g}^{k} } \right). $$
(4.8)

The iterative part of the equation is as (4.9):

$$ Q_{g}^{k + 1} = Q_{g}^{k} - \left[ {F \left( {Q_{g}^{k} } \right)} \right]^{ - 1} \quad \nabla f\left( {Q_{g}^{k} } \right). $$
(4.9)

The idea in Quasi-Newton is to define H as (4.10):

$$ - \left[ {F\left( {Q_{g}^{k} } \right)} \right]^{ - 1} = H^{k} $$
(4.10)

And for its iterative purposes (4.11) is defined as:

$$ H^{k + 1} = \left[ {H^{k} - \frac{{H^{k} y^{k} y^{{k^{T} }} H^{k} }}{{y^{{k^{T} }} H^{k} y^{k} }}} \right]\gamma^{k} - \frac{{\delta^{k} \delta^{{k^{T} }} }}{{\delta^{{k^{T} }} y^{k} }} $$
(4.11)

The parameters of (4.11) are defined in (4.12)–(4.15):

$$ \gamma^{k} = - \frac{{\delta^{{k^{T} }} y^{k} }}{{y^{{k^{T}}} H^{k} y^{k}}} $$
(4.12)
$$ y^{k} = g^{k + 1} - g^{k} . $$
(4.13)
$$ \delta^{k} = Q_{g}^{k + 1} - Q_{g}^{k} $$
(4.14)
$$ d^{k} = H^{k} g^{k} $$
(4.15)

There are other mathematical methods for optimization that the interested reader can find in Rao (2009, Iqbal (2013). A lot of them have been used in gas allocation optimization. For example, Edwards et al. (1990) used numerical methods to create a model for gas allocation optimization. He considered the facilities in his model.

Dutta-Roy and Kattapuram (1997) used mixed-integer linear programming optimized gas allocation optimization. They proposed a model of wells and some surface facilities. The main idea in their work was to see the effect of interaction of wells in the result. Alarcón et al. (2002) used nonlinear constrained programming for solving the gas allocation optimization problem; He used the Nishikiori (Nishikiori et al. 1989) method, but modified that by using sequential quadratic programming. Fang and Lo (1996) used a linear programming method for solving this problem and Wang et al. (2002) used mixed integer non-linear programming to generalize the previous approaches. Camponogara and Nakashima (2006) used a recursive algorithm to solve the problem. Camponogara and de Conto (2005) used a piecewise linear method. Their model was based on mixed integer linear programming. Guyaguler and Byer (2008) used mixed-integer linear programming for solving this problem. Khishvand et al. (2015) used a nonlinear programming approach for solving this problem. In addition to the mentioned works, there are some other numerical methods for gas allocation optimization in McCracken and Chorneyko (2006), Lo (1992), Staudtmeister and Rokahr (1997) and El-Massry and Price (1995).

The numerical methods were common for years. However, they suffered from a high complexity in the problems with a little more complexity. They were very slow when the number of parameters increased and had some big problems when dealing with constraint optimization. Thus, using them for all people in all problems was not an easy and applicable way, so some new methods were born.

4.3 Heuristic Algorithms

As the problems became more complex, the number of variables increased and using numerical methods became more tedious. In this situation, using heuristic algorithms became much more attractive (Lima Silva et al. 2015; Buitrago et al. 2016; Christensen and Bastien 2016).

In heuristic algorithms, some possible solutions are initially selected, then during some iterations (generations) this population is modified until a satisfying solution is found. There are different algorithms in this category that have been used or can be used in a gas allocation optimization problem such as: Genetic Algorithm (GA) (Ray and Sarker 2007; Ghaedi et al. 2013), Scatter Search (SS) (Chithra Chakra et al. 2013), Simulated Annealing (Raoufi et al. 2015), Tabu Search (Anon 2010), Artificial immune system (Araujo et al. 2003), Memetic Algorithm (Neri and Cotta 2012), Ant Colony Algorithm (ACO) (Ghaedi et al. 2013), Particle Swarm Optimization (PSO) (Hamedi et al. 2011; Hamedi and Khamehchi 2012), Differential Evolution (DE) (Price et al. 2006), Cross Entropy Method (CEM) (Bejan 1995), Harmony Search (HS) (Anon 2011), Bootstrap Algorithm (BA) (Slupphaug and Elgsaeter 2013), Bees Optimization (BO) (Jansen and Shoham 1994), Glowworm Swarm Optimization (GSO) (Fonseca and Fleming 1995), Bee Colony Algorithm (ABC) (Zitzler et al. 2000), Honey bee Mating Optimization (HMO) (Afshar et al. 2007), Intelligent Water Drops (IWD) (Shah-Hosseini 2009), Imperialist Competitive Algorithm (ICA) (Atashpaz-Gargari and Lucas 2007), Monkey Search (MS) (Mucherino et al. 2007), League Championship Algorithm (LCA) (Husseinzadeh Kashan 2011), Gravitational Search Algorithm (GSA) (Su and Wang 2015), Bat Algorithm (BA) (Yang 2011), Galaxy based Search Algorithm (GbSA) (Shah-Hosseini 2011), Spiral Optimization (SO) (Benasla et al. 2014), Teaching Learning Based Optimization (TLBO) (Rao et al. 2011), Krill Herd (KH) Algorithm (Gandomi and Alavi 2012), Differential Search Algorithm (DSA) (Price et al. 2006), firefly optimization (Kisi and Parmar 2016), bat optimization (Meng et al. 2015), cuckoo search (Huang et al. 2016).

As an example, Fig. 4.3 shows a pseudo code of the genetic algorithm, and other algorithms have a similar procedure.

Fig. 4.3
figure 3

Pseudo code of genetic algorithm (Beheshti et al. 2013)

Full size image

These algorithms find the optimum solutions by step by step modification. Figure 4.4 shows the optimization process in a gas allocation optimization with heuristic algorithms.

Fig. 4.4
figure 4

Using heuristic algorithm to maximize the NPV in a gas allocation optimization (Mahmudi and Sadeghi 2013)

Full size image

There are some works that have used a hybrid of Heuristic algorithms for gas allocation optimization. Zerafat et al. (2009) and Khamehchi et al. (2009) used both the genetic algorithm and ant colony and Ghaedi et al. (2013) used a hybrid of the genetic algorithm for solving this optimization problem. Rasouli et al. (2015) used a hybrid of the genetic algorithm and neural network and created a real-time optimization. Mahdiani and Khamehchi (2015) compared the genetic algorithm and a hybrid of the genetic algorithm and quasi-Newton for solving the problem and said using the hybrid was a more efficient method. Mahdiani (2013) in his M.Sc. thesis compared some of the most common heuristic algorithms for gas allocation optimization problems. These algorithms include the genetic algorithm, simulated annealing, particle swarm optimization, differential search, cuckoo search, firefly optimization and harmony search. He considered different case studies and compared their optimum points and the convergence speed. He concluded that in most cases particle swarm optimization has the best optimum point and the highest speed and is highly recommended for gas allocation optimization problems. Firefly optimization occasionally leads to a local optimum point and simulated annealing is often slower than other algorithms. Finally, the performances of the other four algorithms are similar but not as good as the particle swarm optimizer. However, in some way their results can be accepted. During his studies he observed that in most cases firefly optimization found a local optimum point. But on the other hand, the rate of optimum point improvement in different iterations is very fast. After summarizing the result of the performance of different algorithms he concluded that the simulated annealing can find a good optimum point but its problem is that this algorithm is very slow. It seems that if the problem was first optimized by another algorithm and then the found optimum point was used as the start point of the simulated annealing the resulted point could have a very good total production oil rate. In one case he injected 18 MMscf/d gas to 20 different wells by various heuristic algorithms and then he compared their total oil production. Figure 4.5 shows the amount of total oil production.

Fig. 4.5
figure 5

The comparison of the total oil production of allocating 18 MMscf gas to 20 wells by different heuristic algorithms (Mahdiani 2013)

Full size image

For comparing the speed of these algorithms he did not compare the runtime of the optimizers, because it depends on the used computer and its internal hardware and software configuration. Instead he compared the number of fitness function evaluation. Figure 4.6 shows the number of fitness function evaluation of different algorithms.

Fig. 4.6
figure 6

The comparison of the total amount of fitness function evaluation of the heuristic algorithms in allocating 18 MMscf of gas to 20 wells (Mahdiani 2013)

Full size image

In most of the considered cases Mahdiani saw the huge number of fitness function evaluation of the simulated annealing in comparison to other algorithms. In addition to the above factors, he considered another factor called optimizer speed. This showed the average amount of fitness function improvement by the number of fitness function evaluation (Fig. 4.7).

Fig. 4.7
figure 7

The comparison of the optimizer speed of the heuristic algorithms in allocating 18 MMscf of gas to 20 wells (Mahdiani 2013)

Full size image

Mahdiani also changed the number of wells and maximum amount of available lift gas and repeated his calculation to see the application of the optimization algorithms in different conditions.