From: Steve Hampson After working on the Traveling Salesman Problem and various class scheduling problems, and finding iterative improvement (hill climbing) plus simulated annealing to be highly effective, a similar approach was tried on Boolean satisfiability. The results were surprisingly good. Selman (last AAAI) implemented and tested a similar algorithm, also with good results. The only significant difference in algorithms is that Selman et al use multiple restarts while ours uses fluctuations in temperature and simulated annealing. In limited testing using Selman's 50:50 "hard" CNF generation technique, the annealing approach appears to work better, but the difference has not been quantified. This difference is one point of interest. A second point is the surprising efficiency of random walk on the "plateaus" of hill climbing, as compared to other, more methodical approaches (e.g. breadth-first or depth-first). It is our goal to better understand the nature of the plateaus and the best methods for searching them. A related issue is the best allocation of time between more extensive plateau search, and a greater number of restarts. A third point, which we have not yet attempted, is to add a capability to learn macros, i.e. ability to change multiple variables at the same time. This form of learning has been successful for the NxN tile puzzle and for circuit optimization. Our guess is that it won't be successful for boolean-satisfiability but we would like to understand why. However this suspicion need to verified and we have been surprised before in this domain. We suspect that learning will not be useful on randomly generated problems, but real problems have structure. If this structure contains local regularity, then the suggested approach towards macro learning ought to work. In general, our goal is to better understand the strengths and weaknesses of iterative improvement (at least in the 3-Sat domain) and to identify methods for improving performance without sacrificing tractability. This work is being done in collaboration with Dennis Kibler, also of the ICS Dept. of UCI. Steven Hampson Information and Computer Science Dept. UCI Irvine, CA. 92717