CRIL in short

présentation

Lens Computer Science Research Lab (CRIL UMR 8188) is a joint laboratory between Université d’Artois and CNRS, grouping together 50 members, including researchers, lecturers, PhD students, postdocs and administrative or technical staff.

Learn more

Artificial Intelligence Research and Applications

mots clés du CRIL

News (RSS)

PhD defense of Marwa Harzi - An optimization based framework for routing and scheduling activities in healthcare emergency departments

December the 17th, 2018,9AM, salle des thèses at Faculté Jean Perrin.

Résumé :

In this thesis, we focus on the routing and scheduling activities of patients in the Healthcare Emergency Department while involving optimization tools. We address three categories of research questions. The first category includes question about patient flow to the Emergency department. In this part we focuses on patient transportation problem derived from emergency medical services (EMS). Ambulance routing problem is a significant challenge. Bearing in mind that the travel cost of an EMS is a crucial feature since cost is vital in emergency situations. Hence, we aim to push forward the total travel cost performance of EMS by handling the ARP. In order to do so, we propose a cluster-first route-second algorithm based on the Petal algorithm and the particle swarm optimization approach. In order to study the performance of the proposed method, we test it in a set of instances and compared the results with state-of-art methods. The second category is associated to the patient flow in the Emergency Department. A mixed integer linear programming, a hybrid ILS/VND method, a genetic algorithm and a reactive algorithm are developed to solve this real patient scheduling problem. Approximate methods are alternatives to exact methods to quickly solve large instances taking into account a set of constraints. The reactive algorithm consist to schedule patients with consideration of perturbation. The third category of questions is a combination of two previous questions. It deals with routing and scheduling process of patients where we investigate the patient flow to and in the ED. A Decision Support System was set up to facilitate mutual interaction and cooperation between the optimization tools and the Decision Maker in the addressed case study.

Learn more

PhD defense of Imen Ouled Dlala - Declarative Approaches for Mining Frequent Itemsets over Transactional Databases

December the 17th, 2018, 2PM, salle des thèses at Faculté Jean Perrin.

Abstract:

La fouille de données est une étape primordiale du processus d’extraction de connaissances à partir des données. Elle a pour but d’analyser de grandes quantités de données afin de découvrir des connaissances. L’extraction des itemsets fréquents à partir d’une base de données transactionnelle est l’une des tâches principales de la fouille de données, qui consiste à identifier divers types de motifs afin de répondre aux besoins des utilisateurs ou des applications. Différentes approches d’extraction des itemsets fréquents ont été introduites dans la littérature et peuvent être scindées en deux catégories: spécialisées et déclaratives. Les travaux de cette thèse se situent dans la seconde catégorie d’approches. Les approches déclaratives basées sur SAT pour l’extraction des itemsets fréquents se distinguent par leurs flexibilités et permettent d’extraire divers types de motifs particuliers par ajout de contraintes. Toutefois, ces approches sont inefficaces pour traiter les grandes bases de données transactionnelles dû principalement à la taille des encodages et au nombre élevé des itemsets à extraire. Dans notre première contribution, nous montrons les limites des approches d’énumération de modèles à base des solveurs CDCL pour ces encodages et proposons une solution alternative de type DPLL plus appropriée. Dans la deuxième contribution, et pour pallier le problème de la taille de l’encodage, nous proposons d’utiliser une technique de partitionnement. Cela permet de ramener l’énumération de tous les modèles en l’énumération de modèles de sous-problèmes de taille réduite. Cette approche permet un passage à l’échelle et se montre plus performante que les approches basées sur la programmation par contraintes. Nous étendons également ce cadre pour considérer la résolution en parallèle des sous-problèmes générés. Notre troisième contribution est une nouvelle approche d’extraction des motifs fréquents maximaux, appelé SATMax, utilisant de manière originale les solveurs SAT pour énumérer efficacement tous les itemsets maximaux d’une base de données transactionnelle. L’évaluation expérimentale sur différents jeux de données montre l’efficacité de cette approche par rapport à quelques algorithmes spécialisés et déclaratifs de l’état de l’art. La dernière contribution de cette thèse porte sur l’énumération des motifs fréquents à partir des données incertaines. Nous étendons les approches déclaratives basées sur les contraintes. Nous montrons que la contrainte de support (expected support) donne lieu à une contrainte non linéaire. Nous introduisons par la suite une approche incrémentale en la taille des itemsets associée et une relaxation de la contrainte d’expected support exprimée par une contrainte linéaire permettant d’accélérer l’énumération.

Learn more

PhD defense of Yacine Izza - Informatique ubiquitaire : techniques du curage d'informations perverties

December the 7th, 2018, 10h30, salle des thèses at Faculté Jean Perrin.

Abstract :

This thesis studies a possible approach of artificial intelligence for detecting and filtering inconsistent information in knowledge bases of intelligent objects and components in ubiquitous computing. This approach is addressed from a practical point of view in the SAT framework;it is about implementing a techniques of filtering inconsistencies in contradictory bases. Several contributions are made in this thesis. Firstly, we have worked on the extraction of one maximal information set that must be satisfiable with multiple assumptive contexts. We have proposed an incremental approach for computing such a set (AC-MSS).
Secondly, we were interested about the enumeration of maximal satisfiable sets (MSS) or
their complementary minimal correction sets (MCS) of an unsatisfiable CNF instance.
In this contribution, a technique is introduced that boosts the currently most efficient practical approaches to enumerate MCS. It implements a model rotation paradigm that allows the set of MCS to be computed in an heuristically efficient way. Finally, we have studied a notion of consensus to reconcile several sources of information. This form of consensus can obey various preference criteria, including maximality one. We have then developed an incremental algorithm for computing one maximal consensus with respect to set-theoretical inclusion. We have also introduced and studied the concept of admissible consensus that refines the initial concept of consensus.

Learn more

HDR defense of Saïd Jabbour

December the 6th, 2018, 2PM, salle des thèses at Faculté Jean Perrin.

Abstract:

Mes travaux de recherche sont à la frontière de plusieurs domaines incluant l’Intelligence Artificielle (IA) symbolique, la fouille de données, les graphes et les systèmes d’information. Ils se répartissent autour des mots clés suivants : raisonnement par contraintes, représentation des connaissances, modélisation des raisonnements, fouille de motifs sous contraintes, clustering, détection de communautés, compression de données et composition de services web.

La première partie de mon HDR donne un aperçu de mes contributions algorithmiques au problème de la satisfiabilité propositionnelle incluant l’apprentissage de clauses, les solveurs SAT parallèles de type portfolio, l’énumération de modèles et d’impliquants premiers et les transformations de contraintes de cardinalité (conditionnelles) sous forme normale conjonctive.

La seconde partie aborde les problématiques de la fouille de données et du clustering. Mes contributions portent sur les approches déclaratives pour différentes tâches de fouille de données : la fouille des itemsets fréquents et de leurs diverses formes condensées, l’extraction de règles d’association et de ses nombreuses variantes, la fouille de motifs séquentiels, l’énumération des motifs Top-k modulo une relation de préférence, la fouille de motifs sous incertitude, méthodes parallèles par décomposition et le clustering symbolique de formules propositionnelles. Pour mettre en lumière les fertilisations croisées entre l’IA symbolique et la fouille de données, je montre d’une part comment le concept de symétrie largement exploré en SAT/CP est étendu à la fouille des motifs ensemblistes, et d’autre part, comment la fouille de données peut être exploitée pour compresser des formules booléennes et des contraintes CSP exprimées en extension.

La troisième partie traite de mes contributions à la détection de communautés et à la compression de grands graphes, en exploitant les contraintes pseudo-booléennes et la logique propositionnelle.

La quatrième partie se focalise sur le raisonnement en présence d’incohérences et la théorie de l’argumentation. Je présente différentes méthodes pour la quantification de conflits dans les bases de connaissances et également pour le raisonnement en présence d’incohérences et d’incertitude dans les ontologies.

La dernière partie est consacrée à mes contributions à la composition des services web, en proposant diverses modélisations en logique de ce problème.

Ce travail se termine en évoquant mes projets de recherche actuels et futurs.

Learn more

PhD defense of Nizar Mhadhbi

December the 3rd, 2018, 2PM, salle des thèses at Faculté Jean Perrin.

Abstract :

This thesis focuses on the field of complex networks analysis. A complex network can be
defined as a system of interacting entities often represented by a graph. Two problems related
to the study of large networks are addressed in this thesis. Our first goal is to extract relevant knowledge
in graphs by identifying community structures. The second problem related
to big graphs summarization. The first problem is known as community detection. Indeed, the
existence of more dense connected subparts than others is one of the main characteristics of
complex graphs. These subparts are called communities. These communities may be overlapping or
disjoint and may have several meanings depending on the type of the input graph. The
second problem studied is about graph compression : it consists on discovering hidden graph
structures and exploiting them to compactly summarize large graphs.

In the first contribution, we introduce a new community concept called k-linked community, allowing us
to characterize node/edge centered k-linked community with bounded diameter. Such community admits
a node or an edge with a distance at most k/2 from any other node
of that community. First, we show how the problem of detecting node/edge centered k-linked
overlapping communities can be expressed as a Partial Max-SAT optimization problem. Then,
we provide a second method to refine our SAT-based model by incorporating preferences in order to
select more efficiently the centroid for each community in the input graph. In the second
contribution, we propose two seed-expanding models for overlapping community detection in
large complex networks. The first model consists of a relaxation of the clique structure. This
relaxation gives rise to a new notion of community named k-clique-star. The second model
aims to extend maximal cliques in order to identify overlapping communities in networks. In
the last contribution, we propose a novel approach to summaize big data graphs. First, we show
that some special graph classes can be represented effeciently as Pseudo Boolean constraints
(PB). Then, we propose new several graph classes expressed as PB constraints. Finally, we
present a novel PB constraints based algorithm to summarize big graphs.
All the proposed methods are efficient and very competitive w.r.t. state-of-the-art approaches in the
literature.

Learn more