mots clés axe AIC

Cette dernière décennie, des avancées spectaculaires ont été obtenues dans les domaines de recherche croisés que constituent la résolution de problèmes de satisfaction de contraintes à domaines discrets (CSP), la satisfaisabilité propositionnelle (SAT), la représentation et le raisonnement sur le temps et l’espace et les extensions de ces différents problèmes. La taille des instances de ces problèmes combinatoires qui sont à présent résolues a souvent crû de plusieurs ordres de grandeur tandis que leurs champs d’application se sont multipliés.

L’activité de l’axe thématique « Algorithmes pour l’Inférences et Contraintes » (AIC) du CRIL relève de ces domaines de recherche connexes et de leur fertilisation croisée. Elle vise à améliorer les techniques au niveau conceptuel et à les implanter au sein de logiciels-solveurs innovants (le plus souvent, sous le format de logiciels libres).

Ces recherches sont conduites par un groupe à fort rayonnement international : au cours de la période écoulée, le CRIL a produit différents logiciels qui ont été primés lors des compétitions internationales de solveurs et a affiché une présence majeure notamment dans les congrès les plus sélectifs et les plus prestigieux du domaine.

La taille et la difficulté sans cesse croissantes des instances de ces problèmes combinatoires qui peuvent maintenant être résolues par les méthodes systématiques et heuristiques ouvrent de nouveaux horizons applicatifs. Ces méthodes permettent aujourd’hui de résoudre des instances difficiles qui peuvent parfois comprendre plusieurs centaines de milliers de variables et plusieurs millions de contraintes, exprimées dans des cadres de types booléen ou discret. Ce changement d’échelle rend possible la résolution d’un éventail toujours croissant d’applications qui va de questions d’ordonnancement, à des problèmes d’allocation de fréquences, en passant par la conception de circuits VLSI, par la vérification et la validation de bases de connaissances, par différentes questions de bio-informatique, de fouille de données, de démonstration automatique et d’implantation de raisonnements non monotones.

Au sein de l’axe AIC, le CRIL s’intéresse donc à principalement aux classes importantes de problèmes combinatoires que voici. SAT (une formule propositionnelle donnée sous forme normale conjonctive admet-elle une valuation qui la rende vraie ?). Les CSP discrets (un réseau de contraintes à domaines discrets donné possède-t-il une solution ?). Le formalisme qualitatif pour le temps et l’espace (un réseau de contraintes qualitatives (RCQ) est-il cohérent ?). Un RCQ permet de spécifier qualitativement des configurations d’entités temporelles ou spatiales en définissant les positions relatives possibles entre les différentes entités à l’aide de relations souvent complexes issues du formalisme considéré.

SAT et CSP sont deux problèmes de décision NP-complets. Dans le cas général, décider de la cohérence d’un réseau de contraintes qualitatives est aussi NP-complet. Il existe des réductions polynomiales entre ceux-ci. Les recherches conduites au CRIL se concentrent donc non seulement sur les questions algorithmiques et conceptuelles propres à chacun de ces domaines, mais se focalisent aussi sur leur fertilisation croisée.

La résolution de ces problèmes combinatoires constitue aussi un sujet d’études transverse à de nombreux domaines de l’informatique qui nous concernent donc au premier chef : théorie de la complexité, intelligence artificielle, démonstration automatique et recherche opérationnelle, principalement.

Du point de vue de la théorie de la complexité, les problèmes de décision ou d’optimisation associés sont typiquement intraitables. L’existence d’algorithmes déterministes de complexitétemporelle polynomiale est fort peu vraisemblable. Ce verrou majeur rend primordial le développement d’approches alternatives dont l’objectif est de permettre de pousser aussi loin que possible la classe des instances traitables « en pratique ». La résolution efficace d’applications réelles dépend fortement de ces développements.

Au sein de l’axe thématique AIC, le CRIL s’intéresse donc à différentes questions inter-corrélées qui vont du codage à la résolution en passant par l’extension de cadres existants et l’utilisation de techniques issues de SAT, CSP et RCQ pour résoudre des problèmes qui gravitent autour d’eux et qui permettent d’en élargir les champs d’application.

Rapport d’activités  

Membres impliqués dans l’axe

Thèses en cours