Interior Points Algorithms in Data Envelopment Analysis (Case Study: An Iranian Bank)

Authors

  • Farhad Hosseinzade Lotfi * Department of Mathematics, Science and Research Branch, Islamic Azad University, Tehran, Iran. https://orcid.org/0000-0001-5022-553X
  • Amin Jabbari Department of Mathematics, Science and Research Branch, Islamic Azad University, Tehran, Iran.

https://doi.org/10.48314/anowa.v1i1.31

Abstract

In this paper, interior point methods are discussed and analyzed. First, general aspects of Data Envelopment Analysis (DEA) are expressed, then the concept of efficiency, CCR and BCC, BCC-CCR, CCR-BCC  models, and the reference sets in DEA  models and super-efficiency in ranking are presented. Ellipsoid methods that theoretically prove that linear programming problems are efficiently solvable are also used. The result is significant since when a problem is solvable, practical and efficient algorithms can be developed. The ellipsoid method is not a practical algorithm for solving linear programming problems. Finally, a new category of algorithms, known as the interior point optimization method, is introduced, both valuable and efficient. The other advantage of the process above is that the complexity of the interior point algorithm is in polynomial order. In contrast, the simplex algorithm uses exponential order in the worst cases. This is a good reason to indicate the priority of the interior point optimization algorithm compared with the simplex algorithm. Therefore, this point justifies using the interior point methods in DEA.

Keywords:

Interior points algorithms, Data envelopment analysis, Efficiency, Linear programming

References

  1. [1] Charnes, A., Cooper, W. W., & Rhodes, E. (1978). Measuring the efficiency of decision making units. European journal of operational research, 2(6), 429–444. https://doi.org/10.1016/0377-2217(78)90138-8
  2. [2] Banker, R. D., Charnes, A., & Cooper, W. W. (1984). Some models for estimating technical and scale inefficiencies in data envelopment analysis. Management science, 30(9), 1031-1142. https://doi.org/10.1287/mnsc.30.9.1078
  3. [3] Cooper, W. W., Seiford, L. M., Tone, K. (2007). Data envelopment analysis: A comprehensive text with models, applications, references and DEA-solver software (Vol. 2). Springer. https://doi.org/10.1007/b109347
  4. [4] Bertsimas, D., & Tsitsiklis, J. N. (1997). Introduction to linear optimization (Vol. 6). Athena Scientific Belmont, MA. https://B2n.ir/tb1508
  5. [5] Cooper, A. C. W. W., & Charnes, W. (1962). Programming with linear fractional functionals. Naval research logistics quarterly, 9(3), 181–186. https://doi.org/10.1002/nav.3800090303
  6. [6] Alizadeh, F. (1995). Interior point methods in semidefinite programming with applications to combinatorial optimization. SIAM journal on optimization, 5(1), 13–51. https://doi.org/10.1137/0805002
  7. [7] Alizadeh, F., Haeberly, J. P. A., & Overton, M. L. (1998). Primal-dual interior-point methods for semidefinite programming: Convergence rates, stability and numerical results. SIAM journal on optimization, 8(3), 746–768. https://doi.org/10.1137/S1052623496304700
  8. [8] Karmarkar, N. (1984). A new polynomial-time algorithm for linear programming. Proceedings of the Sixteenth annual acm symposium on theory of computing (pp. 302–311). Association for Computing Machinery. https://doi.org/10.1145/800057.808695
  9. [9] Borgwardt, K. H. (2012). The simplex method: A probabilistic analysis (Vol. 1). Springer Science & Business Media. https://doi.org/10.1007/978-3-642-61578-8
  10. [10] Fiacco, A. V, & McCormick, G. P. (1964). Computational algorithm for the sequential unconstrained minimization technique for nonlinear programming. Management science, 10(4), 601–617. https://doi.org/10.1287/mnsc.10.4.601
  11. [11] Andersen, E. D., & Andersen, K. D. (1995). Presolving in linear programming. Mathematical programming, 71, 221–245. https://doi.org/10.1007/BF01586000
  12. [12] Andersen, K. D. (1996). A modified Schur-complement method for handling dense columns in interior-point methods for linear programming. ACM transactions on mathematical software (TOMS), 22(3), 348–356. https://doi.org/10.1145/232826.232937
  13. [13] Kojima, M., Shindoh, S., & Hara, S. (1997). Interior-point methods for the monotone semidefinite linear complementarity problem in symmetric matrices. SIAM journal on optimization, 7(1), 86–125. https://doi.org/10.1137/S1052623494269035
  14. [14] Jansen, B., Roos, C., & Terlaky, T. (1996). A polynomial primal-dual Dikin-type algorithm for linear programming. Mathematics of operations research, 21(2), 341–353. https://doi.org/10.1287/moor.21.2.341
  15. [15] Chvatal, V. (1983). Linear programming.” W. H. Freeman and Company, New York. https://B2n.ir/pb2293
  16. [16] Freund, R. M. (1991). Polynomial-time algorithms for linear programming based only on primal scaling and projected gradients of a potential function. Mathematical programming, 51(1), 203–222. https://doi.org/10.1007/BF01586933
  17. [17] Freund, R. W., & Jarre, F. (1997). A QMR-based interior-point algorithm for solving linear programs. Mathematical programming, 76, 183–210. https://doi.org/10.1007/BF02614383
  18. [18] Gonzaga, C. C. (1990). Polynomial affine algorithms for linear programming. Mathematical programming, 49, 7–21. https://doi.org/10.1007/BF01588776
  19. [19] Ahuja, R. K., Magnanti, T. L., Orlin, J. B. (1993). Network flows: Theory, algorithms, and applications (Vol. 1). Prentice Hall Englewood Cliffs, NJ. https://B2n.ir/jg9167
  20. [20] Adler, I., & Monteiro, R. D. C. (1991). Limiting behavior of the affine scaling continuous trajectories for linear programming problems. Mathematical programming, 50, 29–51. https://doi.org/10.1007/BF01594923
  21. [21] Jarre, F., & Saunders, M. A. (1995). A practical interior-point method for convex programming. SIAM journal on optimization, 5(1), 149–171. https://doi.org/10.1137/0805008
  22. [22] Karmarkar, N. K., Lagarias, J. C., Slutsman, L., & Wang, P. (1989). Power series variants of Karmarkar-type algorithms. AT & T technical journal, 68(3), 20–36. https://doi.org/10.1002/j.1538-7305.1989.tb00316.x
  23. [23] Fourer, R., & Mehrotra, S. (1993). Solving symmetric indefinite systems in an interior-point method for linear programming. Mathematical programming, 62(1), 15–39. https://doi.org/10.1007/BF01585158
  24. [24] Kojima, M., Mizuno, S., & Yoshise, A. (1989). A primal-dual interior point algorithm for linear programming. Springer. https://doi.org/10.1007/BF01582151
  25. [25] Den Hertog, D. (2012). Interior point approach to linear, quadratic and convex programming: Algorithms and complexity (Vol. 277). Springer Science & Business Media. https://doi.org/10.1007/978-94-011-1134-8

Downloads

Published

2025-02-17

Issue

Vol. 1 No. 1 (2025): Annals of Optimization With Applications (ANOWA)

Section

Articles

How to Cite

Interior Points Algorithms in Data Envelopment Analysis (Case Study: An Iranian Bank). (2025). Annals of Optimization With Applications, 1(1), 1-11. https://doi.org/10.48314/anowa.v1i1.31

Similar Articles

1-10 of 11

You may also start an advanced similarity search for this article.