Résumé
In a purely constraint programming (CP) context, Andersen et al. [Andersen et al., 2007] proposed to use the Multivalued Decision Diagram structure (MDD) to replace the domain store where constraints have an MDD-Based presentation. An MDD is graphically represented by a (rooted) directed acyclic graph of an ordered list of variables, and can be exponentially smaller than the extensional version of feasible outcomes. Each outcome is encoded as a path in the graph, and each edge in the path encodes a variable assignment. Additionally, an MDD comes with a fast and effective GAC algorithm [Cheng and Yap, 2010], that has time complexity linear to the size of the MDD, and achieves full incrementality in constant time.To take advantage of MDDs we consider the case of preference constrained problems. That is, not all possible outcomes are feasible. In this proposal, we attempt to address the problem of outcomes representation using MDDs where, in our context, domain store represents all possible outcomes and constraints are constraints restricting the feasibility of outcomes