Améliorer les méthodes de décomposition pour le dénombrement exact de solutions

Philippe Jégou (1, 2) , Hanan Kanso (2) , Cyril Terrioux (1, 2)

1 LSIS - Laboratoire des Sciences de l'Information et des Systèmes
2 COALA - COntraintes, ALgorithmes et Applications

Leprobì eme du dénombrement de solutions d'une instance CSP, appelé #CSP, constitue unprobì eme ex-trêmement difficile qui possède de multiples applications en Intelligence Artificielle. S'il est le plus souvent résolu par des méthodes approchées, ici, nous nous focalisons sur le dénombrement exact. Nous montrons comment il est possible d'améliorer les méthodes basées sur les décompositions structurelles en améliorant la recherche d'une nouvelle solution, qui est uné etape essentielle, en particulier pour de telles méthodes. De plus, si les res-sources en temps ou en espace sont insuffisantes, nous montrons comment notre approche est capable de four-nir une borne inférieure du nombre de solutions. Des expérimentations sur des benchmarks CSP mettent en avant l'intérêt pratique de notre approche par rapport aux meilleures méthodes de la littérature. Ce papier est un résumé de [6]. Abstract The problem of counting solutions in CSP, called #CSP, is an extremely difficult problem that has many applications in Artificial Intelligence. This problem can be addressed by exact methods, but more classically it is solved by approximate methods. Here, we focus primarily on the exact counting. We show how it is possible to improve the methods based on structural decomposition by offering to enhance the search for a new solution which is a critical step for counting, particularly for such methods. Moreover, if the resources in time or in space are insufficient, we show that our approach is still able to provide a lower bound of the result. Experiments on CSP benchmarks show the practical advantage of our approach w.r.t. the best methods of the literature. This is a summary of [6].

Domaines: Informatique [cs]

Philippe Jégou, Hanan Kanso, Cyril Terrioux. Améliorer les méthodes de décomposition pour le dénombrement exact de solutions. Treizièmes Francophones de Programmation par Contraintes, JFPC 2017, Jun 2017, Montreuil-sur-Mer, France. ⟨hal-01785197⟩