Importance de la sémantique dans le codage CNF de contraintes de cardinalité : application au diagnostic de SED

Résumé : Le codage d'un problème a un impact énorme sur le temps de calcul en SAT : un solveur SAT peut résoudre très facilement un problème codé d'une certaine manière, et éprouver des difficultés pour le même problème codé d'une autre manière. Pire, un codage peut favoriser le temps de calcul d'un solveur, et se montrer au contraire inadapté pour un autre solveur. Dans cet article, nous nous concentrons sur l'expression en CNF de contraintes de cardinalité : étant donné un ensemble V de variables propositionelles, étant donnée une valeur entière k, exactement k variables de V doivent être évaluées à vrai. Nous proposons de nouvelles manières de modéliser ces contraintes en cherchant à grouper les variables dont la sémantique est proche. Nous étudions ces codages sur des problèmes de diagnostic de système à événements discrets (SED). Des problèmes jusqu'ici insolubles peuvent être à présent résolus à la fois par des procédures systématiques ou stochastiques. Les résultats mettent également en lumière l'existence d'un codage qui convienne aux deux types d'algorithme
Type de document :
Communication dans un congrès
Gilles Trombettoni. JFPC 2008- Quatrièmes Journées Francophones de Programmation par Contraintes, Jun 2008, Nantes, France. pp.31-40, 2008
Liste complète des métadonnées

Littérature citée [12 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00290714
Contributeur : Service Ist Inria Sophia Antipolis-Méditerranée / I3s <>
Soumis le : jeudi 26 juin 2008 - 11:38:59
Dernière modification le : vendredi 11 juillet 2008 - 18:22:17
Document(s) archivé(s) le : vendredi 28 mai 2010 - 20:19:30

Fichier

pages-031-40-article23.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00290714, version 1

Collections

Citation

A. Anbulagan, Alban Grastien. Importance de la sémantique dans le codage CNF de contraintes de cardinalité : application au diagnostic de SED. Gilles Trombettoni. JFPC 2008- Quatrièmes Journées Francophones de Programmation par Contraintes, Jun 2008, Nantes, France. pp.31-40, 2008. 〈inria-00290714〉

Partager

Métriques

Consultations de la notice

68

Téléchargements de fichiers

47