SAT problems with chains of dependent
Steven Prestwich · 2002
This paper has two related themes. Firstly, arti+cial SAT problems are used to show that certain chains of variable dependency have a harmful e,ect on local search, sometimes causing 9 exponential scaling on intrinsically easy problems. Secondly, systematic, local and hybrid SAT algorithms are evaluated on Hamiltonian cycle problems, exposing weaknesses in all three. The 11 connection between the two themes is that some Hamiltonian cycle problems also cause local search to scale badly, indicating that pathological variable dependencies occur in more realistic 13 applications. More generally, the results highlight the need for alternative models and search algorithms, and new examples of both are described. 15 ? 2002 Published by Elsevier Science B.V.