理解 Minizincs geost 约束的输入格式

Question

我正在尝试了解 MiniZincsgeost约束，这在 docs的打包约束部分中进行了描述。我正在尝试使用旋转来实现矩形的 2D 包装：所以我想将矩形放在给定长度和宽度的板上，但我很难理解预期的输入格式。

我有以下模型，我在其中读取了要放入nParts. nShapes是这些矩形可以采用的形状数。

include "globals.mzn";

int: nParts;
set of int: PARTS = 1..nParts;

int: nShapes; 
set of int: SHAPES = 1..nShapes;

int: plateLength;
int: plateWidth;

set of int: LEN = 0..plateLength;
set of int: WID = 0..plateWidth;

int: k = 2;
set of int: DIM = 1..k;

array[SHAPES,DIM] of int: rect_size;
array[SHAPES,DIM] of 0..0: rect_offset;
array[PARTS] of set of SHAPES: shape;

array[PARTS,DIM] of var int: xy;
array[PARTS] of var SHAPES: kind;

constraint geost(k, rect_size, rect_offset, shape, xy, kind);

constraint forall(i in PARTS)(kind[i] in shape[i]);

constraint forall(i in PARTS)(xy[i,1] in LEN);
constraint forall(i in PARTS)(xy[i,1] + rect_size[kind[i], 1] in LEN);

constraint forall(i in PARTS)(xy[i,2] in WID);
constraint forall(i in PARTS)(xy[i,2] + rect_size[kind[i], 2] in WID);

给定模型似乎适用于这种极其简单的数据（仅放置一个矩形，具有两种可能的形状）：

plateLength = 4000;
plateWidth = 4000;

nParts = 1;
nShapes = 2;

rect_size = [|4000, 2000|
2000, 4000|];
rect_offset = [|0, 0|
0, 0|];

shape = [{1,2}];

然而，对于更复杂的数据，我遇到了错误，导致我对输入格式的理解可能是错误的结论。在下面的示例中，我想将 5 个零件放在一个板上，我希望得到这样的结果：第一个矩形可以采用 [4000, 2000] 或 [2000, 4000] 的形状，因此通过 {1, 2}，第二个矩形可以采用形状 [2000, 2000] 并通过 {3} 进行索引。

plateLength = 4000;
plateWidth = 4000;

nParts = 5;
nShapes = 7;

rect_size = [|4000, 2000|
2000, 4000|
2000, 2000|
1000, 2000|
2000, 1000|
500, 1000|
1000, 500|];
rect_offset = [|0, 0|
0, 0|
0, 0|
0, 0|
0, 0|
0, 0|
0, 0|];

shape = [{1,2}, {3}, {4,5}, {6,7}, {6,7}];

这个规格正确吗？如果没有，我如何正确指定 geost 约束的输入？一个简单的例子也有帮助，我只在这里和这里找到了相当复杂的例子。

Answer 1

全球非重叠约束geost的k三维物体强制执行没有任何两个物体重叠。它的表亲geost_bb进一步约束对象以适应全局k维度边界框。

假设我们要为以下三个对象在 2D 平面上找到合适的位置：

假设我们可以将每个对象旋转 90°（或其倍数），那么我们的问题是在 2D 平面上为 3 个可以采用以下 10 种形状之一的对象找到合适的位置：

（请注意，我们只需要考虑第二个对象的两个可能的旋转。）

现在，让我们看一下geost_bb约束的定义：

constraint
    geost_bb(
        k,              % the number of dimensions
        rect_size,      % the size of each box in k dimensions
        rect_offset,    % the offset of each box from the base position in k dimensions
        shape,          % the set of rectangles defining the i-th shape
        x,              % the base position of each object.
                        % (var) x[i,j] is the position of object i in dimension j
        kind,           % (var) the shape used by each object
        l,              % array of lower bounds
        u               % array of upper bounds
    );

除 之外的所有内容都是x, kind, l, u约束的输入。矩阵x指定包裹每个对象的（最小）矩形凸包的左下角坐标i。矢量kind指定给定对象的形状i。向量l并u指定k包含问题中所有对象的 N 维矩形凸包的每个维度的下限和上限约束。

形状由一组矩形的组合给出。每个矩形都由其大小和偏移 wrt 唯一标识。相应形状的左下角坐标。

请注意，可以有多种方法将一组形状分解为一组矩形。根据经验，使用尽可能少的矩形总是一个好主意。

这是我们运行示例的可能分解（具有相同大小和偏移量的矩形具有相同的颜色）：

让我们将此示例编码为 Minizinc。

我们首先声明问题的输入参数和输出变量：

int: k;
int: nObjects;
int: nRectangles;
int: nShapes; 

set of int: DIMENSIONS = 1..k;
set of int: OBJECTS    = 1..nObjects;
set of int: RECTANGLES = 1..nRectangles;
set of int: SHAPES     = 1..nShapes;

array[DIMENSIONS] of int:             l;
array[DIMENSIONS] of int:             u;
array[RECTANGLES,DIMENSIONS] of int:  rect_size;
array[RECTANGLES,DIMENSIONS] of int:  rect_offset;
array[SHAPES] of set of RECTANGLES:   shape;
array[OBJECTS,DIMENSIONS] of var int: x;
array[OBJECTS] of var SHAPES:         kind;

• 二维平面的维数为 2，所以k等于2；
• 对象的数量是 3，所以nObjects是相等的3；
• 设计问题中所有形状所需的唯一矩形的数量是 13，所以nRectangles是相等的13；
• 形状的数量是 10，所以nShapes是相等的10；

因此，我们写：

k = 2;                  % Number of dimensions for a 2D Plane
nObjects = 3;           % Number of objects
nRectangles = 13;       % Number of rectangles
nShapes = 10;           % Number of shapes

从右上角开始，我们定义13我们需要的矩形的大小和偏移量，如下所示：

rect_size = [|
     4, 2|
     2, 4|
     4, 2|
     2, 4|

     1, 2|
     2, 1|
     1, 2|
     2, 1|

     2, 1|
     1, 2|

     1, 1|
     1, 1|
     1, 1|];

rect_offset = [|
     0, 0|
     0, 0|
     0, 2|
     2, 0|

     2, 2|
     2, 1|
     1, 0|
     0, 2|

     0, 0|
     0, 0|

     0, 1|
     1, 1|
     0, 0|];

现在我们可以10根据给定的列表或矩形定义我们需要的形状：

shape = [
    { 1, 5 },
    { 2, 6 },
    { 3, 7 },
    { 4, 8 },

    { 9 },
    { 10 },

    { 9, 11 },
    { 10, 12 },
    { 7, 11 },
    { 7, 13 }
];

我们要求问题的解决方案必须将所有对象放置在位于原点的 4x4 方格内：

l = [0, 0];
u = [4, 4];

为了完成这个例子，我们需要一个额外的约束来确保每个对象都被分配了一个有效的形状：

array[OBJECTS] of set of SHAPES: valid_shapes;

valid_shapes = [{1, 2, 3, 4}, {5, 6}, {7, 8, 9, 10}];

constraint forall (obj in OBJECTS) (
    kind[obj] in valid_shapes[obj]
);

...

solve satisfy;

这个微不足道的问题的可能解决方案是：

x = array2d(1..3, 1..2, [0, 0, 0, 3, 0, 0]);
kind = array1d(1..3, [4, 5, 7]);
----------

从图形上看，解决方案是：

你问：

这个规格正确吗？

不。明显的混淆来源是形状的定义。上面的解释应该澄清这一方面。