Local Search and Encoding Schemes for Soft Constraint Minimization Problems
Michael P. Moran · 2001
... In this paper, we first extend local search, WalkSAT in particular, to SCMPs and study the existing SAT encoding schemes for SCMPs. We propose a general encoding method called k-encoding. We then investigate the effects of local search neighborhood structures introduced by encoding schemes and analyze the anytime performance of extended WalkSAT using dierent encoding methods. Our experimental results on various graph coloring problems show that a direct extension of WalkSAT is most effective, and that WalkSAT using binary encoding is particularly ineective. Our study also shows that encoding may provide special neighborhood structures that can speed up local search algorithms