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

<p>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 &gt; 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.</p>

<p>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.</p>

CC BY-SA 3.0
2016-02-15T22:17:05.473Z
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).
mnmp
CC BY-SA 3.0
2016-02-15T15:50:53.790Z
2016-02-15T15:50:53.790Z
András Salamon
<p>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 &gt;0$ and try again. If it doesn't work I increase $a$ by $2\delta$ and so on. </p>

CC BY-SA 3.0
2016-02-04T06:47:33.440Z
Thanks @Masood_mj. How should I test whether there is a solution? Using heuristics would work?
mnmp
CC BY-SA 3.0
2016-02-04T20:55:22.907Z
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.
Masood_mj
CC BY-SA 3.0
2016-02-03T20:55:47.103Z
2016-02-03T20:55:47.103Z
Masood_mj
<p>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.</p>

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

<p>Thank you.</p>

<hr>

<p>EDIT:</p>

<p>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:</p>

<p>$(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$.</p>

<p>$(2)$ Remove the biggest object and call it $O$. </p>

<p>$(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$. </p>

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

<p>$(5)$ Goto $(2)$ if there are more balls.</p>

CC BY-SA 3.0
2016-02-05T18:45:05.340Z
Are you assuming $O_1 \le \dots \le O_n \le B_1 \le \dots \le B_m$?
András Salamon
CC BY-SA 3.0
2016-02-06T05:49:23.840Z
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.
mnmp
CC BY-SA 3.0
2016-02-06T08:42:02.283Z
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.
András Salamon
CC BY-SA 3.0
2016-02-06T09:01:31.733Z
The setup seems to be a variable-dimension input minimisation problem (open dimension problem), in the typology of Wäscher et al. http://www.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.
András Salamon
CC BY-SA 3.0
2016-02-07T09:18:37.727Z
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?
mnmp
CC BY-SA 3.0
2016-02-08T07:46:05.343Z
This seems similar to the factor of 2 setup mentioned by  @Masood_mj (greedy packing, largest first), but these proofs can be a bit tricky.  If one bin is large, the others small, then a sequence of large objects will keep being put in the large bin until the small bins have all been increased in size to reach the large bin's capacity.  A sequence of half-size objects (plus epsilon) will then only use half the small-bin space in use, whereas putting the smaller objects in the large bin then the large objects into the smaller bins would be optimal.
András Salamon
CC BY-SA 3.0
2016-02-08T16:43:23.870Z
@AndrásSalamon What if we sort bins from small to large and items from large to small? This is what I did in a project.
Masood_mj
CC BY-SA 3.0
2016-02-11T07:10:42.117Z
1. You should not wipe out the question. 2. Asking if your implementation of some idea is correct would be off-topic here, please read [help/on-topic].
Kaveh
CC BY-SA 3.0
2016-02-13T04:47:31.810Z
@AndrásSalamon I am not sure but I think there might be a relationship between the worst case here and in Best Fit Decreasing algorithm for which we have 11/9*OPT+1 (11/9 = 1.22). What do you think Andras?
mnmp
CC BY-SA 3.0
2016-02-14T01:35:10.283Z
Some points.  I cannot wade through your code to check, but step (4) should surely be max, not min?  I cannot follow your reasoning about optimality (for instance, what is the input you are assuming?); the example I sketched still seems to work to establish 2 as the worst case ratio.  The executable code doesn't belong here.  Please follow the site guidelines: there should be a clear question that can be answered, a Q&A forum is not suitable for extended discussions.
András Salamon
CC BY-SA 3.0
2016-02-14T08:17:48.130Z
@AndrásSalamon thank you for taking the time to see my discoveries. Could you tell me what your example is (in which you're getting a worst case of 2)?
mnmp
CC BY-SA 3.0
2016-02-15T15:53:03.327Z
On further reflection, my supposed example doesn't work against your heuristic.  See my answer for an argument that the worst case performance ratio is greater than 1.2807, which is quite a bit smaller than 2.
András Salamon
<polynomial-time><heuristics><packing><greedy-algorithms>
Packing $n$ objects into $m$ bins whose size is variable
mnmp
# Packing $n$ objects into $m$ bins whose size is variable

(Asked by: username_0 on 2016-02-03)

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.

**Tags:** polynomial-time, heuristics, packing, greedy-algorithms

> **Comments:**
> **username_1**: Are you assuming $O_1 \le \dots \le O_n \le B_1 \le \dots \le B_m$?  
> **username_0**: 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.  
> **username_1**: 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.  
> **username_1**: The setup seems to be a variable-dimension input minimisation problem (open dimension problem), in the typology of Wäscher et al. http://www.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.  
> **username_0**: 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?  
> **username_1**: This seems similar to the factor of 2 setup mentioned by  @username_2 (greedy packing, largest first), but these proofs can be a bit tricky.  If one bin is large, the others small, then a sequence of large objects will keep being put in the large bin until the small bins have all been increased in size to reach the large bin's capacity.  A sequence of half-size objects (plus epsilon) will then only use half the small-bin space in use, whereas putting the smaller objects in the large bin then the large objects into the smaller bins would be optimal.  
> **username_2**: @AndrásSalamon What if we sort bins from small to large and items from large to small? This is what I did in a project.  
> **username_3**: 1. You should not wipe out the question. 2. Asking if your implementation of some idea is correct would be off-topic here, please read [help/on-topic].  
> **username_0**: @AndrásSalamon I am not sure but I think there might be a relationship between the worst case here and in Best Fit Decreasing algorithm for which we have 11/9*OPT+1 (11/9 = 1.22). What do you think Andras?  
> **username_1**: Some points.  I cannot wade through your code to check, but step (4) should surely be max, not min?  I cannot follow your reasoning about optimality (for instance, what is the input you are assuming?); the example I sketched still seems to work to establish 2 as the worst case ratio.  The executable code doesn't belong here.  Please follow the site guidelines: there should be a clear question that can be answered, a Q&A forum is not suitable for extended discussions.  
> **username_0**: @AndrásSalamon thank you for taking the time to see my discoveries. Could you tell me what your example is (in which you're getting a worst case of 2)?  
> **username_1**: On further reflection, my supposed example doesn't work against your heuristic.  See my answer for an argument that the worst case performance ratio is greater than 1.2807, which is quite a bit smaller than 2.  

---

## 2 answers

### Answer by username_1 on 2016-02-15. Score: 2 | Accepted answer

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.

> **Comments:**
> **username_0**: 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).  

---

### Answer by username_2 on 2016-02-03. Score: 1

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.

> **Comments:**
> **username_0**: Thanks @username_2. How should I test whether there is a solution? Using heuristics would work?  
> **username_2**: 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.  

---

