Problem: I have come across a problem similar to bin packing that I am unable to solve using any techniques that I have seen for solving bin packing or any of its variations. The problem is as follows:
Example: To give an example, imagine I have 3 bins (bin 0 with capacity 2, bin 1 with capacity 2, and bin 2 with capacity 1) and a list of 6 items. The first two items in the list can fit into bin 0 and bin 1. The next two items can only fit into bin 0, and the last item can only fit into bin 2. If I iterate through the list of items and then buckets sequentially, I will end up putting the first two items into bin 0, the third item nowhere, the fourth item nowhere, and the fifth item into bin 2. This is not optimal as I could have placed the first two items into bin 1, then the next two into bin 0, and finally the last item into bin 2.
What I’ve found so far:
I have found that simply sorting the bins by capacity or sorting the items by the number of bins they can go into does not work. Also, I have found someone with a similar problem (here, but in this case the OP is looking for an algorithm that minimizes the number of bins in each class, where I have a fixed number of bins that is known before the algorithm runs.
Also, I have found literature regarding bin packing with item-to-item incompatibility and tried modeling the problem as such, but I do not believe that is the correct solution as it runs into problems when deciding whether items that have only some bins in common are compatible. I believe a similar logic can be applied to bin-packing with compatible categories (see research paper here), but there may be some clever way to frame the problem so that these solutions work.
Basically, I was wondering if anyone could provide some guidance as to how to approach this problem or if there are any techniques for similar problems that can be used to approach this one.
Turn this into a graph theory problem.
Make a graph with a node for every item and every bin.
Make an arc from every item to every bin that can take it. The capacity of these arcs is infinite (or can be modeled as the capacity of the bin they point at).
Make a source node with an arc to every item. The capacity of these arcs is equal to the number of items.
Make a sink node with an arc from every bin into it. The capacity of these arcs is equal to the capacity of the bins.
Now, use the max-flow-min-cut algorithm to find the maximum flow through the network. The capacity used by arcs between items & bins in the solution you find is the allocation you're looking for.