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