1

I'm having trouble defining this problem space (example below), where to look, what to search etc. and would appreciate any help with suggestions of algorithms or libraries that I should look into. I've spent some time looking into constraint programming & OR-Tools but most problems seem to be scalar and I haven't yet been able to figure out how to use any of the solutions effectively to solve my problem. My project is in C# (.NET Core 3.0)

EXAMPLE:

Say I have 3 objects (o) that each have associated attributes (a):

//object 1 has attributes 1, 2, and 3
o1 { a1, a2, a3 }
//object 2 has attributes 1 and 3
o2 { a1, a3 }
//object 3 has attributes 2 and 3
o3 { a2, a3 }

Then say that a person is able to select certain attributes they are interested in, specifically in this example the person is interested in:

//the person wants to see objects or groups/sets of objects that have attributes 1 and 2
a1 and a2

The goal then would be to return to the person set(s) of the objects that best contain the selected attributes with the least number of objects needed. In this case the desired return result would be:

//object 1 is the best solution because it contains attributes 1 and 2 by itself
1. o1 
//object's 2 and 3 together is the 2nd best solution because they contain attributes 1 and 2 between themselves
2. o2 and o3

This is a very simple example but the actual scale of the objects and attributes associated to those objects will require something much more efficient than brute force. Thanks in advance!

  • 1
    What is "the actual scale of the objects and attributes" here? If there are 100 objects and 100 attributes, that may require a certain solution; if there are 100,000,000 objects and 100 attributes, a different solution; and if there are 100,000,000 objects and 100,000,000 attributes, yet another solution. Also, is it completely mandatory for the suggested set of objects to contain all of the desired attributes, or is it also acceptable (but worse) if a set contains most but not all of the desired attributes? – Tanner Swett Dec 4 '20 at 3:15
  • 3
    Finally, is it absolutely necessary for the algorithm to find the set with the absolute least number of objects, or would you also accept, say, an algorithm which runs a million times faster but only returns the best solution 99% of the time? – Tanner Swett Dec 4 '20 at 3:17
  • So the max number of objects currently is about 100 (with the capacity to grow over time) and the number of possible attributes is around 110 (again with the capacity to grow over time). I imagine the ideal solution would be the faster algorithm that is accurate 99%. It is very likely that the objects (or sets of objects) will not fully cover all desired attributes (meaning it is very unlikely there will be full coverage with 1 object and still not a great chance for full coverage with a set of the objects). Many of the objects also cover the same or almost the same attributes. – 3r1nnn Dec 4 '20 at 14:46
7

Unfortunately, this is known as a Set Cover problem, and this type of problem is known to be NP-Complete.

You can find approximations to the correct answer in polynomial time, but a guaranteed correct answer is going to be unfindable for anything but very small datasets.

  • well, it would be findable, but with no better algorithm than "brute-force" (try and compare all possibilities) – Pac0 Dec 4 '20 at 13:31
  • 2
    @Pac0 Right. I should have said "is going to be unfindable in anything resembling a reasonable timeframe for anything but very small datasets." – Beska Dec 4 '20 at 13:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.