GSAT and Local Consistency

Abstract

It has been shown that hill-climbing constraint satisfaction methods like min-conflicts [Minton et al., 1990] and GSAT [Selman et a/., 1992] can outperform complete systematic search methods like backtracking and backjumping on many large classes of problems. In this paper we investigate how preprocessing improves GSAT. In particular, we will focus on the effect of enforcing local consistency on the performance of GSAT. We will show that enforcing local consistency on uniform random problems has very little effect on the performance of GSAT. However, when the problem has hierarchical structure, local consistency can significantly improve GSAT. It has been shown [Konolige, 1994] that there are certain structured problems that are very hard for GSAT while being very easy for the Davis-Putnam procedure. We will show that they become very easy for GSAT once a certain level of local consistency is enforced.