ACCUEIL

Consignes aux
auteurs et coordonnateurs
Nos règles d'éthique

APPEL À
CONTRIBUTION
Masses de données hétérogènes
En savoir plus >>
Autres revues >>

Revue d'Intelligence Artificielle

0992-499X
Revue des Sciences et Technologies de l'Information
 

 ARTICLE VOL 28/5 - 2014  - pp.571-592  - doi:10.3166/ria.28.571-592
TITRE
Compacité pratique des diagrammes de décision valués. Normalisation, heuristiques et expérimentations

TITLE
Succinctness of valued decision diagrams. Normalization, heuristics and experiments

RÉSUMÉ

Les diagrammes de décision valués (VDD) sont particulièrement intéressants pour la compilation de problèmes de satisfaction de contraintes valuées (VCSP). L’intérêt des différents langages de la famille VDD (en particulier, les langages ADD, SLDD, AADD) est qu’ils ad- mettent des algorithmes en temps polynomial pour des traitements (comme l’optimisation) qui ne sont pas polynomiaux à partir des VCSP de départ. Comme l’efficacité pratique de tels trai- tements dépend de la taille du VDD compilé obtenu, il est important d’obtenir une forme la plus compacte possible. Nous décrivons dans cet article quelques résultats issus de nos travaux sur l’étude de la compacité pratique des VDD. Nous présentons un compilateur ascendant de VCSP en SLDD + (resp. SLDD  ), un jeu d’heuristiques d’ordonnancement des variables, des procé- dures de traduction des langages SLDD + (resp. SLDD  ) vers les langages ADD et AADD, et nous identifions quelques requêtes et transformations d’intérêt, réalisables en temps polynomial quand l’ensemble des affectations est représenté par un VDD. Les différents langages cibles et les heuristiques ont été testés sur deux familles de jeux d’essai, des VCSP additifs représentant des problèmes de configuration de voitures avec fonctions de coût, et des réseaux bayésiens. Il apparaît que, bien que le langage AADD soit strictement plus succinct en théorie que SLDD + (resp. SLDD  ), le langage SLDD + (resp. SLDD  ) convient bien en pratique quand il s’agit de compiler des problèmes de nature purement additive (resp. purement multiplicative).



ABSTRACT

Valued decision diagrams (VDDs) prove valuable data structures for compiling va- lued constraint satisfaction problems (VCSPs). Indeed, languages from the VDD family (espe- cially, ADD, SLDD, AADD) benefit from polynomial-time algorithms for some tasks of interest (e.g., the optimization one) for which no polynomial-time algorithm exists when the input is the VCSP considered at start. Since the practical efficiency of such tasks depends in practice on the size of the compiled VDD, it is important to look for diagrams which are as compact as possible n this paper some results from our study of the practical compactness of VDDs are pointed out. We present a VCSP-to-SLDD + bottom-up compiler (resp. a VCSP-to-SLDD  bottom-up com- piler), several variable ordering heuristics, some translation procedures from SLDD + (resp. SLDD  ) to ADD and to AADD, and we identify some useful queries and transformations than can be achieved in polynomial time when the set of assignments is represented as a VDD. The target languages and the heuristics under consideration have been tested on two families of benchmarks, additive VCSPs representing car configuration problems with cost functions and multiplicative VCSPs representing Bayesian nets. It turns out that even if the AADD language is strictly more succinct (from the theoretical side) than SLDD + (resp. SLDD  ), the language SLDD + (resp. SLDD  ) proves to be good enough in practice when purely additive (resp. purely multiplicative) problems are to be compiled.



AUTEUR(S)
Hélène FARGIER , Pierre MARQUIS , Nicolas SCHMIDT

MOTS-CLÉS
compilation, configuration, diagramme de décision valué

KEYWORDS
compilation, configuration, valued decision diagram

LANGUE DE L'ARTICLE
Français

 PRIX
• Abonné (hors accès direct) : 7.5 €
• Non abonné : 15.0 €
|
|
--> Tous les articles sont dans un format PDF protégé par tatouage 
   
ACCÉDER A L'ARTICLE COMPLET  (524 Ko)



Mot de passe oublié ?

ABONNEZ-VOUS !

CONTACTS
Comité de
rédaction
Conditions
générales de vente

 English version >> 
Lavoisier