Multiple criteria ranking; Preference learning; SAT formulation; Learning procedures; Multi-criteria ranking; Multiple criteria; Multiple references; Reference points; SAT-based; Stated preferences; Computer Science (all); Modeling and Simulation; Management Science and Operations Research; General Computer Science
Abstract :
[en] We consider the multicriteria ranking problem, and specifically a ranking procedure based on reference points recently proposed in the literature, named Ranking with Multiple reference Points (RMP). Implementing RMP in a real world decision problem requires to elicit the model preference parameters. This can be done indirectly by inferring the parameters from stated preferences. Learning an RMP model from stated preferences proves however to be computationally costly, and can hardly be put in practice using currently available algorithms. In this paper, we propose a Boolean satisfiability formulation for inferring an RMP model from a set of pairwise comparisons which is much faster than the existing algorithms.
Research center :
CRTI - Centre de Recherche en Technologie de l'Information
Disciplines :
Computer science
Author, co-author :
Belahcène, Khaled; Heudiasyc, UMR 7523, CNRS, Université de Technologie de Compiègne, France
Mousseau, Vincent; MICS, CentraleSupélec, Université Paris-Saclay, France
Ouerdane, Wassila ; MICS, CentraleSupélec, Université Paris-Saclay, France
Pirlot, Marc ; Université de Mons - UMONS > Faculté Polytechniqu > Service de Mathématique et Recherche opérationnelle
Sobrie, Olivier ; Université de Mons - UMONS > Faculté Polytechniqu > Service de Mathématique et Recherche opérationnelle
Language :
English
Title :
Ranking with Multiple Reference Points: Efficient SAT-based learning procedures
Almeida-Dias, J., Figueira, J.R., Roy, B., Electre Tri-C: A multiple criteria sorting method based on characteristic reference actions. European J. Oper. Res. 204:3 (2010), 565–580.
Almeida-Dias, J., Figueira, J.R., Roy, B., A multiple criteria sorting method where each category is characterized by several reference actions: The Electre Tri-nC method. European J. Oper. Res. 217:3 (2012), 567–579.
Alviano, M., Dodaro, C., Ricca, F., 2015. A MaxSAT Algorithm Using Cardinality Constraints of Bounded Size. In: Proceedings of the 24th International Joint Conference on Artificial Intelligence. IJCAI 2015, pp. 92677–2683.
Arrow, K.J., Social Choice and Individual Values. 1953, Wiley, Cowles Foundation Monographs; New York.
Bacchus, F., Järvisalo, M., Martins, R., MaxSAT evaluation 2018: New developments and detailed results. J. Satisf. Boolean Model. Comput. 11:1 (2019), 99–131.
Bana e Costa, C.A., Vansnick, J.-C., MACBETH: An interactive path towards the construction of cardinal value functions. Int. Trans. Oper. Res. 1:4 (1994), 489–500.
Belahcène, K., Towards Accountable Decision Aiding: Explanations for the Aggregation of Preferences. (Ph.D. thesis), 2018, CentraleSupélec, Université Paris-Saclay.
Belahcène, K., Labreuche, C., Maudet, N., Mousseau, V., Ouerdane, W., An efficient SAT formulation for learning multiple criteria non-compensatory sorting rules from examples. Comput. Oper. Res. 97 (2018), 58–71.
Benabbou, N., Perny, P., Viappiani, P., Incremental elicitation of choquet capacities for multicriteria choice, ranking and sorting problems. Artificial Intelligence 246 (2017), 152–180.
Biere, A., Heule, M., van Maaren, H., Walsh, T., Handbook of Satisfiability Frontiers in Artificial Intelligence and Applications 185, 2009, IOS Press.
Bous, G., Fortemps, P., Glineur, F., Pirlot, M., ACUTA: A novel method for eliciting additive value functions on the basis of holistic preference statements. European J. Oper. Res. 206:2 (2010), 435–444.
Bouyssou, D., Marchant, T., An axiomatic approach to noncompensatory sorting methods in MCDM, I: The case of two categories. European J. Oper. Res. 178:1 (2007), 217–245.
Bouyssou, D., Marchant, T., An axiomatic approach to noncompensatory sorting methods in MCDM, II: More than two categories. European J. Oper. Res. 178:1 (2007), 246–276.
Bouyssou, D., Marchant, T., Multiattribute preference models with reference points. European J. Oper. Res. 229:2 (2013), 470–481.
Brans, J.-P., Mareschal, B., PROMETHEE methods. Multiple Criteria Decision Analysis: State of the Art Surveys, 2005, Springer, New York, 163–186.
Condorcet, 1785. Essai sur l'application de l'analyse à la probabilité des décisions rendues à la pluralité des voix. Paris.
Cook, S., The complexity of theorem proving procedures. Proceedings of the Third Annual ACM Symposium on Theory of Computing, 1971, 151–158.
de Finetti, B., Sul significato soggetivo della probabilità. Polska Akad. Nauk. Fundam. Math. 17 (1931), 298–329.
Dias, L., Mousseau, V., Figueira, J.R., Clímaco, J., An aggregation/disaggregation approach to obtain robust conclusions with ELECTRE TRI. European J. Oper. Res. 138:1 (2002), 332–348.
Doumpos, M., Marinakis, Y., Marinaki, M., Zopounidis, C., An evolutionary approach to construction of outranking models for multicriteria classification: The case of the ELECTRE TRI method. European J. Oper. Res. 199:2 (2009), 496–505.
Fernández, E., Figueira, J., Navarro, J., Roy, B., ELECTRE TRI-nB: A new multiple criteria ordinal classification method. European J. Oper. Res. 263:1 (2017), 214–224.
Ferretti, V., Liu, J., Mousseau, V., Ouerdane, W., Reference-based ranking procedure for environmental decision making: Insights from an ex-post analysis. Environ. Model. Softw. 99 (2018), 11–24 URL http://www.sciencedirect.com/science/article/pii/S136481521631132X.
Figueira, J., Mousseau, V., Roy, B., Electre methods. Multiple Criteria Decision Analysis: State of the Art Surveys, 2005, Springer New York, New York, NY, 133–153.
Fishburn, P.C., Finite linear qualitative probability. J. Math. Psych. 40:1 (1996), 64–77.
Grabisch, M., Set Functions, Games and Capacities in Decision Making Theory and Decision Library C, vol. 46, 2016, Springer.
Greco, S., Mousseau, V., Słowiński, R., Ordinal regression revisited: multiple criteria ranking using a set of additive value functions. European J. Oper. Res. 191:2 (2008), 416–436.
Hwang, C.-L., Lai, Y.-J., Liu, T.-Y., A new approach for multiple objective decision making. Comput. Oper. Res. 20:8 (1993), 889–899.
Jacquet-Lagrèze, E., Siskos, Y., Assessing a set of additive utility functions for multicriteria decision-making, the UTA method. European J. Oper. Res. 10:2 (1982), 151–164.
Kahneman, D., Tversky, A., Prospect theory: An analysis of decision under risk. Econometrica 47:2 (1979), 263–291.
Kemeny, J.G., Mathematics without numbers. Daedalus 88:4 (1959), 577–591.
Khannoussi, A., Olteanu, A., Labreuche, C., Meyer, P., Simple ranking method using reference profiles: incremental elicitation of the preference parameters. 4OR, 2021.
Khannoussi, A., Olteanu, A., Labreuche, C., Narayan, P., Dezan, C., Diguet, J.Ph., Petit-Frère, J., Meyer, P., Integrating operators’ preferences into decisions of unmanned aerial vehicles: Multi-layer decision engine and incremental preference elicitation. Pekec, S., Venable, K.B., (eds.) Algorithmic Decision Theory, Proceedings Lecture Notes in Computer Science, vol. 11834, 2019, Springer, 49–64.
Koszegi, B., Rabin, M., A model of reference-dependent preferences. Q. J. Econ. 121:4 (2006), 1033–1065.
Kraft, C.H., Pratt, J.W., Seidenberg, A., Intuitive Probability on Finite Sets. Ann. Math. Stat. 30:2 (1959), 408–419.
Labreuche, C., Grabisch, M., Using multiple reference levels in multi-criteria decision aid: The generalized-additive independence model and the choquet integral approaches. European J. Oper. Res. 267 (2018), 598–611.
Leroy, A., Mousseau, V., Pirlot, M., Learning the parameters of a multiple criteria sorting method. Brafman, R., Roberts, F., Tsoukiàs, A., (eds.) Algorithmic Decision Theory Lecture Notes in Artificial Intelligence, vol. 6992, 2011, 219–233.
Liu, J., Preference Elicitation for Multi-Criteria Ranking with Multiple Reference Points. (Ph.D. thesis), 2016, CentraleSupélec, Université Paris-Saclay.
Liu, J., Ouerdane, W., Mousseau, V., 2014. A Metaheuristic approach for preference Learning in multicriteria ranking based on reference points. In: Proceedings of the 2nd Workshop “from Multiple Criteria Decision Aid To Preference Learning”. DA2PL, Chatenay-Malabry, France, pp. 76–86.
Meyer, P., Olteanu, A.-L., Handling imprecise and missing evaluations in multi-criteria majority-rule sorting. Comput. Oper. Res. 110 (2019), 135–147.
Morgado, A., Heras, F., Liffiton, M.H., Planes, J., Marques-Silva, J., Iterative and core-guided MaxSAT solving: A survey and assessment. Constraints 18:4 (2013), 478–534.
Moskewicz, M., Madigan, C., Zhao, Y., Zhang, L., Malik, S., Chaff: engineering an efficient SAT solver. Proceedings of the 38th Annual Design Automation Conference, DAC ’01, 2001, ACM, New York, NY, USA, 530–535.
Mousseau, V., Słowiński, R., Inferring an ELECTRE TRI model from assignment examples. J. Global Optim. 12:2 (1998), 157–174.
Ngo The, A., Mousseau, V., Using assignment examples to infer category limits for the ELECTRE TRI method. J. Multi-Criteria Decis. Anal. 11:1 (2002), 29–43.
Olteanu, A.L., Belahcene, K., Mousseau, V., Ouerdane, W., Rolland, A., Zheng, J., Preference elicitation for a ranking method based on multiple reference profiles. 4OR 20:1 (2022), 63–84.
Rawla, P., Epidemiology of prostate cancer. World J. Oncol. 10:2 (2019), 63–89.
Rolland, A., Procédures d'agrégation ordinale de préférences avec points de référence pour l'aide à la décision. (Ph.D. thesis), 2008, 219 p. Université Paris 6, France.
Rolland, A., Reference-based preferences aggregation procedures in multi-criteria decision making. European J. Oper. Res. 225:3 (2013), 479–486.
Roy, B., Bouyssou, D., Aide multicritère à la décision: méthodes et cas. 1993, Economica, Paris.
Sobrie, O., Mousseau, V., Pirlot, M., Learning a majority rule model from large sets of assignment examples. Perny, P., Pirlot, M., Tsoukiás, A., (eds.) Algorithmic Decision Theory Lecture Notes in Artificial Intelligence, vol. 8176, 2013, Springer, 336–350.
Sobrie, O., Mousseau, V., Pirlot, M., Learning the parameters of a non compensatory sorting model. Walsh, T., (eds.) Algorithmic Decision Theory Lecture Notes in Artificial Intelligence, vol. 9346, 2015, Springer, Lexington, KY, USA, 153–170.
Sobrie, O., Mousseau, V., Pirlot, M., A population-based algorithm for learning a majority rule sorting model with coalitional veto. Trautmann, H., Rudolph, G., Klamroth, K., Schütze, O., Wiecek, M.M., Jin, Y., Grimme, Chr., (eds.) Evolutionary Multi-Criterion Optimization - 9th International Conference, EMO 2017, Münster, Germany, March 19-22, 2017, Proceedings Lecture Notes in Computer Science, vol. 10173, 2017, Springer, 575–589.
Sobrie, O., Mousseau, V., Pirlot, M., Learning monotone preferences using a majority rule sorting model. Int. Trans. Oper. Res. 26:5 (2019), 1786–1809.
Soos, M., The CryptoMiniSat 5 set of solvers at SAT Competition 2016. Proceedings of SAT Competition 2016: Solver and Benchmark Descriptions, Volume B-2016-1 of Department of Computer Science Series of Publications B, 2016, University of Helsinki.
Tversky, A., Kahneman, D., Loss aversion in riskless choice. A reference-dependent model. Q. J. Econ. 106:4 (1991), 1039–1061.
Wang, X., Triantaphyllou, E., Ranking irregularities when evaluating alternatives by using some ELECTRE methods. Omega 36:1 (2008), 45–63.
Weber, T., Conchon, S., Déharbe, D., Heizmann, M., Niemetz, A., Reger, G., The SMT competition 2015–2018. J. Satisf. Boolean Model. Comput. 11:1 (2019), 221–259.
Yu, W., Aide multicritère à la décision dans le cadre de la problématique du tri: concepts, méthodes et applications. (Ph.D. thesis), 1992, Université Paris-Dauphine, Paris, France (in French, https://bu.dauphine.psl.eu/fileviewer/view.php?doc=1992PA090032&target=internet).
Zheng, Jun, Preference Elicitation for Aggregation Models based on Reference Points: Algorithms and Procedures. (Ph.D. dissertation), 2012, Ecole Centrale Paris.
Zheng, J., Rolland, A., Mousseau, V., Preference Elicitation for a Ranking Method based on Multiple Reference Profiles: Technical Report., 2012, Laboratoire Génie Industriel, Ecole Centrale Paris Research report 2012-05.
