5.134. geost

DESCRIPTIONLINKS
Origin

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

Constraint

𝚐𝚎𝚘𝚜𝚝(𝙺,π™Ύπ™±π™Ήπ™΄π™²πšƒπš‚,πš‚π™±π™Ύπš‡π™΄πš‚)

Types
πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(𝚟-πšπšŸπšŠπš›)
π™Έπ™½πšƒπ™΄π™Άπ™΄πšπš‚πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(𝚟-πš’πš—πš)
π™Ώπ™Ύπš‚π™Έπšƒπ™Έπš…π™΄πš‚πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(𝚟-πš’πš—πš)
Arguments
π™Ίπš’πš—πš
π™Ύπ™±π™Ήπ™΄π™²πšƒπš‚πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(πš˜πš’πš-πš’πš—πš,πšœπš’πš-πšπšŸπšŠπš›,𝚑-πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚)
πš‚π™±π™Ύπš‡π™΄πš‚πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(πšœπš’πš-πš’πš—πš,𝚝-π™Έπ™½πšƒπ™΄π™Άπ™΄πšπš‚,πš•-π™Ώπ™Ύπš‚π™Έπšƒπ™Έπš…π™΄πš‚)
Restrictions
πš›πšŽπššπšžπš’πš›πšŽπš(πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚,𝚟)
|πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚|=𝙺
πš›πšŽπššπšžπš’πš›πšŽπš(π™Έπ™½πšƒπ™΄π™Άπ™΄πšπš‚,𝚟)
|π™Έπ™½πšƒπ™΄π™Άπ™΄πšπš‚|=𝙺
πš›πšŽπššπšžπš’πš›πšŽπš(π™Ώπ™Ύπš‚π™Έπšƒπ™Έπš…π™΄πš‚,𝚟)
|π™Ώπ™Ύπš‚π™Έπšƒπ™Έπš…π™΄πš‚|=𝙺
π™Ώπ™Ύπš‚π™Έπšƒπ™Έπš…π™΄πš‚.𝚟>0
𝙺>0
πš›πšŽπššπšžπš’πš›πšŽπš(π™Ύπ™±π™Ήπ™΄π™²πšƒπš‚,[πš˜πš’πš,πšœπš’πš,𝚑])
π™Ύπ™±π™Ήπ™΄π™²πšƒπš‚.πš˜πš’πšβ‰₯1
π™Ύπ™±π™Ήπ™΄π™²πšƒπš‚.πš˜πš’πšβ‰€|π™Ύπ™±π™Ήπ™΄π™²πšƒπš‚|
π™Ύπ™±π™Ήπ™΄π™²πšƒπš‚.πšœπš’πšβ‰₯1
π™Ύπ™±π™Ήπ™΄π™²πšƒπš‚.πšœπš’πšβ‰€|πš‚π™±π™Ύπš‡π™΄πš‚|
πš›πšŽπššπšžπš’πš›πšŽπš(πš‚π™±π™Ύπš‡π™΄πš‚,[πšœπš’πš,𝚝,πš•])
πš‚π™±π™Ύπš‡π™΄πš‚.πšœπš’πšβ‰₯1
πš‚π™±π™Ύπš‡π™΄πš‚.πšœπš’πšβ‰€|πš‚π™±π™Ύπš‡π™΄πš‚|
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,...,𝙺}. 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 the set of dimensions {1,2,...,𝙺} 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,...,𝙺} 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,πš˜πš’πš-1πšœπš’πš-1𝚑-1,2,πš˜πš’πš-2πšœπš’πš-5𝚑-2,1,πš˜πš’πš-3πšœπš’πš-8𝚑-4,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.134.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 (i.e., see part (D) if Figure 5.134.1).

Figure 5.134.1. The three objects of the example
ctrs/geost1
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.

Usage

The 𝚐𝚎𝚘𝚜𝚝 constraint allows to model directly a large number of placement problems.

Remark

In the two -dimensional case, when rectangles heights are all equal to one and when rectangles starts in the first dimension are all fixed, the 𝚐𝚎𝚘𝚜𝚝 constraint can be rewritten as a πš”_πšŠπš•πš•πšπš’πšπšπšŽπš›πšŽπš—πš constraint corresponding to a system of πšŠπš•πš•πšπš’πšπšπšŽπš›πšŽπš—πš constraints derived from the maximum cliques of the corresponding interval graph.

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 𝚐𝚎𝚘𝚜𝚝 a chain of lexicographical ordering constraints like πš•πšŽπš‘_πšŒπš‘πšŠπš’πš—_πš•πšŽπšœπšœ for enforcing a lexicographic ordering on the origin coordinates of identical objects, are described inΒ [AgrenCarlssonBeldiceanuSbihiTruchetZampelli09].

Systems

geost in Choco, geost in JaCoP, geost in SICStus.

See also

common keyword: πšŒπšŠπš•πšŽπš—πšπšŠπš›Β (scheduling with machine choice, calendars and preemption), πšπš’πšπšπš—Β (geometrical constraint,non-overlapping),

πš•πšŽπš‘_πšŒπš‘πšŠπš’πš—_πš•πšŽπšœπšœ, πš•πšŽπš‘_πšŒπš‘πšŠπš’πš—_πš•πšŽπšœπšœπšŽπššΒ (symmetry),

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

generalisation: 𝚐𝚎𝚘𝚜𝚝_πšπš’πš–πšŽΒ (πšπšŽπš–πš™πš˜πš›πšŠπš• πšπš’πš–πšŽπš—πšœπš’πš˜πš— added to πšπšŽπš˜πš–πšŽπšπš›πš’πšŒπšŠπš• πšπš’πš–πšŽπš—πšœπš’πš˜πš—πšœ).

specialisation: πš”_πšŠπš•πš•πšπš’πšπšπšŽπš›πšŽπš—πšΒ (when rectangles heights are all equal to 1 and rectangles starts in the first dimension are all fixed), πš•πšŽπš‘_πšŠπš•πš•πšπš’πšπšπšŽπš›πšŽπš—πšΒ (πš˜πš‹πš“πšŽπšŒπš replaced by πšŸπšŽπšŒπšπš˜πš›).

Keywords

application area: floor planning problem.

combinatorial object: pentomino.

constraint arguments: business rules.

constraint type: decomposition, timetabling constraint, predefined constraint, relaxation.

filtering: sweep.

geometry: geometrical constraint, non-overlapping.

heuristics: heuristics for two-dimensional rectangle placement problems.

modelling: scheduling with machine choice, calendars and preemption, disjunction, assignment dimension, assigning and scheduling tasks that run in parallel, assignment to the same set of values, relaxation dimension.

modelling exercises: scheduling with machine choice, calendars and preemption, assigning and scheduling tasks that run in parallel, assignment to the same set of values, relaxation 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.