exact cover set problem 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.
To convert to MaxSAT:


For each set $ S $ introduce a fresh variable $ X_S $.
If two sets $ S $ and $ D $ intersect, produce the hard clause $\lnot X_S\lor \lnot X_D$.
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.
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.