<p>sometimes with various CS optimization problems, the best available or most evolved implementations can be found in EE applications. in this case, consider <a href="http://en.wikipedia.org/wiki/Espresso_heuristic_logic_minimizer" rel="nofollow">Espresso</a>, a logic minimizer. its open source and mainly written in C. it has a built in [exact] and also heuristic set cover as a subroutine after generating prime implicants for SAT. the exact covering is chosen with a command line switch.</p>

<p>ie it implements the <a href="http://en.wikipedia.org/wiki/Quine_McCluskey" rel="nofollow">Quine-McCluskey</a> method where set cover is part of the final optimization. there is some research on an improved exact set cover (also called the "minimum canonical cover") by McGeer et al called <a href="http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.51.4580" rel="nofollow">Espresso Signature</a> which was implemented but may be more difficult to obtain source code. </p>

<p>note the set cover algorithms are apparently decoupled in the code but possibly not decoupled in the <a href="http://bear.ces.cwru.edu/eecs_cad/man_octtools_espresso.html" rel="nofollow">interface</a>. ie it might require a little bit of "wrapper" coding to provide a direct interface to the set cover subroutines. another possibility is using monotone formula inputs in which there are no "derived" prime implicants other than those supplied as input in which the entire logic minimization reduces to set cover only.</p>

CC BY-SA 3.0
2012-09-20T22:57:33.570Z
note the optimum cover takes exponential time in worst case and the heuristics run in less time but dont guarantee the optimum which may be "good enough" for many applications
vzn
CC BY-SA 3.0
2012-09-20T15:22:29.873Z
2012-09-20T15:22:29.873Z
vzn
<p>Does anyone know of any tools that solve the approximate minimum set cover problem?</p>

<p>I know of the greedy algorithm (which is straightforward to implement myself), but I've also been reading about more sophisticated algorithms/heuristic that do better on many problems in practice.  (e.g., <a href="http://www.dei.unipd.it/~fisch/papers/survey_set_covering_problem.pdf" rel="nofollow">Algorithms for the Set Covering Problem</a> by Caprara et al.)  Are there any implementations generally available?  Any tools that others can use to find approximately optimal solutions, for large problem instances?  I'd prefer to use an existing tool, rather than try to understand and implement these sophisticated algorithms myself.</p>

CC BY-SA 3.0
2012-09-17T07:37:16.267Z
I would welcome feedback about whether this question is suitable, on-topic, and a good fit for this site.   (For instance, should I ask on [CS.SE](http://cs.stackexchange.com/) instead?)
D.W.
CC BY-SA 3.0
2012-09-20T00:46:40.627Z
see [about finding code for algorithms](http://meta.cstheory.stackexchange.com/questions/1101/questions-about-finding-code-for-algorithms). imho there are particular algorithms that have a TCS flavor with set covering definitely affirmative... try also "application-of-theory" tag
vzn
<ds.algorithms><optimization><set-cover><implementation>
Implementation that solves minimum set cover
D.W.
# Implementation that solves minimum set cover

(Asked by: username_0 on 2012-09-15)

Does anyone know of any tools that solve the approximate minimum set cover problem?

I know of the greedy algorithm (which is straightforward to implement myself), but I've also been reading about more sophisticated algorithms/heuristic that do better on many problems in practice. (e.g., [Algorithms for the Set Covering Problem](http://www.dei.unipd.it/~fisch/papers/survey_set_covering_problem.pdf) by Caprara et al.) Are there any implementations generally available? Any tools that others can use to find approximately optimal solutions, for large problem instances? I'd prefer to use an existing tool, rather than try to understand and implement these sophisticated algorithms myself.

**Tags:** ds.algorithms, optimization, set-cover, implementation

> **Comments:**
> **username_0**: I would welcome feedback about whether this question is suitable, on-topic, and a good fit for this site.   (For instance, should I ask on [CS.SE](http://cs.stackexchange.com/) instead?)  
> **username_1**: see [about finding code for algorithms](http://meta.cstheory.stackexchange.com/questions/1101/questions-about-finding-code-for-algorithms). imho there are particular algorithms that have a TCS flavor with set covering definitely affirmative... try also "application-of-theory" tag  

---

## 1 answers

### Answer by username_1 on 2012-09-20. Score: 3

sometimes with various CS optimization problems, the best available or most evolved implementations can be found in EE applications. in this case, consider [Espresso](http://en.wikipedia.org/wiki/Espresso_heuristic_logic_minimizer), a logic minimizer. its open source and mainly written in C. it has a built in [exact] and also heuristic set cover as a subroutine after generating prime implicants for SAT. the exact covering is chosen with a command line switch.

ie it implements the [Quine-McCluskey](http://en.wikipedia.org/wiki/Quine_McCluskey) method where set cover is part of the final optimization. there is some research on an improved exact set cover (also called the "minimum canonical cover") by McGeer et al called [Espresso Signature](http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.51.4580) which was implemented but may be more difficult to obtain source code.

note the set cover algorithms are apparently decoupled in the code but possibly not decoupled in the [interface](http://bear.ces.cwru.edu/eecs_cad/man_octtools_espresso.html). ie it might require a little bit of "wrapper" coding to provide a direct interface to the set cover subroutines. another possibility is using monotone formula inputs in which there are no "derived" prime implicants other than those supplied as input in which the entire logic minimization reduces to set cover only.

> **Comments:**
> **username_1**: note the optimum cover takes exponential time in worst case and the heuristics run in less time but dont guarantee the optimum which may be "good enough" for many applications  

---

