Prise de décision multiattribut avec le modèle GAI

GAI networks are a graphical model, both compact and expressive, for representing the preferences of a Decision Maker in the context of Multiattribute Decision Making, i.e., in situations where the set of alternatives among which the Decision Maker has to make decisions are described as a set of attributes (or features). GAI network's graphical structures are exploited to develop e cient elicitation pro cedures (determination of the Decision Maker's preferences using questionnaires) as well as e ffective Decision Making algorithms (e.g., computing the preferred alternative or the k-best alternatives). The goal of this PhD thesis is twofold. First, it extends the aforementioned state-of-the-art Decision Making algorithms to be able to cope with dense GAI networks, i.e., with situations where the GAI network's treewidth is to o high for these algorithms to complete in a reasonable amount of time. For this purpose, a new triangulation method has been developed which produces approximated GAI networks on which tailored inference mechanisms determine the alternatives that are actually optimal for the original GAI network. Second, we have prop osed new inference algorithms for Multicriteria Decision Making. More precisely, new approaches for determining Pareto-optimal sets (exact and approximate with performance guarantee) and Lorenz-optimal sets have b een developed. In addition, we have also proposed new algorithms for computing the optimal solutions in situations where criteria are aggregated using various op erators like OWA (Ordered Weighted Average), Choquet integrals and Tchebyche ff's norm.Les réseaux GAI sont une représentation graphique compacte et expressive des préférences d'un décideur en Décision Multiattribut, c'est-à-dire dans des situations où les alternatives sur lesquelles portent les choix du décideur sont décrites à l'aide d'un ensemble d'attributs (de caractéristiques). L'exploitation de leur structure graphique permet de définir des procédures efficaces d'élicitation de préférences (détermination des préférences à l'aide de questionnaires) ainsi que des algorithmes assez performants de prise de décision (calcul de l'alternative préférée du décideur ou des k meilleures alternatives). Le but de cette thèse est double. Tout d'abord elle vise à étendre les algorithmes de prise de décision dans des cas où les réseaux GAI sont denses, c'est-à-dire dans des situations où leur structure ne permet pas aux algorithmes de l'état de l'art de s'exécuter en un temps raisonnable. Pour cela, une nouvelle méthode de triangulation approchée a été développée, qui produit des réseaux GAI approchés sur lesquels des mécanismes d'inférence adaptés permettent d'obtenir les alternatives optimales des réseaux GAI d'origine. Ensuite, elle propose de nouvelles méthodes d'inférence en Décision multicritère. Plus précisément, elle propose des approches pour déterminer des frontières de Pareto (exactes ou approchées avec garantie de performance) ou des frontières de Lorenz. Elle prop ose également des algorithmes pour déterminer des solutions optimales dans les cas où les critères peuvent être agrégés via des opérateurs tels que OWA (Ordered Weighted Average), l'intégrale de Choquet ou bien encore la norme de Tchebyche ff