Reducing Search Space in Local Search for Constraint Satisfaction

Book One

Volume

Proceedings of the AAAI Conference on Artificial Intelligence, 18

Constraint Satisfaction

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 neighbor 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 signifi- cantly improve search performance of the DLM local search method.