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

Question

我正在尝试编写一个为分区Panel生成绘图的应用程序.

我有N个小隔间(2D矩形)(N <= 40).对于每个隔间,存在最小高度(minHeight [i])和最小宽度(minWidth [i]).面板本身也有一个MAXIMUM_HEIGHT约束.

这些N小室必须以列方式网格排列,以便满足每个小隔间的上述限制.

此外,每列的宽度由该列中每个隔间的最大minWidth决定.

此外,每列的高度应相同.这决定了面板的高度

我们可以在任何列的左侧空白处添加备用隔间,或者我们可以将任何隔间的高度/宽度增加到指定的最小值以外.但是我们不能旋转任何小隔间.

OBJECTIVE: TO MINIMIZE TOTAL PANEL WIDTH.

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

我能比这更好吗？

编辑1:面板的MAXIMUM_HEIGHT = 2100mm,最小宽度范围(350mm至800mm),最小高度范围(225mm至2100mm)

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

Answer 1

公式

鉴于:

• 对于每个单元格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, ..., 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值给出的单元到列映射.

这是你不想重塑自己的部分.使用现有的求解器!

注意

根据混合整数程序求解程序包的表现力,您可能会或可能无法直接应用我上面描述的公式.如果由于它们的"基于集合"性质而无法指定约束[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.