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

Question

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

algorithmmathoptimizationknapsack-problem

12

示例：次优的输出

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

我有N个小隔间（2D矩形）（N <= 40）。对于每个隔间，都有最小高度（minHeight [i]）和最小宽度（minWidth [i]）相关联。面板本身还有一个MAXIMUM_HEIGHT约束。

这些N个隔间必须按列排列，以便满足每个隔间的上述约束条件。

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

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

我们可以在任何列的剩余空间中添加备用隔间，或者可以将任何隔间的高度/宽度增加到指定的最小值以上。但是我们不能旋转任何隔间。

OBJECTIVE: TO MINIMIZE TOTAL PANEL WIDTH.

目前，我在我的优化过程中只是简单地忽略了隔间的宽度。我只选择具有最大 minHeight 的隔间并尝试将其放入面板中。然而，这不能保证最优解。

我能不能做得更好呢？

编辑1：面板的 MAXIMUM_HEIGHT = 2100mm，minwidth 范围为（350 mm 到 800 mm），minheight 范围为（225 mm到2100 mm）

编辑2：问题目标：最小化面板的宽度（不是面积）。

- Abhishek Bansal

我正在努力理解问题中的高度部分。你是将小隔间堆叠起来吗？顶部的小隔间需要提供楼梯或梯子吗？ - Gilbert Le Blanc

@NealB 是的，你在可视化方面是正确的。 - Abhishek Bansal

你是否计算过每行/列最大排列数量下的最大隔间数？只是为了大致了解是否可以尝试每种组合，因为即使你编写了一个良好的算法，仅测试1％的组合也可能太大而无法测试所有情况。 - ColdCat

当您得到一个首选解决方案时，您能否发布“之后”配置的图片？ - Peter M

这不就是二维背包问题吗？因此是NP难问题吗？ - user180326

显示剩余4条评论

3个回答

2

一种解决方案是将小隔间行的宽度除以最小宽度。这样可以得到一排中可以容纳的最大小隔间数。

将第一个除法的余数除以小隔间数。这样可以得到额外的宽度，加上最小宽度即可使所有小隔间的宽度相等。

例如：您有一排小隔间长63米。每个小隔间的最小宽度为2米。我假设其中一个小隔间墙壁的厚度已经包含在2米内。我还假设一端的小隔间会靠着一堵墙。

进行计算，我们得到63 / 2 = 31.5或31个小隔间。

现在我们将0.5米除以31个小隔间，得到16毫米。因此，小隔间宽度为2.016米。

- Gilbert Le Blanc

列的宽度不必全部相同。例如，需要在窄列中放置窄隔间，在宽列中放置宽隔间。 - James Waldby - jwpat7

此外，每个小隔间的最小宽度和高度也不同。（抱歉，情况非常复杂） :) - Abhishek Bansal

@AbhishekBansal：好的，我的错。您可以使用与我的答案相同的想法，只是将隔间按最小宽度排序并降序排列。您仍然要均匀地分配剩余空间给该行中的所有隔间。 - Gilbert Le Blanc

谢谢你的回答。实际上，正如我所说的，目前我已经按照你建议的方式实现了它。但问题是还有第二个维度。例如，最小高度可能很大，而最小宽度可能很小，反之亦然。在这种情况下，这种方法是否可行？ - Abhishek Bansal

@AbhishekBansal：我仍然没有弄清楚高度如何影响放置小隔间。你需要发布一张照片来向我们展示。 - Gilbert Le Blanc

已添加图片，如有任何疑问，请询问。谢谢。 - Abhishek Bansal

2

您可以了解虚拟机打包，特别是针对虚拟机位置共存的共享感知算法：http://dl.acm.org/citation.cfm?id=1989554。您还可以阅读关于装箱问题的内容。这个问题已经很困难了，但是隔间可以共享宽度或高度。因此搜索空间变得更大。

- Micromega

谢谢提供链接。看起来很有趣，但我无法将那个问题适应到我的需求上。有什么想法吗？ - Abhishek Bansal

在虚拟机打包中，物品共享空间。总大小可能会比每个单独的物品小。http://en.m.wikipedia.org/wiki/Bin_packing_problem - Micromega

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Timothy Shields · Accepted Answer

数学公式

已知：

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

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

注意

根据您的混合整数程序求解器包的表达能力，您可能无法直接应用我上面描述的公式。如果由于它们的“集合基础”性质或max而无法指定约束条件[1]和[2]，则可以手动将公式转换为等效的、更少声明但更经典的公式，这些公式不需要这种表达能力。

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描述：当且仅当C_i_k = 1时，单元格i属于列k。