What is the right algorithm to solve this problem?

Question

The problem is - We have a series of boxes (A, B, C, D, ...). Each box contains bricks of different colours. For eg.

Box A - red, blue
Box B - blue, red, green
... and so on...

and there are multiple versions of each of the boxes -

Box A1 - red, blue
Box A2 - green, red, yellow
...
Box B1 - blue, red, green
Box B2 - blue, red
... and so on ... 

The idea is to choose one of the versions of each of the boxes, such the total number of unique bricks is minimum. For eg. in this example -

Box A1 + Box B1 = blue, red, green (3 unique bricks)

but

Box A2 + Box B1 = blue, red, green, yellow (4 unique bricks)

So Box A1 + Box B1 is the better choice.

We need to build a collection of such boxes, choosing at least one version of each box such that the total unique number of bricks is minimum.

Is there a known algorithm to solve this problem?

• Kilian Foth: This seems to be one of the many variants of the set covering problem, which is NP-hard. This would mean that there is not better correct algorithm than the obvious "try everything and compare". There may be incorrect, e.g. approximate algorithms which improve on this bound.

Answer 1

As mentioned in the comments this problem can be seen as a Set Covering Problem. If you are interested by the optimal solution you can solve it using a Mixed Integer Programming (MIP) solver. For Open source solver you can give a look at glpk or cbc. If you are interested in proprietary solver you can give a look at Cplex, Gurobi or XPress-MP.

You could model it in the following way:

• Associate a binary variable to each individual brick of the problem. Your objective function will be to minimise the sum of those positive variable.

• Associate a binary variable to every possible variation of your boxes. For each box add a constraint stating that the sum of the binary variable associated with variation of this box should be equal to one.

• Finally, for every combination of box variation and brick being part of that variation, add a constraint stating that the binary associated with the box variation should be less or equal to the binary variable associated with the brick.