Abstract
The Constrained CP-net problem concerns finding solutions that satisfy a set of hard constraints and not preferentially dominated by other satisfiable solution in the search space. In this paper, we propose an algorithm to fmd k optimal solutions given a constrained CP-net structure. We identify sufficient conditions under which the proposed algorithm is guaranteed to have the anytime property where the solutions found so far will never be dominated by any future solution. Furthermore, to enhance the solving process in practice, we rely on constraint propagation techniques and maintain a heuristic search function based on the minimum number of worsening flips and hamming distance to the optimal.