Introduction de contraintes structurelles pour la résolution du problème du voyageur de commerce

Plusieurs modèles basés sur la programmation par contraintes ont été proposés pour résoudre le problème du voyageur de commerce (TSP). Les plus efficaces, telle que la weighted circuit constraint (WCC), s'appuient prin-cipalement sur la relaxation lagrangienne du TSP, basée sur la recherche d'arbres recouvrants ou plus précisément de "one-trees". Le défaut de cette méthode est qu'elle n'inclut pas assez de contraintes structurelles et se base presque exclusivement sur les coûts des arêtes. L'objectif de cet article est de corriger ce défaut. Aussi, nous cherchons des motifs empêchant l'existence d'un cycle hamiltonien dans un graphe ou, à l'inverse, des motifs imposant que certaines arêtes soient dans l'ensemble de solutions du TSP. Nous proposons un propagateur basé sur la recherche de k-cutsets pour la contrainte de cycle hamiltonien. Sa combinaison avec la contrainte WCC permet d'obtenir, pour la résolution du TSP, des gains d'un ordre de magnitude pour le nombre de backtracks ainsi qu'une forte réduction du temps de calcul.