Exploitation de la décomposition arborescente dans une méthode recherche locale pour la résolution de problèmes d’optimisation de contraintes

Dans les méthodes de recherche locale, le choix de voisinages pertinents à explorer est un point essentiel pour un bon parcours de l’espace de recherche. La prise en compte de la structure du problème à résoudre est primordiale lors de la construction de ces voisinages. La décomposition arborescente est une méthode de partitionnement d’un problème en clusters formant un graphe acyclique. Cette structure est exploitée par des méthodes de recherche complète dans le cadre des problèmes d’optimisation sous contraintes.

Dans cet exposé, nous montrons comment exploiter cette décomposition pour construire des voisinages pertinents pour les méthodes de recherche locale à voisinages larges (VNS). Puis, nous proposons un affinement de cette méthode par la prise en compte de la dureté des contraintes. Enfin, des résultats expérimentaux obtenus dans le cadre des problème de satisfaction de contraintes valuées (WCSP) seront présentés afin de montrer la pertinence et l’efficacité de l’approche proposée.