Document Type

Technical Report

Department

Computer Science and Engineering

Publication Date

2001-01-01

Filename

WUCS-01-01.PDF

Technical Report Number

WUCS-01-01

Abstract

Soft constraint minimization problems (SCMPs) contain hard constraints that cannot be violated and soft constraints that may be violated but carry penalties if not satisfied. 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 neiborhood structures introduced by encoding schemes and analyze the anytime performance of extended WalkSAT using different 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 ineffective. Our study also shows that encoding may provide special neighborhood structures that can speed up local search algorithms.

Comments

Permanent URL: http://dx.doi.org/10.7936/K7J67F5J

Download

Share

COinS