CAMA: A Multi-Valued Satisfiability Solver

Abstract

This paper presents the multi-valued SAT solver CAMA. CAMA generalizes the recently developed speed-up techniques used in state-of-the-art binary SAT solvers, such as the two-literal-watching scheme for Boolean constraint propagation (BCP), conflict-based learning with identifying the first unique implication point (UIP), and non-chronological back-tracking. In addition, a novel minimum value set (MVS) technique is introduced for improving the efficiency of conflict-based learning. By analyzing the conflict clauses, MVS can potentially prune conflicting space that has not been searched before. Two different decision heuristics are discussed and evaluated. Finally the performance of CAMA is compared with Chaff using on a one-hot-encoding scheme. The experimental results show that, for MV-SAT problems with large variable domains, CAMA outperforms Chaff.