IDEAS home Printed from https://ideas.repec.org/a/eee/ejores/v298y2022i3p979-1006.html
   My bibliography  Save this article

Learning non-compensatory sorting models using efficient SAT/MaxSAT formulations

Author

Listed:
  • Tlili, Ali
  • Belahcène, Khaled
  • Khaled, Oumaima
  • Mousseau, Vincent
  • Ouerdane, Wassila

Abstract

The Non-Compensatory Sorting model aims at assigning alternatives evaluated on multiple criteria to one of the predefined ordered categories. Computing parameters of the Non-Compensatory Sorting model compatible to a set of reference assignments is computationally demanding. To overcome this problem, two formulations based on Boolean satisfiability have recently been proposed to learn the parameters of the Non-Compensatory Sorting model from perfect preference information, i.e. when the set of reference assignments can be completely represented in the model. In this paper, two popular variants of the Non-Compensatory Sorting model are considered, the Non-Compensatory Sorting model with a unique profile and the Non-Compensatory Sorting model with a unique set of sufficient coalitions. For each variant, we start by extending the formulation based on a separation principle to the multiple category case. Moreover, we extend the two formulations to handle inconsistency in the preference information using the Maximum satisfiability problem language. A computational study is proposed to compare the efficiency of both formulations to learn the two Non-Compensatory Sorting models (with a unique profile and with a unique set of sufficient coalitions) from noiseless and noisy preference information.

Suggested Citation

  • Tlili, Ali & Belahcène, Khaled & Khaled, Oumaima & Mousseau, Vincent & Ouerdane, Wassila, 2022. "Learning non-compensatory sorting models using efficient SAT/MaxSAT formulations," European Journal of Operational Research, Elsevier, vol. 298(3), pages 979-1006.
    • Handle: RePEc:eee:ejores:v:298:y:2022:i:3:p:979-1006
    DOI: 10.1016/j.ejor.2021.08.017
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0377221721006858
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.ejor.2021.08.017?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Greco, Salvatore & Mousseau, Vincent & Slowinski, Roman, 2010. "Multiple criteria sorting with a set of additive value functions," European Journal of Operational Research, Elsevier, vol. 207(3), pages 1455-1470, December.
    2. Bouyssou, Denis & Marchant, Thierry, 2007. "An axiomatic approach to noncompensatory sorting methods in MCDM, I: The case of two categories," European Journal of Operational Research, Elsevier, vol. 178(1), pages 217-245, April.
    3. Greco, Salvatore & Matarazzo, Benedetto & Slowinski, Roman, 2001. "Rough sets theory for multicriteria decision analysis," European Journal of Operational Research, Elsevier, vol. 129(1), pages 1-47, February.
    4. Almeida-Dias, J. & Figueira, J.R. & Roy, B., 2010. "Electre Tri-C: A multiple criteria sorting method based on characteristic reference actions," European Journal of Operational Research, Elsevier, vol. 204(3), pages 565-580, August.
    5. Jacquet-Lagreze, E. & Siskos, J., 1982. "Assessing a set of additive utility functions for multicriteria decision-making, the UTA method," European Journal of Operational Research, Elsevier, vol. 10(2), pages 151-164, June.
    6. Arcidiacono, Sally Giuseppe & Corrente, Salvatore & Greco, Salvatore, 2021. "Robust stochastic sorting with interacting criteria hierarchically structured," European Journal of Operational Research, Elsevier, vol. 292(2), pages 735-754.
    7. Denis Bouyssou & Thierry Marchant & Marc Pirlot, 2020. "A theoretical look at ELECTRE TRI-nB," Working Papers hal-02898131, HAL.
    8. Liu, Jiapeng & Liao, Xiuwu & Kadziński, Miłosz & Słowiński, Roman, 2019. "Preference disaggregation within the regularization framework for sorting problems with multiple potentially non-monotonic criteria," European Journal of Operational Research, Elsevier, vol. 276(3), pages 1071-1089.
    9. Bouyssou, Denis & Marchant, Thierry, 2007. "An axiomatic approach to noncompensatory sorting methods in MCDM, II: More than two categories," European Journal of Operational Research, Elsevier, vol. 178(1), pages 246-276, April.
    10. Mousseau, Vincent & Figueira, Jose & Dias, Luis & Gomes da Silva, Carlos & Climaco, Joao, 2003. "Resolving inconsistencies among constraints on the parameters of an MCDA model," European Journal of Operational Research, Elsevier, vol. 147(1), pages 72-93, May.
    11. Herrera-Viedma, E. & Herrera, F. & Chiclana, F. & Luque, M., 2004. "Some issues on consistency of fuzzy preference relations," European Journal of Operational Research, Elsevier, vol. 154(1), pages 98-109, April.
    12. Patrice Perny, 1998. "Multicriteria filtering methods based onconcordance and non-discordance principles," Annals of Operations Research, Springer, vol. 80(0), pages 137-165, January.
    13. Almeida-Dias, J. & Figueira, J.R. & Roy, B., 2012. "A multiple criteria sorting method where each category is characterized by several reference actions: The Electre Tri-nC method," European Journal of Operational Research, Elsevier, vol. 217(3), pages 567-579.
    14. Kadziński, Miłosz & Tervonen, Tommi & Rui Figueira, José, 2015. "Robust multi-criteria sorting with the outranking preference model and characteristic profiles," Omega, Elsevier, vol. 55(C), pages 126-140.
    15. Tervonen, Tommi & Figueira, José Rui & Lahdelma, Risto & Dias, Juscelino Almeida & Salminen, Pekka, 2009. "A stochastic method for robustness analysis in sorting problems," European Journal of Operational Research, Elsevier, vol. 192(1), pages 236-242, January.
    16. Denis Bouyssou & Thierry Marchant & Marc Pirlot, 2020. "A theoretical look at ELECTRE TRI-nB," Working Papers hal-02917994, HAL.
    17. Liu, Jiapeng & Kadziński, Miłosz & Liao, Xiuwu & Mao, Xiaoxin & Wang, Yao, 2020. "A preference learning framework for multiple criteria sorting with diverse additive value models and valued assignment examples," European Journal of Operational Research, Elsevier, vol. 286(3), pages 963-985.
    18. Salvatore Corrente & Michael Doumpos & Salvatore Greco & Roman Słowiński & Constantin Zopounidis, 2017. "Multiple criteria hierarchy process for sorting problems based on ordinal regression with additive value functions," Annals of Operations Research, Springer, vol. 251(1), pages 117-139, April.
    19. Kadziński, Miłosz & Ciomek, Krzysztof, 2021. "Active learning strategies for interactive elicitation of assignment examples for threshold-based multiple criteria sorting," European Journal of Operational Research, Elsevier, vol. 293(2), pages 658-680.
    20. Kadziński, Miłosz & Ghaderi, Mohammad & Dąbrowski, Maciej, 2020. "Contingent preference disaggregation model for multiple criteria sorting problem," European Journal of Operational Research, Elsevier, vol. 281(2), pages 369-387.
    21. Blaszczynski, Jerzy & Greco, Salvatore & Slowinski, Roman, 2007. "Multi-criteria classification - A new scheme for application of dominance-based decision rules," European Journal of Operational Research, Elsevier, vol. 181(3), pages 1030-1044, September.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Khaled Belahcène & Vincent Mousseau & Wassila Ouerdane & Marc Pirlot & Olivier Sobrie, 2023. "Multiple criteria sorting models and methods—Part I: survey of the literature," 4OR, Springer, vol. 21(1), pages 1-46, March.
    2. Ali Tlili & Oumaima Khaled & Vincent Mousseau & Wassila Ouerdane, 2023. "Interactive portfolio selection involving multicriteria sorting models," Annals of Operations Research, Springer, vol. 325(2), pages 1169-1195, June.
    3. Wenfeng Zhu & Hengjie Zhang & Jing Xiao, 2023. "Coming to Consensus on Classification in Flexible Linguistic Preference Relations: The Role of Personalized Individual Semantics," Group Decision and Negotiation, Springer, vol. 32(5), pages 1237-1271, October.

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Khaled Belahcène & Vincent Mousseau & Wassila Ouerdane & Marc Pirlot & Olivier Sobrie, 2023. "Multiple criteria sorting models and methods—Part I: survey of the literature," 4OR, Springer, vol. 21(1), pages 1-46, March.
    2. Arcidiacono, Sally Giuseppe & Corrente, Salvatore & Greco, Salvatore, 2021. "Robust stochastic sorting with interacting criteria hierarchically structured," European Journal of Operational Research, Elsevier, vol. 292(2), pages 735-754.
    3. Fernández, Eduardo & Figueira, José Rui & Navarro, Jorge & Solares, Efrain, 2023. "A generalized approach to ordinal classification based on the comparison of actions with either limiting or characteristic profiles," European Journal of Operational Research, Elsevier, vol. 305(3), pages 1309-1322.
    4. Ru, Zice & Liu, Jiapeng & Kadziński, Miłosz & Liao, Xiuwu, 2023. "Probabilistic ordinal regression methods for multiple criteria sorting admitting certain and uncertain preferences," European Journal of Operational Research, Elsevier, vol. 311(2), pages 596-616.
    5. Sarah Ben Amor & Fateh Belaid & Ramzi Benkraiem & Boumediene Ramdani & Khaled Guesmi, 2023. "Multi-criteria classification, sorting, and clustering: a bibliometric review and research agenda," Annals of Operations Research, Springer, vol. 325(2), pages 771-793, June.
    6. Denis Bouyssou & Thierry Marchant & Marc Pirlot, 2023. "A theoretical look at Electre Tri-nB and related sorting models," 4OR, Springer, vol. 21(1), pages 1-31, March.
    7. Kadziński, Miłosz & Ciomek, Krzysztof, 2021. "Active learning strategies for interactive elicitation of assignment examples for threshold-based multiple criteria sorting," European Journal of Operational Research, Elsevier, vol. 293(2), pages 658-680.
    8. Khaled Belahcène & Vincent Mousseau & Wassila Ouerdane & Marc Pirlot & Olivier Sobrie, 2023. "Multiple criteria sorting models and methods. Part II: theoretical results and general issues," 4OR, Springer, vol. 21(2), pages 181-204, June.
    9. Liu, Jiapeng & Kadziński, Miłosz & Liao, Xiuwu & Mao, Xiaoxin & Wang, Yao, 2020. "A preference learning framework for multiple criteria sorting with diverse additive value models and valued assignment examples," European Journal of Operational Research, Elsevier, vol. 286(3), pages 963-985.
    10. Cinelli, Marco & Kadziński, Miłosz & Miebs, Grzegorz & Gonzalez, Michael & Słowiński, Roman, 2022. "Recommending multiple criteria decision analysis methods with a new taxonomy-based decision support system," European Journal of Operational Research, Elsevier, vol. 302(2), pages 633-651.
    11. Eduardo Fernández & José Rui Figueira & Jorge Navarro, 2023. "A theoretical look at ordinal classification methods based on comparing actions with limiting boundaries between adjacent classes," Annals of Operations Research, Springer, vol. 325(2), pages 819-843, June.
    12. Murat Köksalan & Vincent Mousseau & Selin Özpeynirci, 2017. "Multi-Criteria Sorting with Category Size Restrictions," International Journal of Information Technology & Decision Making (IJITDM), World Scientific Publishing Co. Pte. Ltd., vol. 16(01), pages 5-23, January.
    13. Vincent Mousseau & Özgür Özpeynirci & Selin Özpeynirci, 2018. "Inverse multiple criteria sorting problem," Annals of Operations Research, Springer, vol. 267(1), pages 379-412, August.
    14. Fernandez, Eduardo & Navarro, Jorge & Bernal, Sergio, 2009. "Multicriteria sorting using a valued indifference relation under a preference disaggregation paradigm," European Journal of Operational Research, Elsevier, vol. 198(2), pages 602-609, October.
    15. Eduardo Fernandez & Jorge Navarro & Rafael Olmedo, 2018. "Characterization of the Effectiveness of Several Outranking-Based Multi-Criteria Sorting Methods," International Journal of Information Technology & Decision Making (IJITDM), World Scientific Publishing Co. Pte. Ltd., vol. 17(04), pages 1047-1084, July.
    16. Govindan, Kannan & Jepsen, Martin Brandt, 2016. "ELECTRE: A comprehensive literature review on methodologies and applications," European Journal of Operational Research, Elsevier, vol. 250(1), pages 1-29.
    17. Denis Bouyssou & Thierry Marchant, 2013. "Some remarks on ELECTRE TRI," Working Papers hal-00942310, HAL.
    18. Bouyssou, Denis & Marchant, Thierry, 2015. "On the relations between ELECTRE TRI-B and ELECTRE TRI-C and on a new variant of ELECTRE TRI-B," European Journal of Operational Research, Elsevier, vol. 242(1), pages 201-211.
    19. Wu, Xingli & Liao, Huchang, 2023. "Value-driven preference disaggregation analysis for uncertain preference information," Omega, Elsevier, vol. 115(C).
    20. Liu, Jiapeng & Liao, Xiuwu & Huang, Wei & Yang, Jian-bo, 2018. "A new decision-making approach for multiple criteria sorting with an imbalanced set of assignment examples," European Journal of Operational Research, Elsevier, vol. 265(2), pages 598-620.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:eee:ejores:v:298:y:2022:i:3:p:979-1006. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Catherine Liu (email available below). General contact details of provider: http://www.elsevier.com/locate/eor .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.