<p>To convert to MaxSAT:</p>

<ol>
<li>For each set $ S $ introduce a fresh variable $ X_S $.</li>
<li>If two sets $ S $ and $ D $ intersect, produce the hard clause $\lnot X_S\lor \lnot X_D$.</li>
<li>For each element $e$ produce the hard clause $\bigvee_{e\in S} X_S$, making sure that at least one set that contains $ e $ is selected.</li>
<li>For each set $ S$ with weight $W$ produce the soft clause $\lnot X_S$ with weight $W$, to minimize the total weight of selected sets.</li>
</ol>

<p>I wrote a Python script for this (<a href="http://sat.inesc-id.pt/~mikolas/excover" rel="nofollow">http://sat.inesc-id.pt/~mikolas/excover</a>). This is the most naïve encoding. I believe there are ways how to make it smaller.</p>

CC BY-SA 3.0
2018-02-22T06:58:03.973Z
Do you know any library for solving this?
kostrykin
CC BY-SA 3.0
2018-02-22T07:29:32.373Z
@theV0ID No and I'd be surprised if there was one. You can use my script to generate a MaxSAT encoding of the problem and then send it to a MaxSAT solver. You can use [mine](http://sat.inesc-id.pt/~mikolas/sw/mifumax/) but there are other (better ones). E.g. [msuncore](http://logos.ucd.ie/web/doku.php?id=msuncore) or [open-wbo](http://sat.inesc-id.pt/open-wbo/)
Mikolas
CC BY-SA 3.0
2018-02-22T17:36:42.633Z
Thanks, but as far as I can see, these all are exact solvers. Do you maybe know any approximate solvers?
kostrykin
CC BY-SA 3.0
2018-02-22T17:44:40.087Z
@theVOID correct. These are exact. There are some local search ones. Also some that look for local optima  (MCS). You can check out the maxsat competition. If you have some interesting instances, I could try to look at them.
Mikolas
CC BY-SA 3.0
2015-09-03T10:28:45.273Z
2015-09-03T10:28:45.273Z
Mikolas
<p>i am searching an heuristic algorithm for a weighted exact cover problem shown here: <a href="http://en.wikipedia.org/wiki/Exact_cover" rel="nofollow">http://en.wikipedia.org/wiki/Exact_cover</a></p>

<p>On my research i only found algorithm which calculates all solutions without any cost function, like <a href="http://en.wikipedia.org/wiki/Knuth%27s_Algorithm_X" rel="nofollow">http://en.wikipedia.org/wiki/Knuth%27s_Algorithm_X</a></p>

<p>Do you know some algorithm for that?</p>

<p>My problem has a Universe of size 200 and about 500 000 subsets, so it is not possible to calculate all solutions.</p>

<p>--------------EDIT--------------</p>

<p>Example:</p>

<p>Universe = { 1, 2 ,3 ,4 ,5 ,6 ,7}</p>

<p>Sets=[</p>

<p>{1,2,3,4}, Cost 10 </p>

<p>{5,6,7}, Cost 20</p>

<p>{5}, Cost 5</p>

<p>{6,7}, Cost 10
]</p>

<p>On this example i have to possible solutions {1,2,3,4} and {5,6,7} with cost 30 and the second solution is {1,2,3,4}, {5} and {6,7} with cost 25.</p>

CC BY-SA 3.0
2014-08-19T13:00:01.587Z
could this be converted to maxsat/sat?
Mikolas
CC BY-SA 3.0
2014-08-20T09:23:24.817Z
I don't think that it is converted to maxSat. Because i have only fixed conditions with the exact full cover, but with only the constraint that i want to minimize my global Cost.
Hunk
CC BY-SA 3.0
2014-08-20T15:20:15.613Z
and one more question. Can i proof is the problem is solvable without testing all combinations?
Hunk
CC BY-SA 3.0
2014-08-20T16:44:33.503Z
It seems to me that minimizing the global cost is exactly what maxsat would do. Introduce a variable $r_s$ for each set $s$, encode the condition the condition that each element in the set is touched exactly once, put a weight on each $r_c$ and minimize the cost.
Mikolas
CC BY-SA 3.0
2014-08-20T19:16:56.787Z
Ok so I wrote an encoding into maxsat an am getting 25 for your example; (here's the script)[sat.inesc-id.pt/~mikolas/excover]. The encoding is somewhat naive, let me know if you'd be interesting on improving on this.
Mikolas
CC BY-SA 3.0
2015-09-02T09:17:43.297Z
@Mikolas is this encoding scheme generate maximum value too. I want to know about encoding scheme you used here. Will it generate the sets which gives maximum value in this approach.
NARAYAN CHANGDER
<optimization><exact-cover>
exact cover set problem
Hunk
# exact cover set problem

(Asked by: username_0 on 2014-08-18)

i am searching an heuristic algorithm for a weighted exact cover problem shown here: <http://en.wikipedia.org/wiki/Exact_cover>

On my research i only found algorithm which calculates all solutions without any cost function, like <http://en.wikipedia.org/wiki/Knuth%27s_Algorithm_X>

Do you know some algorithm for that?

My problem has a Universe of size 200 and about 500 000 subsets, so it is not possible to calculate all solutions.

--------------EDIT--------------

Example:

Universe = { 1, 2 ,3 ,4 ,5 ,6 ,7}

Sets=[

{1,2,3,4}, Cost 10

{5,6,7}, Cost 20

{5}, Cost 5

{6,7}, Cost 10
]

On this example i have to possible solutions {1,2,3,4} and {5,6,7} with cost 30 and the second solution is {1,2,3,4}, {5} and {6,7} with cost 25.

**Tags:** optimization, exact-cover
> **Comments:**
> **username_1**: could this be converted to maxsat/sat?  
> **username_0**: I don't think that it is converted to maxSat. Because i have only fixed conditions with the exact full cover, but with only the constraint that i want to minimize my global Cost.  
> **username_0**: and one more question. Can i proof is the problem is solvable without testing all combinations?  
> **username_1**: It seems to me that minimizing the global cost is exactly what maxsat would do. Introduce a variable $r_s$ for each set $s$, encode the condition the condition that each element in the set is touched exactly once, put a weight on each $r_c$ and minimize the cost.  
> **username_1**: Ok so I wrote an encoding into maxsat an am getting 25 for your example; (here's the script)[sat.inesc-id.pt/~mikolas/excover]. The encoding is somewhat naive, let me know if you'd be interesting on improving on this.  
> **username_2**: @Mikolas is this encoding scheme generate maximum value too. I want to know about encoding scheme you used here. Will it generate the sets which gives maximum value in this approach.  

---

## 1 answers

### Answer by username_1 on 2015-09-03. Score: 3

To convert to MaxSAT:

1. For each set $ S $ introduce a fresh variable $ X\_S $.
2. If two sets $ S $ and $ D $ intersect, produce the hard clause $\lnot X\_S\lor \lnot X\_D$.
3. For each element $e$ produce the hard clause $\bigvee\_{e\in S} X\_S$, making sure that at least one set that contains $ e $ is selected.
4. For each set $ S$ with weight $W$ produce the soft clause $\lnot X\_S$ with weight $W$, to minimize the total weight of selected sets.

I wrote a Python script for this (<http://sat.inesc-id.pt/~mikolas/excover>). This is the most naïve encoding. I believe there are ways how to make it smaller.

> **Comments:**
> **username_3**: Do you know any library for solving this?  
> **username_1**: @theV0ID No and I'd be surprised if there was one. You can use my script to generate a MaxSAT encoding of the problem and then send it to a MaxSAT solver. You can use [mine](http://sat.inesc-id.pt/~mikolas/sw/mifumax/) but there are other (better ones). E.g. [msuncore](http://logos.ucd.ie/web/doku.php?id=msuncore) or [open-wbo](http://sat.inesc-id.pt/open-wbo/)  
> **username_3**: Thanks, but as far as I can see, these all are exact solvers. Do you maybe know any approximate solvers?  
> **username_1**: @theVOID correct. These are exact. There are some local search ones. Also some that look for local optima  (MCS). You can check out the maxsat competition. If you have some interesting instances, I could try to look at them.  

---

