Compilation de préférences - application à la configuration de produits
- Doctorant:
- Nicolas Schmidt
- Co-directeurs de thèse :
- Hélène Fargier
- Pierre Marquis
- Financement : ANR
- Thèse soutenue le :
- 17 sept. 2015
L’intérêt des différents langages de la famille des diagrammes de décision valués (VDD) est qu’ils admettent des algorithmes en temps polynomial pour des traitements (comme l’optimisation, la cohérence inverse globale, l’inférence) qui ne sont pas polynomiaux (sous l’hypothèse P≠NP), si ils sont effectués sur le problème dans sa forme originale tel que les réseaux de contraintes ou les réseaux bayésiens.
Dans cet exposé, nous nous intéressons au problème de configuration de produit, et plus spécifiquement, la configuration en ligne avec fonction de valuation associée (typiquement, un prix). Ici, la présence d’un utilisateur en ligne nous impose une réponse rapide à ses requêtes, rapidité rendant impossible l’utilisation de langages n’admettant pas d’algorithmes en temps polynomial pour ces requêtes. La solution proposée est de compiler hors-ligne ces problèmes vers des langages satisfaisant ces requêtes, afin de diminuer le temps de réponse pour l’utilisateur.
Une première partie de cet exposé est consacrée à l’étude théorique des VDD, et plus particulièrement les trois langages Algebraic Decision Diagrams, Semi ring Labelled Decision Diagrams et Affine Algebraic Decision Diagrams (ADD, SLDD et AADD). Nous y remanions le cadre de définition des SLDD, proposons des procédures de traductions entre ces langages, et étudions la com pacité théorique de ces langages. Nous établissons dans une deuxième partie la carte de compilation de ces langages, dans laquelle nous déterminons la complexité algorithmique d’un ensemble de requêtes et transformations correspondant à nos besoins. Nous proposons également un algorithme de compilation à approche ascendante, ainsi que plusieurs heuristiques d’ordonnancement de variables et contraintes visant à minimiser la taille de la représentation après compilation ainsi que le temps de compilation. Enfin la dernière partie est consacrée à l’étude expérimentale de la compilation et de l’utilisation de formes compilées pour la configuration de produit. Ces expérimentations confirment l’intérêt de notre approche pour la configuration en ligne de produit. Nous avons implémenté un compilateur (le compilateur SALADD) pleinement fonctionnel, réalisant la compilation de réseaux de contraintes et de réseaux bayésiens, et avons développés un ensemble de fonctions adaptées à la configuration de produit. Le bon fonctionnement et les bonnes performances de ce compilateur ont été validés via un protocole de validation commun à plusieurs solveurs.
Mots-clefs : Compilation, configuration de produit, recommandation,diagramme de décision valué, heuristique d’ordonnancement, CSP