Technical reports
Survey propagation applied to weighted partial maximum satisfiability
Richard Russell, Sean B. Holden
March 2016, 15 pages
DOI: 10.48456/tr-883
Abstract
We adapt the survey propagation method for application to weighted partial maximum satisfiability (WPMax-SAT) problems consisting of a mixture of hard and soft clauses. The aim is to find the truth assignment that minimises the total cost of unsatisfied soft clauses while satisfying all hard clauses. We use fixed points of the new set of message passing equations in a decimation procedure to reduce the size of WPMax-SAT problems. We evaluate this strategy on randomly generated WPMax-SAT problems and find that message passing frequently converges to non-trivial fixed points, and in many cases decimation results in simplified problems for which local search solvers are able to find truth assignments of comparable cost faster than without decimation.
Full text
PDF (0.3 MB)
BibTeX record
@TechReport{UCAM-CL-TR-883, author = {Russell, Richard and Holden, Sean B.}, title = {{Survey propagation applied to weighted partial maximum satisfiability}}, year = 2016, month = mar, url = {https://www.cl.cam.ac.uk/techreports/UCAM-CL-TR-883.pdf}, institution = {University of Cambridge, Computer Laboratory}, doi = {10.48456/tr-883}, number = {UCAM-CL-TR-883} }