Un nogood est une instanciation partielle qui ne peut être prolongée vers une solution. L’intérêt des nogoods est d’éviter le phénomène de thrashing, c’est-à-dire d’explorer de manière répétée les mêmes sous-arbres incohérents. Deux approches classiques existent pour les identifier et les enregistrer que ce soit au cours de la recherche ou au redémarrage.

L’apprentissage de nogoods est un thème qui a été introduit dans les années 90 (Dechter (1990), Schiex et Verfaillie (1994), Frost et Dechter (1994)) pour la résolution de problèmes de satisfaction de contraintes. Les nogoods classiques, dits standards, sont des instanciations partielles ne pouvant mener à aucune solution. Ils ont été assez rapidement utilisés pour gérer l’explication (Ginsberg (1993), Jussien et al. (2000)) de valeurs supprimées au cours de la recherche et de la propagation de contraintes. Ils ont ensuite été généralisés (Katsirelos et Bacchus (2003), abordés en section 4.1) en permettant la combinaison d’affectations de variables (décisions positives) et de réfutations de valeurs (décisions négatives). L’intérêt pratique des nogoods (généralisés) a été revisité par les travaux portant sur la génération paresseuse de clauses (Feydy et Stuckey (2009), détaillée en section 4.3).

Les nogoods peuvent également être utiles dans un contexte de redémarrage régulier d’un algorithme de recherche arborescente. Il est en effet possible d’identifier (Lecoutre et al. (2007a;b)) sur la dernière branche de l’arbre de recherche (traditionnellement représentée par celle qui est la plus à droite) un ensemble de nogoods représentant la partie de l’espace de recherche qui vient d’être explorée. Par le fait de simplement enregistrer ces nogoods, appelés nld-nogoods (réduits), nous avons la garantie de ne jamais explorer de nouveau les mêmes sous-arbres. Certaines extensions de ces travaux ont porté sur l’élimination de symétries (Lecoutre et Tabary (2011), Lee et Zhu (2014)) et l’exploitation du caractère croissant des nld-nogoods (Lee et al. (2016)), appelés de ce fait increasing-nogoods.

Nogoods standards 

Un nogood est un ensemble de décisions qui n’apparaît dans aucune solution d’un problème donné, il ne pourra donc jamais être étendu à une solution dudit problème. L’idée est de garder une trace des calculs effectués pour ne pas avoir à les refaire et de les stocker dans une base de connaissances. Celle-ci pour être efficace doit persister lors des redémarrages car pour un algorithme de résolution avec retours arrière, les nogoods ne servent qu’après un redémarrage pour élaguer les branches déjà parcourues et connues comme insatisfiables.

Définition 11 (Décision positive/négative)

Soit P = (X , C) un réseau de contraintes et (x, v) un couple tel que x ∈ X et a ∈ dom(x). L’affectation x = a est appelée décision positive tandis que x ≠ a est appelée décision négative.

Remarque 3 : ¬(x = a) (resp. ¬(x ≠ a)) signifie x ≠ a (resp. x = a).

Définition 12 (Nogood standard)

Un nogood standard est un ensemble de décisions positives, c’est-à-dire d’instanciations de la forme X = a, parfois noté X ← a, qui ne sont cohérentes avec aucune solution.

Enregistrement et exploitation des nogoods

Les nogoods ont initialement été développés pour la programmation par contraintes mais l’absence de résultats convaincants pendant de longues années n’a pas permis de retenir cette technique. Celle-ci a par contre obtenu des résultats en satisfaction booléenne (SAT) notamment grâce aux watched literals (Zhang et al. (2001), présentés section 3.4.2) combinés avec l’heuristique VSIDS (présentée section 3.4.3) et les retours arrière non chronologiques (backjump).

Pour rendre cette technique efficace en CP, des optimisations sont nécessaires, notamment, limiter la taille des nogoods. Traiter les nogoods revient ainsi à ajouter des contraintes à satisfaire.

Cela alourdit le problème et augmente le temps d’exécution des algorithmes de cohérence, donc limiter leur taille est capital. Afin de pallier ce problème, en SAT, les nogoods enregistrés ne sont pas systématiquement minimaux et l’enregistrement de nogoods est restreint aux nogoods inférieurs à une certaine taille définie auparavant et à un seul par échec, selon le principe du First Unique Implication Point (1-UIP, Zhang et al. (2001)). Le but n’est pas de tous les générer mais de garder ceux qui permettent d’élaguer le plus de branches en ayant le moins d’impact sur le temps du processus de recherche.