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

Krivulin, Nikolai

Kybernetika, Tome 58 (2022) no. 5, pp. 665-690

Abstract (VO)

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.

Détail

DOI : 10.14736/kyb-2022-5-0665

Classification : 15A80, 90B50, 90C24, 90C29, 90C47
Keywords: idempotent semifield; tropical optimization; constrained bi-criteria decision problem; Pareto-optimal solution; box constraints; pairwise comparisons

Bibliographie

[1] Barzilai, J.: Deriving weights from pairwise comparison matrices. J. Oper. Res. Soc. 48 (1997), 12, 1226-1232. | DOI

[2] Belton, V., Gear, T.: On a short-coming of Saaty's method of analytic hierarchies. Omega 11 (1983), 3, 228-230. | DOI

[3] Benson, H. P.: 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

[4] Choo, E. U., Wedley, W. C.: A common framework for deriving preference values from pairwise comparison matrices. Comput. Oper. Res. 31 (2004), 6, 893-908. | DOI

[5] Crawford, G., Williams, C.: A note on the analysis of subjective judgment matrices. J. Math. Psych. 29 (1985), 4, 387-405. | DOI

[6] Ehrgott, M.: Multicriteria Optimization. Second edition. Springer, Berlin 2005. | DOI

[7] Elsner, L., Driessche, P. van den: Max-algebra and pairwise comparison matrices. Linear Algebra Appl. 385 (2004), 1, 47-62. | DOI

[8] Elsner, L., Driessche, P. van den: Max-algebra and pairwise comparison matrices, II. Linear Algebra Appl. 432 (2010), 4, 927-935. | DOI

[9] Gavalec, M., Ramík, J., Zimmermann, K.: Decision Making and Optimization. Lecture Notes in Economics and Mathematical Systems 677, Springer, Cham 2015. | DOI

[10] Golan, J. S.: Semirings and Ane Equations Over Them. Mathematics and Its Applications. 556, Springer, Dordrecht 2003. | DOI

[11] Gondran, M., Minoux, M.: Graphs, Dioids and Semirings. Operations Research/ Computer Science Interfaces 41, Springer, Boston 2008. | DOI

[12] Goto, H., Wang, S.: Polyad inconsistency measure for pairwise comparisons matrices: max-plus algebraic approach. Oper. Res. Int. J. 22 (2022), 1, 401-422. | DOI

[13] Gursoy, B. B., Mason, O., Sergeev, S.: The analytic hierarchy process, max algebra and multi-objective optimisation. Linear Algebra Appl. 438 (2013), 7, 2911-2928. | DOI

[14] Heidergott, B., Olsder, G. J., Woude, J. van der: Max Plus at Work. Princeton Series in Applied Mathematics. Princeton University Press, Princeton 2006.

[15] Kolokoltsov, V. N., Maslov, V. P.: Idempotent Analysis and Its Applications. Mathematics and Its Applications 401, Springer, Dordrecht 1997. | DOI | Zbl

[16] Krivulin, N.: 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

[17] Krivulin, N.: Extremal properties of tropical eigenvalues and solutions to tropical optimization problems. Linear Algebra Appl. 468 (2015), 211-232. | DOI

[18] Krivulin, N.: A multidimensional tropical optimization problem with nonlinear objective function and linear constraints. Optimization 64 (2015), 5, 1107-1129. | DOI

[19] Krivulin, N.: 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

[20] Krivulin, N.: 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

[21] Krivulin, N.: Direct solution to constrained tropical optimization problems with application to project scheduling. Comput. Manag. Sci. 14 (2017), 1, 91-113. | DOI

[22] Krivulin, N.: Using tropical optimization techniques in bi-criteria decision problems. Comput. Manag. Sci. 17 (2020), 1, 79-104. | DOI

[23] Krivulin, N.: Algebraic solution to constrained bi-criteria decision problem of rating alternatives through pairwise comparisons. Mathematics 9 (2021), 4, 303. | DOI

[24] Krivulin, N., Sergeev, S.: Tropical implementation of the Analytical Hierarchy Process decision method. Fuzzy Sets Systems 377 (2019), 31-51. | DOI

[25] Luc, D. T.: 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

[26] Maclagan, D., Sturmfels, B.: Introduction to Tropical Geometry. Graduate Studies in Mathematics 161, AMS, Providence 2015. | DOI

[27] Pappalardo, M.: 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

[28] Portugal, R. D., Svaiter, B. F.: Weber-Fechner law and the optimality of the logarithmic scale. Minds Mach. 21 (2011), 1, 73-81. | DOI

[29] Ramesh, R., Zionts, S.: 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

[30] Ramík, J.: Pairwise Comparisons Method. Lecture Notes in Economics and Mathematical Systems 690, Springer, Cham 2020. | DOI

[31] Saaty, T. L.: A scaling method for priorities in hierarchical structures. J. Math. Psych. 15 (1977), 3, 234-281. | DOI

[32] Saaty, T. L.: The Analytic Hierarchy Process. Second edition. RWS Publications, Pittsburgh 1990.

[33] Saaty, T. L.: 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

[34] Saaty, T. L., Vargas, L. G.: Comparison of eigenvalue, logarithmic least squares and least squares methods in estimating ratios. Math. Modelling 5 (1984), 5, 309-324. | DOI