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 metadatas

https://hal-lirmm.ccsd.cnrs.fr/lirmm-01276183
Contributor : Joël Quinqueton <>
Submitted on : Thursday, October 18, 2018 - 12:50:34 PM
Last modification on : Sunday, December 16, 2018 - 10:42:02 AM
Long-term archiving on : Saturday, January 19, 2019 - 2:03:04 PM

File

ip15-mdd-prefs.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : lirmm-01276183, version 1

Collections

Citation

Noureddine Aribi, Souhila Kaci, Nadjib Lazaar. Towards an MDD-based representation of preferences. IJCAI Joint Workshop, Jul 2015, Buenos Aires, Argentina. ⟨lirmm-01276183⟩

Share

Metrics

Record views

240

Files downloads

7