3
$\begingroup$

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
$\endgroup$
  • 3
    $\begingroup$ 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. $\endgroup$ – David Richerby Aug 4 '15 at 16:49
  • 2
    $\begingroup$ This is NP-complete, by reduction from SUBSET-SUM or PARTITION. $\endgroup$ – Yuval Filmus Aug 4 '15 at 17:02
  • 2
    $\begingroup$ 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. $\endgroup$ – D.W. Aug 4 '15 at 17:36
  • 1
    $\begingroup$ @YuvalFilmus *blink* It's NP-complete by the near-trivial reduction from the ordinary bin-packing problem that I gave in my comment! $\endgroup$ – David Richerby Aug 4 '15 at 19:13
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.