Simple, non-trivial bin-packing instance

0
votes

Bin packing problem is to find the minimal number of bins of size v, which can contain all objects of size [s_1, s_2, s_3, ..., s_n]

I'm searching for a simple, non-trivial instance of the bin-packing problem.

A simple instance is an instance which can be solved with no more than 5 bins.

A non-trivial instance is an instance, which can't be solved by the best-fit-decreasing heuristic algorithm, but can be solved with complete search.

For example, the instance v = 20, objects = [15, 7, 14, 3, 14, 7, 9] is simple, but not non-trivial, because complete search proves that the minimal number of bins is 5:

[[15, 3], [7, 7], [14], [14], [9]]

however, best-fit heuristic also produces a 5-bin packing:

[[15], [14], [14], [9, 7, 3], [7]]

Does a simple, non-trivial instance of bin packing exist?

1
algorithmbin-packinginteger-programmingnp-hard
Why not write a program that implements both algorithms and do an exhaustive search for it? Otherwise this sounds more like a Mathematics proof problem, in which case you should post it on math.stackexchange.com – Dijkgraaf
thanks @Dijkgraaf, that's what I've ended up doing (exhaustive search over randomised inputs). – Adam Kurkiewicz
Ask yourself what would be needed in your example to make a simple algorithm miss the solution. I assume that 2 items per bin is too easy; if you have a 15 and a 3, there's no reason not to put them together. A larger example, where you have 3 items or more per bin, is more likely to be problematic; say (14,10,10,7,7,3,3,2,2,2); if you add the 3's to the 14 instead of the 2's, you can't do 3 bins. – m69 ''snarky and unwelcoming''
@m69 your example is invalid. Both best-fit-decrasing and optimal solutions are 3 bin solutions: [[14, 3, 3], [10, 10], [7, 7, 2, 2, 2]] [[14, 2, 2, 2], [10, 10], [7, 7, 3, 3]] – Adam Kurkiewicz
How about v = 7, sizes = [3, 3, 2, 2, 2, 2] – Adam Kurkiewicz

1 Answers

2
votes

Indeed, such instance exists, namely:

v = 20, objects = [11, 7, 7, 6, 5, 3, 1]

Best-fit-decreasing heuristic gives: [[11, 7], [7, 6, 5, 1], [3]]

Optimal packing is: [[11, 6, 3], [7, 7, 5, 1]]