Set cover: Generating test instances

Question

I'm looking forward to solve the Set Cover Problem using a genetic algorithm. I've been looking everywhere for some good test instances, but without any big success.

What I'm looking for would be some instances under the form: a set U = {1,2,...,n} and a collection of its subsets S={{1,2}, {4}, {3,4,5}}, where the union of S is U.

Of course that this is a small example, as I would like to find some bigger instances.

So, does anyone have any idea about a good source of this kind of instances, or maybe about a way of generating them?

Later edit: So I see that the question has been put on hold. My bad then, I will add a little bit more details.

Firstly, I've googled for some test instances for set cover problem. What I was expecting to find were some instances like the ones I've described above. Tough luck, I've found something similar to this. I must say that there were not that many details in the link which lend me to those instances.

So I began thinking a method of generating them. A pseudocodish solution:

given set G=[1,2....,n]
no_of_subsets  = random integer
subsets = []
for i in k: 
    subset = random.sample(G, random(0, len(G))
    subsets.add(subset)

Though I wasn't sure if union(subsets) = G, so there was where my doubts were, so that's why I was in need for some already produced test instances.

score 1 · Accepted Answer · answered May 27 '17 at 15:00

You can generate a set getting a random sample from a list of possible numbers. And them generate a list (with pre-determined size) of its subsets also by getting random samples with random size, and for the last subset you just complete what was missing so the sum of the subsets will be entire set.

Example:

import random

n = 100
m = 10 #size of set
l = 5 #size of list of subsets
possible_numbers = range(n)

U = set(random.sample(possible_numbers, m))

subsets = []
control = set()
for i in range(l - 1):
    sub_size = random.randrange(m)
    sub = set(random.sample(U, sub_size))
    subsets += [sub]
    control |= sub

rest = U - control     
if rest:
    subsets += [rest]

print(U)
--> {97, 99, 69, 9, 15, 52, 53, 55, 28, 30}

print(subsets)
--> [{28, 52, 69, 55}, {69}, {99, 28, 52, 55}, {69, 9, 15, 52, 53, 55}, {97, 30}]

Set cover: Generating test instances

1 Answers1