Reducing search space in local search for constraint satisfaction

H. Fang, Y. Kilani, J. H.M. Lee, P. J. Stuckey

Research output: Contribution to conferencePaper

3 Citations (Scopus)

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 each move and also the overall search space. The treating of some constraints as hard requires that the space of valuations that are satisfied is connected in order to guarantee that a solution can be found from any starting position within the region. Treating some constraints as hard also provides difficulties for the search mechanism since the search space becomes more jagged, and there are more deep local minima. A new escape strategy is needed. We show in this paper how, for DIMACS translations of binary CSPs, treating some constraints as hard can significantly improve search performance of the DLM local search method.

Keywords

  • Binary CSP
  • Local search
  • SAT

Cite this