Set Covering Algorithm

asked 2017-09-09 01:02:27 +0100

Antonio
11 ●1 ●4

Is there a Sage implementation of the Set Covering Algorithm?

Thanks in advance

Comments

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

slelievre ( 2017-09-09 05:46:22 +0100 )edit

add a comment

answered 2017-09-09 11:05:49 +0100

tmonteil
27413 ●31 ●204 ●517 http://wiki.sagemath.o...

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.

edit flag offensive delete link

Comments

Maybe another option is to index variables by the sorted tuple representing the set?

fidbc ( 2017-09-10 04:43:48 +0100 )edit

Thanks, I'm aware of the fact that the set cover problem is NP hard but so is the TSP and Sage has a method for solving these type of problems.

Antonio ( 2017-09-11 15:34:29 +0100 )edit

add a comment

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Set Covering Algorithm

Comments

1 Answer

Comments

Your Answer

Question Tools

Stats

Related questions

Set Covering Algorithm edit

Comments

1 Answer

Comments

Your Answer

Question Tools

Stats

Related questions

Set Covering Algorithm