Résolution exacte de MinSAT

Résumé : MinSAT est le problème consistant à trouver une affectation qui minimise le nombre de clauses satisfaites dans une formule CNF. Nous présentons une approche originale pour résoudre MinSAT de façon exacte, qui repose sur le codage MaxSAT et les solveurs MaxSAT. Notre étude empirique fournit la preuve que, en l'absence de spécifiques solveurs exacts pour MinSAT, l'approche générique proposée dans ce papier est compétitive.
Type de document :
Communication dans un congrès
JFPC 2010 - Sixièmes Journées Francophones de Programmation par Contraintes, Jun 2010, Caen, France. pp.217-226, 2010
Liste complète des métadonnées

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

https://hal.inria.fr/inria-00520378
Contributeur : Christophe Lecoutre <>
Soumis le : jeudi 23 septembre 2010 - 09:38:50
Dernière modification le : jeudi 23 septembre 2010 - 10:47:18
Document(s) archivé(s) le : jeudi 30 juin 2011 - 13:30:09

Fichier

quan2.pdf
Accord explicite pour ce dépôt

Identifiants

  • HAL Id : inria-00520378, version 1

Collections

Citation

Chu Min Li, Felip Manya, Zhe Quan, Zhu Zhu. Résolution exacte de MinSAT. JFPC 2010 - Sixièmes Journées Francophones de Programmation par Contraintes, Jun 2010, Caen, France. pp.217-226, 2010. 〈inria-00520378〉

Partager

Métriques

Consultations de la notice

82

Téléchargements de fichiers

192