Quantum algorithms for solving data envelopment analysis models

Document Type : Research Paper

Authors

1 Department of Mathematics, South Tehran Branch, Islamic Azad University, Tehran, Iran.

2 Department of Mathematics, Qaemshahr Branch, Islamic Azad University, Qaemshahr, Iran

3 Department of Computer Engineering, South Tehran Branch, Islamic Azad University, Tehran, Iran

Abstract

In traditional optimization models, classical computers have been used to solve mathematical linear or non-linear models. In addition, by data envelopment analysis (DEA) models one can evaluate the relative efficiency of the decision-making units originally in the form of mathematical non-linear models. In this paper, a new attitude is presented in which quantum computers and quantum algorithms can be used to solve DEA models by two different methods. This suggested attitude is worthy to mention as this subject is new and will attract researchers to discuss and improve it.

Keywords

[1] M.S. Bazaraa, J.J. Jarvis and H.D. Sherali, Linear programming and network flows, John Wiley and Sons, 2010.
[2] A. Charnes, W.W. Cooper and E.L. Rhodes, Measuring the efficiency of decision making units, Euro. J. Oper. Res. 2 (1978), 429–444.
[3] K. Chen, Matrix Preconditioning Techniques and Applications, Cambridge University Press, 2005.
[4] W.W. Cooper, LM. Seiford and K. Tone, Data Envelopment Analysis: A Comprehensive Text with Models, Applications, References and DEA-solver Software, Kluwer Academic Publishers: Norwell, MA, 2000.
[5] A.W. Harrow and A. Hassidim, S. Lloyd, Quantum algorithm for linear systems of equation, Phys. Rev. Lett. 103 (2009), 150–502.
[6] T. Hogg and D. Portnov, Quantum optimization, Inf. Sci. 128 (2000), 181–197.
[7] D. McMahon, Quantum computing explained, John Wiley and Sons, 2008.
[8] M. Nielsen and I. Chuang, Quantum Computation and Quantum Information, Cambridge University Press, New York, 2010.
[9] M. Side and V. Erol, Applying quantum optimization algorithms for linear programming, doi:10.20944/preprints201703.0238.v2, April 2017.
[10] D.A. Spielman and S.H. Teng , Nearly-linear time algorithms for preconditioning and solving symmetric, diagonally dominant linear systems, SIAM J. Matrix Anal. Appl. 35 (2014), no. 3, 835–885.
[11] J. Sun, J. Liu and W. Xu, Using quantum-behaved particle swarm optimization algorithm to solve non-linear programming problems, Int J. Comput. Math. 84 (2007), 261–272.
[12] A.D. Athanassopoulos, N. Lambroukos and L.M. Seiford, Data envelopment scenario analysis for setting targets to electricity generating plants, Euro. J. Operational Res. 115 (1999), 413–428.
[13] AJ. Manuel, S. Carmen and S. Lozano, A fuzzy DEA slacks-based approach, J. Comput. Applied Math. 404 (2022), 113–180.
[14] F. Hosseinzadeh Lotfi, A. Ebrahimnejad, M. Vaez-Ghasemi and Z. Moghaddas, Data Envelopment Analysis with R, Springer, 2020.
[15] R. Banker, Stochastic data envelopment analysis, Data Envelop Analy. J. 5 (2021), 281–309.
Volume 14, Issue 1
January 2023
Pages 3063-3070
  • Receive Date: 26 January 2022
  • Revise Date: 04 May 2022
  • Accept Date: 12 May 2022