Constraint-Based Preferential Optimization

Abstract

We first show that the optimal and undominated outcomes of an unconstrained (and possibly cyclic) CP-net are the solu-tions of a set of hard constraints. We then propose a new algo-rithm for finding the optimal outcomes of a constrained CP-net which makes use of hard constraint solving. Unlike pre-vious algorithms, this new algorithm works even with cyclic CP-nets. In addition, the algorithm is not tied to CP-nets, but can work with any preference formalism which produces a preorder over the outcomes. We also propose an approxima-tion method which weakens the preference ordering induced by the CP-net, returning a larger set of outcomes, but provides a significant computational advantage. Finally, we describe a weighted constraint approach that allows to find good solu-tions even when optimals do not exist.