Bin-packing satisfiability rather than minimization

Question

Here's a problem I need to solve that's clearly related to the standard bin-packing problem, but I'm not sure how to approach it.

Suppose you have some finite set of bins $B$, and each $b_i \in B$ has some integer capacity $\mathit{cap}(b_i)$. You also have some set of items $L$ where each item $l_j \in L$ has some integer volume $vol(l_j)$. The question is, is there some way of assigning each item in $L$ to some bin in $B$ where no bin is overful, i.e. to find any total mapping $M : L \rightarrow B$ such that $\forall b_i \in B$, the sum of all $vol(l_j)$ with $M(l_j) = b_i$ is less than $cap(b_i)$.

The notable differences from the classic bin-packing problem are: first, we have only a finite set of bins, not an infinite number of bins to draw from. Second, we have no notion of cost; we only want to find some total mapping or determine that no such mapping exists. Third, bins are not homogeneous; we might have one bin with capacity 5 and another with capacity 10.

I'm not sure how to approach this problem or whether standard bin-packing approaches can be adapted to work with it. What is a good algorithm for answering the question?

For extra credit, there are a few extra bells and whistles that I would like to add, though these are optional:

• Add a constraint that some bins can only contain a maximum number of items as well as having a volume limit
• Some bins may have a minimum per item volume as well as a maximum volume; i.e. you don't have to put an item in the bin, but if you that item must have at least a given volume

Answer 1

Having a fixed number of bins makes little difference. If you use sorted-first-fit for example, the only difference is that the algorithm can fail. On the other hand, if you use a better algorithm for bin-packing (one that considers all bins before it is proven that they are all needed), you would find a trivial lower bound l for the number of bins, try to fit them all, and if it fails increase l by 1 and start all over again.

The different sizes make the problem likely harder to solve. For example, if you only wanted to decide which bin contains the largest item, that would in normal bin packing be no problem: Just put it into the first bin; it doesn't matter which one. With different bin sizes, pick all the bins that are big enough, remove duplicates with the same size, and try putting it into each of these bins. So you have more possible combinations. (If you had 100 bins of size 10 and 100 bins of size 5, then items of size 6 would be no problem, but a largest item of size 5 or smaller would be put into one of two bins).

I say "likely harder" because in the extreme you might have items that fit into one bin only.

Once you try to find an optimal solution using brute force, any additional restrictions make it easier because they remove possibilities from the search tree.