Понимание формата ввода ограничения Geost Minizincs

Question

Я пытаюсь понять ограничение 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? Простой пример также помог бы, я нашел только довольно сложные здесь и здесь .

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 определяет нижнюю левую координату (наименьшего) прямоугольника angular выпуклой оболочки, охватывающей каждый объект i. Вектор kind определяет форму данного объекта i. Векторы l и u задают ограничения нижней и верхней границ для каждого измерения k N-мерного прямоугольника angular выпуклой оболочки, охватывающей все объекты в задаче.

A форма задается композицией набора прямоугольников. Каждый прямоугольник уникально идентифицируется по размеру и смещению относительно него. нижняя левая координата в соответствующей форме.

Обратите внимание, что может быть несколько способов разложить коллекцию фигур в набор прямоугольников. Как правило, всегда рекомендуется использовать наименьшее количество прямоугольников, насколько это возможно.

Это возможное разложение для нашего рабочего примера (прямоугольники с одинаковым размером и смещением имеют одинаковый цвет) :

Давайте закодируем этот пример в Minizin c.

Мы начнем с объявления входных параметров и выходных переменных наша задача:

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;

• Количество измерений для 2D-плоскости равно 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]);
----------

Графически решение:

---

Вы спрашиваете:

Является ли эта спецификация правильной?

Нет. Очевидным источником путаницы является определение формы . Приведенное выше объяснение должно прояснить этот аспект.