Understanding the input format of Minizincs geost constraint

Question

I'm trying to understand MiniZincs geost constraint, which is described in the packing constraint section of the docs. I'm trying to implement 2D packing of rectangles with rotation: So I'd like to fit rectangles on a plate of given length and width, but I'm having a hard time understanding the expected input format.

I have the following model, where I read the number of parts or rectangles to be placed into nParts. nShapes is the number of shapes those rectangles can take.

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

Given model seems to work for this extremly simple data (placing only one rectangle, with two possible shapes):

plateLength = 4000;
plateWidth = 4000;

nParts = 1;
nShapes = 2;

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

shape = [{1,2}];

Yet for more complex data, I'm running into errors, leading to the conclusion my understanding of the input format might be wrong. In the following example, I want to place 5 parts on a plate and I'd expect a result like this: The first rectangle can take the shape [4000, 2000] or [2000, 4000] and is therefor indexed via {1,2}, the second rectangle can take the shape [2000, 2000] and is indexed via {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}];

Is this specification correct? If not, how can I correctly specify the input for the geost constraint? A simple example would also help, I have only found rather complex ones here and here.

Autunite

Answer 1

The global non-overlap constraint geost for k dimensional objects enforces that no two objects overlap. Its cousin geost_bb further constraints the objects to fit within a global k dimensional bounding box.

---

Let's say that we want to find a suitable placement on a 2D plane for the following three objects:

Let's say that we can rotate each object by 90° (or its multiples), then our problem is to find a suitable placement on a 2D plane for 3 objects that can take one of the following 10 shapes:

(Notice that we need to take into account only two possible rotations for the second object.)

Now, let's take a look at the definition of the 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
    );

Everything, except for x, kind, l, u, is an input for the constraint. The matrix x specifies the bottom-left coordinate of the (smallest) rectangular convex-hull wrapping each object i. The vector kind specifies the shape of a given object i. The vectors l and u specify the lower and upper bound constraints for each k dimension of the N-dimensional rectangular convex-hull enveloping all of the objects in the problem.

A shape is given by the composition of a set of rectangles. Each rectangle is uniquely identified by its size and its offset wrt. the bottom-left coordinate in the corresponding shape.

Notice that there can be multiple ways to decompose a collection of shapes into a collection of rectangles. As a rule of thumb, it is always a good idea to use the least number of rectangles as possible.

This is a possible decomposition for our running example (rectangles with the same size and offset have the same color):

Let's encode this example into Minizinc.

We start by declaring the input parameters and the output variables of our problem:

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;

• The number of dimensions for a 2D plane is 2, so k is equal 2;
• The number of objects is 3, so nObjects is equal 3;
• The number of unique rectangles that are necessary to design all shapes in the problem is 13, so nRectangles is equal 13;
• The number of shapes is 10, so nShapes is equal 10;

Hence, we write:

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

Starting from the top-right corner, we define the size and offset of the 13 rectangles we need as follows:

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

Now we can define the 10 shapes we need in terms of the given list or rectangles:

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

    { 9 },
    { 10 },

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

We require that the solution to the problem must place all objects within 4x4 square placed at the origin:

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

In order to complete this example, we need an additional constraint to ensure that each object is assigned a valid shape among those available:

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;

A possible solution to this trivial problem is:

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

Graphically, the solution is:

---

You ask:

Is this specification correct?

No. The apparent source of confusion is the definition of a shape. The above explanation should clarify that aspect.

Teflon

Thanks a lot for the comprehensive explanation! This definitely explains my confusion. Gotta look into building a version that does not require different constraints for different data sets, but that should not be too hard to implement. – Autunite

@Autunite what kind of constraint is problematic for you? – Teflon

The constraints on the kind like constraint kind[1] in { 1 , 2, 3, 4 }; might be different for each data set, assuming I want to solve different packing problems with the same model... – Autunite

@Autunite ah, that was just me being lazy. I updated the answer with a better encoding. In the case that you have many objects of the same type (with the same valid shapes), you can refine it further by introducing an object_type array to act as an intermediary between an actual obj instance and the content of valid_shapes. – Teflon

A yeah, defining an array of valid shapes sounds like the solution to this problem. Once more, thanks alot :) – Autunite

@CarlS. You may want to ask a new question for visibility. I do not have the time to answer now, but other may. Is the solution going to contain a variable number of rectangles? Is it important to see rectangles as rotations or, in your case, can they be seen as different rectangles? The problem may not need geost if that is the case – Teflon