Abstract
This paper challenges the prevailing assumption that complex multiplicative weighting schemes are necessary for state-of-the-art performance in local search SAT solvers. We introduce the Pure Additive Weighting Scheme (PAWS), which utilizes simple integer-based additive weighting. Through extensive benchmarking, we demonstrate that PAWS is faster, easier to tune, and scales significantly better than multiplicative methods like SAPS on large, difficult problem instances.
Introduction
Propositional satisfiability (SAT) testing is a foundational problem in computer science with wide-ranging applications. Local search algorithms are highly effective at finding solutions but frequently encounter "local minima"—states where no single variable flip reduces the number of unsatisfied clauses. To escape these traps, researchers employ clause weighting, increasing the penalty for unsatisfied clauses to drive the search into unexplored regions of the search space.
Historically, the field has trended toward complex multiplicative schemes, which scale weights by a factor, over simpler additive approaches. This study investigates whether this added complexity is truly beneficial or if simpler additive methods have been overlooked due to implementation disparities.
Methodology: PAWS vs. SAPS
To ensure a fair comparison, the authors developed PAWS, a "pure" additive weighting scheme, and embedded it into the same optimized software architecture as the state-of-the-art multiplicative algorithm, SAPS.
- SAPS (Multiplicative): Employs real-valued weights. Upon reaching a local minimum, it multiplies the weights of unsatisfied clauses by a factor ($\alpha$) and periodically "smooths" them back toward a mean using probabilistic decay.
- PAWS (Additive): Utilizes simple integer weights. When stuck, it increments the weights of unsatisfied clauses by 1. After a predefined number of increments ($Max_{inc}$), it decrements all weights greater than 1 by 1.
PAWS also incorporates "Flat Moves" (moves that do not change the total cost) and "Multiple Inclusion" (counting a variable multiple times if it appears in several unsatisfied clauses). By using the same underlying architecture, the researchers isolated the mathematical impact of the weighting scheme itself.
Key Results
The algorithms were evaluated across a diverse range of benchmarks, including standard SATLIB sets, harder DIMACS problems (e.g., graph coloring and parity learning), and random 3-SAT instances.
Computational Efficiency and Tuning
PAWS offers a distinct advantage in computational overhead. By using integer addition and subtraction instead of floating-point multiplication, it is inherently faster. On identical hardware, PAWS achieved approximately 149,000 flips per second, compared to 115,000 for SAPS. Furthermore, PAWS simplifies the tuning process; while SAPS requires four sensitive parameters, PAWS effectively requires only one ($Max_{inc}$), making it more practical for real-world deployment.
Scaling and Success Rates
On the most challenging problem sets, PAWS demonstrated superior scaling and robustness. As shown in Figure 1, PAWS consistently solves a higher percentage of instances in less time than SAPS.
Detailed results on "harder" problems further highlight this dominance. PAWS achieved an overall success rate of 99.46%, compared to 96.23% for SAPS. In specific cases like the g125.17 graph coloring problem, PAWS was nearly ten times faster, with a median solution time of 6.16 seconds versus 60.02 seconds for SAPS.
Discussion: The "Coarseness" Advantage
The success of PAWS can be attributed to the "coarseness" of integer weighting. Multiplicative schemes create fine-grained distinctions between moves, often narrowing the search to a single "best" move. In contrast, the integer-based additive approach results in many moves sharing the same "best" cost. This larger pool of candidate moves provides the algorithm with greater "freedom of movement" to navigate complex cost landscapes effectively.
Conclusion
While SAPS maintains an edge on specific problem types, such as certain random binary CSP-encoded instances, PAWS proves to be a more robust and efficient general-purpose solver for difficult SAT problems. Its simplicity, ease of tuning, and superior scaling suggest that additive weighting is a powerful, often superior, alternative to multiplicative complexity. Future research will focus on identifying specific problem characteristics that favor one scheme over the other, potentially leading to hybrid weighting strategies.
Summary updated