# 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: **131 times**

Last updated: **Sep 09 '17**

Line segments instersection algorithm

Rekursive Generator which fetches a subset of elements on demand

Finding the maximum of a parameter

Rational reconstruction in ring of integers

About algorithm for testing whether a point is in a V-polyhedron

Can I show ordered sets in order?

Sympy integration algorithm towards -infinity

Elliptic curve scalar multiplication algorithm

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

Problem of m travelling salesmen (TSP) in Sage. [Linear programming] [closed]

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?