An alternative transformation in ranking using l1-norm in data envelopment analysis

Ziari, S. Article An alternative transformation in ranking using l1-norm in data envelopment analysis Journal of Industrial Engineering International Provided in Cooperation with: Islamic Azad University (IAU), Tehran Suggested Citation: Ziari, S. (2016) : An alternative transformation in ranking using l1-norm in data envelopment analysis, Journal of Industrial Engineering International, ISSN 2251-712X, Springer, Heidelberg, Vol. 12, pp. 401-405, https://doi.org/10.1007/s40092-016-0149-7 This Version is available at: https://hdl.handle.net/10419/157497 Standard-Nutzungsbedingungen: Die Dokumente auf EconStor dürfen zu eigenen wissenschaftlichen Zwecken und zum Privatgebrauch gespeichert und kopiert werden. Sie dürfen die Dokumente nicht für öffentliche oder kommerzielle Zwecke vervielfältigen, öffentlich ausstellen, öffentlich zugänglich machen, vertreiben oder anderweitig nutzen. Sofern die Verfasser die Dokumente unter Open-Content-Lizenzen (insbesondere CC-Lizenzen) zur Verfügung gestellt haben sollten, gelten abweichend von diesen Nutzungsbedingungen die in der dort genannten Lizenz gewährten Nutzungsrechte. Terms of use: Documents in EconStor may be saved and copied for your personal and scholarly purposes. You are not to copy documents for public or commercial purposes, to exhibit the documents publicly, to make them publicly available on the internet, or to distribute or otherwise use the documents in public. If the documents have been made available under an Open Content Licence (especially Creative Commons Licences), you may exercise further usage rights as specified in the indicated licence. http://creativecommons.org/licenses/by/4.0/ TECHNICAL ARTICLE An alternative transformation in ranking using l1-norm in data envelopment analysis S. Ziari 1 Received: 10 December 2014 / Accepted: 15 April 2016 / Published online: 3 May 2016 ÓThe Author(s) 2016. This article is published with open access at Springerlink.com Abstract Jahanshahloo et al. (Appl Math Comput 153:215–224, 2004) propose a method for ranking extremely efficient decision making units (DMUs) in data envelopment analysis (DEA) using super-efficiency technique and l1-norm and they show that the presented method is able to eliminate the existing difficulties in some methods. This paper suggests an alternative transformation to convert the nonlinear model proposed by Jahanshahloo et al. (Appl Math Comput 153:215–224, 2004) into a linear programming form. The present paper shows that model with this transformation is equivalent to the above-men- tioned nonlinear model. The motivation of this work is to linearize the proposed nonlinear model by Jahanshahloo et al. (Appl Math Comput 153:215–224, 2004) which has the higher order of complexity. Keywords Data envelopment analysis (DEA) Ranking  Efficiency Extremely efficient Chinese cities Introduction For many applications, ranking DMUs is an important and essential procedure to decision makers in DEA, especially when there are extremely efficient DMUs. In these regards, several methods have been proposed for ranking of the extreme efficient DMUs, see Andersen and Petersen (1993), Mehrabian et al. (1999) and Jahanshahloo et al. (2004). A DMU is called extremely efficient if it cannot be represented as a linear combination (with nonnegative coefficients) of the remaining DMUs (Charnes et al. 1991). Andersen and Petersen (AP) (Andersen and Petersen 1993) proposed a new procedure to rank efficient DMUs. The AP model determines the rank of a given DMU by removing it from the reference set and by computing its super-effi- ciency score. However, the AP model may be infeasible in some cases. It is proved that super-efficient DEA models are infeasible (see Thrall 1996; Seiford and Zhu 1999). Mehrabian et al. (1999) suggested the MAJ model for complete ranking of efficient DMUs, but their approach lacks feasibility in some cases, too. To overcome the drawbacks of the AP (Andersen and Petersen 1993) and MAJ (Mehrabian et al. 1999) models, Jahanshahloo et al. (2004) presented a method to rank the extremely efficient DMUs in DEA models with constant and variable returns to scale using L1-norm. Their proposed model is a nonlinear programming form which has the higher order of complexity in solving. In addition, a complex procedure was applied in Jahanshahloo et al. (2004) to provide the nonlinear model into a linear one which obtains an approximately optimal solution. Wu and Yan (2010) have also suggested an effective transformation to convert the nonlinear model in Jahanshahloo et al. (2004) into a linear model. Recently, Ziari and Raissi (2016) proposed an approach to rank the efficient DMUs in DEA based on minimizing distance of the under evaluation DMU to the frontier of efficiency. Following this trend, the present paper is an attempt to provide an alternative transformation to convert the nonlinear model in Jahanshahloo et al. (2004) into a linear model. The proposed model in this paper linearizes model in Jahanshahloo et al. (2004)ina way which is different from the presented method in Wu and Yan (2010). To linearize model in Jahanshahloo et al. (2004), the presented model uses the number of fewer &S. Ziari [email protected] 1 Department of Mathematics, Firoozkooh Branch, Islamic Azad University, Firoozkooh, Iran 123 J Ind Eng Int (2016) 12:401–405 DOI 10.1007/s40092-016-0149-7 auxiliary variables with respect to proposed model in Wu and Yan (2010). Furthermore, it is shown that the model with this transformation is equivalent to the nonlinear model and is easier to be solved. The rest of the paper is organized as follows. Section 2reviews some ranking methods, especially the model by Jahanshahloo et al. (2004). The paper proposes an alternative transformation in Sect. 3. Section 4re-executes the empirical example by Jahanshahloo et al. (2004) for illustration. The last Section concludes the study. Review of some ranking models In this section, we review some ranking models in data envelopment analysis. In the following subsections, it is assumed that there are nDMUs and for each DMUjðj¼ 1;...;nÞa vector of inputs ðXjÞis considered to produce a vector of outputs ðYjÞ, where Xj¼ðx1j;x2j;...;xmjÞand Yj¼ðy1j;y2j;...;ysjÞ. It is also assumed that Xj0;Yj0;Xj6¼ 0;and Yj6¼ 0 for every j¼1;...;n. AP model The ranking method proposed by Andersen and Petersen (1993) is a supper efficiency model. In the AP model, DMU under evaluation is excluded from reference set and using other units, the rank of given DMU is obtained. The input-oriented AP model using the CRS super-ef- ficiency model is as follows: min h s:t:X n j¼1;j6¼ k kjxij hxik;i¼1;...;m X n j¼1;j6¼ k kjyrj yrk;r¼1;...;s kj0;j¼1;...;n;j6¼ k; ð1Þ where kj;j¼j¼1;...;n;j6¼ kand hare the variables of model. In addition, the output-oriented AP model using the CRS super-efficiency model is as follows: max / s:t:X n j¼1;j6¼ k kjxij xik;i¼1;...;m X n j¼1;j6¼ k kjyrj /yrk;r¼1;...;s kj0;j¼1;...;n;j6¼ k; ð2Þ where kj;j¼j¼1;...;n;j6¼ kand /are the variables of model. The main drawbacks of this model are infeasibility and instability for some DMUs. It can be said that a model is stable if the DMU under evaluation which is efficient remains efficient after perturbation on data. MAJ model This ranking model is proposed by Mehrabian et al. (1999) to solve infeasibility of AP models in some cases. The MAJ model can be expressed as follows: min 1 þw s:t:X n j¼1;j6¼ k kjxij xik þw;i¼1;...;m X n j¼1;j6¼ k kjyrj yrk;r¼1;...;s kj0;j¼1;...;n;j6¼ k; ð3Þ where kj;j¼j¼1;...;n;j6¼ kand ware the variables of model. L1-norm model In this subsection, the model of Jahanshahloo et al. (2004) is explained as follows. Then the production possibility set (PPS) with constant returns to scale Tcand the PPS with variable returns to scale Tvare defined as: Tc¼ðX;YÞjXX n j¼1 kjXj;YX n j¼1 kjYj;kj0;j¼1;...;n () ; ð4Þ and Tv¼ðX;YÞjXX n j¼1 kjXj;YX n j¼1 kjYj;X n j¼1 kj¼1kj0;j¼1;...;n () ; ð5Þ respectively. DMUkis assumed to be extremely efficient. By removing ðXk;YkÞfrom Tc, the production possibility set T0 c is defined as: T0 c¼ðX;YÞjXX n j¼1;j6¼ k kjXj;YX n j¼1;j6¼ k kjYj;kj0;j¼1;...;n 8 > < > : 9 > = > ; : ð6Þ To obtain the ranking score of DMUkthe model in Jahanshahloo et al. (2004) is considered as follows: 402 J Ind Eng Int (2016) 12:401–405 123 min Cc kðX;YÞ¼X m i¼1 xixik jj þX s r¼1 yryrk jj s:t:X n j¼1;j6¼ k kjxij xi;i¼1;...;m X n j¼1;j6¼ k kjyrj yr;r¼1;...;s xi0;yr0i¼1;...;m;r¼1;...;s kj0;j¼1;...;n;j6¼ k; ð7Þ where X¼ðx1; :::; xmÞ,Y¼ðy1; :::; ysÞand k¼ðk1; :::; kk1;kkþ1; :::; knÞare the variables of the model (7) and Cc kðX;YÞis the distance between ðXk;YkÞand (X,Y)byl1- norm. To convert model (4) into a linear model, [1] defines the set T00 cas follows: T00 c¼T0 c\nðX;YÞjXXkand YYkoð8Þ and they apply the scaling input and output data by normalization. After these changes, an approximately optimal solution of model (7) is obtained by solving a linear programming model related to it. In next section, an alternative transformation to model (7) is considered and to obtain the optimal solution, an equivalent linear programming model is solved. An alternative transformation For converting model (7) into a linear model, the following transformation is utilized: xixik jj aii¼1;...;mand yryrk jj brr¼1;...;s:Thus, we have: xixik ai;i¼1;...;m; xixik ai;i¼1;...;m; and yryrk br;r¼1;...;s; yryrk br;r¼1;...;s:  Then Model (7) can be converted into the following linear programming problem: min Cc kðX;YÞ¼X m i¼1 aiþX s r¼1 br s:t:X n j¼1;j6¼ k kjxij xi;i¼1;...;m X n j¼1j6¼ k kjyrj yr;r¼1;...;s xixik ai;i¼1;...;m; xiþxik ai;i¼1;...;m; yryrk br;r¼1;...;s; yrþyrk br;r¼1;...;s; xi0;yr0;ai0;br0;i¼1;...;m;r¼1;...;s; kj0;j¼1;...;n;j6¼ k; ð9Þ where X¼ðx1; :::; xmÞ;Y¼ðy1; :::; ysÞ;a¼ða1; :::; amÞ, b¼ðb1; :::; bsÞand k¼ðk1; :::; kk1;kkþ1; :::; knÞare the variables of model (9). It is obvious that model (9) is equivalent with model (7). Furthermore, model (9) is a linear programming problem which can easily provide the optimal solution of model (7). The above-proposed model includes 3ðmþnÞconstraints whereas Wu and Yan (2010) model has 2ðmþnÞcon- straints that obviously the Wu and Yan (2010) model is more efficient than the above model. To overcome this problem, we proposed the following model which is more efficient with respect to Wu and Yan (2010) model. The efficient proposed model is as follows: min Cc kðX;YÞ¼X m i¼1 ðxixikÞþX s r¼1 ðyrþyrkÞ s:t:X n j¼1;j6¼ k kjxij xi;i¼1;...;m X n j¼1;j6¼ k kjyrj yr;r¼1;...;s xixik;i¼1;...;m yryrk;r¼1;...;s xi0;yr0i¼1;...;m;r¼1;...;s kj0;j¼1;...;n;j6¼ k; ð10Þ where X¼ðx1; :::; xmÞ;Y¼ðy1; :::; ysÞand k¼ðk1; :::; kk1;kkþ1; :::; knÞare the variables of model (10). Next, model (10) is reformulated by imposing the convexity constraint Pn j¼1;j6¼ kkj¼1on(10), to extend the model (10) from the constant returns to scale to the variable returns to scale case. Then, to obtain the ranking score of DMU under evaluation, the following linear programming problem is solved: min Cc kðX;YÞ¼X m i¼1 ðxixikÞþX s r¼1 ðyrþyrkÞ s:t:X n j¼1;j6¼ k kjxij xi;i¼1;...;m X n j¼1;j6¼ k kjyrj yr;r¼1;...;s X n j¼1;j6¼ k kj¼1 xixik;i¼1;...;m yryrk;r¼1;...;s kj0;j¼1;...;n;j6¼ k xi0;yr0i¼1;...;m;r¼1;...;s kj0;j¼1;...;n;j6¼ k; ð11Þ J Ind Eng Int (2016) 12:401–405 403 123 Model (11) is similar to model (10) which can be solved by any classical mathematical tool such as GAMS. Empirical example In this section, we apply DEA model (11) on the data set used by Jahanshahloo et al. (2004), with the assumption of variable returns to scale. The data set consists of 28 DMUs with 3 inputs and 3 outputs. Data are originally reported by Charnes et al. (1989) which comprised 28 Chinese cities (DMUs) in 1983. The inputs are labor, working funds, and investment. The outputs are gross industrial output value, profit and taxes, and retail sales. The data in Table 1should be normalized before applying model (11). Table 2 includes the ranking results for 10 extremely efficient DMUs in model (11)ðDMU1;DMU2;DMU6;DMU8; DMU21;DMU23;DMU24;DMU25;DMU26;DMU27Þ. Note that in the empirical study these results are the same as the studies by Jahanshahloo et al. (2004) and Wu and Yan (2010). In this study, we have presented a method for converting the nonlinear programming model by Jahanshahloo et al. (2004) into linear programming problem Table 1 The data for 28 Chinese cities DMU1 Input 1 Input 2 Input 3 Output 1 Output 2 Output 3 1 483.01 1,397,736 616,961 6,785,798 1,594,957 1,088,699 2 371.95 855,509 385,453 2,505,984 545,140 835,745 3 268.23 685,584 341,941 2,292,025 406,947 473,600 4 202.02 452,713 117,424 1,158,016 135,939 336,165 5 197.93 471,650 112,634 1,244,124 204,909 317,709 6 178.96 423,124 189,743 1,187,130 190,178 605,037 7 148.04 367,012 97,004 658,910 86,514 239,760 8 184.93 408,311 111,904 993,238 1,411,954 353,896 9 123.33 245,542 91,861 854,188 135,327 239,360 10 116.91 305,316 91,710 606,743 78,357 208,188 11 129.62 295,812 92,409 736,545 114,365 298,112 12 106.26 198,703 53,499 454,684 67,154 233,733 13 89.70 210,891 95,642 494,196 78,992 118,553 14 109.26 282,209 84,202 842,854 149,186 243,361 15 85.50 184,992 49,357 776,285 116,974 234,875 16 72.17 222,327 73,907 490,998 117,854 118,924 17 76.18 161,159 47,977 482,448 67,857 158,250 18 73.21 144,163 43,312 515,237 114,883 101,231 19 86.72 190,043 55,326 625,514 173,099 130,423 20 69.09 158,436 66,640 382,880 74,126 123,968 21 77.69 135,046 46,198 867,467 65,229 262,876 22 97.42 206,926 66,120 830,142 128,279 242,773 23 54.96 79,563 43,192 521,684 37,245 184,055 24 67.00 144,092 43,350 869,973 86,859 194,416 25 46.30 100,431 31,428 604,715 55,989 127,586 26 65.12 96,873 28,112 601,299 37,088 224,855 27 20.09 50,717 54,650 145,792 11,816 24,442 28 69.81 117,790 30,976 319,218 31,726 169,051 Table 2 The results of ranking by applying model (11)DMU 1268212324252627 Ranking result 18327109564 Value of obj. function 1.521 0.015 0.128 0.700 0.024 0.010 0.013 0.038 0.037 0.090 404 J Ind Eng Int (2016) 12:401–405 123 using an alternative transformation, and it can easily be solved. It is worth nothing that some of the input data of Table 3 in Jahanshahloo et al. (2004) were mistakenly recorded and in this Section we have corrected them. Conclusion Jahanshahloo et al. (2004) propose a new ranking method using super-efficiency technique and l1-norm. It was shown that the proposed method is able to eliminate the existing problems in some methods. In this regard, this paper provides an alternative transformation for converting the nonlinear programming model by Jahanshahloo et al. (2004) into the linear programming model which is equivalent to the original nonlinear model. In addition, we proposed the new efficient model which gives the same solutions of original model proposed by Jahanshahloo et al. (2004). Considering the higher order of complexity of nonlinear model (7), the proposed treatment in this article is easier to be utilized. Open Access This article is distributed under the terms of the Creative Commons Attribution 4.0 International License (http://crea tivecommons.org/licenses/by/4.0/), which permits unrestricted use, distribution, and reproduction in any medium, provided you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons license, and indicate if changes were made. References Andersen P, Petersen NC (1993) A procedure for ranking efficient units in data envelopment analysis. Manage Sci 39:1261–1264 Charnes A, Cooper WW, Li S (1989) Using DEA to evaluate relative efficiencies in the economic performance of Chinese-key cities. Soc Econ Plan Sci 23:325–344 Charnes A, Cooper WW, Thrall RM (1991) A structure for classifying and characterizing efficiency and inefficiency in data envelopment analysis. J Prod Anal 2:197–237 Jahanshahloo GR, Hosseinzadeh Lotfi F, Shoja N, Tohidi G, Razavian S (2004) Ranking by using L1-norm in data envelopment analysis. Appl Math Comput 153:215–224 Liang L, Wu J, Cook WD, Zhu J (2008) Alternative secondary goals in DEA cross efficiency evaluation. Int J Prod Econ 113:1025–1030 Mehrabian S, Alirezaee MR, Jahanshahloo GR (1999) A compelete efficiency ranking of decision making units in data envelopment analysis. Comput Optimiz Appl 14:261–266 Seiford LM, Zhu J (1999) Infeasibility of super-efficiency data envelopment analysis models. INFOR 37(2):174–187 Thrall RM (1996) Duality, classification and slacks in DEA. Ann Oper Res 66:109–138 Wu J, Yan H (2010) An effective transformation in ranking using l1- norm in data envelopment analysis. Appl Math Comput 217:4061–4064 Ziari S, Raissi S (2016) Ranking efficient DMUs using minimizing distance in DEA. J Ind Eng Int. doi:10.1007/s40092-016-0141-2 J Ind Eng Int (2016) 12:401–405 405 123