Leveraging belief propagation, backtrack search, and statistics for model counting

DOI10.1007/S10479-009-0680-7MaRDI QIDQ545553zbMATH OpenOpenAlexFDO

Authors Lukas Kroc, Ashish Sabharwal, Bart Selman

Publication date 22 June 2011

Published in Annals of Operations Research (Search for Journal in Brave)

Full work available at URL http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.147.1370

zbMATH Keywords

lower boundsSATmodel countingupper boundsBoolean satisfiabilitynumber of solutionsbpcountminicount

Mathematics Subject Classification ID

Combinatorial optimization (90C27)

Recommendations

• Leveraging Belief Propagation, Backtrack Search, and Statistics for Model Counting
• Fast and flexible probabilistic model counting
• Exploiting structure in weighted model counting approaches to probabilistic inference
• A new probabilistic algorithm for approximate model counting
• On probabilistic inference by weighted model counting
• Algorithms for Propositional Model Counting
• Algorithms for propositional model counting
• Theory and Applications of Satisfiability Testing
• Model counting: a new stategy for obtaining good bounds

Cites work

• scientific article; zbMATH DE number 48812 (Why is no real title available?)
• scientific article; zbMATH DE number 1983901 (Why is no real title available?)
• scientific article; zbMATH DE number 3249395 (Why is no real title available?)
• scientific article; zbMATH DE number 956863 (Why is no real title available?)
• A Computing Procedure for Quantification Theory
• A machine program for theorem-proving
• A new look at survey propagation and its generalizations
• CCCP Algorithms to Minimize the Bethe and Kikuchi Free Energies: Convergent Alternatives to Belief Propagation
• Characterizing Propagation Methods for Boolean Satisfiability
• Constructing Free-Energy Approximations and Generalized Belief Propagation Algorithms
• Leveraging Belief Propagation, Backtrack Search, and Statistics for Model Counting
• Model counting: a new stategy for obtaining good bounds
• Solving \#SAT and Bayesian inference with backtracking search
• Stochastic Boolean satisfiability
• The complexity of computing the permanent
• Theory and Applications of Satisfiability Testing
• Theory and Applications of Satisfiability Testing

Cited in

(8)

• Model counting with error-correcting codes
• Model counting: a new stategy for obtaining good bounds
• Approximate model counting via extension rule
• Two approximate algorithms for model counting
• Counting Models in Integer Domains
• Solving \#SAT and Bayesian inference with backtracking search
• Leveraging Belief Propagation, Backtrack Search, and Statistics for Model Counting
• Projected model counting: beyond independent support

Describes a project that uses

Uses Software

• RSat
• DIMACS
• Walksat
• MiniSat

This page was built for publication: Leveraging belief propagation, backtrack search, and statistics for model counting

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q545553)