Reducing search space in local search for constraint satisfaction

Abstract

Typically local search methods for solving constraint satisfaction problems such as GSAT, WalkSAT and DLM treat the problem as an optimization problem. Each constraint contributes part of a penalty function in assessing trial valuations. Local search examines the neighbours of the current valuation, using the penalty function to determine a "better" neighbour valuations to move to, until finally a solution which satisfies all constraints is found. In this paper we investigate using some of the constraints, rather than as part of a penalty function, as "hard" constraints, that are always satisfied by every trial valuation visited. In this way the constraints reduce the possible neighbours in ..