Minimum Satisfiability and its Applications

Résumé : Nous proposons, dans cet article, de placer le problème de satisfiabilité minimale (MinSAT) sur le devant de la scène. Pour cela, un algorithme efficace de type {em branch-and-bound} pour résoudre le problème MinSAT partiel avec pondération est introduit, permettant du même coup une évaluation empirique de cet algorithme pour les cas Min-3SAT aléatoires, MaxClique et pour les problèmes d'enchères combinatoires. Les techniques employées pour résoudre MinSAT se démarquent de celles utilisées pour le problème de satisfiabilité maximale (MaxSAT), qui a lui été très étudié. Nos résultats démontrent de manière empirique que, notamment sur les problèmes d'enchères combinatoires, une réduction du problème initial à MinSAT peut être plus intéressante qu'une réduction à MaxSAT, ou même que l'utilisation de méthodes dédiées. Nous étendons par ailleurs ce travail en montrant une corrélation entre le nombre minimal et le nombre maximal de clauses satisfaites dans une instance SAT aléatoire donnée.
Type de document :
Communication dans un congrès
International Joint Conference on Artificial Intelligence, Jul 2011, Barcelona, Spain. 2011
Liste complète des métadonnées

https://hal.inria.fr/hal-00642014
Contributeur : Laurent Simon <>
Soumis le : jeudi 17 novembre 2011 - 10:09:15
Dernière modification le : mardi 24 avril 2018 - 13:39:09

Identifiants

  • HAL Id : hal-00642014, version 1

Collections

Citation

Laurent Simon, Chu Min Li, Felip Manya, Zhu Zhu. Minimum Satisfiability and its Applications. International Joint Conference on Artificial Intelligence, Jul 2011, Barcelona, Spain. 2011. 〈hal-00642014〉

Partager

Métriques

Consultations de la notice

145