Heuristiques pour la recherche énumérative bornée : Vers une libération de l'ordre

Lors des JFPC'2005, les auteurs de la présente contribution, ont montré l'intérêt que recèle l'exploitation des heuristiques pour s'assurer de l'efficacité pratique des méthodes de résolution de CSP par décomposition arborescente. Nous étendons ce travail en le géné- ralisant. Nous montrons qu'au-delà d'heuristiques sur le parcours de l'arborescence associé à la décomposition, une gestion dynamique de l'heuristique de choix des variables s'avère cruciale. Tout en conservant les bornes de complexité (O(exp(w+1)) où w est la tree-width du CSP), nous proposons une voie pour s'aranchir en partie du carcan imposé par la structure arborescente. Cette démarche nous conduit à dénir de nouvelles bornes de complexité qui orent un compromis entre bornes théoriques et libération de l'ordre. En particulier, nous introduisons un nouveau paramètre k indiquant le degré de liberté laissé à l'heuristique de choix de variables qui permet de borner la complexité par O(exp(2(w + k))). Les résultats expérimentaux présentés montrent l'intérêt d'une telle démarche