# Set Covering Algorithm

Is there a Sage implementation of the Set Covering Algorithm?

Thanks in advance

1

I guess you speak about the "set cover problem", which is a well known NP-hard problem (Karp). Sage does not have this though it could be added as a method of `IncidenceStructure`

.

You can however code it yourself :

- look at the
`MixedIntegerProgramming`

examples and tutorial - note that sets are not hashable, so a MIP variable could not be indexed by sets. However, if your sets belong to a list, you just have to index them by their position in the list.

Asked: **
2017-09-08 18:02:27 -0500
**

Seen: **84 times**

Last updated: **Sep 09**

speed up execution time of script (Cython or other...)

Number of line segments in a group - algorithm

Line segments instersection algorithm

Rational reconstruction in ring of integers

How to use Sage to find a pair of vertex-disjoint paths of minimal total length?

Error with .cardinality(algorithm='sae') for elliptic curve

Code stopped compiling out of nowhere for no apparent reason

Copyright Sage, 2010. Some rights reserved under creative commons license. Content on this site is licensed under a Creative Commons Attribution Share Alike 3.0 license.

Could you provide a reference to the "Set Covering Algorithm" you mention?