Preference-based constrained optimization with CP-nets

Many AI tasks, such as product configuration, decision support, and the construction of autonomous agents, involve a process of con-1 strained optimization, that is, optimization of behavior or choices subject to given constraints. In this paper we present an approach for constrained optimization based on a set of hard constraints and a preference ordering represented using a CP-network—a graphical model for representing qualitative preference information. This approach offers both pragmatic and computational advantages. First, it provides a convenient and intuitive tool for specifying the problem, and in particular, the decision maker’s preferences. Second, it admits an algorithm for finding the most preferred feasible (Pareto optimal) outcomes that has the following anytime property: the set of preferred feasible outcomes are enumerated without backtracking. In particular, the first feasible solution generated by this algorithm is Pareto optimal.