TL;DR
This paper introduces a novel metric, the Search Similarity Index (SSI), to quantify how much a SAT solver's search strategy changes after a "restart." By applying SSI, the authors reveal that difficult SAT problems benefit from more intensive searches, and they provide a data-driven explanation for why a leading restart method (EMA) is effective.
What Problem Does This Paper Address?
Solving Boolean Satisfiability (SAT) problems is a fundamental challenge in computer science with applications ranging from hardware verification to artificial intelligence. SAT solvers, particularly those using conflict-driven clause learning (CDCL), employ various heuristics to navigate the vast search space. One crucial technique is "restart," which periodically resets the solver's search to avoid getting stuck in unproductive areas. However, understanding why certain restart strategies are effective, especially in relation to problem difficulty, has been an open question. This paper aims to provide a quantitative tool (SSI) to analyze the impact of restarts and gain deeper insights into SAT solver behavior.
Methods
The core contribution is the Search Similarity Index (SSI). SSI quantifies the similarity between two search states of a SAT solver. A search state is represented by the "current search direction" (CSD), which includes the polarity (True/False assignment) and priority (order of assignment) of variables. SSI is calculated by comparing the CSDs of two search points (e.g., before and after a restart).
- Variable Similarity: Compares the polarity of each variable. If polarities match, similarity is 1; otherwise, 0.
- Priority Similarity: Measures the difference in assignment order for each variable.
- Importance Weighting: Assigns higher importance to variables that were assigned earlier or have higher priority. This weighting is crucial because changes in early assignments are often more impactful.
- Normalization: The final SSI is normalized between 0 and 1, where 0 means completely different searches and 1 means identical searches.
The paper then uses SSI to analyze the effect of restarts by calculating SSI|k|, which represents the average similarity between searches that are k restarts apart. This metric effectively measures how much the search has changed after k restarts.
Datasets
The authors evaluated their approach using 400 industrial SAT competition instances from the main track. These instances were used to benchmark the performance of the CaDiCaL solver.
Key Insights and Ideas
- Intensive Search for Difficult Problems: The study suggests that difficult SAT instances benefit from more intensive searches, characterized by high similarity between consecutive search steps. This implies that once a solver finds a promising direction, it should stick to it.
- Unsolved Instances and Search Variance: Unsolved instances showed the smallest mean and largest variance in SSI, indicating that solvers struggle to find a consistent, effective search strategy for these problems.
- EMA's Faster Search Change: The state-of-the-art EMA restart method achieves the effect of a large number of restarts (e.g., 1000) much faster than other methods. This means EMA can alter the search strategy more efficiently, leading to better performance.
- Explaining EMA's Effectiveness: The SSI analysis provides a quantitative explanation for EMA's success: it triggers more frequent restarts, leading to a greater change in search direction with fewer overall conflicts compared to other methods.
Key Results
- The scatter plot of SSI|100| versus runtime shows that easy instances have widely dispersed SSI values (0.7-1.0), while difficult instances tend to have higher SSI values.
- Unsolved instances exhibited the lowest mean SSI|100| and the largest variance.
- Figure 2 demonstrates that EMA, compared to uniform and Luby restarts, has a higher mean and smaller variance for SSI|1| (similarity after one restart). This indicates EMA causes a more significant and consistent change in search direction with each restart.
- EMA achieved the effect of 1000 restarts faster than other methods, requiring fewer conflicts on average between restarts.
Limitations and Future Work
- Limitations: The paper focuses on analyzing the effect of restarts. While it provides insights into why EMA is effective, it doesn't explore all possible restart strategies or their interactions with other SAT solver heuristics. The analysis is also based on a specific solver (CaDiCaL) and a set of industrial instances.
- Future Work: The authors suggest that SSI can be extended to analyze other SAT solver techniques, such as clause sharing and decision heuristics. They also aim to use these insights to develop improved SAT solver performance.
Summary updated