COALA

COntraintes, ALgorithmes et Applications

Responsable : Philippe JEGOU

Intérêts scientifiques

Dans la continuité des travaux développés au sein de l’équipe INCA, la nouvelle équipe COALA positionne son activité principalement dans l’algorithmique associée à la résolution des problèmes de satisfaction de contraintes (SAT et CSP principalement). Cette activité, historiquement liée aux fondements de l’Intelligence Articifielle, mais également à ceux de la Programmation par Contraintes, a pour objectif l’étude des systèmes à base de contraintes, la mise en évidence de fragments polynomiaux (classes polynomiales), l’élaboration de méthodes et d’algorithmes pour la résolution de problèmes combinatoires, et la conception de solveurs efficaces en pratique. Ces travaux, qui vont naturellement de pair avec une mise en application sur des problèmes réels, portent principalement sur la résolution du problème général de la satisfiabilité (SAT) et des problèmes de satisfaction de contraintes (au sens CSP à domaines finis et qui est une extension de SAT). Nous nous intéressons également à leurs extensions à l’optimisation, avec Max-SAT (qui consiste à maximiser le nombre de clauses satisfiables) d’une part, et les CSP Pondérés ou WCSP (pondération sur les contraintes) d’autre part, ainsi qu’aux questions de dénombrement (#SAT et #CSP). Afin de bien cerner la dfifficulté des problèmes abordés, il est essentiel de rappeler ici certains résultats de complexité : SAT et CSP sont NP complets, Max-SAT et WCSP NP-difficiles tandis que #SAT et #CSP sont #P-complets. À l’origine, cette activité avait pour objectif de doter les systèmes de raisonnement de l’Intelligence Artificielle d’outils de résolution efficaces à la fois en théorie et en pratique. Ils ont désormais des retombées bien au-delà dans de nombreux domaines d’applications, notamment par la place prépondérante prise depuis plusieurs années maintenant par la Programmation par Contraintes. Si le thème central des recherches développées ici concerne l’algorithmique des problèmes de satisfaction de contraintes, on peut cependant évoquer deux autres domaines abordés. D’une part la Théorie (Algorithmique) des Graphes dans la mesure où nos travaux s’appuient très souvent sur les propriétés graphiques associées à l’expression des CSP sous la forme de “réseaux de contraintes” (ce sont des (hyper)graphes étiquetés). D’autre part, la Théorie de la Complexité au niveau de la mise en évidence de nouvelles classes polynomiales, c’est-à-dire d’ensembles infinis d’instances dont la reconnaissance et la résolution admettent des algorithmes de complexité polynomiale.

Nos travaux se déclinent ainsi en plusieurs axes et activités et qui constituent les thèmes de recherches qui seront abordés lors du prochain contrat :
– Classes polynomiales et méthodes de résolution pour CSP, WCSP et #CSP
– Méthodes complètes et incomplètes pour SAT et ses extensions à l’optimisation
– Problèmes connexes et applications
– Conception de Solveurs

Enfin, pour bien appréhender nos axes de recherche, en fin de document, nous proposons une sélection despublications les plus importantes et évocatrices de ces axes de recherche

Voir aussi dans «Calcul»

ACRO CANA DALGO
Tutelles