R46  
A GraphBased Method for Improving GSAT
Kalev Kask (kkask@ics.uci.edu) &
Rina Dechter (dechter@ics.uci.edu)

Abstract GSAT is a randomized greedy local repair procedure that was introduced for solving propositional satisfiability and constraint satisfaction problems. We present an improvement to GSAT that is sensitive to the problem's structure. When the problem has a tree structure the algorithm is guaranteed to find a solution in linear time. For nontree networks, the algorithm designates a subset of nodes, called cutset, and executes a regular GSAT algorithm on this set of variables. On all the rest of the variables it executes a specialized local search algorithm for trees. This algorithm finds an assignment that, like GSAT, locally minimizes the sum of unsatisfied constraints and also globally minimizes the number of conflicts in every treelike subnetwork. We will present results of experiments showing that this new algorithm outperforms regular GSAT on sparse networks whose cyclecutset size is bounded by 30% of the nodes. [ps] [pdf] 