Perturbed message passing for constraint satisfaction problems

MaRDI QIDQ5744803zbMATH OpenFDO

Authors Siamak Ravanbakhsh, Russell Greiner

Publication date 19 February 2016

Full work available at URL https://arxiv.org/abs/1401.6686, http://jmlr.csail.mit.edu/papers/v16/ravanbakhsh15a.html

zbMATH Keywords

belief propagationconstraint satisfaction problemdecimationGibbs samplingmessage passingsurvey propagation

Mathematics Subject Classification ID

Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)

Recommendations

• Survey propagation: An algorithm for satisfiability
• A new look at survey propagation and its generalizations
• Theory and Applications of Satisfiability Testing
• Complete Convergence of Message Passing Algorithms for Some Satisfiability Problems
• Belief propagation guided decimation algorithms for random constraint satisfaction problems with growing domains

Cited in

(6)

• An Ising model inspired extension of the product-based MP framework for SAT
• Local entropy as a measure for sampling solutions in constraint satisfaction problems
• Convergence analysis of distributed inference with vector-valued Gaussian belief propagation
• Belief propagation guided decimation algorithms for random constraint satisfaction problems with growing domains
• Streamlining variational inference for constraint satisfaction problems
• Belief propagation: accurate marginals or accurate partition function—where is the difference?

Describes a project that uses

Uses Software

• LibDAI

This page was built for publication: Perturbed message passing for constraint satisfaction problems

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