Non-trivial bin-packing instance with 5 objects
Bin packing problem is a problem, where one has to find the minimum number of bins of size $v$ required to store $n$ objects of sizes $s_1, \ldots, s_n$. Object sizes are never greater than $v$.
For example, if $v = 10$ and the objects sizes are $2, 5, 4, 7, 1, 3, 8$, we can store objects with 3 bins: [8, 2], [7, 3], [5, 4, 1], but not with 2 bins or less, as this would leave some items unpacked. Therefore 3 is the minimum number of bins required.
The best-fit-decreasing heuristic is a packing strategy, which aims to produce a packing close to optimal. It first sorts all the items in descending order. Then it iterates over all items, and for each item attempts to find an existing bin, which can both fit the item and whose spare capacity is closest to the size of the item. If such bin exists, it puts the object in the bin. If it doesn't, it creates a new bin and puts it there.
A non-trivial bin-packing instance is an instance of the problem, which can't be optimally solved by the best-fit-decreasing heuristic.
For example, the instance $v = 7$, $n=6$ where sizes are $3, 2, 3, 2, 2, 2$ is non-trivial, because the best-fit decreasing heuristic will:
Sort the items to give $3, 3, 2, 2, 2, 2$
Put the first two items in the first bin, producing a bin $[3, 3]$
Put the next three items in the second bin, producing a bin $[2, 2, 2]$
Put the last item in the third bin, producing a packing $[3, 3], [2, 2, 2], [2]$
This is a valid packing, but non-optimal, as it requires 3 bins, and there exists a valid packing with two bins: $[3, 2, 2], [3, 2, 2]$.
Is there a non-trivial bin-packing instance with $n=5$?
algorithms combinatorics packing
Adam KurkiewiczAdam Kurkiewicz
Let's look at two algorithms: Best Fit Ordered, and First Fit Ordered. Both take the items in descending order and put them into a non-empty bin if possible, or into a new empty bin if they don't fit into any existing bin. Best Fit Ordered puts an item into the filled bin with least available space, First Fit Ordered puts an item into the first filled bin with enough space.
Question: Are there five items A ≥ B ≥ C ≥ D ≥ E such that BFO or FFO are not optimal?
If all items fit into one bin then BFO and FFO will fit them into one bin, because both will just put items in the first bin. Both are optimal.
If five bins are optimal then BFO and FFO cannot be non-optimal, since they can't use more than five bins.
If four bins are optimal then there are two items fitting into one bin, therefore D and E fit into one bin, therefore when BFO and FFO finally try to find a bin for E, either four bins are filled and E fits into the bin with D, or there are only three bins filled and E goes into the fourth bin.
So the only cases to consider are those where two or three bins are optimal. I'll consider cases systematically:
A, B and another fit -> 2 bins, BFO and FFO are optimal A, B fit, C, D, E fit -> 2 bins, BFO and FFO are optimal A, B fit, C, D, E don't fit -> 3 bins required, BFO and FFO are optimal.
We now assume A and B don't fit into a bin, so A goes in the first and B in the second:
A, C and another fit -> 2 bins, BFO and FFO are optimal A, C fit, B, D, E fit -> 2 bins, BFO and FFO are optimal A, C fit, B, D, E don't fit: A, D, E don't fit, A, D or A, E doesn't help -> 3 bins required -> BFO and FFO are optimal.
We now assume neither A and B, nor A and C, fit into one bin. If B and C don't fit, then A, B, C go in three different bins. 3 bins are optimal, so D and E can be made to fit, and BFO and FFO will both find a way.
So we assume B and C fit in one bin. Both BFO and FFO will fit them in one bin. D E must also fit into one bin, so if three bins are optimal, then BFO and FFO will find a solution.
If two bins are optimal, then one bin must contain A, one must contain B and C. D and E fit, so BFO and FFO will fit them.
gnasher729gnasher729
Interesting little brainteaser. The answer likely depends on your precise definition of "optimally solved". But if you mean "solved with the least number of bins", then the answer is no. The algorithm will always find an optimal solution.
Think about it this way. The optimal solution for 5 items needs to be a two-bin solution. A one-bin solution will always be found by the algorithm. For a two-bin solution, it is trivial to see that the algorithm needs to place the first two items in the first bin, while the optimal solution has them spread over two bins.
Then the reasoning is as follows: the algorithm will place $s_{1}$ and $s_{2}$ in bin 1, $s_{3}$ and $s_{4}$ in bin 2, and $s_{5}$ in bin 3, which implies that: $$ s_{3} + s_{4} + s_{5} > v $$
One optimal solution would be to fit item $s_{3}$ and $s_{5}$ in with $s_{2}$, because there is more room left over there. Then $s_{4}$ goes in with $s_{1}$, necessarily leaving some space there. If that all does not fit, then there is no optimal solution with 2 bins.
For that to work, it needs to be true that: $$ s_{2} + s_{3} + s_{5} \leq v $$ Which necessarily implies that: $$ s_{3} + s_{4} + s_{5} \leq v $$ because $s_{4} \leq s_{2}$.
But that means that the algorithm would have been able to put $ s_{3}$, $s_{4}$, and $s_{5}$ together in the second bin.
You might think that an optimal solution for 3 bins would be possible, with the algorithm taking 4 bins. But it is easy to see that that is not possible.
The optimal and the algorithm solutions need to differ in the first bin already. If not, then you can imagine replacing whatever items are placed there with one large item, giving you a solution for 4 items. For the optimal solution to beat the algorithm, the algorithm must place a second large item in the first bin, while two smaller ones would fit there. That can only be $x_2$ or $x_3$, for otherwise there are no two items left over. That implies that that item, and all the remaining ones, are all smaller than $\tfrac{1}{2}v$. But in that case it is trivial to put the remaining items in the third bin.
fishinearfishinear
$\begingroup$ I disagree with "The optimal solution for 5 items needs to be a two-bin solution" consider $v = 5$ and $sizes = [4, 4, 4, 1, 1]$ The optimal solution is a three bin solution. You are correct that by optimal solution I mean a solution with fewest bins. $\endgroup$ – Adam Kurkiewicz Nov 21 '17 at 23:15
$\begingroup$ I meant an optimal solution for which the algorithm would find a worse solution. For a three bin solution optimal solution would have to find a four bin solution. It pretty trivial to see that that is not going to work. $\endgroup$ – fishinear Nov 21 '17 at 23:22
$\begingroup$ So you mean the heuristic finding a 4-bin solution, despite the existence of a 3-bin solution? for n=7 and v=7 an example would be [7, 3, 3, 2, 2, 2, 2]. Then the optimal packing is [7], [3, 2, 2], [3, 2, 2], which is 3 bins. The heuristic will give [7], [3, 3], [2, 2, 2], [2], which is a 4-bin solution. Why can't this happen for n=5? $\endgroup$ – Adam Kurkiewicz Nov 25 '17 at 16:00
$\begingroup$ I have added an explanation for the 3-bin case. $\endgroup$ – fishinear Nov 25 '17 at 17:10
$\begingroup$ The ideas are good, but I'm still not convinced by the details. For example in the 4-bin case you say that the solutions need to differ in the first bin. That's probably the case. But your explanation doesn't convince me "If not, then you can imagine replacing whatever items are placed there with one large item, giving you a solution for 4 items." Well, what about the already mentioned case v=7, sizes = [7, 3, 3, 2, 2, 2, 2]? $\endgroup$ – Adam Kurkiewicz Nov 26 '17 at 12:02
Not the answer you're looking for? Browse other questions tagged algorithms combinatorics packing or ask your own question.
Relaxed Bin Packing Problem
Bin-packing satisfiability rather than minimization
How to solve the feasibility problem in 0-1 integer programs?
How to solve variable sized bin packing when the items have equal weights, or is it still NP-hard?
How to show that there are $\binom{M+K}{M}$ different number of type bins?
Constructing an optimal solution to bin packing using a "magical function" $\phi$
Why this greedy algorithm does not return the optimal solution to this NP-hard problem?
Is this problem NP-Complete (Bin packing with seperable items and penalty)?