Optimal 2D bin packing

1
votes

Given a set of rectangles of various sizes (items) and a set of rectangles of identical sizes (bins), place items into as few bins as possible.

I'm aware of A Thousand Ways to Pack the Bin but I was wondering, if the number of items was suitably small and perhaps the dimensions were integers, is there a way to always pack the items optimally? Is anyone aware of a strategy or algorithm for optimal rectangle bin packing?

1
algorithmoptimizationgeometryknapsack-problembin-packing
Related: stackoverflow.com/q/46630524/555045 (without "holes" this time, which makes little difference) – harold
@harold Interesting! Please, I'm not familiar with integer programming so I have a few questions. It works by writing down a lot of some constrains and the running a solver over them which then outputs the positions of items w.r.t. the bins, correct? Is there a mechanical way how to construct the constrains for 2D bin packing? I mean, there probably always has to be a constrain "every item has to go somewhere", is it know what kind of constrains 2D bin packing needs? What if some items cannot be fitted into any bin (all are full)? What if there are multiple optimal packings? – Ecir Hana
That answer has the mechanical construction already, it's a little high level, but that can all be written as code that appends linear inequalities to an ILP model. It doesn't take every item and try to put them somewhere, the inner problem generates "ways to pack a bin" and the outer problem optimizes the total number of such "ways" used under the constraint that every item occurs at least as many times as we wanted it. So bins cannot really "run out" – harold
@harold And this "outer" and "inner" problem is expressed in the same set of constrains and solved in one run? Or the results of "inner" are somehow iteratively fed into "outer"? And when you say "[t]here are different models", what do you mean be "model"? Different ways of expression the constrains which ultimately lead to the same optimal packing? – Ecir Hana
The outer and inner problems are quite different. The inner problem is roughly "given one bin, what's a good way to fill it". The outer problem is roughly "given all these possible packings, what's a good selection of them". They are connected by giving the dual costs of the outer problem as item values for the inner problem, so that the inner problem tries to pack a bin in an "immediately useful" way (improving the state of the outer problem) – harold

1 Answers

1
votes

Have a look at the survey of Lodi et al. on two-dimensional bin packing problems which has a section on exact algorithms. For a very small number of items you may be able to solve the problem using integer programming models, for larger sizes you will likely need a tailored tree search or branch-and-bound algorithm. An example is the article of Pisinger & Sigurd which uses a Dantzig-Wolfe decomposition and relies on constraint programming to pack individual bins, and are able to solve problems with about 100 items.