Cooperative Approach for the Satisfiability Problem

Michel Vasquez (1) , Djamal Habet (2)

1 LGI2P - Laboratoire de Génie Informatique et Ingénierie de Production
2 LSIS - Laboratoire des Sciences de l'Information et des Systèmes

We present a cooperation model between complete and incomplete algorithms to solve SAT problem. The involved algorithms are an exhaustive search; Satz and a local search; Walksat and its variants. An important feature of this hybridization is the exploitation, during the local search, of the variable dependencies (implications and equivalencies).

Mots clés: Satisfiability; Local Search

Domaines: Recherche opérationnelle [math.OC]; Intelligence artificielle [cs.AI]

Michel Vasquez, Djamal Habet. Cooperative Approach for the Satisfiability Problem. 17th Triennial Conference of the International Federation of Operational Research Societies IFORS, Jul 2005, Honolulu Hawaï, United States. ⟨hal-00354776⟩