5.135. geost_time

DESCRIPTIONLINKS
Origin

Generalisation of πšπš’πšπšπš—.

Constraint

𝚐𝚎𝚘𝚜𝚝_πšπš’πš–πšŽ(𝙺,π™³π™Έπ™Όπš‚,π™Ύπ™±π™Ήπ™΄π™²πšƒπš‚,πš‚π™±π™Ύπš‡π™΄πš‚)

Types
πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(𝚟-πšπšŸπšŠπš›)
π™Έπ™½πšƒπ™΄π™Άπ™΄πšπš‚πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(𝚟-πš’πš—πš)
π™Ώπ™Ύπš‚π™Έπšƒπ™Έπš…π™΄πš‚πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(𝚟-πš’πš—πš)
Arguments
π™Ίπš’πš—πš
π™³π™Έπ™Όπš‚πšœπš’πš—πš
π™Ύπ™±π™Ήπ™΄π™²πšƒπš‚πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—πš˜πš’πš-πš’πš—πš,πšœπš’πš-πšπšŸπšŠπš›,𝚑-πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚,πšœπšπšŠπš›πš-πšπšŸπšŠπš›,πšπšžπš›πšŠπšπš’πš˜πš—-πšπšŸπšŠπš›,πšŽπš—πš-πšπšŸπšŠπš›
πš‚π™±π™Ύπš‡π™΄πš‚πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(πšœπš’πš-πš’πš—πš,𝚝-π™Έπ™½πšƒπ™΄π™Άπ™΄πšπš‚,πš•-π™Ώπ™Ύπš‚π™Έπšƒπ™Έπš…π™΄πš‚)
Restrictions
πš›πšŽπššπšžπš’πš›πšŽπš(πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚,𝚟)
|πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚|=𝙺
πš›πšŽπššπšžπš’πš›πšŽπš(π™Έπ™½πšƒπ™΄π™Άπ™΄πšπš‚,𝚟)
|π™Έπ™½πšƒπ™΄π™Άπ™΄πšπš‚|=𝙺
πš›πšŽπššπšžπš’πš›πšŽπš(π™Ώπ™Ύπš‚π™Έπšƒπ™Έπš…π™΄πš‚,𝚟)
|π™Ώπ™Ύπš‚π™Έπšƒπ™Έπš…π™΄πš‚|=𝙺
π™Ώπ™Ύπš‚π™Έπšƒπ™Έπš…π™΄πš‚.𝚟>0
𝙺β‰₯0
π™³π™Έπ™Όπš‚β‰₯0
π™³π™Έπ™Όπš‚<𝙺
πš›πšŽπššπšžπš’πš›πšŽπš(π™Ύπ™±π™Ήπ™΄π™²πšƒπš‚,[πš˜πš’πš,πšœπš’πš,𝚑])
πš›πšŽπššπšžπš’πš›πšŽ_𝚊𝚝_πš•πšŽπšŠπšœπš(2,π™Ύπ™±π™Ήπ™΄π™²πšƒπš‚,[πšœπšπšŠπš›πš,πšπšžπš›πšŠπšπš’πš˜πš—,πšŽπš—πš])
π™Ύπ™±π™Ήπ™΄π™²πšƒπš‚.πš˜πš’πšβ‰₯1
π™Ύπ™±π™Ήπ™΄π™²πšƒπš‚.πš˜πš’πšβ‰€|π™Ύπ™±π™Ήπ™΄π™²πšƒπš‚|
π™Ύπ™±π™Ήπ™΄π™²πšƒπš‚.πšœπš’πšβ‰₯1
π™Ύπ™±π™Ήπ™΄π™²πšƒπš‚.πšœπš’πšβ‰€|πš‚π™±π™Ύπš‡π™΄πš‚|
π™Ύπ™±π™Ήπ™΄π™²πšƒπš‚.πšπšžπš›πšŠπšπš’πš˜πš—β‰₯0
πš›πšŽπššπšžπš’πš›πšŽπš(πš‚π™±π™Ύπš‡π™΄πš‚,[πšœπš’πš,𝚝,πš•])
πš‚π™±π™Ύπš‡π™΄πš‚.πšœπš’πšβ‰₯1
πš‚π™±π™Ύπš‡π™΄πš‚.πšœπš’πšβ‰€|πš‚π™±π™Ύπš‡π™΄πš‚|
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 (O i ,O j ), i<j, O i and O j do not overlap with respect to a set of dimensions depicted by π™³π™Έπ™Όπš‚ as well as to the time axis. 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. More precisely, a shifted box is an entity defined by its shape id πšœπš’πš, 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 πš˜πš’πš, shape id πšœπš’πš and origin 𝚑.

An object O i does not overlap an object O j with respect to a set of dimensions depicted by π™³π™Έπ™Όπš‚ 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βˆˆπ™³π™Έπ™Όπš‚ 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,{0,1},πš˜πš’πš-1πšœπš’πš-1𝚑-1,2πšœπšπšŠπš›πš-0πšπšžπš›πšŠπšπš’πš˜πš—-1πšŽπš—πš-1,πš˜πš’πš-2πšœπš’πš-5𝚑-2,1πšœπšπšŠπš›πš-0πšπšžπš›πšŠπšπš’πš˜πš—-1πšŽπš—πš-1,πš˜πš’πš-3πšœπš’πš-8𝚑-4,1πšœπšπšŠπš›πš-0πšπšžπš›πšŠπšπš’πš˜πš—-1πšŽπš—πš-1,πšœπš’πš-1𝚝-0,0πš•-2,1,πšœπš’πš-1𝚝-0,1πš•-1,2,πšœπš’πš-1𝚝-1,2πš•-3,1,πšœπš’πš-2𝚝-0,0πš•-3,1,πšœπš’πš-2𝚝-0,1πš•-1,3,πšœπš’πš-2𝚝-2,1πš•-1,1,πšœπš’πš-3𝚝-0,0πš•-2,1,πšœπš’πš-3𝚝-1,1πš•-1,2,πšœπš’πš-3𝚝--2,2πš•-3,1,πšœπš’πš-4𝚝-0,0πš•-3,1,πšœπš’πš-4𝚝-0,1πš•-1,1,πšœπš’πš-4𝚝-2,1πš•-1,3,πšœπš’πš-5𝚝-0,0πš•-2,1,πšœπš’πš-5𝚝-1,1πš•-1,1,πšœπš’πš-5𝚝-0,2πš•-2,1,πšœπš’πš-6𝚝-0,0πš•-3,1,πšœπš’πš-6𝚝-0,1πš•-1,1,πšœπš’πš-6𝚝-2,1πš•-1,1,πšœπš’πš-7𝚝-0,0πš•-3,2,πšœπš’πš-8𝚝-0,0πš•-2,3

PartsΒ (A), (B) and (C) of FigureΒ 5.135.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 𝚐𝚎𝚘𝚜𝚝_πšπš’πš–πšŽ constraint holds since the three objects do not overlap: even if 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.135.1).

Figure 5.135.1. The three objects of the example
ctrs/geost_time1
Typical
|π™Ύπ™±π™Ήπ™΄π™²πšƒπš‚|>1
Symmetries
  • Items of π™Ύπ™±π™Ήπ™΄π™²πšƒπš‚ are permutable.

  • Items of πš‚π™±π™Ύπš‡π™΄πš‚ are permutable.

  • Items of π™Ύπ™±π™Ήπ™΄π™²πšƒπš‚.𝚑, πš‚π™±π™Ύπš‡π™΄πš‚.𝚝 and πš‚π™±π™Ύπš‡π™΄πš‚.πš• are permutable (same permutation used).

  • πš‚π™±π™Ύπš‡π™΄πš‚.πš•.𝚟 can be decreased to any value β‰₯1.

  • One and the same constant can be added to the πšœπšπšŠπš›πš and πšŽπš—πš attributes of all items of π™Ύπ™±π™Ήπ™΄π™²πšƒπš‚.

Usage

The 𝚐𝚎𝚘𝚜𝚝_πšπš’πš–πšŽ constraint allows to model directly a large number of placement problems. FigureΒ 5.135.2 sketches ten typical use of the 𝚐𝚎𝚘𝚜𝚝_πšπš’πš–πšŽ constraint:

  • The first caseΒ (A) corresponds to a non -overlapping constraint among three segments.

  • 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 πšŽπš•πšŽπš–πšŽπš—πš 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 πšŽπš•πšŽπš–πšŽπš—πš_πš•πšŽπšœπšœπšŽπšš 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.

Figure 5.135.2. Ten typical examples of use of the 𝚐𝚎𝚘𝚜𝚝_πšπš’πš–πšŽ constraint (ground instances)
ctrs/geost_time2
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

common keyword: πšπš’πšπšπš—, πš—πš˜πš—_πš˜πšŸπšŽπš›πš•πšŠπš™_πšœπš‹πš˜πš‘πšŽπšœΒ (geometrical constraint,non-overlapping), πšŸπš’πšœπš’πš‹πš•πšŽΒ (geometrical constraint,sweep).

specialisation: 𝚐𝚎𝚘𝚜𝚝 (πšπšŽπš–πš™πš˜πš›πšŠπš• πšπš’πš–πšŽπš—πšœπš’πš˜πš— removed).

Keywords

constraint type: decomposition, timetabling constraint, predefined constraint.

filtering: sweep.

geometry: geometrical constraint, non-overlapping.

modelling: assignment dimension, assignment to the same set of values, assigning and scheduling tasks that run in parallel, disjunction.

modelling exercises: assignment to the same set of values, assigning and scheduling tasks that run in parallel.