Weight Redistribution for Unweighted MAX-SAT

Abstract

Many real-world problems are over-constrained and require search techniques adapted to optimising cost functions rather than search- ing for consistency. This makes the MAX-SAT problem an important area of research for the satis¯ability (SAT) community. In this study we perform an empirical analysis of several of the best performing SAT local search techniques in the domain of unweighted MAX-SAT. In particular, we test two of the most recently developed SAT clause weight redistri- bution algorithms, DDFW and DDFW+, against three more well-known techniques (RSAPS, AdaptNovelty+ and PAWS). Based on an empir- ical study across a range of previously studied problems we conclude that DDFW is the most promising algorithm in terms of robust average performance.