0
$\begingroup$

Assume we have $n$ fixed size objects with sizes $O_1$ to $O_n$. Also, assume we have $m$ bins with size $a \times B_1$ to $a \times B_m$ in which $a$ is a real number and $a\ge1$. We want to put these objects into bins. If in the process of putting an object to bins, there is a step where there is not enough room in any of the bins to put the object, we can increase $a$ so that we have larger buckets. Starting at $a=1$, the problem is to find the smallest $a$ where all objects can go to bins. Obviously, if $a$ is very large, we can put all objects in one bin.

  • Is this similar to a known problem in computer science?
  • Can this be modeled using some variation of bin-packing?
  • Can you suggest a heuristic?

Thank you.

EDIT:

I implemented the following heuristic and also the optimal version using the integer programming. The average ratio of $a_{heuristic}/a_{optimal}$ is 1.02 (worst case was 1.23) over 200 runs of the simulation for 20 objects, varying number of bins and randomly generated ball and bin sizes. The heuristic is as follows:

$(1)$ Sort objects from largest to smallest using a priority queue. Set $a = 1$. Assume $U_i$ is the total size of all objects in $B_i$.

$(2)$ Remove the biggest object and call it $O$.

$(3)$ For all bins, find the $1 \le i \le m$ for which $(U_i+O)/B_i$ is the least. Add $O$ to $B_i$ and $U_i = U_i + O$.

$(4)$ $a = max(a, U_i/B_i)$.

$(5)$ Goto $(2)$ if there are more balls.

Improve this question
$\endgroup$
12
  • $\begingroup$ Are you assuming $O_1 \le \dots \le O_n \le B_1 \le \dots \le B_m$? $\endgroup$
    – András Salamon
    Feb 5, 2016 at 18:45
  • $\begingroup$ Not really, but you could assume that if it helps with solving the problem. For the case I am working on, it may not be true. $\endgroup$
    – mnmp
    Feb 6, 2016 at 5:49
  • $\begingroup$ I was trying to clarify whether every object can fit into some bin to begin with. However, I suppose one can always adjust $a$ upwards as a first step if not, since this will have to be done anyway. The simultaneous increase of all bin sizes when necessary seems unfamiliar to me, something like having lots of identical rolls of fabric on a locked set of rollers, and one is then trying to cut orders of given lengths while minimising how much fabric is released -- the natural setup then seems to be to start with $a=0$. This may then be a known cutting stock problem. $\endgroup$
    – András Salamon
    Feb 6, 2016 at 8:42
  • $\begingroup$ The setup seems to be a variable-dimension input minimisation problem (open dimension problem), in the typology of Wäscher et al. mansci.ovgu.de/mansci_media/publikationen/2007/typology.pdf and it seems to me this kind of problem has not been studied much, at least not with $m>1$. Cannot understand why some people just drive-by downvote without leaving a comment. $\endgroup$
    – András Salamon
    Feb 6, 2016 at 9:01
  • $\begingroup$ Thank you @AndrásSalamon for reading through my problem and thinking about it. I really appreciate. Yesss, some people just downvote and I don't understand why? Do you suggest any changes to the question so that it is easier to understand for other people? I guess maybe that's why they downvote! For now I have decided to go with a simple heuristic. I match the biggest object to the bin with largest leftover capacity (if not possible I increase $a$), and do so until all objects get in. Not sure how close the resulting $a$ is to the optimal $a$. How good/bad do you think this heuristic is? $\endgroup$
    – mnmp
    Feb 7, 2016 at 9:18

2 Answers 2

Reset to default
2
$\begingroup$

One simple "bad" input that needs to be considered for worst-case analysis of this problem is as follows.

Let $c=(\sqrt{17}-1)/2 \approx 1.56$. There are three objects of size $c$, $1$, and $1$. There are two bins of size $2$ and $c$. Initially $a=1$. Some heuristics will place the largest object into the big bin, necessitating $a$ increasing from 1 to at least $(c+1)/2 = 2/c > 1.2807$. An optimal packing leaves $a=1$, placing the two small objects into the big bin and the big object into the smaller bin, with no waste. Hence such heuristics will have a worst-case actual-to-optimal ratio of more than 1.2807.

Notwithstanding this worst-case analysis, a heuristic like the one described in the edited question is likely to work well for practical examples, even if its worst-case performance is at least 28% worse than optimal. Similar heuristics are often used in practice, sometimes with adjustments like "instead of the general criterion, prefer a bin that is only a tiny bit larger than the object to be placed, if one such exists". Most implemented heuristics I'm familiar with are a big mess of such case analysis, but work extremely well in practice. However, it is often quite hard to come up with badly behaved inputs for such complex algorithms, and it is even harder to prove that they are the worst possible.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thank you for the insightful answer! Is it possible that for less number of bins and balls we might see a worse estimation of optimal answer? I tried running my simulation for 3 balls and 2 bins for 20000 random cases and I got 1.263 as the worst case. On average, the result is still around 2% worse than the optimal. Your example is very well crafted, thank you @Andras (I guess it's the answer to $c^2+c-4=0$ which causes different heuristics that sort decreasingly and increasingly to result in 1.28). $\endgroup$
    – mnmp
    Feb 15, 2016 at 22:17
1
$\begingroup$

This seems similar to bin-packing problem. I set $a=1$ and try to solve the bin-packing problem of putting objects of size $O_1$ to $O_n$. If I cannot find the solution then I increase $a$ with value $\delta >0$ and try again. If it doesn't work I increase $a$ by $2\delta$ and so on.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Thanks @Masood_mj. How should I test whether there is a solution? Using heuristics would work? $\endgroup$
    – mnmp
    Feb 4, 2016 at 6:47
  • 1
    $\begingroup$ A simple approximation solution for bin packing with bound 2x is to sort items from the largest to the smallest and for each object you pick start from the first bin and check if it fits. If it fits, just put it there, otherwise check the next bin. Obviously there are much better solutions with tighter bounds. $\endgroup$
    – Masood_mj
    Feb 4, 2016 at 20:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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