TL;DR
This paper introduces a novel local search strategy called ANC (Adding New Clauses) for solving CNF satisfiability problems. ANC significantly outperforms existing "WEIGHT" methods by dynamically adding new clauses derived from existing ones, leading to faster convergence and more stable performance, especially on challenging problem instances.
What Problem Does This Paper Address?
The paper tackles a fundamental challenge in local search algorithms for Conjunctive Normal Form (CNF) satisfiability: escaping "local minima." Local search algorithms start with a random assignment of truth values to variables and iteratively move to neighboring assignments that reduce the number of unsatisfied clauses. A local minimum is an assignment where no single flip of a variable improves the situation, even though it's not a globally optimal solution (a "satisfying assignment").
Traditional methods like "WEIGHT" (also known as weighted local search) address this by increasing the "weight" of unsatisfied clauses at a local minimum. This makes those clauses "more important" and aims to guide the search away. However, the authors observe that WEIGHT can be slow and prone to "wandering in circles," revisiting the same assignments repeatedly. They propose ANC as a more sophisticated approach to smooth the search space and prevent this unproductive behavior.
Methods
The core innovation is the Adding New Clauses (ANC) algorithm. When a local minimum is detected, ANC doesn't just increase clause weights. Instead, it generates new clauses by taking the resolvent of an unsatisfied clause at the local minimum and a randomly selected "neighboring" clause. A neighboring clause is defined as one that shares exactly one variable, with one having the variable positively and the other negatively. The resolvent is a new clause that is satisfied if either of the original clauses is satisfied.
The idea is that these newly generated clauses, by combining aspects of unsatisfied and neighboring clauses, create a smoother "slope" in the search space, making it easier to escape local minima and preventing the algorithm from getting stuck in cycles. The paper also briefly discusses a variation called "HALF" which adds a single random literal to an unsatisfied clause, serving as a baseline for smaller added clauses.
Datasets
The experiments were conducted using two main types of 3CNF formulas:
- Random 3CNF formulas: These are denoted by
rN, whereNis the number of variables. The clause-to-variable ratio was 4.3. - AIM Generator formulas: These are generated by the AIM Generator, allowing control over attributes like the clause-to-variable ratio and the number of solutions. The paper specifically uses formulas with a clause-to-variable ratio of 2.0 that have only one solution, denoted by
oN. These are highlighted as particularly hard instances for local search. - Natural formulas: The paper also mentions experiments on more natural formulas from VLSI design and block world planning.
Key Insights and Ideas
- Resolvents as "Smoother" Search Space Tools: The core insight is that generating new clauses via resolution, rather than just increasing weights, can more effectively alter the search landscape to prevent cycles and improve convergence.
- Preventing "Wandering in Circles": A major weakness of WEIGHT is its tendency to revisit assignments. ANC significantly reduces this revisiting, leading to more efficient searches.
- Smaller Added Clauses are Better: The paper suggests that the "hole" at a local minimum might be smaller than what a clause with three literals (a common resolvent size) can fill. Experiments with "HALF" (adding a single literal) show it's better than WEIGHT, implying that smaller, more targeted additions are beneficial. ANC's resolvents, while potentially larger than HALF, are still more effective than WEIGHT.
- Divergence Matters: The stability of the search (low divergence in running time across different tries) is highlighted as a crucial advantage of ANC, making it more reliable for tasks like proving unsatisfiability (where a search that doesn't stop is a hint).
Key Results
- Significant Speedup: ANC is substantially faster than WEIGHT. For instances with 200 or more variables, ANC is roughly four to ten times faster in terms of the number of search steps.
- Reduced Divergence: The variation in computation time across different runs (tries) is much smaller for ANC compared to WEIGHT. For example, the number of cell moves in ANC is within three times the average, while WEIGHT can be 10 times or more occasionally.
- Fewer Revisited Cells: ANC revisits truth assignments 10 to 100 times less frequently than WEIGHT.
- Performance on Hard Instances: ANC shows strong performance on the challenging single-solution instances generated by AIM, outperforming WEIGHT considerably.
Limitations and Future Work
- Computational Cost of Cell Moves: While ANC is faster in terms of search steps, the process of adding resolvents is computationally more expensive per cell move than simply increasing weights. The authors suggest that better coding techniques and parallelization could mitigate this.
- Size of Added Clauses: The paper suggests that even smaller added clauses might be beneficial. One future direction is to take resolvents multiple times or to impose conditions on the clauses used for resolution (e.g., selecting clauses that cover specific neighboring cells).
- Performance Metric: The paper primarily measures performance by the number of cell moves. The authors acknowledge that computation time per cell move is also critical and suggest exploring optimizations.
- Proving Unsatisfiability: While reduced divergence is helpful for indicating potential unsatisfiability, local search algorithms are inherently incomplete for proving unsatisfiability.
Summary updated