带约束的矩形包装

Question

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

因此总高度尽可能低,矩形必须在它们开始的同一列中结束. 矩形允许彼此"移动"以达到最终状态,只要它们不' t在末尾相交.

我们当前的算法是处理从最大高度到最小高度的矩形,并将它们放在可用的最低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为足够大的"Big 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

这是一个混合整数线性优化问题.您可以直接应用此类问题的常规解算器.

通常情况下,他们将执行的技巧,比如放宽对二元约束z_k的约束z_k在[0,1]算法,它变成了这个过程中的线性规划问题,这可以解决非常有效.

我不建议尝试重塑这些解决方案.