2D bin packing with predefined gaps in container

Question

I have a problem with optimal placing of rectangular objects with different size and amount in rectangular container. The problem can be perfectly solved with the one of 2D bin packing algorithms but only on empty container. For me it is almost always not a case. My containers can have a restricted places where no object can be placed. Packing example

Surely I am not the first one who encountered this kind of problem and I hope someone already developed a good solution for it. Anything is good: book references, articles, code snippets, etc. Formal algorithms are prefered upon neural networks and this kind of things.

Answer 1

One possible way to solve it is with integer linear programming. There are different models but here is a simple one (with a bit of an issue, but you can improve on this if necessary).

Split the problem into a master problem and sub problems, with the master problem looking like this:

minimize sum(p)
s.t.
for all i: sum[j] p[j]*count[j,i] >= n[i]
p[i] >= 0 (and integer, don't add this constraint)

Where:

• p are the decision variables, deciding how many instances to use of a particular "packing" of the available items into the container. There are obviously way too many of these to list in advance, but they can be generated dynamically.
• count[j,i] is the number of times that packing j contains item i.
• n[i] is the number of times we want item i.
• the constraints are >= because packing a couple extra items is OK and it lets us use fewer different packings (otherwise the master problem would need special "deliberately subobtimal" packings to be able to fulfill the constraint).
• the integer constraint shouldn't be added explicitly if you're using a solver, because an integer solution may need columns that were not needed yet in the fractional solution.

Start with a couple of dumb packings for each item so that there definitely is some solution, bad as it may be. You can even just place one item in the container which is trivial to do even without using the solver for the sub problem, but the sub problem has to be solved anyway so you may as well reuse it here.

The sub problem is finding out what packing can be made that would improve the current solution that the master problem has. So take the dual costs of the rows of the master problem C (there are as many as there are different kinds of item) and solve

maximize y.C
s.t.
1) for all i: y[i] <= n[i]
2) for all i: y[i] = sum[j] P[j] if j is a placement of item i
3) for all cells (a,b): sum[j] P[j] (if j covers a,b) <= 1
4) for all existing packings e: e.y <= sum(e) - 1
y >= 0 and integer
P boolean

Where,

• y are implied variables that follow from a choice for P, y[i] is how many times item i occurs in the packing.
• P are the real decision variables, deciding whether or not to use a particular placement of a particular item. There are 62 different item-placements in your example problem, including rotations.
• constraint 1 ensures that a packing can actually be used in an integer solution to the master problem (using too many of an item would doom the corresponding variable to be fractional or zero).
• constraint 2 links y to P
• constraint 3 ensures that the solution is a valid packing, in the sense that items do not overlap each other.
• constraint 4 is necessary to avoid re-creating a column that was already added to the master problem.

Re-creating a column wouldn't happen if the master problem was a regular linear program, but it's an integer program and after branching constraint 4 needed to explicitly prevent re-creation. For example, on the "low" branch (recall this means we took some variable k that had a fractional value f and limited it to be <= ⌊f⌋), the first thing the sub problem tries to do is re-create exactly the same packing that corresponds k, so that it can be added to the master problem to "undo the damage". That is exactly the opposite of what we need though. So re-creating a column must be banned.

Constraint 4 is not a great way to do it, because now what the sub problem will try is generating all equivalent packings, thanks to symmetries. For example, after rounding down the variable of this packing:

It generates equivalent packings like these:

etc. There are a lot of these, and they're all pointless because it doesn't matter (for the objective value of the master problem, when the integer constraint is taken into account) where the 1x3 piece goes, it just matters that the packing contains a 1x3 piece and 14 1x1 pieces.

So ideally constraint 4 would be replaced by something more complicated that bans a packing equivalent to any that have come before, but something else that mostly works is first trying the high branch. At least in this example, that works out just fine.

In this example, after adding the columns that allow the master problem to be optimal (but still fractional, before any branching), the objective value is 5.5882352941176467. That already means that we know we'll need at least 6 containers, because this being the optimal fractional value proves that it cannot be done with 5 and a fractional number of containers is not an option.

A solution with 6 containers is found quickly, namely

Three of these:

One each of these:

Which packs all the pieces plus an extra 1x4 piece and 3 extra 1x1 pieces.

This algorithm does not depend the shape of the pieces or the container much, except that they have to be expressible as cells on a grid. The container can have holes all over the place, the pieces can be more like tetris pieces or even have disconnected parts. A downside is that the list of placements that it needs scales badly with the size of the container.