Minimizing colors: a variation of the knapsack algorithm?

Question

Working on a project I've met this problem, which I will reword here in terms outside of the real domain of the problem (I suppose I could talk about calibers of fireworks and shapes, but it would complicate even more the understanding). I'm looking for a (possibly approximate) algorithm to solve it.

I have n containers of various sizes, and m objects with different size occupations and different colors (objects can be multicolored, so the color of an object is truly a set).

My aim is to fit all the objects into the containers (i already know that's possible) such that the variety of colors is minimized per container. With "the variety of colors is minimized" I mean the sum of the number of different colors per container is minimal.

An example. I have two containers of size 2, and four objects, whose colors are {red}, {red, green}, {blue}, {blue, green}, each one of size 1. An optimal solution would be [{red}, {red, green}], [{blue}, {blue, green}], where the total variety is 2+2=4. A worse solution would be [{red}, {blue}], [{red, green}, {blue, green}], where the total variety is 2+3=5.

My guess is that the problem is NP hard, since it sounds more difficult than the knapsack problem: the value of objects is transformed in a negative value which moreover depends on the other objects inside the same container. But I have no good idea as how to tackle the problem for an approximate solution, which would be more than welcome anyway.

Answer 1

Bin-packing or Knapsack?

This problem appears to have more in common with the bin-packing problem than with the knapsack problem. In the knapsack problem, you only have one single knapsack to fill, but it has a capacity you must not exceed. And you must do this while maximizing the total value of the items you choose to put in. Here, you don't have to use up all the items.

In the bin packing problem, however, you have multiple bins each with a capacity. You are interested in minimizing the number of bins while fitting every item into some bin. You also have to respect the capacity constraint of each bin. Unlike in knapsack, here you have to use up all the items.

In your case, you are also trying to minimize the number of bins, only they can't fit into less than two. And you also want to use up all the objects. You didn't say much about the capacity constraint, but I'm assuming you also have to respect that as well. So far, it looks pretty much like the bin packing problem. You also have one extra constraint: to minimize the number of colors in each container.

NP-hard?

Now, I'm beginning to share you hunch about it being NP-hard -- it's got all the elements of bin-packing and one extra constraint. A reduction from bin-packing should be easy to show say, by using an instance with objects all colored red say. We only need to show that the problem in in NP -- i.e. that we can verify the result in polynomial time. There you go, we've got an informal proof there!

Greedy Heuristic I

Here's a greedy heuristic that might help.

Representation: Instead of using sets, consider a bit sequence of length k, where k is the number of distinct colors that you have. So, say that you have 3 colors - red, green, blue. You would represent [blue] 001, [green, blue] as 011, [red] as 100, etc.

1. Sort the items by their color bit sequences using a comparison function that results in an ordering such as 001, 010, 100, 011, 110, 111. You can devise such a comparison function as a weighted function of the Hamming weight of the bit sequence and its actual numerical value.

2. Note that many color patterns (bit sequences) are most likely going to be shared by many objects. These objects will show up as contiguous objects in the sorted list.

3. Traverse the sorted list assigning contiguous items of same color patterns to the same bin. You would go from single colors to multi-color items.

4. You continue this way until you exhaust the capacity of each bin.

Greedy Heuristic II

Another approach would be to start filling the bins in reverse order. Starting by objects with the largest number of colors. Again fill contiguous objects into the same bin, if they can fit. As you get to the items with fewer colors, fit them into existing bins that already has that color covered.

Conclusion

Neither of these two approaches would be optimal, but hey, didn't we already know that? We've just sketched out an informal proof the problem is NP hard.

Good luck!