Introduction
The Maximum Satisfiability (Max-SAT) problem is a cornerstone of combinatorial optimization, with applications ranging from circuit debugging to bioinformatics. Exact solvers typically employ a Branch-and-Bound (BnB) framework, where the efficiency of the search is heavily dependent on the quality of the lower bound (LB)—an estimate of the minimum number of unsatisfied clauses in a given subproblem.
Current lower-bound methods often suffer from three primary inefficiencies:
- Redundancy: Solvers frequently rediscover identical inconsistencies as they traverse the search tree.
- Wasted Computational Effort: Effort expended on computing lower bounds that do not lead to immediate pruning is often discarded.
- Non-monotonicity: In certain solvers, the lower bound can counter-intuitively decrease deeper in the search tree, hindering pruning efficiency.
This paper introduces "within-problem learning" to address these issues, allowing search tree nodes to inherit and refine inconsistent subformulas from their parent nodes.
Methodology: The IncMax Algorithm
The proposed IncMax algorithm implements within-problem learning through several key mechanisms:
- Inconsistency Inheritance: Child nodes inherit a set of "inconsistent subformulas" (ISS) from their parents. Since an inconsistency in a general formula remains valid when variables are assigned, this approach preserves previous computational work.
- Subformula Shrinking: Through Unit Propagation (UP), inherited inconsistent subformulas can be simplified as variables are assigned. Smaller subformulas are more efficient, as they "free up" clauses to participate in new, disjoint inconsistencies, potentially increasing the lower bound.
- Selective Learning ($\alpha$-ratio): To avoid overhead, learning is triggered only when the search is close to a potential prune, determined by a ratio ($\alpha$) between the current lower bound and the upper bound.
- Adaptive Failed Literal (FL) Detection: The solver dynamically monitors the success rate of expensive FL detection. If FL has not recently contributed to backtracks, it is skipped to conserve time.
Experimental Evaluation
The researchers evaluated the incmaxsatz and incmaxsatz+fl solvers using benchmarks from the Max-SAT Evaluations 2006 and 2007. These included:
- Random Max-2-SAT: Instances with 100 and 140 variables.
- Random Max-3-SAT: Instances with 70 and 80 variables.
- Structured Benchmarks: Classic instances such as
brock(clique),c-fat,hamming,johnson, andkeller.
Results and Discussion
The performance of incmaxsatz was compared against state-of-the-art solvers, including the original maxsatz, Toolbar3.0, and MiniMaxSat.
Efficiency and Pruning Power
On 100-variable Max-2-SAT instances, incmaxsatz demonstrated significant speedups over maxsatz. As the number of clauses increased, the performance gap widened, highlighting the scalability of the learning approach.
The improved efficiency is directly attributable to the increased pruning power of the inherited lower bounds. The incmaxsatz solver consistently explored fewer branches than maxsatz, confirming that the learned inconsistencies lead to a more compact search tree.
Performance on Structured Benchmarks
In structured problem domains, incmaxsatz+fl emerged as the superior solver. It outperformed Toolbar3.0 and MiniMaxSat on nearly all benchmarks, often solving instances multiple times faster. For example, on the san benchmark, it achieved a 3x speedup over the next best competitor.
Conclusion and Future Work
Within-problem learning transforms static lower bound calculation into a dynamic learning process. By treating inconsistent subformulas as reusable assets, the incmaxsatz solver achieves state-of-the-art performance.
Future research will focus on extending these techniques to weighted and partial Max-SAT variants, which are highly relevant for industrial applications. Additionally, further investigation into parameter sensitivity and memory management for extremely large problem instances is warranted.
Summary updated