奇怪但实用的二维装箱优化 [英] Strange but practical 2D bin packing optimization
问题描述
我想编写一个生成图纸条块分割的面板应用程序。
I am trying to write an application that generates drawing for compartmentalized Panel.
我有N个机柜（2D矩形）（N＆LT; = 40）。为每个隔间有一最小高度（了minHeight [I]）和最小宽度（了minWidth [I]）相关联。面板本身也有一个MAXIMUM_HEIGHT约束
I have N cubicles (2D rectangles) (N <= 40). For each cubicle there is a minimum height (minHeight[i]) and minimum width (minWidth[i]) associated. The panel itself also has a MAXIMUM_HEIGHT constraint.
这些N隔间必须被布置在列方向格，使得上面的约束得到满足为每个隔间
These N cubicles have to be arranged in a column-wise grid such that the above constraints are met for each cubicle.
此外，每列的宽度，通过在该列中的每个隔间的minWidths的最大值决定。
Also, the width of each column is decided by the maximum of minWidths of each cubicle in that column.
此外，每个柱的高度应该是相同的。这决定了面板的高度
Also, the height of each column should be the same. This decides the height of the panel
我们可以留在任何一列空的空间添加备用开关柜，或者我们可以增加超过规定的最低任何柜体的高度/宽度。然而，我们不能旋转任何的小隔间。
We can add spare cubicles in the empty space left in any column or we can increase the height/width of any cubicle beyond the specified minimum. However we cannot rotate any of the cubicles.
OBJECTIVE: TO MINIMIZE TOTAL PANEL WIDTH.
在present我只是忽略柜的宽度在我的优化来实现它。我只是选择具有最大的了minHeight柜，并尝试在我的面板，以适应它。然而，它不出示担保的最佳解决方案。
At present I have implemented it simply by ignoring the widths of cubicles in my optimization. I just choose the cubicle with largest minHeight and try to fit it in my panel. However, it does not gurantee an optimal solution.
我可以得到任何比这更好的？
Can I get any better than this?
编辑1：面板=2100毫米，范围了minWidth（350毫米至800mm），范围了minHeight（225毫米到2100毫米）的MAXIMUM_HEIGHT
EDIT 1: MAXIMUM_HEIGHT of panel = 2100mm, minwidth range (350mm to 800mm), minheight range (225mm to 2100mm)
编辑2：问题的目的，为减少面板宽度（不是面板区域）
EDIT 2: PROBLEM OBJECTIVE: TO MINIMIZE PANEL WIDTH (not panel area).
推荐答案
由于：
- 在每个单元的
I = 1，...，M时，（分）宽度W_i和（分）高度H_i - 在任何堆叠的最大允许高度，
T
- for each cell
i = 1, ..., M, the (min) widthW_iand (min) heightH_i - the maximum allowed height of any stack,
T
我们可以制定混合整数计划如下：
We can formulate the mixed integer program as follows:
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 ）。
You can pick N to be any sufficiently large integer (for example, N = M).
插入这种混合整数规划到一个现有的混合整数规划求解确定的细胞 - 列映射的最佳 C_I，I = 1，...，M 值。
Plug this mixed integer program into an existing mixed integer program solver to determine the cell-to-column mapping given by the optimal C_i, i = 1, ..., M values.
这就是你不想重塑自我的部分。使用现有的解算器！
根据您的混合整数规划求解器软件包的前pressive力量，你可能会或可能无法直接适用我上面描述的制定。如果约束 [1] 和 [2] 由于基于集不能指定他们的性质或在最高，您可以手动转换制定一个相当于较少的声明，但更规范的一个并不需要这种EX pressive功率：
Depending on the expressive power of your mixed integer program solver package, you may or may not be able to directly apply the formulation I described above. If the constraints [1] and [2] cannot be specified because of the "set based" nature of them or the max, you can manually transform the formulation to an equivalent less-declarative but more-canonical one that does not need this expressive power:
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 =总和{C_i_k | K = 1，...，N} 。
Here the C_i variables from before (taking values in { 1, ..., N }) have been replaced with C_i_k variables (taking values in { 0, 1 }) under the relationship C_i = sum { C_i_k | k = 1, ..., N }.
最后一个单元到列映射描述了在 C_i_k ：细胞我所属列 K 当且仅当 C_i_k = 1 。
The final cell-to-column mapping is described by the the C_i_k: cell i belongs in column k if and only if C_i_k = 1.
这篇关于奇怪但实用的二维装箱优化的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
