organizing rectangles on top of each other

Question

We have some rectangles that should be organized in a number of columns. Each column height should be in the range of $[H, H+d]$ in which $d$ is a small number relative to the height of the rectangles. We can only put one rectangle on top of the other one and we are not allowed to rotate them. Objective is to maximize the number of columns and simultaneously minimize the empty space between columns.

Answer 1

Suppose the rectangles are numbered $i\in\{1,2,\dots,N\}$ and their respective heights are $h_i$. Now we define $A\in\{0,1\}^{N\times N}$ and $B\in\{0,1\}^N$. The interpretation of these variables is as follows:

• $A_{ij}=1$ if rectangle $i$ is in column $j$, $A_{ij}=0$ otherwise.
• $B_j=1$ if column $j$ is occupied, $B_j=0$ otherwise.

I believe this binary linear program will do it:

$$ \textstyle \begin{array}{lll} \text{maximize} & \sum_j B_j & \\ \text{subject to} & \sum_j A_{ij} = 1 & i=1,2,\dots,N \\ & B_j H \leq \sum_i h_i A_{ij} \leq B_j( H + d ) & j=1,2,\dots,N \\ & B_j \leq \sum_i A_{ij} & j = 1,2,\dots,N \\ & A\in\{0,1\}^{N\times N} \\ & B\in\{0,1\}^N \end{array}$$ Explanation:

• $\sum_j B_j$ counts the number of columns with a non-zero number of rectangles.
• $\sum_j A_{ij}=1$ ensures that each rectangle is assigned to exactly one column.
• $B_j H \dots B_j(H+d)$ ensures that if a column is occupied, it has a height of between $H$ and $H+d$, inclusive. But if a column is not occupied, the left- and right-hand terms in this inequality chain will be zero, allowing for a zero-height, but un-occupied, column.
• $B_j \leq \sum_i A_{ij}$ ensures that a column is counted as occupied only if there is at least one rectangle in it.

Note that this does nothing to minimize the empty space between columns. That is easily rectified with a post-processing step that rearranges the columns in an order that puts them adjacent to each other. Another option is to add a sorting constraint, like $$\textstyle \sum_i A_{ij} \geq \sum_i A_{i{j+1}}, \quad j=1,2,\dots,N-1$$ This ensures that the columns are arranged from the most number of rectangles to the least. But it also has the effect of ensuring that all of the columns with zero rectangles will have the highest indices. But to be honest, the post-processing step is your better choice.

All that said, a problem like this may be better suited for constraint programming than binary linear programming.