@inproceedings{283f852f6b1244a5beb70778b970a032,
title = "Variable dependency in local search: Prevention is better than cure",
abstract = "Local search achieves good results on a variety of SAT problems and often scales up better than backtrack search. But despite recent advances in local search heuristics it has failed to solve some structured problems, while backtrack search has advanced greatly on such problems. We conjecture that current modelling practices are unintentionally biased in favour of solution by backtrack search. To test this conjecture we remodel two problems whose large instances have long resisted solution by local search: parity learning and Towers of Hanoi as STRIPS planning. By reducing variable dependencies and using other techniques we boost local search performance by several orders of magnitude in both cases, and we can now solve 32-bit and 6-disk instances for the first time using a standard SAT local search algorithm.",
author = "Steven Prestwich",
year = "2007",
doi = "10.1007/978-3-540-72788-0\_14",
language = "English",
isbn = "9783540727873",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Verlag",
pages = "107--120",
booktitle = "Theory and Applications of Satisfiability Testing - SAT 2007 - 10th International Conference, Proceedings",
address = "Germany",
note = "10th International Conference on Theory and Applications of Satisfiability Testing, SAT 2007 ; Conference date: 28-05-2007 Through 31-05-2007",
}