# Constrained Optimization with Qualitative Preferences

arXiv: https://arxiv.org/abs/2109.12179 · HTML: https://mlsanity.com/paper/2109.12179/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 1 of its 42 references that are in the map.
- First posted on arXiv 24 Sep 2021.

## Builds on (most cited first, 1 of 1)

- [The Computational Complexity of Dominance and Consistency in CP-Nets](https://mlsanity.com/paper/1401.3453/) (2014)

## Abstract (arXiv)

The Conditional Preference Network (CP-net) graphically represents user's qualitative and conditional preference statements under the ceteris paribus interpretation. The constrained CP-net is an extension of the CP-net, to a set of constraints. The existing algorithms for solving the constrained CP-net require the expensive dominance testing operation. We propose three approaches to tackle this challenge. In our first solution, we alter the constrained CP-net by eliciting additional relative importance statements between variables, in order to have a total order over the outcomes. We call this new model, the constrained Relative Importance Network (constrained CPR-net). Consequently, We show that the Constrained CPR-net has one single optimal outcome (assuming the constrained CPR-net is consistent) that we can obtain without dominance testing. In our second solution, we extend the Lexicographic Preference Tree (LP-tree) to a set of constraints. Then, we propose a recursive backtrack search algorithm, that we call Search-LP, to find the most preferable outcome. We prove that the first feasible outcome returned by Search-LP (without dominance testing) is also preferable to any other feasible outcome. Finally, in our third solution, we preserve the semantics of the CP-net and propose a divide and conquer algorithm that compares outcomes according to dominance testing.