Constrained Optimization with Qualitative Preferences

Abstract The Conditional Preference Network (CP-net) graphically represents the 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. Existing algorithms for solving the constrained CP-net require expensive dominance testing operations. 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 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 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 called 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.