Assas Recherche | Hypergraphes partiels de largeur bornée, décompositions arborescentes et contraintes globales

Hypergraphes partiels de largeur bornée, décompositions arborescentes et contraintes globales (Document en Français)

Accès au(x) document(s)

Accéder au(x) document(s) :

http://www.theses.fr/2023AIXM0404/abes

Ce document est protégé en vertu du Code de la Propriété Intellectuelle.

Modalités de diffusion de la thèse :

Thèse consultable sur internet, en texte intégral.

Informations sur les contributeurs

Auteur : Adrar Nabil

Adrar, Nabil

Nom

Adrar

Prénom

Nabil

Nationalité

Français

Date de soutenance : 23-11-2023

Directeur(s) de thèse : Jégou Philippe

Jégou, Philippe

Nom

Jégou

Prénom

Philippe

- Terrioux Cyril

Terrioux, Cyril

Nom

Terrioux

Prénom

Cyril

Etablissement de soutenance : Aix-Marseille

Aix-Marseille

Nom

Aix-Marseille

Laboratoire : Laboratoire d’Informatique et Systèmes (Marseille ; La Garde, Var ; 2018-….)

Laboratoire d’Informatique et Systèmes (Marseille ; La Garde, Var ; 2018-….)

Nom

Laboratoire d’Informatique et Systèmes (Marseille ; La Garde, Var ; 2018-….)

Ecole doctorale : École Doctorale Mathématiques et Informatique de Marseille (Marseille)

École Doctorale Mathématiques et Informatique de Marseille (Marseille)

Nom

École Doctorale Mathématiques et Informatique de Marseille (Marseille)

Informations générales

Discipline : Informatique
Classification : Informatique

Mots-clés libres : Programmation par contraintes, Problème de satisfaction de contraintes, Contraintes globales, Graphes, Hypergraphes, Décomposition arborescente
Mots-clés :

Informatique
Hypergraphes
Programmation par contraintes

Résumé : Cette thèse s'inscrit dans le cadre de la programmation par contraintes, et porte sur l'étude et le traitement par décomposition structurelle des réseaux de contraintes au sens des problèmes de satisfaction de contraintes (CSP). Dans la première partie, nous traitons le calcul d'hypergraphes partiels dont la largeur (au sens de la décomposition arborescente) est bornée par une constante entière .Il s'agit, étant donné un hypergraphe H' = (V, E') et un entier k, de trouver un hypergraphe partiel H' = (V, E') (E' ? E) tel que la largeur (au sens de la emph{treewidth}) de sa 2-section ou emph{graphe primal} est au plus k - 1. Cette question originellement issue d'une approche de filtrage de CSP basée sur la structure trouve également un intérêt dans le cadre plus général des modèles graphiques (réseaux bayésiens, réseaux de fonctions de coût, champs aléatoires de Markov, etc). Nous proposons un algorithme de complexité polynomiale sans garantie d'optimalité, mais qui permet néanmoins de calculer l'optimum dans certains cas (dont celui des hypergraphes alpha-acycliques). La proximité fréquente de l'optimum est par ailleurs validée par les évaluations expérimentales que nous avons menées. Il s'avère cependant que son exploitation pour l'approche de filtrage qui avait motivé cette étude est beaucoup moins probante sur un plan expérimental. En deuxième partie, nous proposons une nouvelle approche de calcul de décompositions arborescentes d'hypergraphes. Cette approche fait évoluer, en cours de calcul, une décomposition arborescente en ajoutant progressivement les hyperarêtes de l'hypergraphe considéré, au moyen d'une heuristique de choix d'hyperarête, jusqu'à obtenir une décomposition arborescente finale globale de l'hypergrahe en entrée. Cette approche recèle potentiellement deux vertus. Tout d'abord, elle permet la prise en compte de nouvelles hyperarêtes au sein de la décomposition arborescente associée sans devoir recalculer à nouveau une nouvelle décomposition arborescente. En outre, cette approche permet potentiellement de mieux gérer certains paramètres qui sont cruciaux pour la résolution de CSP, comme notamment la taille des séparateurs entre clusters, ce qui constitue un réel avantage par rapport à des approches heuristiques telles que des méthodes de l'état de l'art comme emph{Min-Fill} ou emph{MCS}. Cette nouvelle approche est évaluée expérimentalement au regard des paramètres utiles pour son exploitation pour la résolution de CSPs. La troisième partie de ce manuscrit porte sur la prise en compte des contraintes globales par des approches de résolution fondées sur la décomposition. S'il est maintenant admis que les contraintes globales constituent un outil quasiment incontournable dans la cadre de la modélisation puis de la résolution de problèmes en termes de contraintes, leur traitement via des approches fondées sur la décomposition constitue un réel défi pour la communauté. En effet, leur intégration dans les réseaux de contraintes engendre généralement une dégradation rédhibitoire de la largeur et donc des garanties en termes de bornes de complexité par les méthodes de résolution par décomposition. Pour contourner cette difficulté, nous étudions cette question par une approche fondée sur la réécriture de ces contraintes globales de sorte à conserver leur sémantique, tout en limitant l'accroissement de la larguer induite. Cette approche devrait rendre admissible des traitements par décomposition. Enfin, nous fournissons une évaluation expérimentale de cette nouvelle approche

Informations techniques

Type de contenu : Text
Format : PDF

Informations complémentaires

Entrepôt d'origine :

STAR : dépôt national des thèses électroniques françaises

Identifiant : 2023AIXM0404
Type de ressource : Thèse

Fiche descriptive