Une étude empirique des heuristiques de branchement pour le problème MAX-SAT

Résumé : MOMS et Jeroslow-Wang sont deux des heuristiques les plus utilisées pour ordonner les variables dans les algorithmes traitant les problèmes SAT etMAXSAT. Toutefois, leurs comportements ne sont pas très bien compris dans le contexte du problème MAX-SAT. Dans ce papier, nous nous sommes intéressés à ces deux heuristiques ainsi qu'à l'heuristiqueDynamic- weighting pour la résolution du problème MAX-SAT. Nous montrons empiriquement que leurs comportements dans un algorithme de type Branch and Bound dépend de la borne supérieure initiale ainsi que de mécanismes spécifiques comme la propagation unitaire ou encore l'estimation de la borne inférieure. À partir de ces résultats, nous avons proposé une combinaison intuitive des heuristiques MOMS and Jeroslow-Wang qui fournit des performances intéressantes.
Type de document :
Communication dans un congrès
Deuxièmes Journées Francophones de Programmation par Contraintes (JFPC06), 2006, Deuxièmes Journées Francophones de Programmation par Contraintes (JFPC06), 2006
Liste complète des métadonnées

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

https://hal.inria.fr/inria-00085817
Contributeur : Laurent Henocque <>
Soumis le : vendredi 14 juillet 2006 - 16:10:41
Dernière modification le : mercredi 21 février 2018 - 15:48:03
Document(s) archivé(s) le : mardi 6 avril 2010 - 00:10:18

Fichier

Identifiants

  • HAL Id : inria-00085817, version 1

Collections

Citation

Frédéric Lardeux, Frédéric Saubion, Jin-Kao Hao. Une étude empirique des heuristiques de branchement pour le problème MAX-SAT. Deuxièmes Journées Francophones de Programmation par Contraintes (JFPC06), 2006, Deuxièmes Journées Francophones de Programmation par Contraintes (JFPC06), 2006. 〈inria-00085817〉

Partager

Métriques

Consultations de la notice

152

Téléchargements de fichiers

260