Finding the Next Solution in Constraint-and Preference-Based Knowledge Representation Formalisms. Conference Paper uri icon


  • Abstract 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 …

publication date

  • January 1, 2010

presented at event

  • KR  Conference