Constrained LP-trees
Sultan Ahmed, Malek Mouhoub · 2019
In preference-based constrained optimization problems, helping users by providing the most preferable feasible outcome is crucial. The Lexicographic Preference Tree (LP- tree) and the Conditional Preference Network (CP-net) are two fundamental graphical models to represent and reason about user's qualitative preferences. In this paper, we extend the LP- tree with a set of hard feasibility constraints, and then we propose a recursive backtrack search algorithm that we call Search-LP to find the most preferable feasible outcome for the Constrained LP-tree. Search-LP instantiates the variables with respect to a hierarchical order defined by the LP-tree. Given that the LP-tree represents a total order over the outcomes, Search-LP simply returns the first feasible outcome. We prove that this returned outcome is also preferable to every other feasible outcome. The main advantage of Search-LP is that it does not require dominance testing (the task of comparing two outcomes using preferences) to find the optimal solution(s), while dominance testing is a very expensive operation in the case of Constrained CP-nets.