Résumé en anglais

In many application domains we need to find solutions that satisfy, apart from a set of hard constraints, a set of user defined preferences. Ceteris Paribus (CP)-networks have been proposed as an intuitively appealing framework for expressing preference statements. CP-nets have been further extended to incorporate information on the relative importance of the variables, resulting in a formalism called TCP-nets. Despite their high expressive power, TCP-nets do not capture certain types of preference statements that seem to arise naturally in practice. In this paper we extend TCP-networks with variable importance statements that specify that a variable is more important than its ancestors in the network. These importance statements may induce preference relations on the set of outcomes that contain conflicting pairs. To handle such cases we propose a new semantics that aggregates preference and variable important information in such a way that preferences on more important variables override preferences on less important variables.