Automated Discovery of Composite SAT Variable-Selection Heuristics

AAAI 2002

TL;DR

This paper introduces CLASS, a system that automatically discovers effective variable selection heuristics for SAT solvers by composing existing primitive heuristics. The discovered heuristics, particularly CLH1, demonstrate competitive performance against state-of-the-art hand-coded methods, suggesting that automated discovery can be a powerful approach for designing complex search algorithms.

What Problem Does This Paper Address?

Satisfiability (SAT) solvers are crucial for many computational problems. Local search algorithms like GSAT and Walksat are highly effective for finding solutions to SAT instances, but their performance heavily relies on sophisticated variable selection heuristics. Developing these heuristics has traditionally been a manual, empirical process, often involving extensive trial-and-error. This paper addresses the challenge of automating this discovery process, aiming to find novel, effective variable selection heuristics by systematically combining existing building blocks.

Methods

The core of the paper is the CLASS system, which employs a meta-level search approach. It uses a composition operator to combine existing variable selection primitives (like net gain, variable age, and clause locality) into new, composite heuristics. These heuristics are represented as Lisp-like s-expressions. CLASS uses a population-based search algorithm (similar to genetic programming) where heuristics are evolved over generations. The system starts with a random population of heuristics and iteratively applies the composition operator to generate children, which are then evaluated and potentially replace older heuristics in the population. An extension, CLASS-L, incorporates a library of pre-defined "good" and "bad" heuristics to guide the search.

Datasets

The paper uses standard random 3-SAT instances from the SATLIB benchmark suite for both training and evaluation. Specifically:

  • Training: 50-variable, 215-clause (uf50-215) and 100-variable, 430-clause (uf100-430) random 3-SAT instances.
  • Evaluation: Larger random 3-SAT instances (uf150, uf200, uf250), as well as structured problem instances like graph-coloring (flat125), All-Interval-Series (ais6, 8, 10), and planning instances (medium, huge, bw_large, logistics.c).

Key Insights and Ideas

  • Compositional Nature of Heuristics: The paper highlights that many successful SAT heuristics are not monolithic but rather combinations of simpler, interpretable primitives. This suggests that a compositional approach is a natural way to explore the heuristic space.
  • Automation's Potential: The success of CLASS in discovering competitive heuristics demonstrates that automated discovery can be a viable and powerful alternative to manual heuristic design, especially for complex combinatorial problems.
  • Importance of Coverage: The analysis of local search characteristics (depth, mobility, coverage) suggests that "coverage" is a particularly strong predictor of performance on random 3-SAT instances, indicating how systematically the search explores the solution space.
  • Generalization vs. Specialization: While CLASS can discover heuristics that generalize well to different problem classes, tailoring the training data to specific problem types (as hinted by CLASS-L) is likely necessary for achieving peak performance on those specialized domains.

Key Results

  • CLASS discovered heuristics (CH1, CH2) that are competitive with well-known Walksat variants on standard random 3-SAT benchmarks.
  • CLASS-L, an extension, discovered CLH1, which outperformed even a highly tuned R-Novelty heuristic on the target problem class (uf100-430).
  • The learned heuristics demonstrated good generalization capabilities on larger random 3-SAT instances and some structured problem classes.
  • Analysis using depth, mobility, and coverage metrics showed that the learned heuristics exhibit desirable local search behaviors, correlating well with their performance.

Limitations and Future Work

  • Runtime of Learned Heuristics: The paper notes that the learned heuristics are currently slower (execute fewer flips per second) than standard ones, though they believe this can be improved through optimization.
  • Parameter Tuning: While CLASS implicitly handles some parameter tuning through its composition operator, explicit parameter tuning for learned heuristics is still an area for exploration.
  • Extending Primitives: Future work could involve extending CLASS with more sophisticated primitives, such as clause-weighting mechanisms and different objective function metrics, to discover even more powerful heuristics.
  • Domain-Specific Training: For optimal performance on structured problem instances, tailoring the training data to those specific problem classes is suggested.
  • Efficiency of Evaluation: The current evaluation process is computationally expensive. Exploring faster proxy metrics (like coverage) for heuristic evaluation is a promising direction.

Summary updated

BibTeX
@inproceedings{2002automated,
  title = {{Automated Discovery of Composite SAT Variable-Selection Heuristics}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2002},
}
Figure