Skip to Main content Skip to Navigation
Conference papers

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
Document type :
Conference papers
Complete list of metadata

Cited literature [12 references]  Display  Hide  Download

https://hal.inria.fr/inria-00290714
Contributor : Service Ist Inria Sophia Antipolis-Méditerranée / I3s <>
Submitted on : Thursday, June 26, 2008 - 11:38:59 AM
Last modification on : Friday, July 11, 2008 - 6:22:17 PM
Long-term archiving on: : Friday, May 28, 2010 - 8:19:30 PM

File

pages-031-40-article23.pdf
Files produced by the author(s)

Identifiers

  • 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. JFPC 2008- Quatrièmes Journées Francophones de Programmation par Contraintes, LINA - Université de Nantes - Ecole des Mines de Nantes, Jun 2008, Nantes, France. pp.31-40. ⟨inria-00290714⟩

Share

Metrics

Record views

85

Files downloads

65