Abstract
We study in this paper the computation of Choquet optimal solutions in decision contexts involving multiple criteria or multiple agents. Choquet optimal solutions are solutions that optimize a Choquet integral, one of the most powerful tools in multicriteria decision making. We develop a new property that characterizes the Choquet optimal solutions. From this property, a general method to generate these solutions in the case of several criteria is proposed. We apply the method to different Pareto non-dominated sets coming from different knapsack instances with a number of criteria included between two and seven. We show that the method is effective for a number of criteria lower than five or for high size Pareto non-dominated sets. We also observe that the percentage of Choquet optimal solutions increase with the number of criteria.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
References
Choquet, G.: Theory of capacities. Annales de l’Institut Fourier (5), 131–295 (1953)
Grabisch, M., Labreuche, C.: A decade of application of the Choquet and Sugeno integrals in multi-criteria decision aid. Annals OR 175(1), 247–286 (2010)
Grabisch, M., Marichal, J.C., Mesiar, R., Pap, E.: Aggregation functions. Encyclopedia of Mathematics and its Applications, vol. 127. Cambridge University Press, Cambridge (2009)
Yager, R.: On ordered weighted averaging aggregation operators in multicriteria decision making. IEEE Trans. Systems, Man and Cybern. 18, 183–190 (1998)
Torra, V.: The weighted OWA operator. Int. J. Intell. Syst. (12), 153–166 (1997)
Grabisch, M., Kojadinovic, I., Meyer, P.: A review of methods for capacity identification in choquet integral based multi-attribute utility theory: Applications of the kappalab R package. European Journal of Operational Research 186(2), 766–785 (2008)
Grabisch, M.: The application of fuzzy integrals in multicriteria decision making. European Journal of Operational Research 89, 445–456 (1996)
Nicosia, G., Pacifici, A., Pferschy, U.: On multi-agent knapsack problems. In: Proceedings of the 8th Cologne-Twente Workshop on Graphs and Combinatorial Optimization, pp. 44–47 (2009)
Goldsmith, J., Sloan, R.: The conference paper assignment problem. In: AAAI Workshop on Preference Handling for Artificial Intelligence (2007)
Gent, I., Irving, R., Manlove, D., Prosser, P., Smith, B.: A constraint programming approach to the stable marriage problem. In: Walsh, T. (ed.) CP 2001. LNCS, vol. 2239, pp. 225–239. Springer, Heidelberg (2001)
Ehrgott, M.: Multicriteria Optimization, 2nd edn. Springer, Berlin (2005)
Ojalehto, V., Miettinen, K., Mäkelä, M.: Interactive software for multiobjective optimization: IND-NIMBUS. WSEAS Transactions on Computers 6, 87–94 (2007)
Fouchal, H., Gandibleux, X., Lehuédé, F.: Preferred solutions computed with a label setting algorithm based on Choquet integral for multi-objective shortest paths. In: 2011 IEEE Symposium on Computational Intelligence in Multicriteria Decision-Making (MDCM), Paris, France, pp. 143–150. IEEE (2011)
Galand, L., Perny, P., Spanjaard, O.: Choquet-based optimisation in multiobjective shortest path and spanning tree problems. European Journal of Operational Research 204(2), 303–315 (2010)
Galand, L., Perny, P., Spanjaard, O.: A branch and bound algorithm for Choquet optimization in multicriteria problems. In: Proceedings Lecture Notes in Economics and Mathematical Systems, vol. 634, pp. 355–365 (2011)
Lust, T., Rolland, A.: Choquet optimal set in biobjective combinatorial optimization. Computers & Operations Research 40(10), 2260–2269 (2013)
Rota, G.C.: On the foundations of combinatorial theory I. Theory of Mobius functions. Z. Wahrscheinlichkeitstheorie und Verw. Gebiete 2, 340–368 (1964)
Chateauneuf, A., Jaffray, J.Y.: Some characterizations of lower probabilities and other monotone capacities through the use of mobius inversion. Mathematical Social Sciences 17(3), 263–283 (1989)
Lust, T., Teghem, J.: The multiobjective multidimensional knapsack problem: a survey and a new approach. International Transactions in Operational Research 19(4), 495–520 (2012)
Meyer, P., Pirlot, M.: On the expressiveness of the additive value function and the Choquet integral models. In: DA2PL 2012: from Multiple Criteria Decision Aid to Preference Learning, pp. 48–56 (2012)
Grabisch, M.: k-order additive discrete fuzzy measures and their representation. Fuzzy Sets and Systems (92), 167–189 (1997)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2013 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Lust, T., Rolland, A. (2013). On the Computation of Choquet Optimal Solutions in Multicriteria Decision Contexts. In: Ramanna, S., Lingras, P., Sombattheera, C., Krishna, A. (eds) Multi-disciplinary Trends in Artificial Intelligence. MIWAI 2013. Lecture Notes in Computer Science(), vol 8271. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-44949-9_13
Download citation
DOI: https://doi.org/10.1007/978-3-642-44949-9_13
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-44948-2
Online ISBN: 978-3-642-44949-9
eBook Packages: Computer ScienceComputer Science (R0)