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 范围（350mm 到 800mm），minheight 范围（225mm 到 2100mm）

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

4

3 回答 3

7

公式

鉴于：

  • 对于每个单元格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。

于 2013-09-03T17:05:38.417 回答
2

您可以查看 vm 打包，尤其是虚拟机配置的共享感知算法：http ://dl.acm.org/citation.cfm?id=1989554 。您还可以阅读有关 @ http://en.m.wikipedia.org/wiki/Bin_packing_problem的信息。这个问题已经很困难了，但隔间可以共享宽度或高度。因此搜索空间变得更大。

于 2013-09-03T08:00:52.873 回答
2

一种解决方案是将隔间行的宽度除以最小宽度。这为您提供了可以排成一排的最大隔间数量。

将第一个除法的余数除以隔间的数量。这为您提供了额外的宽度以添加到最小宽度，以使所有隔间宽度均匀。

示例：您有一排 63 米的隔间。每个隔间的最小宽度为 2 米。我假设其中一个隔间墙的厚度包含在 2 米中。我还假设一端隔间将靠墙。

算一下，我们得到 63 / 2 = 31.5 或 31 个隔间。

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

于 2013-08-30T17:23:50.663 回答