## 5.160. geost_time

 DESCRIPTION LINKS
Origin

Generalisation of $\mathrm{𝚍𝚒𝚏𝚏𝚗}$.

Constraint

$\mathrm{𝚐𝚎𝚘𝚜𝚝}_\mathrm{𝚝𝚒𝚖𝚎}\left(𝙺,\mathrm{𝙳𝙸𝙼𝚂},\mathrm{𝙾𝙱𝙹𝙴𝙲𝚃𝚂},\mathrm{𝚂𝙱𝙾𝚇𝙴𝚂}\right)$

Types
 $\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}$ $\mathrm{𝚌𝚘𝚕𝚕𝚎𝚌𝚝𝚒𝚘𝚗}\left(𝚟-\mathrm{𝚍𝚟𝚊𝚛}\right)$ $\mathrm{𝙸𝙽𝚃𝙴𝙶𝙴𝚁𝚂}$ $\mathrm{𝚌𝚘𝚕𝚕𝚎𝚌𝚝𝚒𝚘𝚗}\left(𝚟-\mathrm{𝚒𝚗𝚝}\right)$ $\mathrm{𝙿𝙾𝚂𝙸𝚃𝙸𝚅𝙴𝚂}$ $\mathrm{𝚌𝚘𝚕𝚕𝚎𝚌𝚝𝚒𝚘𝚗}\left(𝚟-\mathrm{𝚒𝚗𝚝}\right)$
Arguments
 $𝙺$ $\mathrm{𝚒𝚗𝚝}$ $\mathrm{𝙳𝙸𝙼𝚂}$ $\mathrm{𝚜𝚒𝚗𝚝}$ $\mathrm{𝙾𝙱𝙹𝙴𝙲𝚃𝚂}$ $\mathrm{𝚌𝚘𝚕𝚕𝚎𝚌𝚝𝚒𝚘𝚗}\left(\begin{array}{c}\mathrm{𝚘𝚒𝚍}-\mathrm{𝚒𝚗𝚝},\hfill \\ \mathrm{𝚜𝚒𝚍}-\mathrm{𝚍𝚟𝚊𝚛},\hfill \\ 𝚡-\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂},\hfill \\ \mathrm{𝚜𝚝𝚊𝚛𝚝}-\mathrm{𝚍𝚟𝚊𝚛},\hfill \\ \mathrm{𝚍𝚞𝚛𝚊𝚝𝚒𝚘𝚗}-\mathrm{𝚍𝚟𝚊𝚛},\hfill \\ \mathrm{𝚎𝚗𝚍}-\mathrm{𝚍𝚟𝚊𝚛}\hfill \end{array}\right)$ $\mathrm{𝚂𝙱𝙾𝚇𝙴𝚂}$ $\mathrm{𝚌𝚘𝚕𝚕𝚎𝚌𝚝𝚒𝚘𝚗}\left(\mathrm{𝚜𝚒𝚍}-\mathrm{𝚒𝚗𝚝},𝚝-\mathrm{𝙸𝙽𝚃𝙴𝙶𝙴𝚁𝚂},𝚕-\mathrm{𝙿𝙾𝚂𝙸𝚃𝙸𝚅𝙴𝚂}\right)$
Restrictions
 $|\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}|\ge 1$ $|\mathrm{𝙸𝙽𝚃𝙴𝙶𝙴𝚁𝚂}|\ge 1$ $|\mathrm{𝙿𝙾𝚂𝙸𝚃𝙸𝚅𝙴𝚂}|\ge 1$ $\mathrm{𝚛𝚎𝚚𝚞𝚒𝚛𝚎𝚍}$$\left(\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂},𝚟\right)$ $|\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}|=𝙺$ $\mathrm{𝚛𝚎𝚚𝚞𝚒𝚛𝚎𝚍}$$\left(\mathrm{𝙸𝙽𝚃𝙴𝙶𝙴𝚁𝚂},𝚟\right)$ $|\mathrm{𝙸𝙽𝚃𝙴𝙶𝙴𝚁𝚂}|=𝙺$ $\mathrm{𝚛𝚎𝚚𝚞𝚒𝚛𝚎𝚍}$$\left(\mathrm{𝙿𝙾𝚂𝙸𝚃𝙸𝚅𝙴𝚂},𝚟\right)$ $|\mathrm{𝙿𝙾𝚂𝙸𝚃𝙸𝚅𝙴𝚂}|=𝙺$ $\mathrm{𝙿𝙾𝚂𝙸𝚃𝙸𝚅𝙴𝚂}.𝚟>0$ $𝙺\ge 0$ $\mathrm{𝙳𝙸𝙼𝚂}\ge 0$ $\mathrm{𝙳𝙸𝙼𝚂}<𝙺$ $\mathrm{𝚍𝚒𝚜𝚝𝚒𝚗𝚌𝚝}$$\left(\mathrm{𝙾𝙱𝙹𝙴𝙲𝚃𝚂},\mathrm{𝚘𝚒𝚍}\right)$ $\mathrm{𝚛𝚎𝚚𝚞𝚒𝚛𝚎𝚍}$$\left(\mathrm{𝙾𝙱𝙹𝙴𝙲𝚃𝚂},\left[\mathrm{𝚘𝚒𝚍},\mathrm{𝚜𝚒𝚍},𝚡\right]\right)$ $\mathrm{𝚛𝚎𝚚𝚞𝚒𝚛𝚎}_\mathrm{𝚊𝚝}_\mathrm{𝚕𝚎𝚊𝚜𝚝}$$\left(2,\mathrm{𝙾𝙱𝙹𝙴𝙲𝚃𝚂},\left[\mathrm{𝚜𝚝𝚊𝚛𝚝},\mathrm{𝚍𝚞𝚛𝚊𝚝𝚒𝚘𝚗},\mathrm{𝚎𝚗𝚍}\right]\right)$ $\mathrm{𝙾𝙱𝙹𝙴𝙲𝚃𝚂}.\mathrm{𝚘𝚒𝚍}\ge 1$ $\mathrm{𝙾𝙱𝙹𝙴𝙲𝚃𝚂}.\mathrm{𝚘𝚒𝚍}\le |\mathrm{𝙾𝙱𝙹𝙴𝙲𝚃𝚂}|$ $\mathrm{𝙾𝙱𝙹𝙴𝙲𝚃𝚂}.\mathrm{𝚜𝚒𝚍}\ge 1$ $\mathrm{𝙾𝙱𝙹𝙴𝙲𝚃𝚂}.\mathrm{𝚜𝚒𝚍}\le |\mathrm{𝚂𝙱𝙾𝚇𝙴𝚂}|$ $\mathrm{𝙾𝙱𝙹𝙴𝙲𝚃𝚂}.\mathrm{𝚍𝚞𝚛𝚊𝚝𝚒𝚘𝚗}\ge 0$ $|\mathrm{𝚂𝙱𝙾𝚇𝙴𝚂}|\ge 1$ $\mathrm{𝚛𝚎𝚚𝚞𝚒𝚛𝚎𝚍}$$\left(\mathrm{𝚂𝙱𝙾𝚇𝙴𝚂},\left[\mathrm{𝚜𝚒𝚍},𝚝,𝚕\right]\right)$ $\mathrm{𝚂𝙱𝙾𝚇𝙴𝚂}.\mathrm{𝚜𝚒𝚍}\ge 1$ $\mathrm{𝚂𝙱𝙾𝚇𝙴𝚂}.\mathrm{𝚜𝚒𝚍}\le |\mathrm{𝚂𝙱𝙾𝚇𝙴𝚂}|$ $\mathrm{𝚍𝚘}_\mathrm{𝚗𝚘𝚝}_\mathrm{𝚘𝚟𝚎𝚛𝚕𝚊𝚙}\left(\mathrm{𝚂𝙱𝙾𝚇𝙴𝚂}\right)$
Purpose

Holds if (1) the difference between the end in time and the start in time of each object is equal to its duration in time, and if (2) for each pair of objects $\left({O}_{i},{O}_{j}\right)$, $i, ${O}_{i}$ and ${O}_{j}$ do not overlap with respect to a set of dimensions depicted by $\mathrm{𝙳𝙸𝙼𝚂}$ as well as to the time axis. Note that an object with duration zero can never overlap any other object. ${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 $𝙺$-dimensional space at a given offset (from the origin of the shape) with given sizes that are all strictly greater than 0. More precisely, a shifted box is an entity defined by its shape id $\mathrm{𝚜𝚒𝚍}$, shift offset $𝚝$, and sizes $𝚕$. 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 $\mathrm{𝚘𝚒𝚍}$, shape id $\mathrm{𝚜𝚒𝚍}$ and origin $𝚡$.

An object ${O}_{i}$ does not overlap an object ${O}_{j}$ with respect to a set of dimensions depicted by $\mathrm{𝙳𝙸𝙼𝚂}$ as well as to the time axis if and only if:

• The start in time of ${O}_{i}$ is greater than or equal to the end in time of ${O}_{j}$.

• The start in time of ${O}_{j}$ is greater than or equal to the end in time of ${O}_{i}$.

• 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\in \mathrm{𝙳𝙸𝙼𝚂}$ 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
$\left(\begin{array}{c}2,\left\{0,1\right\},\hfill \\ 〈\begin{array}{cccccc}\mathrm{𝚘𝚒𝚍}-1\hfill & \mathrm{𝚜𝚒𝚍}-1\hfill & 𝚡-〈1,2〉\hfill & \mathrm{𝚜𝚝𝚊𝚛𝚝}-0\hfill & \mathrm{𝚍𝚞𝚛𝚊𝚝𝚒𝚘𝚗}-1\hfill & \mathrm{𝚎𝚗𝚍}-1,\hfill \\ \mathrm{𝚘𝚒𝚍}-2\hfill & \mathrm{𝚜𝚒𝚍}-5\hfill & 𝚡-〈2,1〉\hfill & \mathrm{𝚜𝚝𝚊𝚛𝚝}-0\hfill & \mathrm{𝚍𝚞𝚛𝚊𝚝𝚒𝚘𝚗}-1\hfill & \mathrm{𝚎𝚗𝚍}-1,\hfill \\ \mathrm{𝚘𝚒𝚍}-3\hfill & \mathrm{𝚜𝚒𝚍}-8\hfill & 𝚡-〈4,1〉\hfill & \mathrm{𝚜𝚝𝚊𝚛𝚝}-0\hfill & \mathrm{𝚍𝚞𝚛𝚊𝚝𝚒𝚘𝚗}-1\hfill & \mathrm{𝚎𝚗𝚍}-1\hfill \end{array}〉,\hfill \\ 〈\begin{array}{ccc}\mathrm{𝚜𝚒𝚍}-1\hfill & 𝚝-〈0,0〉\hfill & 𝚕-〈2,1〉,\hfill \\ \mathrm{𝚜𝚒𝚍}-1\hfill & 𝚝-〈0,1〉\hfill & 𝚕-〈1,2〉,\hfill \\ \mathrm{𝚜𝚒𝚍}-1\hfill & 𝚝-〈1,2〉\hfill & 𝚕-〈3,1〉,\hfill \\ \mathrm{𝚜𝚒𝚍}-2\hfill & 𝚝-〈0,0〉\hfill & 𝚕-〈3,1〉,\hfill \\ \mathrm{𝚜𝚒𝚍}-2\hfill & 𝚝-〈0,1〉\hfill & 𝚕-〈1,3〉,\hfill \\ \mathrm{𝚜𝚒𝚍}-2\hfill & 𝚝-〈2,1〉\hfill & 𝚕-〈1,1〉,\hfill \\ \mathrm{𝚜𝚒𝚍}-3\hfill & 𝚝-〈0,0〉\hfill & 𝚕-〈2,1〉,\hfill \\ \mathrm{𝚜𝚒𝚍}-3\hfill & 𝚝-〈1,1〉\hfill & 𝚕-〈1,2〉,\hfill \\ \mathrm{𝚜𝚒𝚍}-3\hfill & 𝚝-〈-2,2〉\hfill & 𝚕-〈3,1〉,\hfill \\ \mathrm{𝚜𝚒𝚍}-4\hfill & 𝚝-〈0,0〉\hfill & 𝚕-〈3,1〉,\hfill \\ \mathrm{𝚜𝚒𝚍}-4\hfill & 𝚝-〈0,1〉\hfill & 𝚕-〈1,1〉,\hfill \\ \mathrm{𝚜𝚒𝚍}-4\hfill & 𝚝-〈2,1〉\hfill & 𝚕-〈1,3〉,\hfill \\ \mathrm{𝚜𝚒𝚍}-5\hfill & 𝚝-〈0,0〉\hfill & 𝚕-〈2,1〉,\hfill \\ \mathrm{𝚜𝚒𝚍}-5\hfill & 𝚝-〈1,1〉\hfill & 𝚕-〈1,1〉,\hfill \\ \mathrm{𝚜𝚒𝚍}-5\hfill & 𝚝-〈0,2〉\hfill & 𝚕-〈2,1〉,\hfill \\ \mathrm{𝚜𝚒𝚍}-6\hfill & 𝚝-〈0,0〉\hfill & 𝚕-〈3,1〉,\hfill \\ \mathrm{𝚜𝚒𝚍}-6\hfill & 𝚝-〈0,1〉\hfill & 𝚕-〈1,1〉,\hfill \\ \mathrm{𝚜𝚒𝚍}-6\hfill & 𝚝-〈2,1〉\hfill & 𝚕-〈1,1〉,\hfill \\ \mathrm{𝚜𝚒𝚍}-7\hfill & 𝚝-〈0,0〉\hfill & 𝚕-〈3,2〉,\hfill \\ \mathrm{𝚜𝚒𝚍}-8\hfill & 𝚝-〈0,0〉\hfill & 𝚕-〈2,3〉\hfill \end{array}〉\hfill \end{array}\right)$

Parts (A), (B) and (C) of Figure 5.160.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 $\mathrm{𝚐𝚎𝚘𝚜𝚝}_\mathrm{𝚝𝚒𝚖𝚎}$ constraint holds since the three objects do not overlap: even though the time intervals associated with each object overlap (i.e., they are in fact identical), their corresponding shapes do not overlap (i.e., see part (D) if Figure 5.160.1).

Typical
$|\mathrm{𝙾𝙱𝙹𝙴𝙲𝚃𝚂}|>1$
Symmetries
• Items of $\mathrm{𝙾𝙱𝙹𝙴𝙲𝚃𝚂}$ are permutable.

• Items of $\mathrm{𝚂𝙱𝙾𝚇𝙴𝚂}$ are permutable.

• Items of $\mathrm{𝙾𝙱𝙹𝙴𝙲𝚃𝚂}.𝚡$, $\mathrm{𝚂𝙱𝙾𝚇𝙴𝚂}.𝚝$ and $\mathrm{𝚂𝙱𝙾𝚇𝙴𝚂}.𝚕$ are permutable (same permutation used).

• $\mathrm{𝚂𝙱𝙾𝚇𝙴𝚂}.𝚕.𝚟$ can be decreased to any value $\ge 1$.

• One and the same constant can be added to the $\mathrm{𝚜𝚝𝚊𝚛𝚝}$ and $\mathrm{𝚎𝚗𝚍}$ attributes of all items of $\mathrm{𝙾𝙱𝙹𝙴𝙲𝚃𝚂}$.

Usage

The $\mathrm{𝚐𝚎𝚘𝚜𝚝}_\mathrm{𝚝𝚒𝚖𝚎}$ constraint allows to model directly a large number of placement problems. Figure 5.160.2 sketches ten typical use of the $\mathrm{𝚐𝚎𝚘𝚜𝚝}_\mathrm{𝚝𝚒𝚖𝚎}$ constraint:

• The first case (A) corresponds to a non-overlapping constraint among three segments (or three tasks in disjunction).

• The second, third and fourth cases (B,C,D) correspond to a non-overlapping constraint between rectangles where (B) and (C) are special cases where the sizes of all rectangles in the second dimension are equal to 1; this can be interpreted as a machine assignment problem where each rectangle corresponds to a non-pre-emptive task that has to be placed in time and assigned to a specific machine so that no two tasks assigned to the same machine overlap in time. In Part (B) the duration of each task is fixed, while in Part (C) the duration depends on the machine to which the task is actually assigned. This dependence can be expressed by the $\mathrm{𝚎𝚕𝚎𝚖𝚎𝚗𝚝}$ constraint, which specifies the dependence between the shape variable and the assignment variable of each task.

• The fifth case (E) corresponds to a non-overlapping constraint between rectangles where each rectangle can have two orientations. This is achieved by associating with each rectangle two shapes of respective sizes $l·h$ and $h·l$. Since their orientation is not initially fixed, an $\mathrm{𝚎𝚕𝚎𝚖𝚎𝚗𝚝}_\mathrm{𝚕𝚎𝚜𝚜𝚎𝚚}$ constraint can be used for enforcing the three rectangles to be included within the bounding box defined by the origin's coordinates $1,1$ and sizes $8,3$.

• The sixth case (F) corresponds to a non-overlapping constraint between more complex objects where each object is described by a given set of rectangles.

• The seventh case (G) describes a rectangle placement problem where one has to first assign each rectangle to a strip so that all rectangles that are assigned to the same strip do not overlap.

• The eighth case (H) corresponds to a non-overlapping constraint between parallelepipeds.

• The ninth case (I) can be interpreted as a non-overlapping constraint between parallelepipeds that are assigned to the same  container. The first dimension corresponds to the identifier of the  container, while the next three dimensions are associated with the position of a parallelepiped inside a  container.

• Finally the tenth case (J) describes a rectangle placement problem over three consecutive time-slots: rectangles assigned to the same time-slot should not overlap in time. We initially start with the three rectangles 1, 2 and 3. Rectangle 3 is no more present at instant 2 (the arrow $↓$ within rectangle 3 at time 1 indicates that rectangle 3 will disappear at the next time-point), while rectangle 4 appears at instant 2 (the arrow $↑$ within rectangle 4 at time 2 denotes the fact that the rectangle 4 appears at instant 2). Finally rectangle 2 disappears at instant 3 and is replaced by rectangle 5.

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.

Systems

geost in Choco, geost in JaCoP.

See also

specialisation: $\mathrm{𝚐𝚎𝚘𝚜𝚝}$ ($\mathrm{𝚝𝚎𝚖𝚙𝚘𝚛𝚊𝚕}$ $\mathrm{𝚍𝚒𝚖𝚎𝚗𝚜𝚒𝚘𝚗}$ removed).

Keywords