2021/09/24 by Sultan Ahmed, Ahmed, Sultan, Malek Mouhoub +1
Computer Science · Decision Sciences · #Artificial Intelligence (cs.AI) #Constraint Satisfaction and Optimization #FOS: Computer and information sciences #Multi-Criteria Decision Making #Rough Sets and Fuzzy Logic
paper · pdf · doi:10.48550/arxiv.2109.12179
openalex publication_date 2021/09/24 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The Conditional Preference Network (CP-net) graphically represents user's qualitative and conditional preference statements under the ceteris paribus interpretation. The constrained CP-net is an extension of the CP-net, to a set of constraints. The existing algorithms for solving the constrained CP-net require the expensive dominance testing operation. We propose three approaches to tackle this challenge. In our first solution, we alter the constrained CP-net by eliciting additional relative importance statements between variables, in order to have a total order over the outcomes. We call this new model, the constrained Relative Importance Network (constrained CPR-net). Consequently, We show that the Constrained CPR-net has one single optimal outcome (assuming the constrained CPR-net is consistent) that we can obtain without dominance testing. In our second solution, we extend the Lexicographic Preference Tree (LP-tree) to a set of constraints. Then, we propose a recursive backtrack search algorithm, that we call Search-LP, to find the most preferable outcome. We prove that the first feasible outcome returned by Search-LP (without dominance testing) is also preferable to any other feasible outcome. Finally, in our third solution, we preserve the semantics of the CP-net and propose a divide and conquer algorithm that compares outcomes according to dominance testing.