The island confinement method for reducing search space in local search methods

Abstract

Typically local search methods for solving constraint satisfaction problems such as GSAT, WalkSAT, DLM, and ESG treat the problem as an optimisation 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 valuation to move to, until finally a solution which satisfies all the constraints is found. In this paper we investigate using some of the constraints as "hard" constraints, that are always satisfied by every trial valuation visited, rather than as part of a penalty function. In this way these constraints reduce the possible neig..