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.