<  Back to the Polytechnique Montréal portal

Preuves de non réalisabilité et filtrage de domaines pour les problèmes de satisfaction de contraintes : application à la confection d'horaires

Sandrine Paroz

PhD thesis (2009)

[img]
Preview
Published Version
Terms of Use: All rights reserved.
Download (3MB)
Cite this document: Paroz, S. (2009). Preuves de non réalisabilité et filtrage de domaines pour les problèmes de satisfaction de contraintes : application à la confection d'horaires (PhD thesis, École Polytechnique de Montréal). Retrieved from https://publications.polymtl.ca/8281/
Show abstract Hide abstract

Abstract

Contexte global -- Objectifs de cette thèse -- Organisation de la thèse -- Notions préliminaires -- Problèmes de coloration de graphes -- Les problèmes de sastisfaction de contraintes -- Problème SAT de satisfaisabilité booléenne -- Programmation par contraintes -- Sous-ensembles incohérents irréductibles -- Revue de la littérature concernant l'extraction d'IIS dans les CSP, la résolution du problème SAT et l'extraction d'IIS pour le problème SAT -- Détection de sous-ensembles incohérents dans des CSP -- Le problème SAT et sa résolution -- Utilisation d'heuristiques pour trouver des sous-ensembles incohérents minimaux pour le problème SAT -- Algorithmes de détection d'IIS -- Autres procédures -- Algorithme tabou pour Max WSAT -- Détails d'implémentation -- Résultats expérimentaux -- Revue de la littérature concernant le filtrage de contraintes globales de CSP -- Algorithme de filtrage pour la contrainte AllDifferent -- Algorithme de filtrage de domaines pour la contrainte SomeDifferent -- Autres travaux concernant le filtrage de contraintes globales -- Algorithme de filtrage pour la contrainte SomeDifferent -- Description de l'algorithme de filtrage -- Résultats expérimentaux -- Revue de la littérature concernant le problème de confection d'horaires pour le personnel navigant aérien -- Les méthodes de résolution du PBS -- Détection de sous-ensembles incohérents minimaux dans le problème de confection d'horaires pour le personnel navigant aérien -- Algorithmes de détection de sous-ensembles incohérents minimaux -- Algorithme tabou -- Algorithme exact de vérification des sous-problèmes incohérents -- Résultats expérimentaux -- Méthodes de recherche locale.

Uncontrolled Keywords

Contraintes (Intelligence artificielle) -- Mathématiques; Horaires de travail -- Modèles mathématiques

Open Access document in PolyPublie
Additional Information: Le fichier PDF de ce document a été produit par Bibliothèque et Archives Canada selon les termes du programme Thèses Canada https://canada.on.worldcat.org/oclc/646564852
Department: Département de mathématiques et de génie industriel
Academic/Research Directors: Alain Hertz and Philippe Galinier
Date Deposited: 04 Aug 2021 11:04
Last Modified: 21 Sep 2021 10:34
PolyPublie URL: https://publications.polymtl.ca/8281/

Statistics

Total downloads

Downloads per month in the last year

Origin of downloads

Repository Staff Only