algorithm - 奇怪但实用的二维装箱优化

Question

我正在尝试编写一个为分隔面板生成绘图的应用程序。

我有 N 个隔间(二维矩形)(N <= 40)。对于每个隔间，都有一个最小高度 (minHeight[i]) 和最小宽度 (minWidth[i]) 相关联。面板本身也有 MAXIMUM_HEIGHT 约束。

这 N 个隔间必须按列排列，以便每个隔间都满足上述限制条件。

此外，每列的宽度由该列中每个隔间的最大 minWidths 决定。

此外，每列的高度应该相同。这决定了面板的高度

我们可以在任何列的空白处添加备用隔间，或者我们可以将任何隔间的高度/宽度增加到超过指定的最小值。但是，我们不能轮换任何隔间。

OBJECTIVE: TO MINIMIZE TOTAL PANEL WIDTH.

目前我只是通过在我的优化中忽略小隔间的宽度来实现它。我只是选择具有最大 minHeight 的隔间并尝试将其放入我的面板中。但是，它并不能保证最佳解决方案。

我还能得到比这更好的吗？

编辑 1:面板的最大高度 = 2100 毫米，最小宽度范围(350 毫米到 800 毫米)，最小高度范围(225 毫米到 2100 毫米)

编辑 2:问题目标:最小化面板宽度(不是面板区域)。

Answer 1

配方

给定:

• 对于每个单元格 i = 1, ..., M ，(最小)宽度 W_i和(最小)高度 H_i
• 任何堆栈的最大允许高度，T

我们可以制定混合integer program如下:

minimize sum { CW_k | k = 1, ..., N }
with respect to

    C_i in { 1, ..., N },                        i = 1, ..., M

    CW_k >= 0,                                   k = 1, ..., N

and 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 给出的单元格到列的映射值(value)观。

这是您不想 reshape 自己的部分。使用现有的求解器!

注意事项

根据混合整数规划求解器包的表达能力，您可能会也可能不会直接应用我上面描述的公式。如果约束[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, ..., N

and 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 .