loading...
 This Article 
   
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
19th IEEE International Conference on Tools with Artificial Intelligence - Vol.2 (ICTAI 2007)
Consistent Neighborhood for the Satisfiability Problem
Paris, France
October 29-October 31
ISBN: 0-7695-3015-X
Most of the local search methods for the satisfiability problem deal with a complete and inconsistent truth as- signment of the problem variables, and try to repair it by switching the truth value of some variables until reaching a model. We propose a new local search algorithm which works on partial truth assignments, but always consistent, instead of complete and inconsistent ones. This method at- tempts to extend a current partial assignment as a complete method would do. However, instead of backtracking when a conflict arises, it frees at least one variable involved in each falsified clause to restore consistency. Thus, the ex- plored neighborhood is always consistent whereas it is not the case for classical local search algorithms. Experimen- tal results show the competitiveness of our method towards other local search methods.
Citation:
Djamal Habet, Lionel Paris, Bela? Benhamou, "Consistent Neighborhood for the Satisfiability Problem," ictai, vol. 2, pp.497-501, 19th IEEE International Conference on Tools with Artificial Intelligence - Vol.2 (ICTAI 2007), 2007
Usage of this product signifies your acceptance of the Terms of Use.