Combining Cubic Dynamical Solvers with Make/Break Heuristics to Solve SAT

Anshujit Sharma, Matthew Burns, Michael C. HuangSAT 2023 · OpenReview

TL;DR

This paper tackles the challenge of solving the Boolean Satisfiability (SAT) problem using specialized hardware called Cubic Dynamical Solvers (CDS). They found that existing "problem-agnostic" approaches struggle with complex SAT instances, leading them to develop a novel "make/break" heuristic that leverages the underlying physics of the CDS to achieve significant speedups over traditional software solvers.

What Problem Does This Paper Address?

The Boolean Satisfiability (SAT) problem is a fundamental challenge in computer science, asking whether there's an assignment of truth values to variables that makes a given logical formula true. Many real-world problems can be translated into SAT instances. While specialized hardware like Ising machines (which use quadratic interactions) have shown promise for optimization problems, they struggle with the higher-degree interactions inherent in SAT. Cubic Dynamical Solvers (CDS) were proposed to address this, but initial attempts using "problem-agnostic" heuristics (like random noise) performed poorly on complex, "scale-free" SAT instances, similar to those found in industrial applications. This gap highlights the need for SAT-specific heuristics that can better exploit the problem structure within the constraints of dynamical solver hardware.

Methods

The core of this work involves developing a new heuristic for Cubic Dynamical Solvers (CDS). The authors first establish that existing "make-only" heuristics (which focus on how flipping a variable satisfies new clauses) are insufficient for complex SAT problems. They then derive a crucial relationship between the "make" and "break" counts (how flipping a variable satisfies new clauses vs. unsatisfies existing ones) and the underlying physics of their CDS formulation. This allows them to efficiently recover break counts from the hardware's internal state, which is difficult to measure directly. Based on this, they propose a novel "tanh-make-break" (TMB) heuristic that combines both make and break information using a non-linear function. This TMB heuristic is then integrated with a state-of-the-art CDS architecture (called cBRIM) to create a new solver, CBRIM-TMB.

Datasets

The paper uses generated datasets for evaluation:

  • Uniform random problems: These are generated using a standard methodology and represent a simpler class of SAT instances.
  • Scale-free problems: These are generated to mimic the structure of industrial SAT instances, characterized by a power-law distribution of variable degrees (how many clauses a variable appears in). These are considered more challenging.

The authors do not introduce new benchmark datasets but rather use existing generation methods to create problems that highlight the differences in solver performance.

Key Insights and Ideas

  • Make-only heuristics are insufficient for complex SAT: The paper convincingly shows that relying solely on "make" counts, common in simpler heuristics, fails to solve challenging, scale-free SAT problems. This underscores the importance of considering how flips break existing solutions.
  • Bridging the gap between physics and SAT heuristics: The most significant contribution is deriving a way to efficiently extract "break" counts from the CDS formulation. This is a clever workaround for hardware limitations, allowing the use of more sophisticated heuristics without requiring complex new hardware.
  • The power of combining make and break: The TMB heuristic, by leveraging both make and break information, demonstrates a substantial improvement in solving scale-free problems, suggesting that a balanced approach is key for complex SAT instances.
  • CDS speed advantage is immense: The paper highlights that despite potentially requiring more "flips" than some software solvers, the incredibly fast dynamics of CDS (on the order of picoseconds) lead to massive overall speedups.

Key Results

  • CBRIM-TMB significantly outperforms CBRIM-BRW: On scale-free problems, CBRIM-TMB (using make/break) consistently solved about 4x more problems than CBRIM-BRW (using only make) and could solve all scale-free instances, whereas CBRIM-BRW failed on 6%.
  • Orders of magnitude faster than software solvers: CBRIM-TMB achieved a net speedup of 25x over WalkSAT and 147x over ProbSAT on scale-free problems, and a 53x and 8.7x reduction in flips respectively. This speedup is attributed to the extremely fast dynamics of the CDS hardware.
  • Robustness to parameters: The TMB heuristic showed less sensitivity to parameter tuning across different problem sizes and types compared to the BRW heuristic.
  • Competitive with state-of-the-art: While KISSAT (a CDCL solver) performed well on scale-free problems, CBRIM-TMB was competitive and often faster, especially on uniform random problems where KISSAT struggled.

Limitations and Future Work

  • Hardware constraints: The current CDS systems are simulated, and the paper acknowledges that real-world SAT instances are massive (hundreds of thousands of variables), requiring efficient software-hardware co-design due to hardware capacity limitations.
  • Parameter tuning: While TMB is less sensitive than BRW, some parameter tuning is still required.
  • Real-world SAT instances: The current evaluation uses generated problems. Testing on actual industrial SAT instances is needed to fully assess the solver's effectiveness.
  • Further heuristic exploration: The authors suggest exploring other non-linear functions for the make/break heuristic and investigating the redundancy of parallel flips.
  • Time-dependent solver behavior: Analyzing how the solver's behavior evolves over time and relating it to problem structure is identified as future work.

Summary updated

Abstract

Dynamical solvers for combinatorial optimization are usually based on 2superscript{nd} degree polynomial interactions, such as the Ising model. These exhibit high success for problems that map naturally to their formulation. However, SAT requires higher degree of interactions. As such, these quadratic dynamical solvers (QDS) have shown poor solution quality due to excessive auxiliary variables and the resulting increase in search-space complexity. Thus recently, a series of cubic dynamical solver (CDS) models have been proposed for SAT and other problems. We show that such problem-agnostic CDS models still perform poorly on moderate to large problems, thus motivating the need to utilize SAT-specific heuristics. With this insight, our contributions can be summarized into three points. First, we demonstrate that existing make-only heuristics perform poorly on scale-free, industrial-like problems when integrated into CDS. This motivates us to utilize break counts as well. Second, we derive a relationship between make/break and the CDS formulation to efficiently recover break counts. Finally, we utilize this relationship to propose a new make/break heuristic and combine it with a state-of-the-art CDS which is projected to solve SAT problems several orders of magnitude faster than existing software solvers.
BibTeX
@inproceedings{sharma2023combining,
  author = {Anshujit Sharma and Matthew Burns and Michael C. Huang},
  title = {{Combining Cubic Dynamical Solvers with Make/Break Heuristics to Solve SAT}},
  booktitle = {SAT},
  year = {2023},
  url = {https://openreview.net/forum?id=eGcinChxRF},
}
Figure