Abstract
Core-guided MAXSAT algorithms dominate other methods in solving industrial MAXSAT problems. In this work, we propose a new efficient algorithm that is guided by correction sets and cores. At every iteration, the algorithm obtains a correction set or a core, which is then used to rewrite the formula using incremental and succinct transformations. We theoretically show that correction sets and cores have complementary strengths and empirically demonstrate that their combination leads to an efficient MAXSAT solver that outperforms state-of-the-art WPMS solvers on the 2014 Evaluation on industrial instances.
Introduction
Maximum Satisfiability (MaxSAT) is a fundamental optimization problem in computer science, crucial for applications ranging from bioinformatics to software verification. In MaxSAT, one must satisfy a set of "hard" clauses while maximizing the number (or total weight) of satisfied "soft" clauses. Historically, solvers have specialized in either core-guided (lower bound) or correction-set-guided (upper bound) search strategies.
The researchers introduce PRIMALDUALMAXSAT, an algorithm that bridges these two search strategies. By alternating between cores and correction sets and using lightweight, incremental formula transformations, it achieves state-of-the-art performance on industrial benchmarks without the overhead of heavy mathematical constraints.
Methodology
The core innovation of PRIMALDUALMAXSAT lies in its "best of both worlds" approach to search.
The Primal-Dual Loop
In each iteration, the algorithm performs a partition phase. It utilizes a SAT solver to determine if a candidate set of clauses constitutes a valid core or a valid correction set. The solver dynamically decides which to find based on the current state, allowing for a flexible search process.
Succinct Transformations
To avoid the bloat associated with traditional Pseudo-Boolean (PB) constraints, the authors employ local formula rewrites:
- TransformCore: Based on the MAXRES algorithm, this handles lower-bound updates.
- TransformCSet: A novel, lightweight transformation for correction sets that uses a minimal number of fresh variables and clauses to block certain solutions.
These transformations are succinct (linear in size), allowing the solver to maintain its "learnt clauses" across iterations, significantly speeding up the incremental solving process.
Experimental Results
The algorithm was evaluated using the industrial instances from the 2014 Max-SAT Evaluation, covering domains such as bioinformatics (haplotyping), software upgrading (packup), and circuit debugging.
Performance and Robustness
The variant $PD^m$, which incorporates a core-minimization step, emerged as the overall winner. It consistently solved more instances within the 3600-second time limit than any other tool.
As shown in the cactus plot above, the PRIMALDUAL solvers ($PD$ and $PD^m$) demonstrate superior robustness, solving a higher total number of instances as time progresses compared to competitors like evac and msuoll (represented as msu-oll-sn-wo in the plot).
Specifically, on Weighted Partial MaxSAT (WPMS) industrial instances, $PD^m$ solved 365 instances, outperforming the runner-up evac which solved 354. The algorithm also showed significant efficiency gains in specific domains; for example, it was approximately 3x faster than competitors on "pref. plan" and "One path" benchmarks.
Conclusion
The success of PRIMALDUALMAXSAT highlights the power of duality in optimization. By theoretically proving and empirically demonstrating that cores and correction sets have complementary strengths, the authors provide a more robust framework for MaxSAT solving. Moving away from heavy Pseudo-Boolean constraints toward leaner, local transformations ensures that the underlying SAT engine remains efficient. Future work may involve refining upper-bound guarantees and exploring more direct handling of weights in the transformations.
This paper is based on research presented at IJCAI 2015 by researchers from Microsoft Research and Carnegie Mellon University.
Summary updated