Skip to Main content Skip to Navigation
Conference papers

Towards an MDD-based representation of preferences

Noureddine Aribi 1 Souhila Kaci 2 Nadjib Lazaar 3
2 SMILE - Système Multi-agent, Interaction, Langage, Evolution
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
3 COCONUT - Agents, Apprentissage, Contraintes
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Abstract : 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
Document type :
Conference papers
Complete list of metadata
Contributor : Joël Quinqueton Connect in order to contact the contributor
Submitted on : Thursday, October 18, 2018 - 12:50:34 PM
Last modification on : Friday, October 22, 2021 - 3:07:33 PM
Long-term archiving on: : Saturday, January 19, 2019 - 2:03:04 PM


Files produced by the author(s)


  • HAL Id : lirmm-01276183, version 1



Noureddine Aribi, Souhila Kaci, Nadjib Lazaar. Towards an MDD-based representation of preferences. CPCR+ITWP@IJCAI, Jul 2015, Buenos Aires, Argentina. pp.34-34. ⟨lirmm-01276183⟩



Les métriques sont temporairement indisponibles