Implementation that solves minimum set cover

Question

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 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.

Answer 1

sometimes with various CS optimization problems, the best available or most evolved implementations can be found in EE applications. in this case, consider Espresso, 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 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 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. 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.