A general computational framework and a hybrid algorithm for large-scale data envelopment analysis

This paper develops a new algorithm to accelerate DEA computation for large-scale datasets. We first provide a general DEA computation framework that employs a simple small-size linear program (LP). This LP can obtain all the critical outcomes simultaneously for accelerating DEA computation in the literature. Based on the general computational framework, we propose a new algorithm (called hybrid algorithm) that uses a hybrid strategy of density-increasing mechanism and reference set selection. The hybrid algorithm continuously solves the simple small-size LP to either identify an extreme efficient DMU or directly obtain the efficiency of the DMU under evaluation. To ensure the LPs solved are always in a small size, the hybrid algorithm selects the data of only a small subsample of the identified extreme efficient DMUs into the LPs’ coefficient matrix each time when a DMU is evaluated. A new subsample selection technique is also suggested. The numerical experiment shows that the new technique can select subsample of extreme efficient DMUs more effectively compared with the previous subsample selection technique. Consequently, the hybrid algorithm solves only one or a minuscule number of small-size LPs to obtain each DMU’s efficiency. Therefore, the hybrid algorithm ensures that the size and number of LPs solved for each DMU are small. The computational experiment on large datasets shows that the hybrid algorithm performs more than an order of magnitude faster than the existing representative algorithms.