algorithm - 带约束的矩形包装

Question

我想打包一组矩形(示例):

因此总高度尽可能低，同时限制条件是矩形必须在它们开始时所在的同一列结束。允许矩形相互“移动”以到达最终状态，只要它们在最后不相交。

我们当前的算法是从最大高度到最小高度处理矩形，并将它们放在可用的最低 y 位置。有没有更优的算法？

编辑: 我不一定需要最佳解决方案，任何生成比当前解决方案更好的解决方案的算法都很有趣。此外，矩形的数量约为 50 个。

Answer 1

假设您有 N矩形。对于每个矩形 i , 让[a_i, b_i]是水平跨度，设h_i是高度。

您的解决方案空间看起来像 y_i, i = 1, ..., N , 其中矩形的垂直跨度 i是[y_i, y_i + h_i] .

不失一般性，我们可以约束y_i >= 0 .然后我们要最小化目标函数 max{y_i + h_i | i} .

非重叠矩形的约束是:

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

找出哪个[a_i, b_i]彼此相交很容易，因此找出哪些矩形对形成这些约束应该很简单。

为了摆脱约束中的 OR，我们可以创建二进制虚拟变量 z_k对于每个约束 k和一个“大M”M足够大并重写:

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

我们可以引入一个虚拟变量H并添加约束 y_i + h_i <= H这样我们就可以将目标函数重写为最小化 H .

由此产生的优化问题是:

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

这是一个 mixed-integer linear optimization problem .存在针对此类问题的通用求解器，您可以直接应用。

通常，他们会执行一些技巧，例如放松对 z_k 的二进制约束到 z_k 的约束在 [0,1]在算法期间，将其变成 linear programming problem ，可以非常有效地解决。

我不建议尝试重新发明那些求解器。