Set Covering Algorithm

Comments

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

slelievre ( 7 years ago )

tmonteil
27473 ●32 ●205 ●519 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.

link

Comments

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

fidbc ( 7 years ago )

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 ( 7 years ago )

add a comment

Your Answer

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

Comments

1 Answer

Comments

Your Answer

Question Tools

Stats

Related questions

Set Covering Algorithm savecancel

Comments

1 Answer

Comments