# Bin-packing satisfiability rather than minimization

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
• The decision version of the standard bin packing problem ("Is it possible to pack these items into $k$ bins each of capacity $b$?") is exactly the special case where $b_1 = \dots = b_k = b$. That doesn't help you much, except for pointing out that your problem is closer to standard bin-packing than you seem to think. Aug 4, 2015 at 16:49
• This is NP-complete, by reduction from SUBSET-SUM or PARTITION. Aug 4, 2015 at 17:02
• 1. What do you mean by "good"? 2. Given that it's NP-complete, what are you looking for? An approximation algorithm? An algorithm for finding the optimal solution, even if it is not efficient/polynomial-time? A heuristic that will sometimes work? Something else? See cs.stackexchange.com/q/1477/755. 3. Also, have you looked at standard approximation algorithms/heuristics/etc. for bin-packing to see which of them can be adapted to your problem? Please do some research into them, then edit your question to show which ones you've looked at and whether/why you rejected each one.
– D.W.
Aug 4, 2015 at 17:36
• @YuvalFilmus *blink* It's NP-complete by the near-trivial reduction from the ordinary bin-packing problem that I gave in my comment! Aug 4, 2015 at 19:13