Tuning Local Search for Satisfiability Testing

AAAI 1996

TL;DR

This paper introduces a novel method called Retrospective Parameter Variation (RPV) to efficiently tune the Maxflips parameter in local search algorithms for Boolean satisfiability (SAT) problems. They demonstrate that RPV significantly reduces the experimental cost of optimization, enabling them to analyze the scaling behavior of WSAT/SKC on Random 3SAT instances, revealing sub-exponential scaling.

What Problem Does This Paper Address?

Solving Boolean Satisfiability (SAT) problems is a fundamental challenge in computer science with applications in areas like artificial intelligence, hardware verification, and operations research. Local search algorithms, such as GSAT and WSAT, have emerged as powerful techniques for tackling large SAT instances, often outperforming traditional methods. However, their performance is highly sensitive to parameter settings, particularly Maxflips (the maximum number of variable flips allowed before restarting the search with a new random assignment).

The paper highlights several key issues:

  • Parameter Tuning: There are no established rules for setting Maxflips, making it an "art" that significantly impacts performance. Efficiently finding optimal settings is crucial for fair comparison and achieving best results.
  • Performance Scaling: Understanding how the runtime of these algorithms scales with problem size is essential for predicting their behavior on even larger instances and comparing them to other algorithmic approaches.
  • False Failures: Local search algorithms can fail to find a solution even for satisfiable instances, and quantifying this "false failure rate" is important.

The authors aim to address the challenge of efficiently optimizing Maxflips and characterizing the performance scaling of local search algorithms on hard SAT problems.

Methods

The core methodological contribution of this paper is Retrospective Parameter Variation (RPV). This technique allows researchers to derive performance estimates for different Maxflips values from a single set of experimental runs.

Here's how it works:

  1. Data Collection: A local search algorithm is run with a high Maxflips value (mp) on a set of problem instances, and the number of flips taken to find a solution for each successful "try" is recorded.
  2. Retrospective Analysis: For a smaller Maxflips value (m < mp), the algorithm simulates what would have happened by considering only the successful tries from the original runs that took m flips or fewer.
  3. Prediction: Using the recorded data from these "reduced bags" of successful tries, the paper derives formulas to predict the expected number of flips (Ev,m) and the probability of success within m flips (pm) for the smaller Maxflips values. This avoids the need for entirely new, costly experimental runs.

The paper also details two specific variants of the WSAT algorithm:

  • WSAT/G: A simpler greedy approach that picks a random unsatisfied clause and then, with some probability, picks a random variable from it, or otherwise picks the variable that maximizes the net increase in satisfied clauses.
  • WSAT/SKC: A more sophisticated variant that prioritizes minimizing the number of broken clauses when making a flip, exhibiting "minimal greediness." This variant was found to be more efficient.

Datasets

The primary dataset used in this paper is Random 3SAT. This is a well-established benchmark for SAT solvers, generated by randomly selecting variables for clauses and negating them with a certain probability. The authors specifically focus on instances near the "crossover point," where the problem difficulty is known to peak for systematic solvers. They used a systematic solver (TABLEAU) to filter out unsatisfiable instances, ensuring their experiments focused on satisfiable problems.

Key Insights and Ideas

  • RPV is a Game Changer for Parameter Tuning: The ability to "retrospectively" vary Maxflips from existing data is a significant efficiency gain. It drastically reduces the computational cost of finding optimal parameter settings, making it feasible to study performance scaling on large problem instances.
  • WSAT/SKC Outperforms WSAT/G: The "minimal greediness" of WSAT/SKC, which prioritizes not breaking already satisfied clauses, leads to significantly better performance and less sensitivity to the Maxflips parameter compared to the more straightforward WSAT/G.
  • Optimal Maxflips Scales Monomially: The optimal Maxflips setting (m*) for WSAT/SKC was found to scale as a power of the number of variables (n), specifically n^b where b is around 2.39. This suggests a predictable relationship that can inform parameter selection.
  • Sub-Exponential Scaling for Local Search: The paper provides strong empirical evidence that WSAT/SKC exhibits sub-exponential scaling on Random 3SAT problems. This is a crucial finding, as it suggests local search can solve much larger problems than previously thought possible with systematic methods, which often scale exponentially.
  • Noise vs. Restarts: The paper touches on how "noise" (randomness in variable selection) and restarts (controlled by Maxflips) serve similar purposes in local search by helping the algorithm escape local optima. WSAT/SKC's reduced sensitivity to Maxflips is attributed, in part, to its sophisticated noise handling.

Key Results

  • RPV Validation: Figure 3 demonstrates that RPV accurately predicts performance for lower Maxflips values, matching directly obtained results, validating its effectiveness.
  • WSAT/SKC Efficiency: WSAT/SKC was found to be significantly faster than WSAT/G, with the latter slowing down by a factor of about 4 when Maxflips was set too high, compared to only 20% for WSAT/SKC.
  • Optimal Maxflips Scaling: The optimal Maxflips (m*) for WSAT/SKC was fitted to m* ≈ 0.02 * n^2.39.
  • Performance Scaling: The mean runtime (Em) for WSAT/SKC on Random 3SAT was found to scale sub-exponentially. The paper provides empirical fits for this scaling, suggesting it's faster than a simple power-law but slower than a simple exponential. For instance, at n=400, the mean runtime is on the order of 10^5 flips.
  • Robustness: The distribution of runtimes for a large sample of instances showed no significant signs of problematic outliers, supporting the validity of the mean runtime results.

Limitations and Future Work

  • RPV's Lower Bound: RPV's effectiveness is limited by the size of the "bag" of successful tries. As Maxflips decreases, the bag shrinks, potentially invalidating estimates. This necessitates careful consideration of sample sizes and can lead to an effective lower bound for RPV application.
  • Noise Parameter p: While RPV is excellent for tuning Maxflips, it cannot directly determine the optimal noise parameter p. This still requires experimental variation, though RPV helps reduce the overall experimental burden.
  • Instance-Specific Behavior: The paper acknowledges that Maxflips-scaling is not solely a function of n and p but is also affected by other problem characteristics like "constrainedness." Future work aims to understand Maxflips-dependence in terms of individual instance behaviors.
  • Real-World Problems: The current experiments are on Random 3SAT. The authors plan to extend their work to more realistic problem domains, such as scheduling problems, to see how local search performs and how parameters behave in those contexts.
  • Theoretical Understanding: While empirical results strongly suggest sub-exponential scaling, a deeper theoretical understanding of why this occurs and how it relates to problem structure is still an open area.

Summary updated

BibTeX
@inproceedings{1996tuning,
  title = {{Tuning Local Search for Satisfiability Testing}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1996},
}
Figure