Non-trivial bin-packing instance with 5 objects

Question

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:

1. Sort the items to give $3, 3, 2, 2, 2, 2$
2. Put the first two items in the first bin, producing a bin $[3, 3]$
3. Put the next three items in the second bin, producing a bin $[2, 2, 2]$
4. 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$?

Answer 1

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.

Answer 2

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.