AAAI Publications, Twelfth International Conference on the Principles of Knowledge Representation and Reasoning

Font Size: 
Finding the Next Solution in Constraint- and Preference-Based Knowledge Representation Formalisms
Ronen Brafman, Francesca Rossi, Domenico Salvagnin, K. Brent Venable, Toby Walsh

Last modified: 2010-04-27


In constraint or preference reasoning, a typical task is to compute a solution, or an optimal solution. However, when one has already a solution, it may be important to produce the next solution following the given one in a linearization of the solution ordering where more preferred solutions are ordered first. In this paper, we study the computational complexity of finding the next solution in some common preference-based representation formalisms. We show that this problem is hard in general CSPs, but it can be easy in tree-shaped CSPs and tree-shaped fuzzy CSPs. However, it is difficult in weighted CSPs, even if we restrict the shape of the constraint graph. We also consider CP-nets, showing that the problem is easy in acyclic CP-nets, as well as in constrained acyclic CP-nets where the (soft) constraints are tree-shaped and topologically compatible with the CP-net.


preferences; soft constraints; constraint satisfaction

Full Text: PDF