Autour des Triangles Cassés

Abstract

Une instance CSP binaire qui satisfait la propriété des triangles cassés (BTP) peut être résolue en temps polynomial. Malheureusement, en pratique, peu d'instances satisfont cette propriété. Nous montrons qu'une version locale de BTP permet de fusionner des valeurs dans les domaines d'instances binaires quelconques. Des expérimentations sur des instances benchmarks démontrent la diminution significative de la taille de l'instance pour certaines classes de problèmes. Nous montrons que cette fusion peut être gén éralisée aux instances ayant des contraintes d'arité quelconque et nous étudions les liens avec la résolution dans SAT. Une version orientée nous permet ensuite d'étendre la classe polynomiale BTP précédemment définie pour les CSP binaires. Ce papier est un résume de l'article M. C. Cooper, A. El Mouelhi, C. Terrioux et B. Zanuttini. On Broken Triangle In Proceedings of CP, LNCS 8656, 9-24, 2014.