<p>You'd have to tweak the limits (in particular <code>max_level</code> may be too low), but for at least some "real" problems this is within the bounds of Knuth's <a href="http://www-cs-faculty.stanford.edu/~knuth/programs/dlx3.w" rel="nofollow noreferrer">algorithm M</a>.</p>

<p>See also</p>

<ul>
<li>The documentation of <a href="http://www-cs-faculty.stanford.edu/~knuth/programs/dlx1.w" rel="nofollow noreferrer">algorithm D</a>, which describes the basic file format; the documentation of algorithm M just explains the changes made to generalise it;</li>
<li>the <a href="http://www-cs-faculty.stanford.edu/~knuth/fasc5c.ps.gz" rel="nofollow noreferrer">latest preprint</a> of fascicle 5c of <em>The Art of Computer Programming</em>, 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.</li>
</ul>

CC BY-SA 3.0
2017-08-24T07:17:48.180Z
2017-08-24T07:17:48.180Z
Peter Taylor
<p>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).</p>

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

CC BY-SA 3.0
2017-08-24T07:34:10.123Z
Have you tried formulating this as an ILP and running off the shelf solvers?
daniello
<ds.algorithms><reference-request><approximation-algorithms><heuristics>
Practical/heuristic algorithm for multi set-cover
Vivek Bagaria
# Practical/heuristic algorithm for multi set-cover

(Asked by: username_0 on 2017-08-23)

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

**Tags:** ds.algorithms, reference-request, approximation-algorithms, heuristics
> **Comments:**
> **username_1**: Have you tried formulating this as an ILP and running off the shelf solvers?  

---

## 1 answers

### Answer by username_2 on 2017-08-24. Score: 2

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](http://www-cs-faculty.stanford.edu/~knuth/programs/dlx3.w).

See also

* The documentation of [algorithm D](http://www-cs-faculty.stanford.edu/~knuth/programs/dlx1.w), which describes the basic file format; the documentation of algorithm M just explains the changes made to generalise it;
* the [latest preprint](http://www-cs-faculty.stanford.edu/~knuth/fasc5c.ps.gz) 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.


---

