理解Minizincs geost约束的输入格式

Question

我正在尝试了解 packing constraint section of the docs 中描述的 MiniZincs geost 约束。我正在尝试实现 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 and 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?

没有。明显的混淆来源是 shape 的定义。上面的解释应该说明了这一点。

理解Minizincs geost约束的输入格式

Understanding the input format of Minizincs geost constraint

constraint-programming

minizinc