Exploitation des symétries dans les formules booléennes quantifiées - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Communication Dans Un Congrès Année : 2006

Exploitation des symétries dans les formules booléennes quantifiées

Said Jabbour
Lakhdar Saïs

Résumé

De nombreuses tâches et problèmes combinatoires exhibent des symétries. La résolution de tels problèmes conduit à répéter inlassablement l'étude de situations ou de sousproblèmes équivalents. Depuis plusieurs années, l'exploitation des symétries a permis une réduction significative de l'espace de recherche et la résolution de problèmes ouverts jusqu'alors. Ce paradigme important a été étudié de manière extensive dans de nombreux domaines, comme les problèmes de satisfaction de contraintes (CSP) ou la satisfiabilité de formules booléennes (SAT). L'approche consistant à rajouter des contraintes (symmetry breaking predicates en anglais) est l'une des techniques les plus utilisées pour casser les symétries. Après avoir montré pourquoi il est difficile d'étendre cette approche aux formules booléennes quantifiées, nous montrons comment générer une nouvelle formule équivalente à la formule de départ, mais ne contenant pas de symétries. L'évaluation expérimentale menée sur un des meilleurs solveurs QBF actuels montre des résultats très convaincants sur une grande variété d'instances QBF structurées.
Fichier principal
Vignette du fichier
27.pdf (215.14 Ko) Télécharger le fichier
Loading...

Dates et versions

inria-00085795 , version 1 (14-07-2006)

Identifiants

  • HAL Id : inria-00085795 , version 1

Citer

Gilles Audemard, Said Jabbour, Lakhdar Saïs. Exploitation des symétries dans les formules booléennes quantifiées. Deuxièmes Journées Francophones de Programmation par Contraintes (JFPC06), 2006, Nîmes - Ecole des Mines d'Alès / France. ⟨inria-00085795⟩
41 Consultations
73 Téléchargements

Partager

Gmail Facebook X LinkedIn More