# 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$?

• Have you tried formulating this as an ILP and running off the shelf solvers? – daniello Aug 24 '17 at 7:34

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.