DPMS: An ADD-Based Symbolic Approach for Generalized MaxSAT Solving
This addresses a bottleneck in Boolean reasoning for researchers and practitioners by enabling native handling of hybrid constraints and generalized formulations, though it appears incremental as it builds on existing ADD and project-join-tree methods.
The authors tackled the problem of solving generalized MaxSAT problems with non-CNF hybrid constraints, such as XORs, by proposing DPMS, a dynamic-programming approach based on Algebraic Decision Diagrams, which scales well on low-width instances and solves problems where other algorithms fail.
Boolean MaxSAT, as well as generalized formulations such as Min-MaxSAT and Max-hybrid-SAT, are fundamental optimization problems in Boolean reasoning. Existing methods for MaxSAT have been successful in solving benchmarks in CNF format. They lack, however, the ability to handle 1) (non-CNF) hybrid constraints, such as XORs and 2) generalized MaxSAT problems natively. To address this issue, we propose a novel dynamic-programming approach for solving generalized MaxSAT problems with hybrid constraints -- called \emph{Dynamic-Programming-MaxSAT} or DPMS for short -- based on Algebraic Decision Diagrams (ADDs). With the power of ADDs and the (graded) project-join-tree builder, our versatile framework admits many generalizations of CNF-MaxSAT, such as MaxSAT, Min-MaxSAT, and MinSAT with hybrid constraints. Moreover, DPMS scales provably well on instances with low width. Empirical results indicate that DPMS is able to solve certain problems quickly, where other algorithms based on various techniques all fail. Hence, DPMS is a promising framework and opens a new line of research that invites more investigation in the future.