Hidden Gold in Random Generation of SAT Satisfiable Instances

IJCAI 1997

TL;DR

This paper introduces a novel method for generating "hard" satisfiable instances for the Boolean Satisfiability Problem (SAT). By carefully controlling the proportion of positive and negative literals in generated clauses, they create instances that challenge even state-of-the-art SAT solvers, offering a more realistic benchmark for evaluating incomplete algorithms.

What Problem Does This Paper Address?

Evaluating SAT solvers, especially incomplete ones like those based on local search, requires realistic benchmarks. Traditional random generation methods for SAT instances often produce instances that are either too easy or don't accurately reflect the difficulty of real-world problems. A key challenge is generating satisfiable instances that are genuinely hard for these algorithms. While incomplete methods have advanced significantly, their performance can be misleading if tested on instances that don't expose their weaknesses. The paper aims to bridge this gap by providing a generator that produces hard satisfiable instances, allowing for a more robust evaluation of SAT solving techniques.

Methods

The core contribution is a new random generation method for kSAT instances, specifically focusing on 3SAT. Instead of purely uniform random generation, the authors introduce a parameter, posp (probability to pick a positive literal), to control the balance of positive and negative literals within clauses. This method, termed "kSAT-consistent," aims to generate instances that are satisfiable but difficult to solve.

They also explore and evaluate several SAT solving algorithms:

  • Complete Method: The classical Davis-Putnam (DP) procedure, implemented with sophisticated heuristics (C-SAT).
  • Incomplete Methods:
    • GSAT with random walk.
  • Break Out Method (BOut) by Morris.
  • New Algorithms: * Break Out Method with Jump (BOJ): An enhancement to BOut that flips all variables in falsified clauses when a local minimum is reached.
  • Mirror: A variation of BOut that flips all variables in falsified clauses immediately after weighting them.

The paper empirically tests these algorithms against instances generated by their new method, analyzing both the number of solved instances and the complexity (median curves).

Datasets

The paper does not introduce new datasets in the traditional sense. Instead, it proposes a new generation method for creating benchmark instances for SAT solvers. The instances generated are for the 3SAT problem and are characterized by the number of variables (nbv), the ratio of clauses to variables (ratio), and the probability of picking a positive literal (posp). They specifically focus on the "hardest areas" of this generation model, often around ratio = 4.4 and posp ≈ 0.64 (the golden ratio).

Key Insights and Ideas

  • The "Golden Ratio" for Hardness: The paper suggests that a specific proportion of positive to negative literals, related to the golden ratio (approximately 0.618), is crucial for generating hard satisfiable instances. This balance seems to create instances that are neither trivially satisfiable nor overwhelmingly unsatisfiable, but rather lie in a difficult region for local search.
  • Beyond Uniform Randomness: Uniform random generation, while theoretically interesting, is insufficient for creating realistic hard benchmarks. Controlling specific clause properties, like literal sign distribution, is key.
  • Incomplete Algorithms Have "Hidden Gold": The proposed generator reveals that even seemingly simple instances can be very hard for sophisticated algorithms. This highlights the need for more nuanced evaluation beyond just the "hardest areas" of a specific generator.
  • Local Search Weaknesses Exposed: The new generator effectively exposes the limitations of local search algorithms, showing that they can struggle with instances that have no apparent structure but are carefully constructed to be difficult.
  • BOJ and Mirror Show Promise: The proposed BOJ and Mirror algorithms demonstrate improved performance on these hard instances, suggesting that new operations like "jumping" or "mirroring" flips can enhance robustness.

Key Results

  • GSAT with random walk and BOut struggle: For instances generated with ratio = 8 and posp = 0.8, GSAT solved close to 0% of instances, and BOut performed poorly.
  • BOJ performs well: The Break Out Method with Jump (BOJ) solved almost all instances, showing significant improvement.
  • Mirror's efficiency is mysterious: The Mirror algorithm was surprisingly efficient on these hard instances, though its effectiveness on easier instances was less consistent.
  • Hardest instances at ratio ≈ 4.4 and posp ≈ 0.64: The paper identifies a "ridge" of hardness for all tested methods, particularly around these parameter values.
  • Complexity scales with ratio: For most incomplete algorithms, complexity increases with the ratio of clauses to variables.

Limitations and Future Work

  • Empirical vs. Theoretical: While the paper provides strong empirical evidence for the effectiveness of their generator and the performance of algorithms, theoretical guarantees for the hardness of these instances are still lacking.
  • Algorithm-Specific Hardness: The paper notes that the "ridge" of hardness observed is not necessarily inherent to the instances but can be influenced by the specific algorithms used. This suggests that evaluating algorithms across different "hard areas" is crucial.
  • Generalizability of Mirror: The Mirror algorithm's efficiency is noted as being "mysterious" and seems to work best with their specific generator. Further investigation is needed to understand its broader applicability.
  • Future Work: The authors suggest that the kSAT-consistent function is a good starting point for generating hard satisfiable instances and that further study into simplified models of satisfiable instance generation is warranted. They also emphasize the need for new operations in local search to improve robustness.

Summary updated

BibTeX
@inproceedings{1997hidden,
  title = {{Hidden Gold in Random Generation of SAT Satisfiable Instances}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {1997},
}
Figure