Conference Papers Year : 2015

Towards an MDD-based representation of preferences

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
Fichier principal
Vignette du fichier
ip15-mdd-prefs.pdf (115) Télécharger le fichier
Origin Files produced by the author(s)

Dates and versions

lirmm-01276183 , version 1 (18-10-2018)

Identifiers

  • HAL Id : lirmm-01276183 , version 1

Cite

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⟩
220 View
44 Download

Share

More