Constrained Optimization with Partial CP-Nets
Malek Mouhoub, Sultan Ahmed · 2018
The Conditional Preference Network (CP-net) is a graphical tool for representing and reasoning about user's conditional ceteris paribus preference statements. In case the user provides partial preferences, we get a partial CP-net. In this paper, we propose a novel algorithm, that we call Search-Partial-CP, to find the Pareto optimal outcomes with respect to an acyclic partial CP-net and a set of hard constraints. Search-Partial-CP is a backtrack search algorithm that utilizes the topological order of the related Directed Acyclic Graph (DAG) to order the variables, as well as the topological order of the partial preferences to order the values, during the instantiation process. Search-Partial-CP can significantly reduce the search space by pruning every infeasible or dominated outcome. We present and discuss the formal properties of Search-Partial-CP.