Abstract
Accompanying the increasing popularity of DEA are computationally challenging applications: large-scale problems involving the solution of thousands of linear programs. This paper describes a new problem decomposition procedure which dramatically expedites the solution of these computationally intense problems and fully exploits parallel processing environments. Testing of a new DEA code based on this approach is reported for a wide range of problems, including the largest reported to date: an 8,700-LP banking-industry application.
Similar content being viewed by others
References
A.I. Ali, IDEAS: Integrated Data Envelopment Analysis system, Technical Report, Department of General Business and Finance, University of Massachusetts, Amherst, MA, 1989.
A.I. Ali, Data Envelopment Analysis: Computational issues, Comput. Environ. and Urban Systems 14(1990)157–165.
A.I. Ali, Streamlined computation for Data Envelopment Analysis, European Journal of Operational Research 64(1993) 61–67.
A.I. Ali, Computational aspects of Data Envelopment Analysis, in: DEA: Theory, Methodology, and Applications, A. Charnes, W.W. Cooper, A.Y. Lewin and L.M. Seiford, eds., Kluwer Academic, Boston, 1994, pp. 63–88.
A. I. Ali and L. Seiford, Computational accuracy and infinitesimals in Data Envelopment Analysis, INFOR 31(1989)290–297.
R.D. Banker, A. Charnes and W.W. Cooper, Some models for estimating technical and scale inefficiencies in Data Envelopment Analysis, Management Science 30(1984)1078–1092.
R.S. Barr and M.L. Durchholz, Parallel software for large-scale Data Envelopment Analysis, presented at the Joint National Meeting of ORSA and TIMS, San Francisco, CA, 1992.
R.S. Barr and M.L. Durchholz, Parallel and hierarchical decomposition approaches for solving large-scale DEA models, presented at the Joint National Meeting of ORSA and TIMS, Chicago, IL, 1993.
R.S. Barr and M.L. Durchholz, Parallel and hierarchical decomposition approaches for solving large-scale DEA models, Technical Report 94-CSE-6, Department of Computer Science and Engineering, Southern Methodist University, Dallas, TX, 1994.
R.S. Barr and B.L. Hickman, Reporting computational experiments with parallel algorithms: Issues, measures, and experts' opinions, ORSA Journal on Computing 5(1993)2–18.
R.S. Barr, B.L. Hickman and J.S. Turner, Statistical file merging: a new, constrained network model and parallel solution approach, Technical Report, Department of Computer Science and Engineering, Southern Methodist University, Dallas, TX, 1997.
R.S. Barr, L. Seiford and T.F. Siems, An envelopment-analysis approach to measuring the managerial quality of banks, Annals of Operations Research 42(1993)1–19.
R.S. Barr and T.F. Siems, Predicting bank failure using DEA to quantify management quality, in: Interfaces in Computer Science and Operations Research: Advances in Metaheuristics, Optimization, and Stochastic Modeling Techniques, R. Barr, R. Helgason and J. Kennington, eds., Kluwer Academic, Boston, 1997, pp. 341–365.
R.E. Bixby, Implementing the simplex method: The initial basis, ORSA Journal on Computing 4 (1992)267–284.
R.G. Bland, New finite pivoting rules for the simplex method, Mathematics of Operations Research 2(1977)103–107.
P. Byrnes, R. Färe and S. Grosskopf, Measuring productive efficiency: An application to Illinois strip mines, Management Science 30(1984)671–681.
A. Charnes and W.W. Cooper, Management Models and Industrial Applications of Linear Programming, Wiley, New York, 1961.
A. Charnes, W.W. Cooper, B. Golany, L. Seiford and J. Stutz, Foundations of Data Envelopment Analysis for Pareto-Koopmans efficient empirical production functions, Journal of Econometrics 30(1985)91–107.
A. Charnes, W.W. Cooper and Z.M. Huang, Polyhedral cone-ratio DEA models with an illustrative application to large commercial banks, Journal of Econometrics 46(1990)73–91.
A. Charnes, W.W. Cooper, Z.M. Huang and D.B. Sun, Relations between half-space and finitely generated cones in polyhedral cone-ratio DEA models, International Journal of Systems Science 22(1991)2057–2077.
A. Charnes, W.W. Cooper, A.Y. Lewin and L.M. Seiford, Data Envelopment Analysis: Theory, Methodology, and Application, Kluwer Academic, Boston, 1994.
A. Charnes, W.W. Cooper and E. Rhodes, Measuring the efficiency of decision making units, European Journal of Operational Research 2 (1978)429–444.
A. Charnes, J. Rousseau and J. Semple, An effective non-Archimedean anti-degeneracy/cycling linear programming method especially for Data Envelopment Analysis and like models, Annals of Operations Research 47(1993)271–278.
C.W. Cobb and P.H. Douglas, A theory of production, American Economic Review (Suppl.) (1928) 139–165.
T.H. Cormen, C.E. Leiverson and R.L. Rivest, Introduction to Algorithms, MIT Press, Cambridge, MA, 1990.
M.J. Flynn, Very high-speed computing systems, Proceedings of the IEEE 54(1966)1901–1909.
D.E. Knuth, The Art of Computer Programming. Volume 3: Sorting and Searching, Addison-Wesley, Reading, MA, 1973.
R. Marsten, The design of the XMP linear programming library, ACM Transactions on Mathematical Software 7(1981)481–497.
J.M. Mulvey, Pivot strategies for primal-simplex network codes, Journal of the ACM 25(1978) 206–270.
W. Orchard-Hays, Advanced Linear Programming Computing Techniques, McGraw-Hill, New York, 1968.
F. Phillips, R.G. Parsons and A. Donoho, Parallel microcomputing for Data Envelopment Analysis, Comput., Environ., and Urban Systems 14(1990)167–170.
L.M. Seiford and R.M. Thrall, Recent development in DEA: The mathematical programming approach to frontier analysis, Journal of Econometrics 46(1990)7–38.
R.G. Thompson, L.N. Langemeier, C.-T. Lee, E. Lee and R.M. Thrall, The role of multiplier bounds in efficiency analysis with application to Kansas farming, Journal of Econometrics 46(1990) 93–108.
Rights and permissions
About this article
Cite this article
Barr, R.S., Durchholz, M.L. Parallel and hierarchical decomposition approaches for solving large-scale Data Envelopment Analysis models. Annals of Operations Research 73, 339–372 (1997). https://doi.org/10.1023/A:1018941531019
Issue Date:
DOI: https://doi.org/10.1023/A:1018941531019