Abstract
Handling over-constrained Boolean Satisfiability (SAT) problems often requires distinguishing between mandatory and optional constraints. Traditional methods employ a decoupled two-phase approach that separates the selection of optional clauses from the satisfiability check. This paper introduces Relaxation Search (RS), a unified framework that integrates these phases into a single search tree by augmenting optional clauses with selector variables. By prioritizing these variables in the solver's decision heuristic, RS achieves state-of-the-art performance in Maximum Satisfiability (MAXSAT) and Minimum Correction Set (MCS) tasks with minimal implementation overhead.
Introduction
In real-world logic applications, such as hardware verification, bioinformatics, and planning, problems are frequently "over-constrained," meaning no solution exists that satisfies every rule. To resolve this, researchers treat a subset of rules as optional. The objective then shifts to either finding a solution that satisfies the maximum number of optional clauses (MAXSAT) or identifying a minimal set of clauses that must be removed to restore satisfiability (Minimum Correction Sets or MCS).
Historically, these problems have been solved using a master-worker architecture. A master algorithm (often based on hitting sets or binary search) selects a subset of clauses to ignore, and a worker SAT solver checks the remaining formula. However, this separation prevents the solver from effectively learning why certain combinations of clauses are incompatible, leading to redundant computations and performance bottlenecks.
The Relaxation Search Framework
The core innovation of Relaxation Search (RS) is the seamless integration of clause selection and logical checking within a single Conflict-Driven Clause Learning (CDCL) search tree. The authors achieve this by transforming each optional clause $c_i$ into a relaxed version: $(c_i \lor b_i)$, where $b_i$ is a new "selector" variable. If $b_i$ is assigned to true, the clause is effectively ignored (relaxed).
The Heuristic Modification
The "secret sauce" of RS is a simple yet profound modification to the SAT solver’s variable selection heuristic. The solver is constrained to branch on unassigned selector variables ($b$) before any regular variables.
- For MCS Extraction: The solver is forced to try setting $b$ variables to false first. This bias pushes the solver to satisfy as many optional clauses as possible. When a contradiction is encountered, the solver’s native clause-learning mechanism automatically identifies the conflict, effectively learning which $b$ variables must be true (i.e., which clauses must be relaxed).
- For MAXSAT: The authors extend RS using techniques like Branch and Bound (pruning the search tree based on weights), Iterative Deepening (gradually increasing the allowed relaxation cost), and Logic-Based Benders Decomposition (using a MIP solver like CPLEX to guide the $b$ variable assignments).
To further optimize performance, the authors introduced the $F^b_{eq}$ constraint, which logically links the selector variable $b_i$ to the falsification of the clause ($b_i \leftrightarrow \neg c_i$). This allows for faster logical propagation and more efficient pruning of the search space.
Experimental Evaluation
The authors evaluated RS against a massive benchmark of 1,343 instances from the 2013 MAXSAT Evaluation, encompassing industrial and combinatorial problems.
Performance on Minimum Correction Sets (MCS)
In the task of finding a single MCS, RS proved to be the most effective algorithm tested. As shown in the cactus plot below, RS (represented by the red line) consistently solved more instances within the 1800-second timeout than specialized competitors like CLD or ELS.
Notably, RS solved 20 instances that no other existing algorithm could solve. When enumerating all MCSes, RS remained a vital component of the "Virtual Best Solver," contributing solutions to 14 instances that were previously unsolvable by any other method.
Performance on MAXSAT
For MAXSAT, the Logic-Based Benders version of RS demonstrated high competitiveness with the reigning champion, MAXHS. While it did not dominate every category, it solved a distinct set of problems compared to MAXHS, suggesting that RS is a complementary tool rather than a mere replacement.
Conclusion and Future Work
Relaxation Search demonstrates that complex optimization problems can often be solved more efficiently by simplifying the architecture and leveraging the inherent power of modern CDCL solvers. By integrating the selection logic directly into the search tree, RS enables the solver to learn and remember incompatible constraints automatically.
Future research directions include developing more sophisticated lower-bound estimates for the Branch and Bound approach and refining knowledge retention strategies in Iterative Deepening. Additionally, the authors suggest that tuning the ordering of $b$ variables based on weights or activity could yield further performance gains. Despite its simplicity—requiring only a few lines of code added to a standard solver like MiniSat—RS represents a significant step forward in managing optional constraints.
Summary updated