Rectangle packing with constraints

Question

I want to pack a set of rectangles (example):

So that the total height is as low as possible with the constraint that the rectangles must end up in the same column they started in. The rectangles are allowed to "move" through each other to reach the final state, as long as they don't intersect at the end.

Our current algorithm is to process the rectangles from largest height to smallest height, and put them at the lowest y position that's available. Is there a more optimal algorithm?

EDIT: I don't necessarily need the optimal solution, any algorithm that generates a better solution than the current one is interesting. Also, the number of rectangles is around 50.

Answer 1

Suppose you have N rectangles. For each rectangle i, let [a_i, b_i] be the horizontal span, and let h_i be the height.

Your solution space looks like y_i, i = 1, ..., N, where the vertical span of rectangle i is [y_i, y_i + h_i].

Without loss of generality, we can constrain y_i >= 0. We then want to minimize the objective function max{y_i + h_i | i}.

The constraints you have for non-overlapping rectangles are:

y_i + h_i <= y_j
   OR
y_j + h_j <= y_i

for all i != j such that `[a_i, b_i]` and `[a_j, b_j]` intersect

Figuring out which [a_i, b_i] intersect with each other is easy, so figuring out for which pairs of rectangles to form these constraints should be straightforward.

To get rid of the OR in our constraint, we can create binary dummy variables z_k for each constraint k and a "Big M" M that is sufficiently large and rewrite:

y_i + h_i <= y_j + (z_k)M
y_j + h_j <= y_i + (1-z_k)M

for all i != j such that `[a_i, b_i]` and `[a_j, b_j]` intersect

We can introduce a dummy variable H and add the constraints y_i + h_i <= H so that we can rewrite the objective function as minimizing H.

The resulting optimization problem is:

minimize H
with respect to: y_i, z_k, H
subject to:

 (1) y_i + h_i <= y_j + (z_k)M    for all i != j such that [a_i, b_i]
     y_j + h_j <= y_i + (1-z_k)M  and [a_j, b_j] intersect

 (2) y_i + h_i <= H               for all i

 (3) y_i >= 0                     for all i

 (4) z_k in {0, 1}                for all constraints of type (1) k

This is a mixed-integer linear optimization problem. There are general solvers that exist for this type of problem that you can apply directly.

Typically, they will perform tricks like relaxing the binary constraint on z_k to the constraint that z_k be in [0,1] during the algorithm, which turns this into a linear programming problem, which can be solved very efficiently.

I would not advise trying to reinvent those solvers.

Answer 2

Given that rectangles can only move vertically, there would appear to be only two solutions: moving all rectangles as far upward as you can until a collision occurs, or moving them all downwards until a collision occurs. I have a sneaking suspicion that these solutions are going to be equivalent*. I can't think that there's a much more sophisticated notion of packing when you're constrained to one dimension. Perhaps I'm missing something?

*If I've understood your constraint correctly, the minimal height is going to always be the number of filled cells in the column with the largest number of filled cells. This doesn't vary whether the translation is applied upwards or downwards.

Answer 3

In my humble opinion, the first step is to calculate, for each column, the least required height. Using your picture as an example, the first column requires at least a height of 10, which is contributed by the red, green and small blue rectangles. This is easily done by iterating through every given rectangle and add their corresponding height to the columns it occupies. By doing so, the maximum number in all the "column height" is found, which I call it the "pillar". In your picture, the "pillar" is at column 8:10 with height of 14, contributed by rectangle 1,2,4,6 (numbered from bottom to top). What this means is the minimum height of the packing is at least the height of the "pillar" since the "pillar" columns is solid filled and can't be further reduced. And stacking these four rectangle up forms such picture: (the non-pillar rectangle not shown)

Then the pillar divides the picture into two parts, one is the region to the left of pillar and another on the other side. Also, the "non-pillar" rectangles (R3,5,7,8) are separately positioned to the two regions as well. R3,R7 on the LHS and R5,R8 on the RHS.

Now consider the left side part first. I rearranged the pillar rectangles as shown it in the picture (fig.3):

With the rearranged pillar rectangle stacking order, though I don't have a rigid proof, it is highly possible that no matter what the shapes and what the number of the rectangles are positioned on the LHS of the pillar, all the given rectangles can fit in the empty space on the LHS (the constraint here is these rectangles can't give a higher solide pillar, otherwise the step 1 would have detected already and use it as the actual pillar). This arrangement gives the empty space on LHS the best "space consistency" which means the empty space created by each pillar rectangle is stacked in ascending order from bottom up. This "consistency" let the empty spaces created by each pillar rectangle to "work together" and then contain retangles that are higher than any single empty space created by single pillar rectangle. For example, the green rectangle in next picture is fit in using the empty space created by blue and purple rectangle together.

Assuming the statements above is true, then the rectangles positioned on the LHS will never make a higher stack than the pillar. However, if these retangles requires any cooperation between the empty spaces to fit in on the LHS, then they actually limit the swapping possibility for the pillar rectangles. Use fig.3 as example, the green rectangle requires the purple and blue to be neighbor to fit in, however, to get the best space consistency on RHS, the magenta has to go between the purple and blue. This means the green on LHS makes it impossible to get the best consistency for RHS and consequently makes it possible to have rectangles positioned on RHS can't fit in the empty space and cause a stack with holes and exceeds the height set by the pillar. Sorry that I can't devise such a case here, but it sure makes a difference.

In conclusion:
step 1 is to find the pillar, one easy answer can be found here if every given rectangle is involved in the pillar -- the height of the pillar is the minimum packing height.

step 2 is to examine both side to the pillar.
case a: If one side has no free rectangle positioned, then the other side can be easily filled with the "best consistency" method and resulting minimum packing height is again the pillar height.

case b: If one side doesn't require free space consistency, then that side can be filled and the other side still can use "the best consistency". For example: (your original picture)

In this case, the empty space require for fitting in R3 is solely created by R6 and the same for R7 and R2. Thus swapping the stacking order of R6 and R2 with other pillar rectangle won't make R3, R7 unfit if R3, R7 follow the swapping. Which can result in a "best consistency" case for RHS:

Then RHS can be filled with the RHS positioned rectangles without exceeding the pillar height.
This non-consistency requiring can be identified by comparing the height of the free rectangle to fit in and the height of the pillar rectangle that's to create the free space for it. If the free rectangle's height is no larger than the other's, then it doesn't require a second pillar rectangle to get involved which means it doesn't require free space consistency.

case c: Both sides need free space consistency. This is where troubles kick in. Take fig.3 as example again. The green in fig.3 had the purple and blue combined. This means the green, purple and blue is considered as a whole to swap stacking order with other pillar rectangles to get the LHS's free rectangle the best fit. And within this whole, the blue and purple can swap as well.
If the RHS can't make the fit, resulting in a packing height larger than the pillar height, then it is required to repeat the step two but with fitting the RHS first and try fitting LHS after that. Then the compared lower packing height result is taken as the final result. The logic for this case is unclear, highly possible has better alternate.

I know this should not really be called as a proper solution but rather random and loose thoughts, but it obviously won't fit in the comments. Forgive me for my clumsy explanation and poor picture handling. Hope this helps.