奇怪但实用的2D装箱优化

奇怪但实用的2D装箱优化 公式

鉴于：

• 对于每个单元格

  i = 1, ..., M

  ，（最小）宽度

  W_i

  和（最小）高度

  H_i

• 任何堆栈的最大允许高度，

  T

我们可以制定混合整数程序，如下所示：

minimize sum { CW_k | k = 1, ..., N }with respect to    C_i in { 1, ..., N },  i = 1, ..., M    CW_k >= 0,  k = 1, ..., Nand subject to[1] sum { H_i | C_i = k } <= T,       k = 1, ..., N[2] CW_k = max { W_i | C_i = k },     k = 1, ..., N(or 0 when set is empty)

您可以选择

N

任何足够大的整数（例如

N = M

）。

算法

将此混合整数程序插入到现有的混合整数程序求解器中，以确定最佳

C_i, i = 1, ..., M

值给出的像元到列的映射。

这是您不想重塑自己的部分。 使用现有的求解器！

注意

根据混合整数程序求解程序包的表达能力，您可能会或可能无法直接应用上述公式。如果由于约束

[1]

或

[2]

的“基于集合”的性质而不能指定约束，则可以将其

max

手动转换为
等效的 较少声明但更具规范的表达，而无需这种表达能力：

minimize sum { CW_k | k = 1, ..., N }with respect to    C_i_k in { 0, 1 },     i = 1, ..., M; k = 1, ..., N    CW_k >= 0,  k = 1, ..., Nand subject to[1] sum { H_i * C_i_k | i = 1, ..., M } <= T,    k = 1, ..., N[2] CW_k >= W_i * C_i_k,   i = 1, ..., M; k = 1, ..., N[3] sum { C_i_k | k = 1, ..., N } = 1,i = 1, ..., M

在此关系下

C_i

，之前的变量（取值

{ 1, ..., N }

）已替换为

C_i_k

变量（取值

{ 0, 1 }

）

C_i = sum {C_i_k | k = 1, ..., N }

。

当且仅当时，最终的单元格到列的映射由

C_i_k

：单元格

i

属于列描述。

k``C_i_k = 1