Constraint-Based Preferential Optimization

Steve Prestwich, Francesca Rossi, Kristen Brent Venable, Toby Walsh

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.

Content Area: 6. Constraint Satisfaction and Satisfiability

Subjects: 15.2 Constraint Satisfaction; 11. Knowledge Representation

Submitted: May 10, 2005

This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.