Ask Your Question
0

Set Covering Algorithm

asked 2017-09-08 18:02:27 -0600

Antonio gravatar image

Is there a Sage implementation of the Set Covering Algorithm?

Thanks in advance

edit retag flag offensive close merge delete

Comments

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

slelievre gravatar imageslelievre ( 2017-09-08 22:46:22 -0600 )edit

1 answer

Sort by ยป oldest newest most voted
1

answered 2017-09-09 04:05:49 -0600

tmonteil gravatar image

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 more

Comments

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

fidbc gravatar imagefidbc ( 2017-09-09 21:43:48 -0600 )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 gravatar imageAntonio ( 2017-09-11 08:34:29 -0600 )edit

Your Answer

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

Add Answer

Question Tools

1 follower

Stats

Asked: 2017-09-08 18:02:27 -0600

Seen: 91 times

Last updated: Sep 09