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.

Brister

Well, I don't have a solution for you (though my gut tells me there is one, probably related to the dynamic-programming solution to finding overlapping intervals), but I can prove that your solution (given in a comment to an answer below) for this specific instance of the problem is optimal: you can easily prove that the max height of any solution can never be below max(sum of squares in one column), so if you find a solution that's equal to that, it must be optimal. – Rad

We can also show your algorithm is not optimal: images two skinny blocks of height 3 on top of each other on the left, then one very wide block of height 4, then a skinny block of height 5 on the right. – Rad

@Andreas Make sure not to miss my answer - I put some time into it. :) – Vivacious

Seems like this is equivalent to scheduling tasks to run concurrently (without context switching), as long as they do not share any resources. Each column represents a resource, each block is a task, the columns which a block intersects represents the resources the task must access, and the height of a block is the time it takes for the task to run. Your problem is a little more restricted than this, because each of your objects is a contiguous block (occupies a set of adjacent columns). Not sure if this insight helps or not. – Chiseler

If you don't need the optimal solution, then I think this problem would be a great candidate for a stochastic algorithm, such as a genetic algorithm or simulated annealing. – Chiseler

Possible duplicate: https://mcmap.net/q/1010730/-packing-rectangles-for-compact-representation/21727 – Chiseler

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.

Vivacious

min{h_i|i} should be max{h_i|i} we want to minimize the maximum height. – Fronia

+1 for the formalization of the problem. Do you know of any free solvers that would accept this kind of optimization problem? – Brister

This question (and related) has a bunch of solvers that will manage it: #502602 – Rainger

-1 from me. "I would not advise trying to reinvent those solvers" - He's not; he's asking if his problem can be done more efficiently than this. Any problem (in NP) can be stated as an MIP problem, but MIP solvers are designed to try to solve an NP-Complete problem, which means if his problem is not NP-Complete, this method will most likely be very inefficient. I don't think it is NP-Complete, which would make this a not-very-helpful answer. – Rad

@BlueRaja The last sentence in the question says "Is there a more optimal algorithm?" The OP described that his algorithm is greedy and suboptimal. I provided a formulation that gives a optimal solution - which I would say is "more optimal," as the OP requested. Furthermore, there are MIP solvers that will use branch and bound techniques such that you can get controllably suboptimal solutions. What's your problem? – Vivacious

@Andreas See rmmh's comment. – Vivacious

@TimothyShields: BlueRaja's complaint is that solving an ILP probably takes longer than this problem requires. I wouldn't go so far as to -1 your answer, which despite probably being slower than necessary is still a fairly practical way to solve the problem, but his criticism is sound. – Melodious

@Melodious "... probably takes longer than this problem ... probably being slower than necessary ..." - I've emphasized the key word: probably. BlueRaja is a troll. He offered nothing constructive in terms of helping the OP, and he downvoted (as is usual for him) a perfectly valid, informative answer containing no misinformation. Anybody who wants to contribute a custom-tailored algorithm for this problem can do so, but until then I think this stands as a very reasonable solution. – Vivacious

Calm down. "I would not advise trying to reinvent those solvers" is arguably misleading, because it suggests that no faster algorithm is possible. For that to actually be the case, there would need to be at least some evidence that the problem may be NP-hard. (To take a more extreme example of the same principle: If the question were "How do I sort an array of numbers?", I could likewise propose an ILP formulation that does it. And if I added "I would not advise trying to reinvent those solvers", this would be misleading.) – Melodious

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.

Langton

I think you're missing that the rectangles are allowed to move through each other, as long as they don't intersect afterwards. Your solution basically amounts to dropping the blocks vertically and see how they settle. This is not the optimal solution. If you look at the example above, the light blue rectangle could be placed at the bottom, below the large blue rectangle. – Brister

Ah, my apologies. I assumed that they could not pass one another. This is a much more interesting problem as a result :) – Langton

@AndreasBrinck You should add this in your question and not only in a comment so that new readers can understand the question without having to read the comments. – Coalition

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.

Impeachable

Forgot to mention, this "solution" only discussed the case of only one pillar found after step 1. If multiply pillars were found, it won't be too hard to apply the step 2 to the first two regions to one side, then take the first two regions as a whole to apply step 2 on the next region. This would lead to much messier swapping and following though. – Impeachable