Le CRIL en bref

présentation

Le Centre de Recherche en Informatique de Lens (CRIL UMR 8188) est un laboratoire de l’Université d’Artois et du CNRS qui regroupe plus de cinquante membres : chercheurs, enseignants-chercheurs, doctorants et personnels administratifs et techniques.

En savoir

Recherches en intelligence artificielle et applications

mots clés du CRIL

Actualités

Invité(s) Visite de Takehide Soh (Kobe, Japon)

Takehide Soh, de l’université de Kobe, Japon, sera en visite au CRIL les 12 et 13 janvier 2016.

Takehide Soh travaille sur la résolution de problèmes à base de contraintes par traduction à SAT.

Il est l’auteur des outils Scarab et Diet-Sugar.

Séminaire On Anti-Subsumptive Knowledge Enforcement

Jean-Marie Lagniez (Université d’Artois)

The anti-subsumptive enforcement of a clause δ in a set of clauses ∆ consists in extracting one cardinality-maximal satisfiable subset ∆0 of ∆ ∪ {δ} that contains δ but that does not strictly subsume δ. In this paper, the computational issues of this problem are investigated in the Boolean framework. Especially, the minimal change policy that requires a minimal number of clauses to be dropped from ∆ can lead to an exponential computational blow-up. Indeed, a direct and natural approach to anti-subsumptive enforcement requires the computation of all inclusion-maximal subsets of ∆ ∪ {δ} that, at the same time, contain δ and are satisfiable with ¬δj where δj is some strict sub-clause of δ. On the contrary, we propose a method that avoids the computation of this possibly exponential number of subsets of clauses. Interestingly, it requires only one single call to a Partial-Max-SAT procedure and appears tractable in many realistic situations, even for very large ∆. Moreover, the approach is easily extended to take into account a preference pre-ordering between formulas and lay the foundations for the practical enumeration of all optimal solutions to the problem of making δ subsumption-free in ∆ under a minimal change policy.

En savoir

Soutenance de thèse de Nebras Gharbi - Compression et parallélisation en CSP

Le 4 décembre 2015, à 14h, salle des thèses de la faculté Jean Perrin

Résumé :

La programmation par contraintes est un cadre puissant utilisé pour modéliser et résoudre des problèmes combinatoires, employant des techniques d’intelligence artificielle, de la recherche opérationnelle, de théorie des graphes,…, etc. L’idée de base de la programmation par contraintes est que l’utilisateur exprime ses contraintes et qu’un solveur de contraintes cherche une ou plusieurs solutions.

Les problèmes de satisfaction de contraintes (CSP), sont au cœur de la programmation par contraintes. Ce sont des problèmes de décision où nous recherchons des états ou des objets satisfaisant un certain nombre de contraintes ou de critères. Ces problèmes de décision renvoient vrai, si le problème admet une solution, faux, sinon. Les problèmes de satisfaction de contraintes sont le sujet de recherche intense tant en recherche opérationnelle qu’en intelligence artificielle. Beaucoup de CSPs exigent la combinaison d’heuristiques et de méthodes d’inférences combinatoires pour les résoudre dans un temps raisonnable.

Avec l’amélioration des ordinateurs, la résolution de plus grands problèmes devient plus facile. Bien qu’il y ait plus de capacités offertes par la nouvelle génération de machines, les problèmes industriels deviennent de plus en plus grand ce qui implique un espace énorme pour les stocker et aussi plus de temps pour les résoudre.

Cette thèse s’articule autour des techniques d’optimisation de la résolution des CSPs en raisonnant sur plusieurs axes.

Dans la première partie, nous traitons la compression des contraintes table. Nous proposons deux méthodes différentes pour la compression des contraintes de table. Les deux approches sont basées sur la recherche des motifs fréquents pour éviter la redondance. Cependant, la façon de définir un motif, la détection des motifs fréquents et la nouvelle représentation compacte diffère significativement. Nous présentons pour chacune des approches un algorithme de filtrage.

La seconde partie est consacrée à une autre façon d’optimiser la résolution de CSP qui est l’utilisation d’une architecture parallèle. Nous proposons une méthode où nous utilisons une architecture parallèle pour améliorer le processus de résolution en établissant des cohérences parallèles. En fait, les esclaves envoient à leur maître le résultat obtenu après avoir établi la cohérence partielle en tant que nouveaux faits. Le maître, à son tour essaye de profiter d’eux en enlevant les valeurs correspondantes.

En savoir

Séminaire Embarrassingly Parallel Search

Jean-Charles Régin (Sophia-Antipolis)

We propose the Embarrassingly Parallel Search, a simple and efficient method for solving constraint programming problems in parallel. We split the initial problem into a huge number of independent subproblems and solve them with available workers (i.e., cores of machines). The decomposition into subproblems is computed by selecting a subset of variables and by enumerating the combinations of values of these variables that are consistent w.r.t. the propagation mechanism of a CP Solver. The experiments on satisfaction problems and on optimization problems suggest that generating between thirty and one hundred subproblems per worker leads to a good scalability. We show that our method is quite competitive with the work stealing approach and able to solve some classical problems at the maximum capacity of the multi-core machines. Thanks to it, a user can parallelize the resolution of its problem without modifying the solver or writing any parallel source code and can easily replay the resolution of a problem.

En savoir

Séminaire NOOSBEE

Nextoo

Noosbee est une plateforme collaborative d’innovation, construite en co-design avec ses utilisateurs.

Actuellement en version beta, Noosbee permet de travailler à plusieurs sur une idée ou un concept. L’approfondissement se fait en discutant bien sur, mais aussi en collectant un maximum de sources d’inspirations provenant du web.

Au dela de la plateforme, c’est aussi la méthode suivie pour son développement qui est intéressante.

Noosbee est donc une belle histoire à raconter ! Mêlant rencontres, échanges et technologies.

C’est cette belle histoire que nous vous raconterons le 26 novembre prochain. Et qui sait, peut être nous aiderez vous à écrire la suite de l’histoire ?

En savoir