Les triangles cassés, encore et encore

Martin Cooper (1, 2) , Achref El Mouelhi (3, 4, 5) , Cyril Terrioux (3, 5)

1 IRIT-ADRIA - Argumentation, Décision, Raisonnement, Incertitude et Apprentissage
2 UT3 - Université Toulouse III - Paul Sabatier
3 LSIS - Laboratoire des Sciences de l'Information et des Systèmes
4 Arts et Métiers ParisTech
5 COALA - COntraintes, ALgorithmes et Applications

Les triangles cassés représentent un concept important, non seulement pour la résolution en temps polynomial des problèmes de satisfaction de contraintes, mais aussi pour l'élimination de variables ou encore la réduction de la taille des domaines par la fusion des valeurs. Plus précisément, pour une variable donnée d'un CSP binaire arc-cohérent, si aucun triangle cassé ne se produit sur aucun couple de valeurs, alors cette variable peut être éliminée tout en préservant la satisfiabilité. Plus récemment, il a été démontré qu'en cas de non applicabilité de cette règle à cause de l'existence d'au moins un triangle cassé, il se peut qu'il existe deux valeurs de cette même variable sur lesquelles aucun triangle cassé ne s'est produit. Dans ce cas, ces deux valeurs peuvent être fusionnées en une seule tout en préservant la satisfiabilité. Dans ce papier, nous montrons que sous certaines conditions, et même en cas d'existence de quelques triangles cassés sur un couple de valeurs d'une variable donnée, les deux valeurs peuvent être fusionnées sans changer la satisfiabilité de l'instance.

Mots clés: Triangles cassés

Domaines: Intelligence artificielle [cs.AI]; Apprentissage [cs.LG]; Logique en informatique [cs.LO]; Informatique et langage [cs.CL]

Martin Cooper, Achref El Mouelhi, Cyril Terrioux. Les triangles cassés, encore et encore. 12emes Journees Francophones de Programmation par Contraintes (JFPC 2016), Jun 2016, Montpellier, France. pp. 133-141. ⟨hal-01671343⟩