Solution of a bi-criteria problem of rating alternatives using tropical optimization
Abstract
A problem is considered to evaluate scores (priorities, weights) of alternatives through the results of pairwise comparisons according to two criteria. A formal derivation and computational procedures of the solution to the problem are described, using methods of tropical mathematics, which studies algebraic systems with specially defined operations of addition and multiplication. The problem is reduced to simultaneous approximation of two matrices of pairwise comparisons by a common consistent matrix, in the Chebyshev metric in logarithmic scale. First, auxiliary variables are introduced to represent the minima of the objective functions, and a parameterized inequality is derived, which determines the set of solutions to the original optimization problem. The necessary and sufficient conditions for the existence of solutions of the inequality are used to evaluate the values of parameters, which correspond to the Pareto front of the problem. All solutions of the inequality under the obtained values are taken as a Pareto-optimal solution for the problem. To illustrate the computational procedures used, numerical examples of evaluating scores of alternatives are given for problems with matrices of the third order.
References
V. V. Podinovskii and V. D. Nogin, Pareto-optimal’nye resheniya mnogokriterial’nykh zadach [Pareto-optimal solutions to multicriteria problems], Moscow: Nauka, 1982 (in Russian).
T. Saaty, Prinyatie reshenii. Metod analiza ierarkhii [Making decisions. Hierarchy Analysis Method], Moscow: Radio i svyaz’, 1993 (in Russian).
V. D. Nogin, Prinyatie reshenii v mnogokriterial’noi srede: kolichestvennyi podkhod [Decision making in a multi-criteria environment: a quantitative approach], Moscow: Fizmatlit, 2002 (in Russian).
M. Ehrgott, Multicriteria Optimization, Berlin: Springer, 2005; doi: 10.1007/3-540-27659-9
L. L. Thurstone, “A law of comparative judgment,” Psychological Review, vol. 34, no. 4, pp. 273–286, 1927; doi: 10.1037/h0070288
T. L. Saaty, “A scaling method for priorities in hierarchical structures,” J. Math. Psych., vol. 15, no. 3, pp. 234–281, 1977; doi: 10.1016/0022-2496(77)90033-5
R. A. Cuninghame-Green, Minimax Algebra, Berlin: Springer-Verlag, 1979; doi: 10.1007/978-3-642-48708-8
F. L. Baccelli, G. Cohen, G. J. Olsder, and J.-P. Quadrat, Synchronization and Linearity. Wiley Series in Probability and Statistics, Chichester, UK: Wiley, 1993.
V. P. Maslov and V. N. Kolokol’tsov, Idempotentnyi analiz i ego primenenie v optimal’nom upravlenii [Idempotent analysis and its application in optimal control], Moscow: Fizmatlit, 1994 (in Russian).
J. S. Golan, Semirings and Affine Equations Over Them (Vol. 556 of Mathematics and Its Applications), New York: Springer, 2003; doi: 10.1007/978-94-017-0383-3
B. Heidergott, G. J. Olsder, and J. van der Woude, Max Plus at Work (Princeton Series in Applied Mathematics), Princeton, NJ: Princeton Univ. Press, 2006.
N. K. Krivulin, Metody idempotentnoi algebry v zadachakh modelirovaniya i analiza slozhnykh sistem [Idempotent algebra methods in modeling and analysis of complex systems], Saint-Petersburg: Izd-vo S.-Peterb. un-ta, 2009 (in Russian).
L. Elsner and P. van den Driessche, “Max-algebra and pairwise comparison matrices, II,” Linear Algebra Appl., vol. 432, no. 4, pp. 927–935, 2010; doi: 10.1016/j.laa.2009.10.005
B. B. Gursoy, O. Mason, and S. Sergeev, “The analytic hierarchy process, max algebra and multiobjective optimisation,” Linear Algebra Appl., vol. 438, no. 7, pp. 2911–2928, 2013; doi: 10.1016/j.laa.2012.11.020
N. K. Krivulin and I. V. Gladkikh, “Postroenie soglasovannoi matritsy parnykh sravnenii v marketingovykh issledovaniyakh na osnove metodov tropicheskoi matematiki” [Building a consistent matrix of paired comparisons in marketing research based on methods of tropical mathematics], Vestn. S.-Peterb. un-ta. Ser. 8. Menedzhment, vol. 1, pp. 3–43, 2015 (in Russian).
N. Krivulin, “Using tropical optimization techniques to evaluate alternatives via pairwise comparisons,” in 2016 Proc. 7th SIAM Workshop on Combinatorial Scientific Computing, A. H. Gebremedhin, E. G. Boman, and B. Ucar eds., Philadelphia, PA: SIAM, 2016, pp. 62–72; doi: 10.1137/1.9781611974690.ch7
N. K. Krivulin, V. A. Ageev, and I. V. Gladkikh, “Primenenie metodov tropicheskoi optimizatsii dlya otsenki al’ternativ na osnove parnykh sravnenii” [Application of tropical optimization methods to evaluate alternatives based on pairwise comparisons], Vestn. S.- Peterb. un-ta. Prikladnaya matematika. Informatika. Protsessy upravleniya, vol. 13, no. 1, pp. 27–41, 2017 (in Russian).
N. K. Krivulin, “Using tropical optimization techniques in bi-criteria decision problems,” Comput. Manag. Sci., vol. 17, no. 1, pp. 79-104, 2018; doi: 10.1007/s10287-018-0341-x
N. K. Krivulin and S. N. Sergeev, “Tropical implementation of the Analytical Hierarchy Process decision method,” Fuzzy Sets and Systems, vol. 377, pp. 31–51, 2019; doi: 10.1016/j.fss.2018.10.013
N. Krivulin, “A multidimensional tropical optimization problem with nonlinear objective function and linear constraints,” Optimization, vol. 64, no. 5, pp. 1107–1129, 2015; doi: 10.1080/02331934.2013.840624
This work is licensed under a Creative Commons Attribution 4.0 International License.
