Sage Journals: Discover world-class research

Abstract

One of the challenging and important subjects in Data Envelopment Analysis (DEA) is the ranking of Decision Making Units (DMUs). In this paper, a new method for ranking the efficient DMUs is firstly proposed by utilizing the DEA technique and also developing a capable metaheuristic, imperialist competitive algorithm, derived from social, political, and cultural phenomena. Efficient DMUs are known as colonizers, and the virtual units, which are within their regions of exclusive domination, are considered as colonies. Efficient units are ranked by utilizing the factor of competition among imperialists to attract each other’s colonies. One advantage of proposed method is that, without solving any mathematical, and complex solution approaches, all extreme and non-extreme units are ranked only by comparing the pairs.

Keywords

Ranking data envelopment analysis imperialist competitive algorithm region of domination

Introduction

Data Envelopment Analysis (DEA) is considered as a non-parametric technique based on mathematical programming, firstly introduced by Charnes et al.¹ DEA assess and measurer the relative efficiency of some homogeneous Decision Making Units (DMUs) which may have multiple inputs and outputs. In the classical models of DEA such as BCC and CCR,^1,2 the level of efficiency of inefficient units is less than one and that of efficient units equals one. This issue creates a problem that is usually the case with most of the above-mentioned models; that is, efficient units cannot be segregated. To solve this problem and to increase the power of segregation among the DMUs, many efforts have been made. For example, one can refer to the two main ranking methods such as AP (Andersen and Petersen)³ and the Cross-Efficiency Method of Sexton et al.⁴

Later, an super-efficient model ranking only efficient units was proposed by Anderson and Peterson.³ They also removed the evaluated decision-making unit is removed from the set of observed DMUs in their approach. Then, the DEA model is utilized for the rest of the DMUs. The main weaknesses of the approach can be stated as to have Instability and infeasibility in some cases, as well as the failure of ranking non-extreme efficient units, and assessments based on different weights.

Recently, to the best of our knowledge, a variety of methods in this area have been developed by researchers to address these infeasibility problems of the super-efficiency models. A MAJ model was proposed by Mehrabian et al.⁵ and received some attentions in the literature later. The proposed model addresses the infeasibility in the basic Andersen and Petersen model. Besides, Jahanshahloo et al.⁶ used Monte Carlo method in order to develop a method abling to rank all kind of efficient DMUs.

For further information about more ranking methods, refer to Dehnokhalaji et al.,⁷ Emrouznejad et al.,⁸ Jahanshahloo et al.,⁹ Liang et al.¹⁰ In line with this, there are algorithms of optimization and meta-heuristic which are inspired by nature as well as socio-political issues and have achieved considerable success as “smart or intelligent” optimization methods alongside classical ones (for instance see Ahmadi and Bazzazi,¹¹ Hajiaghaei-Keshteli and Aminnayeri¹²). In connection with this algorithm, one can refer to the Imperialist Competitive Algorithm presented by Atashpaz-Gargari and Lucas¹³ which stems from social, political, and cultural phenomena. This algorithm has shown its superiority to other optimization algorithms, and has addressed many issues in numerous areas. Apart from these basic contributions, one can mention a variety of recent contributions to the further development of Metaheuristic Algorithms. For instance, see the contributions^14,15 and review paper.¹⁶

In this paper, the efficient units that are aimed to be ranked are considered as imperialists or colonialists. An efficient unit is a unit which is not conquered by any other observed unit; that is, there is no observed unit with less input and more output. To determine the colonies of each imperialist or colonialist, the region of exclusive domination is defined for units, and each virtual unit is considered as a colony for units in this domination area. These points are obtained randomly by utilizing a uniform graph. Competition is run among colonialists with the use of Imperialist Competitive Algorithm, and the colonialist that finally has supremacy and dominance over the colony of all units’ ranks first. The non-convex variable returns to scale model known as FDH Model¹⁷ utilized to compute the power of colonies and imperialists or colonialists. Based on the structure of the FDH model, it can without solving any model leads to the possibility of comparing the power of each imperialist’s colony with that of the colonizer itself.

The main contributions of our paper are as follows: first, In the proposed algorithm, by combing the DEA technique and the Imperialist Competitive Algorithm,¹³ a new type of algorithm is rendered to create a new relation among humanities, mathematics, and social sciences. Second, our proposed approach is fast, memory-efficient, and lacks computational complexity since it does not require solving an optimization model. Third, this proposed method is capable of ranking both extreme and non-extreme units. To illustrate the procedure, we have developed two examples. The first example is a numerical one whose details are rendered in the first stage. In the second example, which included real data, the results were analyzed with those of other existing methods.

The rest of the paper is organized as follows. Section 2 presents a review of the Imperialist Competitive Algorithm and introduces our notation and DEA technology and models. Our proposed algorithm for ranking efficient units is rendered in Section 3. In Section 4, our proposed algorithm is applied to a numerical and a practical example, and Section 5 is the conclusion.

A review of the imperialist competitive algorithm and FDH model in DEA

In this section, first we present the imperialist competitive algorithm proposed by Atashpaz-Gargari and Lucas¹³ which stems from social, political, and cultural phenomena. This algorithm has shown its superiority to other optimization algorithms, and has addressed many issues in numerous areas. Then we review some DEA notations and introduce the technology and FDH model.

Imperialist competitive algorithm

In short, the imperialist competitive algorithm begins in its first step with several countries. Actually, countries, which are considered as the possible solution to the problem, are divided into two colonizers or imperialists and colonies. Enforcing the policy of absorption in line with various areas of optimization, colonizers attract colonies to themselves. Colonial competition, alongside the policy of homogeneity forms the key aspects of this algorithm. It also leads to the countries to move toward an absolute minimum. In terms of optimization, colonialism led to the exit of some countries from being at the bottom of civilization and moved them to another minimum point, which in some cases, proved to be better than the previous condition of the colony. However, this movement required the colony’s advancement towards a more powerful imperialist in various economic and cultural areas; this means the destruction of some of the cultural and social structures. Figure 1 clearly demonstrates this condition. In this figure, due to the homogeneity policy, the colony exits from a minimum point, and enters another minimum point which enjoys a better condition. However, the cost paid for this change is closeness to the imperialist as far as economic, political, and social features are concerned. The continuation of this movement could lead to the entire colonialization or occupation of the colony by the colonizer or imperialist.

Figure 1.

Enforcement of the absorption policy by imperialist on colony.

Here, through the classification of behaviors, finding out their inner order, and finally mathematical modeling of mutual reactions between colonizers and colonies, this complex social phenomenon is organized in the form of a mathematical optimization algorithm. The total power in each empire rests in both emperor and its colonies. In mathematics, this dependence is modeled based on the definition of the imperial power as it equates the power of the emperor adding with a percentage of the average power of its colonies. With the formation of the initial empires, imperialistic rivalry begins among them. Each empire failing to succeed in this competition, will be eliminated from the stage of the colonial competition. Hence, the survival of an empire is subject to its power to attract the colonies of the opponent empires. Consequently, in the course of colonial rivalries, the power of bigger empires shall increase while the weaker ones will be eliminated. To augment their own power, the empires will have to advance their own colonies. With the passage of time, the power of colonies will come close to that of empires, and a kind of convergence shall be observed. The final colonial rivalry ends once there is only one single empire in the world with its colonies.^5,13

Molding of initial empires in imperialist competitive algorithm

Generally, in optimization problem, the objective is to find an optimal response according to the variables defined for the problem. So, an array of variables for the problem must be created and optimized. Here, any solution is known as a “country.” A country is an array of 1 × $N_{var}$ , and this array is defined as follows:

country = [p_{1}, p_{2}, p_{3}, . . ., p_{N_{var}}]

For example, let us assume that we wish to design a PID controller for a control system that has the lowest total sum of the MaxOvershoot and integral of absolute magnitude of the error. In a typical case, possible answers are those that lead to a stable output. For this problem, we create initially a series of possible answers. In this case, Country i will be defined as follows:

countr y_{i} = [K P_{i}, K I_{i}, K D_{i}]

To begin with the algorithm, some of these countries (according to the number of the initial countries of the algorithm) should be created. Therefore, the matrix of the entire countries is formed at random.

\begin{matrix} COUNTRY = [\begin{matrix} countr y_{1} \\ countr y_{2} \\ countr y_{3} \\ . \\ . \\ . \\ countr y_{N_{country}} \end{matrix}] = [\begin{matrix} K P_{1} & K I_{1} & K D_{1} \\ K P_{2} & K I_{2} & K D_{2} \\ K P_{3} & K I_{3} & K D_{3} \\ . & . & . \\ . & . & . \\ . & . & . \\ K P_{N_{country}} & K I_{N_{country}} & K D_{N_{country}} \end{matrix}] \end{matrix}

The costs of a country are found in variables $(p_{1}, p_{2}, p_{3}, . . ., p_{N_{var}})$ by the evaluation of f function. Therefore, $\cos t_{i} = f (countr y_{i}) = f (p_{1}, p_{2}, p_{3}, . . ., p_{N_{var}})$

As to the mentioned objective in designing the controller, this function will be as follows:

F = w_{1} \times MaxOvershoot + w_{2} \times IAE

In which, the MaxOvershoot is the maximum total sum, and the IAE is the integral of absolute magnitude of the error. $w_{1}$ and $w_{2}$ are also the weights that illustrate the importance of each target. Therefore, in order to obtain the cost of a country (a set of parameters of the PID controller), each set of coefficients is considered as a controller, and a systemic step-like response is obtained for this controller. Finally, by calculating the MaxOvershoot and integral of the absolute magnitude of the error, the sum is calculated as the cost of the country (controller coefficients). We look for the best country (the best set of controller coefficients). The algorithm referred to in this paper searches for the best country through generating an initial set of the coefficients and their classification into empires, adopting the imperialist’s absorption policy on colonies, and creating a colonial rivalry among empires.

To begin with the algorithm, we shall create a number of initial $N_{country}$ . $N_{imp}$ is selected as the best member of this group as a colonizer (the countries having the lowest amount of cost function). The remaining $N_{col}$ of countries belongs to an empire. In order to initial distribution of the colonies among imperialists, each colonizer is given a number of colonies based on its power. The policy of absorption and imperialist competition forms the nucleus of this algorithm. In accordance with the absorption policy the colonialist draws the colony to itself regarding the issues of culture and language and so on. As shown in the Figure 2, the colony moves x units towards the imperialist along the connecting line, and reaches to the point of new position of colony. In this Figure 2, d shows the distance between the imperialist and colony and x is a random number with a uniform distribution. For x, we have this formula:

x ~ U (0, β \times d)

In which, $β$ is a larger than unity and is close to 2. A good choice could be $β$ =2.

Figure 2.

Actual movement of colonies towards colonizers.

The existence of the coefficient $β > 1$ causes that while moving towards the colonizer, the colony gets close to it in different aspects. Following the study of the homogeneity phenomenon historically, it became clear that although imperialists seriously followed the absorption policy, things did not turn out to be completely in accordance with their adopted policy since some deviations were observed. By adding a random angle to the colony’s absorption route, the possible deviation is reached. Thus, a slight random angle is also added to the direction of the colony’s movement towards the colonizer. Figure 2 illustrates this condition. Therefore, this time, instead of moving to the extent of x towards the imperialist in the direction of the colony’s vector, the same movement is continued with the same extent but with a $θ$ deviation in the route. We take $θ$ to be random with an even distribution, (though any other desired and appropriate distribution can be utilized). Thence, $θ ~ U (- γ, γ)$ .

In this regard, $γ$ is a desired parameter whose increase causes an augment in the search for surroundings of colonialists, while its decrease could lead colonies, to the most possible extent, to move closer to the imperialists’ vector’s colonies. As to the radian unit for $θ$ , a number closer to 4π is a suitable choice in most implementations.

If in the course of the move, a colony reaches a better position in relation to colonizer; their positions will be switched with each other. In addition, the total power will be defined for an empire according to the total power of the imperialist and a percentage of the colonies’ average power. Therefore, the total cost of an empire is as follows:

\begin{matrix} T . C ._{n} = Cost (imperialis t_{n}) + ξ mean \\ {Cost (colonies of empir e_{n})} \end{matrix}

(1)

In which $T . C ._{n}$ is the total cost of empire n, and $ξ$ is a positive number which is usually considered to be between (0) and (1) but nearer to (0). The less $ξ$ , the total cost of an empire is near to the cost of its central government. Also, the more $ξ$ , the more the effects of the cost of an empire’s colonies. imperialist competition forms another important part of this algorithm. During the imperialist rivalry, weak empires will be disappeared. This is also considered as termination criteria. Figure 3 shows a general view of imperial competition.

Figure 3.

A general view of imperialist competition: Larger empires with a higher degree of probability seize the colonies of other empires.

In this figure, Empire No. (1) is considered as the weakest empire, while empires (2) to (N) compete with each other to seize it. For modeling rivalry among empires to confiscate this colony, at first, the possibility of each empire’s seizure of colony (according to its power) is calculated as follows, taking into account the total cost of the empire. Firstly, the total normalized cost of an empire is calculated from its total cost:

N . T . C ._{n} = max_{i} {T . C ._{i}} - T . C ._{n}

(2)

$T . C ._{n}$ signifies the total cost of the empire n, and $N . T . C ._{n}$ is also its total normalized cost. The lower $T . C ._{n}$ for an empire, the more $N . T . C ._{n}$ . An empire with the minimal cost has the maximum power. An empire’s possible power of seizing another empire’s colony is calculated as follows with regard to the total normalized cost:

p_{p_{n}} = | \frac{N . T . C ._{n}}{\sum_{i = 1}^{N_{imp}} N . T . C ._{i}} |

(3)

As to any empire’s possibility of seizure, a mechanism is needed to give in the disputed colony to one of the empires based on their possible power. Here, a new mechanism is introduced to implement this process. This mechanism has an extremely lower calculated cost in comparison with other mechanisms such as the roulette wheel in the genetic algorithm since the relatively numerous calculation operations eliminate the collective distribution of possibility function, and requires only the possibility density function. The proposed mechanism proposed by Atashpaz-Gargari and Lucas¹³ will be described in the following to give in the disputed colony to the rival empires based on probability.

To divide the colonies among empires randomly according to each empire’s probability of seizure, we form $P$ vector based on the above-mentioned probability values:

P = [p_{p_{1}}, p_{p_{2}}, p_{p_{3}}, . . ., p_{p_{N_{imp}}}]

The vector is of a 1 × N_imp size and is formed from the amount of empire’s probable seizure. Then, the random vector $R$ which is equal in size to vector $P$ is formed. The array of these vectors is random numberswith a uniform distribution within the range of (0 and 1).

\begin{matrix} R = [r_{1}, r_{2}, r_{3}, . . ., r_{N_{imp}}] \\ r_{1}, r_{2}, r_{3}, . . ., r_{N_{imp}} ~ U (0, 1) \end{matrix}

Then, vector $D$ is formed in the following manner:

\begin{matrix} D = P - R = [D_{1}, D_{2}, D_{3}, . . ., D_{N_{imp}}] \\ = [p_{p_{1}} - r_{1}, p_{p_{2}} - r_{2}, p_{p_{3}} - r_{3}, . . ., p_{p_{N_{imp}}} - r_{N_{imp}}] \end{matrix}

Having vector $D$ , colonies is rendered to the empire who has larger index on vector $D$ .¹

Non-convex FDH model in DEA

Let we have $n$ DMUs which consume inputs $x_{ij} (i = 1, 2, . . ., m)$ to produce output $y_{rj} (r = 1, 2, . . ., s)$ . The production possibility set (PPS) or production technology T can be defined as follows: $T = {(x, y) | x \geq 0 can produce y \geq 0}$ .

All through this contribution, technology T holds in the following standard axioms:

The observed activities $(x_{i}, y_{j}) (j = 1, 2, . . ., n)$ belong to T.

Strong Disposability, i.e., if $(x, y) \in T$ and $(x', y') \in R_{+}^{m} \times R_{+}^{s}$ , then $(x', - y') \geq (x, - y) \Rightarrow (x', y') \in T$ .

Thechnology T is a convex set.

Further interpretation of these widely adopted axioms are available in, for instance.⁹ These assumptions are almost universal. While axiom (iii) is also widespread, we do not always maintain it in this contribution. In the proposed approach, we assume that the production technology is a non-convex and variable returns to scale technology. Therefore, we only consider axioms (i) and (ii).

Let we have K observations $(k = 1, \dots, K)$ including inputs and outputs vector of $(x_{k}, y_{k}) \in R_{+}^{m + s}$ . an algebraic representation of nonparametric technologies with axioms of convex (C) and non-convex (NC) under the variable returns to scale assumption can be presented as follows:

\begin{matrix} T^{C} = {(\begin{matrix} x \\ y \end{matrix}) | x \geq \sum_{j = 1}^{n} λ_{j} X_{j}, y \leq \sum_{j = 1}^{n} λ_{j} Y_{j}, \sum_{k = 1}^{K} λ_{k} \\ = 1 and λ_{j} \geq 0, j = 1, 2, \dots, K}, \end{matrix}

and

\begin{matrix} T^{NC} = {(\begin{matrix} x \\ y \end{matrix}) | x \geq \sum_{j = 1}^{n} λ_{j} X_{j}, y \leq \sum_{j = 1}^{n} λ_{j} Y_{j}, \sum_{k = 1}^{K} λ_{k} \\ = 1 and λ_{j} \in {0, 1}, j = 1, 2, \dots, K \end{matrix}},

The activity vector $λ$ when its components are real numbers summing to unity shows that the technology is convex. While in the non-convex technology each component of vector $λ$ is binary integer. The variable returns to scale convex technology satisfies axioms (i) to (iii), while the variable returns to scale non-convex technology adheres to axioms (i) to (ii). In the proposed approach, we assume that the production technology is a non-convex and variable returns to scale technology.

The input-oriented radial technical efficiency model with variable return to scale under non-convex asumption requires the optimization of the following program (see Deprins et al.¹⁷ for more details):

\begin{matrix} Min θ \\ s . t \sum_{j = 1}^{K} λ_{j} x_{ij} \leq θ x_{ip}, i = 1, . . ., m \\ \sum_{j = 1}^{K} λ_{j} y_{rj} \geq y_{rp}, r = 1, . . ., s \\ \sum_{j = 1}^{K} λ_{j} = 1, \\ λ_{j} \in {0, 1}, j = 1, 2, . . ., K \end{matrix}

(4)

The input-oriented efficiency measure which obtains by solving model (4) is a positive number and smaller or equal to unity $(i . e . we have 0 < θ \leq 1)$ . If the evaluted unit locates on the frointier of T, then it is an efficient unit and we have $θ = 1$ , otherwise we have $θ < 1$ . Model (4) is also called FDH model by Tulkens et al.^17,18

In order to calculate the power of imperialists and colonies in our proposed method, we apply the input-oriented FDH model (4). Note that the FDH model (4) is a binary linear model but we can consider the following equivalent steps to obtain the optimum value of objective function of model (4) without solving any models. First, we consider the following model.

\begin{matrix} θ^{j} = Min θ \\ s . t x_{ij} \leq θ x_{ip}, i = 1, . . ., m \\ y_{rj} \geq y_{rp}, r = 1, . . ., s \end{matrix}

(5)

note that model (5) is infeasible for some units.

If $x_{ip} = 0$ for all i, then model (6) is feasible when we have: $x_{ij} = 0, (i = 1, . . ., m)$

Now, let us assume that $x_{ip} > 0$ , hence,

θ^{j} = \underset{i}{Max} {\frac{x_{ij}}{x_{ip}} | x_{ip} > 0}

Therefore,

θ^{*} = \underset{j}{Min} {θ^{j} | y_{rj} \geq y_{rp} & (\forall i (x_{ip} = 0 \to x_{ij} = 0))}

(6)

The efficiency value which obtained from equation (6) is always between 0 and 1. If this value is 1, then the evaluated unit is efficient, otherwise the evaluated unit is inefficient. The value obtained from the relation (6) can be considered as the strength of that unit in the imperialist competitive algorithm. The main advantages of this approach is that the model need not to be solved, and the efficient and inefficient points are specified by a simple mathematical calculation. Hence, instead of solving mixed integer model (4), the equation (6) can be solved separately for each unit, and then the efficiency measure of units are obtained.

Ranking DMUs based on the imperialist competitive algorithm

In order to determine the initial empires, since efficient units have higher efficiency score compared with inefficient units, they are chosen as initial empires in the proposed algorithm. We consider the virtual DMUs which are within each unit’s region of domination as the colonies of each efficient unit.

Definition 1. For $DM U_{p}$ , if the virtual unit $(\begin{matrix} x \\ y \end{matrix}) \in T^{NC}$ is present as $(\begin{matrix} - x_{p} \\ y_{p} \end{matrix}) \geq (\begin{matrix} - x \\ y \end{matrix})$ and there is not any $DM U_{j} \in T^{NC}$ $j \neq p, j = 1, . . ., n,$ such that $(\begin{matrix} - x_{j} \\ y_{j} \end{matrix}) \geq (\begin{matrix} - x \\ y \end{matrix})$ then, the virtual unit $(\begin{matrix} x \\ y \end{matrix})$ is within the region of exclusive domination of $DM U_{p}$ .

Since the number of virtual units in the domination region of efficient units is unlimited, it is difficult and impossible to obtain all of them. Therefore, we select randomly a finite number of units with an uniformly distribution as the units’ colonies.

Let us assume that $DM U_{p}$ , $p \in {1, 2, . . ., n}$ is an efficient unit. Jahanshahloo et al.⁶ defined the dominated area of $DM U_{p}$ as follows:

Definition 2.

An ideal unit $W^{+} = (x_{1}^{+}, . . . ., x_{m}^{+}, y_{1}^{+}, . . . ., y_{s}^{+}) = (x^{+}, y^{+})$ is defined as follows:

{\begin{matrix} x_{i}^{+} = min_{j = 1, . . ., n} {x_{ij}} \\ y_{r}^{+} = max_{j = 1, . . ., n} {y_{rj}} \end{matrix}}

(7)

Also, the counter-ideal unit $W^{-} = (x_{1}^{-}, . . . ., x_{m}^{-}, y_{1}^{-}, . . . ., y_{s}^{-}) = (x^{-}, y^{-})$ is defined as follows. For each r, $y_{r}^{-} = 0$ and,

x_{i}^{-} = \max_{j = 1, \dots, n} {x_{i j}} + δ_{i} i = 1, \dots ., m,

where

\begin{matrix} δ_{i} = {[\frac{1}{n} \sum_{j = 1}^{n} {(x_{ij} - \bar{x_{i}})}^{2}]}^{\frac{1}{2}} \\ \bar{x} = \frac{1}{n} \sum_{j = 1}^{n} x_{ij} \end{matrix}

(8)

Regarding how to obtain the points $W^{+}$ and $W^{-}$ , the domination area of the efficient units is constrained.

Let us assume that N is a set of vectors that is produced randomly with an uniformly distribution, and $N_{p}$ is a set of vectors which is within the domination area of $DM U_{p}$ . Based on this definition, the empire units and each of their colonies are specified. Now, it is time to apply the Imperialist Competitive Algorithm to tank units. Let us assume that ${θ_{j}}^{*}$ is the efficiency score of the unit j which is measured by equation (6). In this case, the power of the empire unit p is obtained by the following formula:

T . c_{p} = {θ_{j}}^{*} + ξ \frac{1}{n} \sum_{j = N_{p}} {θ_{j}}^{*}

(9)

where $ξ$ is a positive number between 0 and 1 and nearer to 0. Usually in applying the Imperialist Competitive Algorithm with value $ξ = 0.05$ , the desired result has been achieved. By utilizing the $N . T c_{p} = \frac{T . c_{p}}{Ma x_{j} {T . c_{j}}}$ , the total normalized power of empire p is achieved.

In addition, the probability of each empire’s power of seizure to take over the colony of the weakest empire is measured as follows:

P = | \frac{N . T . c_{p}}{\sum_{j = 1}^{N_{p}} N . T . c_{i}} |

(10)

Let us assume that $DM U_{k}$ is known as the weakest empire, and $\bar{DMU}$ is its weakest colony. Now, suppose that $DM U_{p}$ in the seizure competition is the candidate for absorbing $\bar{DMU}$ colony. In such a situation, $\bar{DMU}$ is no longer considered as the colony of unit k, and shall be added to the colonies of unit p. We should notice that since these imperialists or colonizers are obtained by the use of even distribution, the replacement of colonies is possible; that is, one colony is added randomly to the domination area of unit p. Similarly, unit k loses all its colonies, and is left out of the domain of competition. This algorithm is continued to the point where there is only one empire left. The remaining empire absorbs all colonies and is ranked first. The rest of the empires are ranked in order of their omission from the realm of competition.

It is important to note that the proposed approach is fast, memory-efficient, and lacks computational complexity since it does not require solving an optimization model. The proposed algorithm was applied using C++on a regular laptop, C++codes available upon request.

First, using a simple numerical example and then a practical or empirical example, we shall demonstrate the results of the algorithm.

Illustrate examples

In this section, a numerical and empirical examples are presented to show our results of the proposed algorithm.

Numerical example

To illustrate our method, consider the example shown in Figure 4. We have 6 DMUs $(A, B, C, D, E, F)$ . The frontier of the production technology is showed by the polyline ABCD and its vertical and horizontal extensions at points A and D, respectively. DMUs $A, B, C$ , and D form the efficient frontier, while DMUs E and F are inefficient and are below the frontier of technology.

Figure 4.

An illustrative example.

In this example, a brief explanation of the results obtained in the first phase of the algorithm is provided.

Step 1: The formation of empires and their colonies

As can be seen in Figure 4, units $A, B, C$ , and D are efficient units. Therefore, they are selected as the initial empires whose domination area is shown in the diagram in a hatched form. For example, the empire formed for $DM U_{C}$ is an area which is only defeated by $DM U_{C}$ , and that’s all. In this example, this area is the rectangle $CC' C ″ C ″'$ . Other empires are formed in the same manner.

The ideal positive and negative points are obtained respectively as such: $w^{+} = (1, 7)$ and $w^{-} = (11, 0)$ based on Definition 2. For each efficient DMU, an empire is formed.

To determine the colonies of each empire, a number of $N = 500000$ points are divided randomly with an even distribution in the dominated area by ideal and counter-ideal points. The second row of Table 1 illustrates the number of each imperialist’s colonies so that units D and B have respectively the maximum and minimum number of colonies. The third row of Table 1 presents the normalized power of each empire prior to the adoption of the absorption policy. In this numerical example, the power of each empire has a direct relation to the number of each empire’s colonies.

Table 1.

The results for empirical example.

Empire	A	B	C	D
Number of colonies (N_p)	15,025	7525	15,520	16,795
Normalized power prior to absorption policy adoption	0.71	0.61	0.85	1
Normalized power after absorption policy adoption	0.73	0.66	0.97	1
Power of seizure	0.67	0.25	0.38	0.40
Ranking	3	4	2	1

Step 2: Adoption of absorption policy

The power of each empire will undergo changes following the adoption of the absorption policy. The fourth row of Table 1 gives an example of the obtained results from this policy. As it is shown, the normalized power of all units, except for unit $D,$ has increased while its power has remained unchanged. As to these results, unit B has the least power after the adoption of the absorption policy. Therefore, its weakest colony should be seized by one of the other empires. From here, we proceed to Step 3.

Step 3: Determining an empire with the maximum seizure power

In this phase, the confiscation power of each empire is specified. The fifth row of Table 1 shows each empire’s power to absorb the weak colony. As it is shown, empire A has the maximum power of absorbing the weakest colony of empire B. Hence, this weak colony leaves the domination area of unit B, and is added to unit A.

To save time and space, the details of other phases are ignored. After the complete implementation of algorithm, our results of ranking are illustrated in the last row of Table 1. Unit D has the highest ranking compared with other units. It should be mentioned that it is not necessary that any unit with more colonies rank the highest. Although it is the case in this example, but, generally speaking, it is not true since given the competition among imperialists, it could be possible that the unit with more colonies is defeated and attains a lower ranking. In addition, the inefficient units of $E$ and F have respectively an efficiency of 0.67 and 0.93, and are ranked respectively in the sixth and fifth place.

Empirical example

In order to test the proposed algorithm practically, we use the data set of 19 DMUs including two inputs and two outputs, are taken from the paper of Jahanshahloo et al.⁶ The information of inputs and outputs are reported in Table 2.

Table 2.

The information of input and output date for empirical example.

$DM U_{j}$	Inputs		Outputs
	$x_{1 j}$	$x_{2 j}$	$y_{1 j}$	$y_{2 j}$
1	81	87.6	5191	205
2	85	12.8	3629	0
3	56.7	55.2	3302	0
4	91	78.8	3379	8
5	216	72	5368	639
6	58	25.6	1674	0
7	112.2	8.8	2350	0
8	293.2	52	6315	414
9	186.6	0	2865	0
10	143.4	105.2	7689	66
11	108.7	127	2165	266
12	105.7	134.4	3963	315
13	235	236.8	6643	236
14	146.3	124	4611	128
15	57	203	4869	540
16	118.7	48.2	3313	16
17	58	47.4	1853	230
18	146	50.8	4578	217
19	0	91.3	0	508

After the implementation of the mentioned algorithm, the results are presented in the Table 3.

Table 3.

The results for empirical example.

Efficient units	$DM U_{1}$	$DM U_{2}$	$DM U_{5}$	$DM U_{9}$	$DM U_{15}$	$DM U_{19}$
Ranking attained fromproposed method
Number of colonies	18,155	73	75,181	15	25,252	112
Rank	2	4	1	6	3	5
Method of Jahanshahlooet al., Monte Carlo method⁶
Number of random points	10,155	3	74,964	2	42,252	16
Rank	3	5	1	6	2	4
Anderson-Peterson (AP)ranking method¹³
Value	115	174	130	Infeasible	133	Infeasible
Rank	4	1	3	–	2	–
MAJ ranking method⁵
Value	105	109	110	104	106	128
Rank	5	3	2	6	4	1

The above Table 3 presents the obtained our results and those from methods such as Monte Carlo,⁶ Anderson-Peterson,³ Mehrabian et al.⁵ which is recognized as MAJ Method.

As it is seen in this table about the proposed method, the 15th unit has more colonies compared with the first unit, but they are ranked vice versa; that is, the first unit stands at a higher ranking than the 15th unit. This result shows that in the rivalry of absorbing colonies, the first unit has acted stronger than the 15th unit. In this method, if the units were ranked according to the number of each unit’s colonies, the obtained results from Monte Carlo Method⁶ would be the same because ranking is performed deponds on the number of points that randomly lie within each unit’s intended area. However, in the proposed method by utilizing the ICA Method, competition is created among units; this rivalry leads to the confiscation of some units’ colonies by another unit. For this reason, the ranking results obtained from this method are different from those attained from Monte Carlo Method.⁶ Compared with Anderson-Peterson³ and MAJ ranking Methods,⁵ the results achieved from the proposed method and those of Monte Carlo Method⁶ are closer to each other. This is due to the fact that the main idea of ranking presented in this paper differs. In MAJ and AP Methods, by eliminating the evaluation aspect, ranking of DMUs is performed based on the observations and determining the efficiency scores for these units. But in the other two methods, as mentioned, this is not the case.

Conclusion

As aforementioned, in this paper we developed an algorithm with a novel method in terms of optimization in the research area in order to create a new relation among humanities, mathematics, and social sciences. The connection among these three aspects is in such a way that mathematics, as an accurate and powerful tool, is usually at the service of humanities, and helps to understand, and analyze its results better. On the contrary, the developed algorithm makes the strong point of humanities and social sciences, that is, their generality and wide-ranging outlook, at the service of mathematics, and utilizes it as an instrument for better understanding mathematics and solving mathematical problems. Therefore, even without taking into account the mathematical and practical capabilities of the developed method, the created link among these three apparent and separate branches has great value as an interdisciplinary research.

In this paper, to rank the DMUs a new approach is proposed. In the mentioned algorithm, by combing the DEA technique and the Imperialist Competitive Algorithm,¹³ a new type of algorithm is rendered; this algorithm ranks all DMUs without solving the mathematical models only by comparing the data. In addition, this proposed method is capable of ranking both extreme and non-extreme units. to illustrate the procedure, we have developed two examples. The first example is a numerical one whose details are rendered in the first stage. In the second example, which included real data, the results were analyzed with those of other existing methods. Considering the characteristics of the algorithm, its results were acceptable, and created a new horizon for improving ranking methods.

Concerning this, there are some proposition for further investigations: In this article, the FDH model the case of variable return to scale with meta-heuristic imperialist competitive algorithm has been used. However, it is also possible to consider other models in DEA with constant and variable return to scale efficiency, like CCR, and BCC models, with the same meta-heuristic imperialist competitive algorithm and compare them. Other meta-heuristic like Keshtel meta-heuristic algorithm¹² which is a newfangled algorithm with different models in DEA, could as well be used to measure decision making units.

Footnotes

Declaration of conflicting interests

The author(s) declared no potential conflicts of interest with respect to the research, authorship, and/or publication of this article.

Funding

The author(s) received no financial support for the research, authorship, and/or publication of this article.

ORCID iD

Mohsen Rostamy-Malkhalifeh

References

Charnes

Cooper

Rhodes

. Measuring the efficiency of decision making units. Eur J Oper Res 1978; 2(6): 429–444.

Banker

Charnes

Cooper

. Some models for estimating technical and scale inefficiencies in data envelopment analysis. Manage Sci 1984; 30(9): 1078–1092.

Andersen

Petersen

. A procedure for ranking efficient units in data envelopment analysis. Manage Sci 1993; 39(10): 1261–1264.

Sexton

Silkman

Hogan

. Data envelopment analysis: critique and extensions. New Dir Eval 1986; 1986(32): 73–105.

Mehrabian

Alirezaee

Jahanshahloo

. A complete efficiency ranking of decision making units in data envelopment analysis. Comput Optim Appl 1999; 14(2): 261–266.

Jahanshahloo

Lotfi

Rezai

, et al. Using Monte Carlo method for ranking efficient DMUs. Appl Math Comput 2005; 162(1): 371–379.

Dehnokhalaji

Hallaji

Soltani

, et al. Convex cone-based ranking of decision-making units in DEA. OR Spectr 2017; 39(3): 861–880.

Emrouznejad

Mustafa

Al-Eraqi

. Aggregating preference ranking with fuzzy data envelopment analysis. Knowl Based Syst 2010; 23(6): 512–519.

Jahanshahloo

Sadeghi

Khodabakhshi

. Fair ranking of the decision making units using optimistic and pessimistic weights in data envelopment analysis. RAIRO: Oper Res 2017; 51(1): 253–260.

10.

Liang

Cook

, et al. Alternative secondary goals in DEA cross-efficiency evaluation. Int J Prod Econ 2008; 113(2): 1025–1030.

11.

Ahmadi

Bazzazi

. Cutoff grades optimization in open pit mines using meta-heuristic algorithms. Resour Policy 2019; 60: 72–82.

12.

Hajiaghaei-Keshteli

Aminnayeri

. Keshtel Algorithm (KA); a new optimization algorithm inspired by Keshtels’ feeding. In: Proceeding in IEEE conference on industrial engineering and management systems, 2013, pp.2249–2253.

13.

Atashpaz-Gargari

Lucas

. Imperialist competitive algorithm: an algorithm for optimization inspired by imperialistic competition. In: 2007 IEEE congress on evolutionary computation (CEC 2007), Singapore, 25–28 September 2007, pp.4661–4667. New York: IEEE.

14.

Alcaraz

Monge

Ramón

. Ranking ranges in cross-efficiency evaluations: a metaheuristic approach. J Oper Res Soc. Epub ahead of print 2 February 2021. DOI: 10.1080/01605682.2020.1860662.

15.

Tayal

Singh

. Integrated SA-DEA-TOPSIS-based solution approach for multi objective stochastic dynamic facility layout problem. Int J Bus Syst Res 2017; 11(1–2): 82–100.

16.

Vaez-Ghasemi

Moghaddas

Askari

, et al. A review of metaheuristic algorithms and data envelopment analysis. Iran J Optim 2020; 12(1): 115–137.

17.

Deprins

Simar

Tulkens

. Measuring labor-efficiency in post offices. In: Public goods, environmental externalities and fiscal competition, 1984, pp. 285–309.

18.

Tulkens

. On FDH efficiency analysis: some methodological issues and applications to retail banking, courts, and urban transit. In: Griliches

Mairesse

(eds) Productivity issues in services at the micro level. Dordrecht, The Netherlands: Springer, 1993, pp.179–206.

Ranking of decision making units using the imperialist competitive algorithm in DEA

Abstract

Keywords

Introduction

A review of the imperialist competitive algorithm and FDH model in DEA

Imperialist competitive algorithm

Molding of initial empires in imperialist competitive algorithm

Non-convex FDH model in DEA

Ranking DMUs based on the imperialist competitive algorithm

Illustrate examples

Numerical example

Step 1: The formation of empires and their colonies

Step 2: Adoption of absorption policy

Step 3: Determining an empire with the maximum seizure power

Empirical example

Conclusion

Footnotes

Declaration of conflicting interests

Funding

ORCID iD

References