Constraint-Based Preferential Optimization

Book One

Volume

Proceedings of the AAAI Conference on Artificial Intelligence, 20

Constraint Satisfaction and Satisfiability

We first show that the optimal and undominated outcomes of an unconstrained (and possibly cyclic) CP-net are the solutions of a set of hard constraints. We then propose a new algorithm for finding the optimal outcomes of a constrained CP-net which makes use of hard constraint solving. Unlike previous 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 approximation 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 solutions even when optimals do not exist.