Practical/heuristic algorithm for multi set-cover 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$?
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.