A method to reduce calculation time of data envelopment analysis problems with big data

Roya Hosseinzadeh; Nima Azarmir Shotorbani; Yasser Jafari; Javad Vakili

doi:10.5269/bspm.62238

Roya Hosseinzadeh Department of Mathematics, Tabriz Branch, Islamic Azad University, Tabriz, Iran https://orcid.org/0000-0002-9352-8212
Nima Azarmir Shotorbani Department of Mathematics, Tabriz Branch, Islamic Azad University, Tabriz, Iran https://orcid.org/0000-0002-4352-7350
Yasser Jafari Department of Mathematics, Shabestar Branch, Islamic Azad University, Shabestar, Iran https://orcid.org/0000-0003-2581-074X
Javad Vakili Department of Mathematics, Statistics and Computer Science, University of Tabriz, Tabriz, Iran

Resumen

Data envelopment analysis problems with big data require solving thousands of linear programs. This article describes a new method that dramatically speeds up the solution of these problems. First, we divide the units into smaller categories, then we identify all the efficient units in the first category, solve the next category together with the efficient units of the previous category, and so on until the last category. In this case, the number of variables and the constraints of each problem is much less; hence much less time is needed to solve problems. Assuming variable returns to scale, an algorithm is designed for big data to calculate runtime using the proposed method, which involves a notable reduction in runtime compared to existing techniques.

Descargas

La descarga de datos todavía no está disponible.

Citas

Banker, R. D., Charnes, A., Cooper, W. W., Some models for estimating technical and scale inefficiencies in data envelopment analysis, Manag. Sci. 30(9), 1078-1092 (1984).

Barr, R. S., Durchholz, M. L., Parallel and hierarchical decomposition approaches for solving large-scale data envelopment analysis models, Ann. Oper. Res. 73, 339-372 (1997).

Charnes, A., Cooper, W. W., Programming with linear fractional functionals, Nav. Res. Logist. 9(3-4), 181-186 (1962).

Charnes, A., Cooper, W. W., Rhodes, E., Measuring the inefficiency of decision making units, Eur. J. Oper. Res. 2(6), 429-444, (1978).

Chen, W. C., Cho, W. J., A procedure for large-scale DEA computations, Comput. Oper. Res. 36(6), 1813-1824 (2009).

Chen, W. C., Lai, S.Y. Determining radial efficiency with a large data set by solving small-size linear programs, Ann. Oper. Res. 250(1), 147-166 (2017).

Dula, J. H., A computational study of DEA with massive data sets, Comput. Oper. Res. 35(4), 1191-1203 (2008).

Dula, J. H., An algorithm for data envelopment analysis, INFORMS. J. Comput. 23(2), 284-296 (2011).

Dula, J. H., Helgason, R.V., A new procedure for identifying the frame of the convex hull of a finite collection of points in multidimensional space, Eur. J. Oper. Res. 92(2), 352-367 (1996).

Dula, J. H., Helgason, R. V., Venugopal, N., An Algorithm for Identifying the Frame of a Pointed Finite Conical Hull, INFORMS. J. Comput. 10(3), 323-330 (1998).

Dula, J. H., Lopez, F. J., DEA with streaming data, Omega. 41(1), 41-47 (2013).

Dula, J. H., Thrall, R. M., A computational framework for accelerating DEA, J. Product. Anal. 16(1), 63-78 (2001).

Khezrimotlagh, D., Zhu, J., Cook, W. D., Toloo, M., Data envelopment analysis and big data, Eur. J. Oper. Res. 274(3) 1047-1054 (2018).

Korhonen, P. J., Siitari, P. A., A dimensional decomposition approach to identifying efficient units in large-scale DEA models, Comput. Oper. Res. 36(1), 234-244 (2009).

Zhu, Q. J., Wu, M., Song, M., Efficiency evaluation based on data envelopment analysis in the big data context, Comput. Oper. Res. 98, 291-300 (2017).