Parallel processing of the Build Hull algorithm to address the large-scale DEA problem
- PDF / 903,024 Bytes
- 29 Pages / 439.37 x 666.142 pts Page_size
- 57 Downloads / 183 Views
Parallel processing of the Build Hull algorithm to address the large-scale DEA problem Tao Jie1 © Springer Science+Business Media, LLC, part of Springer Nature 2020
Abstract Build Hull is currently one of the most efficient methods to address the large-scale data envelopment analysis problem. In this paper, the computational complexity of Build Hull is established, implying that the dimension of the data set has a strong influence on computational efficiency. Based on the complexity result, we find that the “worst density” of Build Hull monotonically increases with respect to dimension. In addition, a two-phase parallel Build Hull algorithm is proposed to enhance the computational efficiency of Build Hull. The parallel procedure is based on the minimum volume enclosing ellipsoid technique, which enables the exclusion of a large number of DMUs in the first phase. A sensitivity analysisbased technique is also proposed to substantially reduce computational time in the second phase. Numerical tests support our theoretical results. Keywords Large scale DEA · Build Hull Algorithm · Parallel processing · Minimum volume enclosing ellipsoid · Sensitivity analysis
1 Introduction The data envelopment analysis (DEA) model is a methodology that measures the relative efficiency of decision making units (DMUs) by using linear programs that is becoming increasingly important in data mining. In recent years, DEA has been successfully applied in various areas, such as energy, supply chain management, the service sector, banking, and transportation (c.f. see Emrouznejad et al. 2008; Mahmoudi et al. 2018). The data for a DEA study consists of n DMUs each characterized by r inputs and s outputs. Each DMU corresponds to a certain point in Rr +s whose components are its input and output values. The sets formed by DMUs, range from convex cones to unbounded polyhedrons (formed by combinations of convex hulls and “inefficiency recession directions”). These sets are referred to as production possibility sets (PPSs), and the boundary of a PPS is referred
In memory of my Mum, Wen Zonglan
B 1
Tao Jie [email protected] Business School, University of Shanghai for Science and Technology, No. 516 Jun Gong Road, Shanghai 200093, China
123
Annals of Operations Research
to as production frontier (PF). A DMU’s efficiency is measured by the distance from its geometric location to a PF. The DMU on a PF is referred to as efficient, and the DMUs that lie in the interior of a PPS are termed inefficient. The shape of a PPS is determined by axioms imposed on DEA, and the choice of different axioms and distance functions results in various DEA models, such as the constant returns to scale (CRS) model, and the variable returns to scale (VRS) model. The emergence of big data has created a new set of problems and challenges for DEA applications, particularly when the scale of the DMUs is large (c.f. see Mishra et al. 2018). Examples can be found in many areas, such as banking (c.f. see Barr and Durchholz 1997; Wheelock and Wilson 2000) and energy manage
Data Loading...
