Kybernetika 58 no. 5, 665-690, 2022

Algebraic solution to box-constrained bi-criteria problem of rating alternatives through pairwise comparisons

Nikolai KrivulinDOI: 10.14736/kyb-2022-5-0665

Abstract:

We consider a decision-making problem to evaluate absolute ratings of alternatives that are compared in pairs according to two criteria, subject to box constraints on the ratings. The problem is formulated as the log-Chebyshev approximation of two pairwise comparison matrices by a common consistent matrix (a symmetrically reciprocal matrix of unit rank), to minimize the approximation errors for both matrices simultaneously. We rearrange the approximation problem as a constrained bi-objective optimization problem of finding a vector that determines the approximating consistent matrix, and then represent the problem in terms of tropical algebra. We apply methods and results of tropical optimization to derive an analytical solution of the constrained problem. The solution consists in introducing two new variables that describe the values of the objective functions and allow reducing the problem to the solution of a system of parameterized inequalities constructed for the unknown vector, where the new variables play the role of parameters. We exploit the existence condition for solutions of the system to derive those values of the parameters that belong to the Pareto front inherent to the problem. Then, we solve the system for the unknown vector and take all solutions that correspond to the Pareto front, as a complete solution of the bi-objective problem. We apply the result obtained to the bi-criteria decision problem under consideration and present illustrative examples.

Keywords:

idempotent semifield, tropical optimization, constrained bi-criteria decision problem, Pareto-optimal solution, box constraints, pairwise comparisons

Classification:

90C24, 15A80, 90B50, 90C29, 90C47

paper.pdf

References:

  1. J. Barzilai: Deriving weights from pairwise comparison matrices. J. Oper. Res. Soc. 48 (1997), 12, 1226-1232.   DOI:10.2307/3010752
  2. V. Belton and T. Gear: On a short-coming of Saaty's method of analytic hierarchies. Omega 11 (1983), 3, 228-230.   DOI:10.1016/0305-0483(83)90047-6
  3. H. P. Benson: Multi-objective optimization: Pareto optimal solutions, properties. In: Encyclopedia of Optimization. Second edition. (C. A. Floudas and P. M. Pardalos, eds), Springer, Boston 2009, pp. 2478-2481.   DOI:10.1007/978-0-387-74759-0\_426
  4. E. U. Choo and W. C. Wedley: A common framework for deriving preference values from pairwise comparison matrices. Comput. Oper. Res. 31 (2004), 6, 893-908.   DOI:10.1016/S0305-0548(03)00042-X
  5. G. Crawford and C. Williams: A note on the analysis of subjective judgment matrices. J. Math. Psych. 29 (1985), 4, 387-405.   DOI:10.1016/0022-2496(85)90002-1
  6. M. Ehrgott: Multicriteria Optimization. Second edition. Springer, Berlin 2005.   DOI:10.1007/3-540-27659-9
  7. L. Elsner and P. van den Driessche: Max-algebra and pairwise comparison matrices. Linear Algebra Appl. 385 (2004), 1, 47-62.   DOI:10.1016/S0024-3795(03)00476-2
  8. L. Elsner and P. van den Driessche: Max-algebra and pairwise comparison matrices, II. Linear Algebra Appl. 432 (2010), 4, 927-935.   DOI:10.1016/j.laa.2009.10.005
  9. M. Gavalec, J. Ramík and K. Zimmermann: Decision Making and Optimization. Lecture Notes in Economics and Mathematical Systems 677, Springer, Cham 2015.   DOI:10.1007/978-3-319-08323-0
  10. J. S. Golan:     CrossRef
  11. M. Gondran and M. Minoux: Graphs, Dioids and Semirings. Operations Research/ Computer Science Interfaces 41, Springer, Boston 2008.   DOI:10.1007/978-0-387-75450-5
  12. H. Goto and S. Wang: Polyad inconsistency measure for pairwise comparisons matrices: max-plus algebraic approach. Oper. Res. Int. J. 22 (2022), 1, 401-422.   DOI:10.1007/s12351-020-00547-9
  13. B. B. Gursoy, O. Mason and S. Sergeev: The analytic hierarchy process, max algebra and multi-objective optimisation. Linear Algebra Appl. 438 (2013), 7, 2911-2928.   DOI:10.1016/j.laa.2012.11.020
  14. B. Heidergott, G. J. Olsder and J. van der Woude: Max Plus at Work. Princeton Series in Applied Mathematics. Princeton University Press, Princeton 2006.   CrossRef
  15. V. N. Kolokoltsov and V. P. Maslov: Idempotent Analysis and Its Applications. Mathematics and Its Applications 401, Springer, Dordrecht 1997.   DOI:10.1007/978-94-015-8901-7
  16. N. Krivulin: A constrained tropical optimization problem: Complete solution and application example. In: Tropical and Idempotent Mathematics and Applications (G. L. Litvinov and S. N. Sergeev, eds.), Contemporary Mathematics 616, AMS, Providence 2014, pp. 163-177.   DOI:10.1090/conm/616/12308
  17. N. Krivulin: Extremal properties of tropical eigenvalues and solutions to tropical optimization problems. Linear Algebra Appl. 468 (2015), 211-232.   DOI:10.1016/j.laa.2014.06.044
  18. N. Krivulin: A multidimensional tropical optimization problem with nonlinear objective function and linear constraints. Optimization 64 (2015), 5, 1107-1129.   DOI:10.1080/02331934.2013.840624
  19. N. Krivulin: Rating alternatives from pairwise comparisons by solving tropical optimization problems. In: 12th Intern. Conf. on Fuzzy Systems and Knowledge Discovery (FSKD) (Z. Tang, J. Du, S. Yin, L. He, and R. Li, eds.), IEEE, 2015, pp. 162-167.   DOI:10.1109/FSKD.2015.7381933
  20. N. Krivulin: Using tropical optimization techniques to evaluate alternatives via pairwise comparisons. In: Proc. 7th SIAM Workshop on Combinatorial Scientific Computing (A. H. Gebremedhin, E. G. Boman, and B. Ucar, eds.), SIAM, Philadelphia 2016, pp. 62-72.   DOI:10.1137/1.9781611974690.ch7
  21. N. Krivulin: Direct solution to constrained tropical optimization problems with application to project scheduling. Comput. Manag. Sci. 14 (2017), 1, 91-113.   DOI:10.1007/s10287-016-0259-0
  22. N. Krivulin: Using tropical optimization techniques in bi-criteria decision problems. Comput. Manag. Sci. 17 (2020), 1, 79-104.   DOI:10.1007/s10287-018-0341-x
  23. N. Krivulin: Algebraic solution to constrained bi-criteria decision problem of rating alternatives through pairwise comparisons. Mathematics 9 (2021), 4, 303.   DOI:10.3390/math9040303
  24. N. Krivulin and S. Sergeev: Tropical implementation of the Analytical Hierarchy Process decision method. Fuzzy Sets Systems 377 (2019), 31-51.   DOI:10.1016/j.fss.2018.10.013
  25. D. T. Luc: Pareto optimality. In: Pareto Optimality, Game Theory and Equilibria (A. Chinchuluun, P. M. Pardalos, A. Migdalas, and L. Pitsoulis, eds.), Springer, New York 2008, pp. 481-515.   DOI:10.1007/978-0-387-77247-9\_18
  26. D. Maclagan and B. Sturmfels: Introduction to Tropical Geometry. Graduate Studies in Mathematics 161, AMS, Providence 2015.   DOI:10.1090/gsm/161
  27. M. Pappalardo: Multiobjective optimization: A brief overview. In: Pareto Optimality, Game Theory and Equilibria (A. Chinchuluun, P. M. Pardalos, A. Migdalas, and L. Pitsoulis, eds.), Springer, New York 2008, pp. 517-528.   DOI:10.1007/978-0-387-77247-9\_19
  28. R. D. Portugal and B. F. Svaiter: Weber-Fechner law and the optimality of the logarithmic scale. Minds Mach. 21 (2011), 1, 73-81.   DOI:10.1007/s11023-010-9221-z
  29. R. Ramesh and S. Zionts: Multiple criteria decision making. In: Encyclopedia of Operations Research and Management Science (S. I. Gass and M. C. Fu, eds.), Springer, Boston 2013, pp. 1007-1013.   DOI:10.1007/978-1-4419-1153-7\_653
  30. J. Ramík: Pairwise Comparisons Method. Lecture Notes in Economics and Mathematical Systems 690, Springer, Cham 2020.   DOI:10.1007/978-3-030-39891-0
  31. T. L. Saaty: A scaling method for priorities in hierarchical structures. J. Math. Psych. 15 (1977), 3, 234-281.   DOI:10.1016/0022-2496(77)90033-5
  32. T. L. Saaty: The Analytic Hierarchy Process. Second edition. RWS Publications, Pittsburgh 1990.   CrossRef
  33. T. L. Saaty: On the measurement of intangibles: A principal eigenvector approach to relative measurement derived from paired comparisons. Notices Amer. Math. Soc. 60 (2013), 2, 192-208.   DOI:10.1090/noti944
  34. T. L. Saaty and L. G. Vargas: Comparison of eigenvalue, logarithmic least squares and least squares methods in estimating ratios. Math. Modelling 5 (1984), 5, 309-324.   DOI:10.1016/0270-0255(84)90008-3