Skip to Main content Skip to Navigation
Conference papers

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.
Complete list of metadata

Cited literature [22 references]  Display  Hide  Download

https://hal.inria.fr/inria-00085817
Contributor : Laurent Henocque <>
Submitted on : Friday, July 14, 2006 - 4:10:41 PM
Last modification on : Thursday, November 26, 2020 - 10:30:09 AM
Long-term archiving on: : Tuesday, April 6, 2010 - 12:10:18 AM

File

Identifiers

  • 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). ⟨inria-00085817⟩

Share

Metrics

Record views

219

Files downloads

803