了解Minizincs地质约束的输入格式

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

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

---

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

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

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

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

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

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

注意，可以有多种方法将形状的集合分解为矩形的集合。根据经验，最好使用尽可能少的矩形。

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

k

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

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

• 2D平面的维数为2，因此

  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;

  等于k；
• 对象数为3，因此2等于nObjects;
• 设计问题中所有形状所需的唯一矩形的数量为13，因此3等于nRectangles；
• 形状的数量是10，所以13等于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

我们要求解决问题的方法必须将所有对象放置在原点的4x4正方形内：

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

    { 9 },
    { 10 },

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

为了完成此示例，我们需要附加约束以确保在可用的对象中为每个对象分配有效的形状：

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]);
----------

---

您询问：

此规范正确吗？

没有明显的混淆源是shape的定义。上面的解释应该阐明这一方面。