Lecture Notes in Computer Science, 2003, Volume 2671/2003, 996, DOI: 10.1007/3-540-44886-1_13

Scaling and Probabilistic Smoothing: Dynamic Local Search for Unweighted MAX-SAT

Dave A. D. Tompkins and Holger H. Hoos

View Related Documents

Abstract

In this paper, we study the behaviour of the Scaling and Probabilistic Smoothing (SAPS) dynamic local search algorithm on the unweighted MAX-SAT problem. MAX-SAT is a conceptually simple combinatorial problem of substantial theoretical and practical interest; many application-relevant problems, including scheduling problems or most probable explanation finding in Bayes nets, can be encoded and solved as MAX-SAT. This paper is a natural extension of our previous work, where we introduced SAPS, and demonstrated that it is amongst the state-of-the-art local search algorithms for solvable SAT problem instances. We present results showing that SAPS is also very e.ective at finding optimal solutions for unsatisfiable MAX-SAT instances, and in many cases performs better than state-of-the-art MAX-SAT algorithms, such as the Guided Local Search algorithm by Mills and Tsang [8]. With the exception of some configuration parameters, we found that SAPS did not require any changes to effeciently solve unweighted MAX-SAT instances. For solving weighted MAX-SAT instances, a modified SAPS algorithm will be necessary, and we provide some thoughts on this topic of future research.

Fulltext Preview

Image of the first page of the fulltext document