I'm working on a problem that is a variation of bin-packing, but a bit more general form with extra constraints. The problem definition is as follows-
We have objects of varying sizes, which can be grouped up into object classes. We have bins that are of differing capacities, which also are grouped into bin classes (all bins within the same class have same capacity). The object classes have constraints on which bins they may be placed into- for example, an object of class 'A' can be placed in either of the bin classes 'X' or 'Y'. The objective is to find the minimum number of bins in each class, that can yield an optimal packing of a given set of objects.
Is there a good mathematical formulation of this problem, and solution methods that you have come across? Is this an extension of the bin-packing problem where the same methods can be applied? I understand it is NP hard. I was unable to find much about how to tackle the problem, so it would be quite helpful if you can point me in the right direction.
Finding the exact solution is NP-hard. But finding an optimal solution is easy.
Since the objective is to minimize the number of bins for each class I would do something like this.
From the input constraints generate a Map that stores the object classes each bin class can pack. E.g. for the constraint "object of class 'A' can be placed in either of the bin classes 'X' or 'Y'. "
M[X] = {A};
M[Y] = {A};
Generate this map by processing through all the constraints. Now start with the bin class that has the minimum number of objects and start packing into it and mark the objects as Packed[Object_A] = true;
Now repeat the above step for the bin classes in the map in the decreasing order of their count.
After this you will be left with objects that has no constraints and bin classes that has zero or more objects.
We can extend First Fit algorithm to solve this part. Sort the bin classes based on the object count in them in increasing order. Run a loop on the left over objects to into put First Fit bin class. In each iteration you need to reorder the bin classes based on the object count.
I hope it helps.