# DPMS: An ADD-Based Symbolic Approach for Generalized MaxSAT Solving

arXiv: https://arxiv.org/abs/2205.03747 · HTML: https://mlsanity.com/paper/2205.03747/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 9 of its 71 references that are in the map.
- First posted on arXiv 8 May 2022.

## Builds on (most cited first, 9 of 9)

- [The Model Counting Competition 2020](https://mlsanity.com/paper/2012.01323/) (2020)
- [FAQ: Questions Asked Frequently](https://mlsanity.com/paper/1504.04044/) (2015)
- [ADDMC: Weighted Model Counting with Algebraic Decision Diagrams](https://mlsanity.com/paper/1907.05000/) (2019)
- [FourierSAT: A Fourier Expansion-Based Algebraic Framework for Solving Hybrid Boolean Constraints](https://mlsanity.com/paper/1912.01032/) (2019)
- [DepQBF 6.0: A Search-Based QBF Solver Beyond Traditional QCDCL](https://mlsanity.com/paper/1702.08256/) (2017)
- [Computing Tree Decompositions with FlowCutter: PACE 2017 Submission](https://mlsanity.com/paper/1709.08949/) (2017)
- [DPMC: Weighted Model Counting by Dynamic Programming on Project-Join Trees](https://mlsanity.com/paper/2008.08748/) (2020)
- [On Continuous Local BDD-Based Search for Hybrid SAT Solving](https://mlsanity.com/paper/2012.07983/) (2020)
- [Positive-instance driven dynamic programming for treewidth](https://mlsanity.com/paper/1704.05286/) (2017)

## Built on by (most cited first, 3 of 3)

- [Solving Quantum-Inspired Perfect Matching Problems via Tutte's Theorem-Based Hybrid Boolean Constraints](https://mlsanity.com/paper/2301.09833/) (2023)
- [DPO: Dynamic-Programming Optimization on Hybrid Constraints](https://mlsanity.com/paper/2205.08632/) (2022)
- [DPER: Dynamic Programming for Exist-Random Stochastic SAT](https://mlsanity.com/paper/2205.09826/) (2022)

## Abstract (arXiv)

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 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.