Practical/heuristic algorithm for multi set-cover

Question

Consider a universe $N$ containing $n$ elements, and a collection of sets $\mathcal{C}$, over $N$. The $k$-multiset multicover (MSMC) problem is to cover all elements of the universe $N$ at least $k$ number of times using minimum number of sets from $\mathcal{C}$. (When $k=1$, the problem reduces to min-set cover).

Are there any heuristics out there with 'good' performance on 'real' data for $n=1000$ and $|\mathcal{C}| = 1000$?

Answer 1

You'd have to tweak the limits (in particular max_level may be too low), but for at least some "real" problems this is within the bounds of Knuth's algorithm M.

See also

• The documentation of algorithm D, which describes the basic file format; the documentation of algorithm M just explains the changes made to generalise it;
• the latest preprint of fascicle 5c of The Art of Computer Programming, which at some point will get as far as explaining the algorithm, but already has a number of exercises that will give you an idea of the problems that Knuth has solved with it.