Une technique de décomposition pour Max-CSP

National audienceL'objectif du problème Max-CSP (Maximal Constraint Satisfaction Problem) est de trouver une instanciation qui minimise le nombre de contraintes violées dans un réseau de contraintes. Dans cet article, à partir du concept de contraintes disjonctives inférées introduit par Freuder et Hubbe, nous montrons qu'il est possible d'exploiter les compteurs d'arc-incohérence, associés à chaque valeur du réseau, de manière à éviter l'exploration de parties inutiles de l'espace de recherche. Le principe est de raisonner à partir de la distance entre les deux meilleures valeurs du domaine d'une variable, selon ces compteurs. Sur cette base, on peut mettre en place une technique de décomposition qui peut être utilisée tout au long de la recherche de manière à réduire le problème courant en sous-problèmes plus simples. Il est intéressant de noter que cette approche ne dépend pas de la structure du graphe de contraintes, comme cela est généralement proposé. Comme alternative à la décomposition, il est possible de poster des contraintes dures qui peuvent être utilisées pour élaguer l'espace de recherche. L'intérêt de notre approche est illustré en pratique, avec cette alternative, par une expérimentation basée sur un algorithme classique de séparation et évaluation, à savoir PFC-MRDAC