Vers une exploitation dynamique de la décomposition pour les CSPs pondérés

Philippe Jégou (1, 2) , Hanan Kanso (2) , Cyril Terrioux (1, 2)

1 LSIS - Laboratoire des Sciences de l'Information et des Systèmes
2 COALA - COntraintes, ALgorithmes et Applications

Pour résoudre les problèmes de satisfaction de contraintes pondérés, les méthodes basées sur une dé-composition arborescente constituent une approche inté-ressante selon la nature des instances considérées. Sou-vent, les décompositions exploitées visent à réduire la taille maximale des clusters, connue comme étant la lar-geur de la décomposition. En effet, l'intérêt de ce pa-ramètre est lié à son importance par rapport à la com-plexité théorique de telles méthodes. À ce niveau, Min-Fill constitue l'heuristique de référence pour le calcul de décompositions. Cependant, son intérêt pratique pour la résolution de problèmes demeure limité au vu de ses multiples défauts, notamment au niveau de la restriction de la liberté de l'heuristique de choix de variables. Ainsi, nous proposons, dans un premier temps, d'ex-ploiter de nouvelles décompositions pour le problème d'optimisation sous contraintes. Le but de ces décom-positions est de capturer des critères permettant d'aug-menter l'efficacité de la résolution. Dans un second temps, nous proposons d'exploiter ces décompositions plus dynamiquement dans le sens où la résolution d'un sous-problème ne se baserait sur la décomposition que lorsque cela semble utile. Les expérimentations réalisées montrent l'intérêt pratique des nouvelles décompositions ainsi que l'apport de leur exploitation dynamique. Abstract When solving weighted constraint satisfaction problems , methods based on a tree-decomposition constitute an interesting approach depending on the nature of the considered instances. The exploited decomposi-tions often aim to reduce the maximal size of the clusters , which is known as the width of the decomposition. Indeed, the interest of this parameter is related to its importance with respect to the theoretical complexity of these methods. However, its practical interest for the solving of instances remains limited if we consider its multiple drawbacks, notably due to the restriction imposed on the freedom of the variable ordering heuristic.

Domaines: Informatique [cs]

Philippe Jégou, Hanan Kanso, Cyril Terrioux. Vers une exploitation dynamique de la décomposition pour les CSPs pondérés. Treizièmes Francophones de Programmation par Contraintes, JFPC 2017, Jun 2017, Montreuil-sur-Mer, France. ⟨hal-01785202⟩