constraint-programming - 理解Minizincs geost约束的输入格式

Question

我正在尝试理解 MiniZincs geost 约束，它在 packing constraint section of the 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 约束的输入？一个简单的例子也会有所帮助，我只找到了相当复杂的例子here和 here .

Answer 1

k 维对象的全局非重叠约束 geost 强制没有两个对象重叠。它的表亲 geost_bb 进一步限制对象以适应全局 k 维边界框。

---

假设我们要在二维平面上为以下三个对象找到合适的位置:

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

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

现在，让我们看一下 geost_bb constraint 的定义:

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 指定 N 维矩形凸包的每个 k 维度的下限和上限约束问题中的对象。

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

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

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

让我们把这个例子编码成 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]);
----------

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

---

你问:

Is this specification correct?

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