5.131. geost

Origin

Generalisation of diffn.

Constraint

geost​(K,​OBJECTS,​SBOXES)​

Type(s)

VARIABLES	collection​(v−dvar)​
INTEGERS	collection​(v−int)​
POSITIVES	collection​(v−int)​

Argument(s)

K	int
OBJECTS	collection​(oid−int,​sid−dvar,​x−VARIABLES)​
SBOXES	collection​(sid−int,​t−INTEGERS,​l−POSITIVES)​

Restriction(s)

required​(VARIABLES,​v)​

|VARIABLES|=K

required​(INTEGERS,​v)​

|INTEGERS|=K

required​(POSITIVES,​v)​

|POSITIVES|=K

POSITIVES.v>​0

K>​0

required​(OBJECTS,​​[oid,​sid,​x]​)​

OBJECTS.oid≥1

OBJECTS.oid≤|OBJECTS|

OBJECTS.sid≥1

OBJECTS.sid≤|SBOXES|

required​(SBOXES,​​[sid,​t,​l]​)​

SBOXES.sid≥1

SBOXES.sid≤|SBOXES|

Purpose

Holds if, for each pair of objects ​(O_i,​O_j)​, i​<j, O_i and O_j do not overlap with respect to a set of dimensions ​{1,​2,​...,​K}​. O_i and O_j are objects that take a shape among a set of shapes. Each shape is defined as a finite set of shifted boxes, where each shifted box is described by a box in a K -dimensional space at a given offset (from the origin of the shape) with given sizes. More precisely, a shifted box is an entity defined by its shape id sid, shift offset t, and sizes l. Then, a shape is defined as the union of shifted boxes sharing the same shape id. An object is an entity defined by its unique object identifier oid, shape id sid and origin x.

An object O_i does not overlap an object O_j with respect to the set of dimensions ​{1,​2,​...,​K}​ if and only if for all shifted box s_i associated with O_i and for all shifted box s_j associated with O_j there exists a dimension d∈​{1,​2,​...,​K}​ such that the start of s_i in dimension d is greater than or equal to the end of s_j in dimension d, or the start of s_j in dimension d is greater than or equal to the end of s_i in dimension d.

Example

( 2,​〈 oid−1 sid−1 x−〈1,​2〉,​ oid−2 sid−5 x−〈2,​1〉,​ oid−3 sid−8 x−〈4,​1〉 〉,​ 〈 sid−1 t−〈0,​0〉 l−〈2,​1〉,​ sid−1 t−〈0,​1〉 l−〈1,​2〉,​ sid−1 t−〈1,​2〉 l−〈3,​1〉,​ sid−2 t−〈0,​0〉 l−〈3,​1〉,​ sid−2 t−〈0,​1〉 l−〈1,​3〉,​ sid−2 t−〈2,​1〉 l−〈1,​1〉,​ sid−3 t−〈0,​0〉 l−〈2,​1〉,​ sid−3 t−〈1,​1〉 l−〈1,​2〉,​ sid−3 t−〈−2,​2〉 l−〈3,​1〉,​ sid−4 t−〈0,​0〉 l−〈3,​1〉,​ sid−4 t−〈0,​1〉 l−〈1,​1〉,​ sid−4 t−〈2,​1〉 l−〈1,​3〉,​ sid−5 t−〈0,​0〉 l−〈2,​1〉,​ sid−5 t−〈1,​1〉 l−〈1,​1〉,​ sid−5 t−〈0,​2〉 l−〈2,​1〉,​ sid−6 t−〈0,​0〉 l−〈3,​1〉,​ sid−6 t−〈0,​1〉 l−〈1,​1〉,​ sid−6 t−〈2,​1〉 l−〈1,​1〉,​ sid−7 t−〈0,​0〉 l−〈3,​2〉,​ sid−8 t−〈0,​0〉 l−〈2,​3〉 〉 )

Parts (A), (B) and (C) of Figure 5.131.1 respectively represent the potential shapes associated with the three objects of the example. Part (D) shows the position of the three objects of the example, where the first, second and third objects were respectively assigned shapes 1, 5 and 8. The coordinates of the leftmost lowest corner of each object are stressed in bold. The geost constraint holds since the three objects do not overlap (i.e., see part (D) if Figure 5.131.1).

Figure 5.131.1. The three objects of the example

Usage

The geost constraint allows to model directly a large number of placement problems.

Algorithm

A sweep-based filtering algorithm for this constraint is described in [BeldiceanuCarlssonPoderSadekTruchet07]. Unlike previous sweep filtering algorithms which move a line for finding a feasible position for the origin of an object, this algorithm performs a recursive traversal of the multidimensional placement space. It explores all points of the domain of the origin of the object under focus, one by one, in increasing lexicographic order, until a point is found that is not infeasible for any non -overlapping constraints. To make the search efficient, instead of moving each time to the successor point, the search is arranged so that it skips points that are known to be infeasible for some non -overlapping constraint.

Within the context of breaking symmetries six different ways of integrating within geost a chain of lexicographical ordering constraints like lex_chain_less for enforcing a lexicographic ordering on the origin coordinates of identical objects, are described in [AgrenCarlssonBeldiceanuSbihiTruchetZampelli09].

Systems

geost in Choco, geost in Jacop.

See also

visible, non_overlap_sboxes, diffn, lex_chain_less, lex_chain_lesseq, lex_alldifferent.

Key words

application area: floor planning problem.

combinatorial object: pentomino.

constraint arguments: business rules.

constraint type: decomposition, timetabling constraint, predefined constraint.

filtering: sweep.

geometry: geometrical constraint, non-overlapping.

heuristics: heuristics for two-dimensional rectangle placement problems.

modelling: disjunction, assignment dimension.

problems: strip packing, two dimensional orthogonal packing, pallet loading.

puzzles: squared squares, packing almost squares, Partridge, pentomino, Shikaku, smallest square for packing consecutive dominoes, smallest square for packing rectangles with distinct sizes, smallest rectangle area, Conway packing problem.

symmetry: symmetry.