Méthodes à divergences pour la résolution de problèmes de satisfaction de contraintes et d’optimisation combinatoire

Méthodes à divergences pour la résolution de problèmes de satisfaction de contraintes et d’optimisation combinatoire

Heuristiques d’instanciation 

 Généralités

 Les heuristiques d’instanciation sont des règles qui déterminent l’ordre suivant lequel on va choisir les variables pour les instancier ainsi que l’ordre suivant lequel on va choisir les valeurs pour les variables. Ainsi, une heuristique d’instanciation est composée : – d’un ordre sur les variables ; – d’un ordre sur les valeurs. Une bonne heuristique d’instanciation peut avoir un grand impact sur la résolution d’un problème de décision et permettre d’accélérer l’obtention de solutions (la détection d’échecs en cas de problèmes insolubles) pendant l’exploration de l’espace de recherche. Ainsi, on évite que de grandes parties de l’arbre de recherche soient explorées en vain. De plus, si l’on veut favoriser l’apparition d’une solution, les variables et les valeurs sont ordonnées par l’heuristique de telle façon que, si une solution existe, elle sera associée à un chemin qui se trouve, par convention, le plus à gauche possible dans l’arbre de 20 recherche et sera ainsi atteinte au plus tôt lors d’une exploration en profondeur d’abord. Plusieurs travaux se sont interessés aux heuristiques, que ce soit dans un contexte SAT, CSP ou optimisation combinatoire [Hooker 2000, Lecoutre 2007b]. Une heuristique peut être statique ou dynamique selon que les ordres de variables et de valeurs sont fixés au préalable ou évoluent pendant la résolution, de telle sorte qu’elle soit affectée par les changements que subit l’espace de recherche. Nous présentons ci-dessous quelques exemples d’heuristiques. 

 Principe de l’échec au plus tôt ou fail-first

Le principe de l’échec au plus tôt ou fail-first de Haralick se résume en cette citation : “To suceed, try first where you are most likely to fail” (Pour réussir, commence par essayer où il est plus probable d’échouer) [Haralick 1980]. 

 Heuristique du domaine minimal (min-domain)

Cette heuristique dynamique d’ordre sur les variables sélectionne en premier la variable qui a le plus petit domaine de valeurs. 

Heuristiques du degré (degree ou deg)

L’heuristique basée sur les degrés [Dechter 1989] ordonne les variables de manière décroissante en fonction de leur degré (cf. paragraphe 1.1.8). 

Heuristiques du degré dynamique (dynamic-degree ou ddeg)

L’heuristique du degré dynamique ordonne les variables de manière décroissante en fonction de leur degrés dynamiques qui évoluent au cours de la recherche. 

Heuristique du degré pondéré (weighted-degree ou wdeg) 

A chaque étape de résolution, l’objectif de cette heuristique de variables dynamique [Boussemart 2004a, Boussemart 2004b] est de s’appuyer sur des informations issues des étapes précédentes du processus de recherche de solution. Pour cela, un poids est associé 21 à chaque contrainte et à chaque fois que le domaine d’une variable devient vide, le poids de la contrainte ayant entrainé cet échec est incrémenté. L’heuristique wdeg choisit alors la variable associée aux contraintes de plus fort poids. 

Heuristique de la largeur minimale (minimal-width ou width)

 L’heuristique de la largeur minimale [Freuder 1982] ordonne les variables de manière à limiter la largeur du graphe de contraintes (cf. paragraphe 1.1.8). 

Heuristique du conflit minimum (min-conflict)

 Contrairement aux heuristiques présentées ci-dessus, l’heuristique du conflit minimum ordonne les valeurs. Il s’agit de choisir une valeur qui permettra à l’instanciation partielle courante d’être étendue à une solution. Une mesure commune pour juger vraisemblable la participation d’une valeur à une solution est de considérer le nombre de valeurs qui ne sont pas en conflit avec la valeur en question. Ainsi, la valeur qui est compatible avec la plupart des valeurs des variables non instanciées est essayée en premier. Ces différentes heuristiques sont également combinées entre elles, on retrouve classiquement l’utilisation de l’heuristique d’ordre sur les variable min-domain ⊕ ddeg ou min-domain/ddeg ou encore min-domain/wdeg. Les algorithmes de résolution qui utilisent des heuristiques d’ordre assurent, dans la plupart des cas, une résolution plus rapide que celle obtenue par des algorithmes sans heuristique d’ordre. Même si les différentes heuristiques d’ordre sont en général incomparables entre elles, dans de nombreux cas (et notamment sur des problèmes structurés) l’heuristique min-domain/wdeg fournit de très bons résultats.