Unsatisfied Variables in Local Search
Ian P. Gent, Toby Walsh · 1995
Several local search algorithms for propositional satis ability havebeen proposed which can solve hard random problems beyond the range of conventional backtracking procedures. In this paper, we explore the impact of focusing search in these procedures on the "unsatisfied variables"; that is, those variables which appear in clauses which are not yet satisfied. For random problems, we show that such a focus reduces the sensitivity to input parameters. We also observe a simple scaling law in performance. For non-random problems, we showthat whilst this focus can improve performance, many problems remain difficult. We speculate that such problems will remain hard for local search unless constraint propagation techniques can be combined with hill-climbing.