Weighted Maximum Satisfiability

<span></span><p dir="ltr"><span><b>The Problem</b></span></p><p dir="ltr"><span>This is a generalization of the maximum satisfiability problem (a seperate bounty) is briefly described in </span><a href="http://en.wikipedia.org/wiki/Maximum_satisfiability_problem"><span>http://en.wikipedia.org/wiki/Maximum_satisfiability_problem</span></a><span>. Each clause has a corresponding weight, and the weight of a solution is just the sum of the weights of the clauses that are satisfied in that solution. The goal is to maximize this weight. Note that maximum satisfiability is just this problem with every clause weight equal to 1.</span></p><p dir="ltr"><span><b>The Interface</b></span></p><p dir="ltr"><span>The algorithm should take a list of clauses &#160;(in string form, see&#160;</span><a href="http://algorithmia.com/algorithms/cloncaric/sat">http://algorithmia.com/algorithms/cloncaric/sat</a>&#160;for an example of how to do the encoding<span>), where we interpret the list of clauses as the conjunction of all of them, as well as a list of doubles, where the ith double in the list is the weight of the ith clause. &#160;The output should be a HashMap&lt;String,Object&gt; with two keys that contains the solution and number of satisfied clauses. The first key should be &#8220;solution&#8221;, whose value is a HashMap&lt;String,Boolean&gt; in which each key is a variable name and its corresponding value is it&#8217;s truth assignment in the solution. The second key is a string &#8220;weight&#8221;, whose value is the number of the total weight of &#160;satisfied clauses (a double).</span></p><p dir="ltr"><span><b>The Algorithm</b></span></p><span>The simplest solution would probably be to build this on top of Binary Integer Programming (</span><a href="https://algorithmia.com/algorithms/JaCoP/BinaryIntegerProgramming"><span>https://algorithmia.com/algorithms/JaCoP/BinaryIntegerProgramming</span></a><span>), which is itself built on top of JaCoP (</span><a href="http://www.jacop.eu/"><span>http://www.jacop.eu/</span></a><span>).</span>
  • {{comment.username}}
submission(s) pending review
Bounty expires in
Bounty expired
(no tags)