DPSampler: Exact Weighted Sampling Using Dynamic Programming

The problem of exact weighted sampling of solutions of Boolean formulas has applications in Bayesian inference, testing, and verification. The state-of-the-art approach to sampling involves carefully decomposing the input formula and compiling a data structure called d-DNNF in the process. Recent work in the closely connected field of model counting, however, has shown that smartly composing different subformulas using dynamic programming and Algebraic Decision Diagrams (ADDs) can outperform d-DNNF-style approaches on many benchmarks. In this work, we present a modular algorithm called DPSampler that extends such dynamic-programming techniques to the problem of exact weighted sampling. DPSampler operates in three phases. First, an execution plan in the form of a project-join tree is computed using tree decompositions. Second, the plan is used to compile the input formula into a succinct tree-of-ADDs representation. Third, this tree is traversed to generate a random sample. This decoupling of planning, compilation and sampling phases enables usage of specialized libraries for each purpose in a black-box fashion. Further, our novel ADD-sampling algorithm avoids the need for expensive dynamic memory allocation required in previous work. Extensive experiments over diverse sets of benchmarks show DPSampler is more scalable and versatile than existing approaches.

Authors

• Jeffrey M. Dudek
• Aditya A. Shrotri
• Moshe Y. Vardi Rice University

Keywords

• Constraint Satisfaction and Optimization: Applications
• Constraint Satisfaction and Optimization: Constraint Satisfaction
• Constraint Satisfaction and Optimization: Other
• Constraint Satisfaction and Optimization: Satisfiabilty
• Constraint Satisfaction and Optimization: Solvers and Tools