5.352. visible

DESCRIPTIONLINKS
Origin

Extension of accessibility parameter of πšπš’πšπšπš—.

Constraint

πšŸπš’πšœπš’πš‹πš•πšŽ(𝙺,π™³π™Έπ™Όπš‚,π™΅πšπ™Ύπ™Ό,π™Ύπ™±π™Ήπ™΄π™²πšƒπš‚,πš‚π™±π™Ύπš‡π™΄πš‚)

Types
πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(𝚟-πšπšŸπšŠπš›)
π™Έπ™½πšƒπ™΄π™Άπ™΄πšπš‚πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(𝚟-πš’πš—πš)
π™Ώπ™Ύπš‚π™Έπšƒπ™Έπš…π™΄πš‚πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(𝚟-πš’πš—πš)
π™³π™Έπ™Όπ™³π™ΈπšπšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(πšπš’πš–-πš’πš—πš,πšπš’πš›-πš’πš—πš)
Arguments
π™Ίπš’πš—πš
π™³π™Έπ™Όπš‚πšœπš’πš—πš
π™΅πšπ™Ύπ™Όπ™³π™Έπ™Όπ™³π™Έπš
π™Ύπ™±π™Ήπ™΄π™²πšƒπš‚πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—πš˜πš’πš-πš’πš—πš,πšœπš’πš-πšπšŸπšŠπš›,𝚑-πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚,πšœπšπšŠπš›πš-πšπšŸπšŠπš›,πšπšžπš›πšŠπšπš’πš˜πš—-πšπšŸπšŠπš›,πšŽπš—πš-πšπšŸπšŠπš›
πš‚π™±π™Ύπš‡π™΄πš‚πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(πšœπš’πš-πš’πš—πš,𝚝-π™Έπ™½πšƒπ™΄π™Άπ™΄πšπš‚,πš•-π™Ώπ™Ύπš‚π™Έπšƒπ™Έπš…π™΄πš‚,𝚏-π™³π™Έπ™Όπ™³π™Έπš)
Restrictions
πš›πšŽπššπšžπš’πš›πšŽπš(πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚,𝚟)
|πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚|=𝙺
πš›πšŽπššπšžπš’πš›πšŽπš(π™Έπ™½πšƒπ™΄π™Άπ™΄πšπš‚,𝚟)
|π™Έπ™½πšƒπ™΄π™Άπ™΄πšπš‚|=𝙺
πš›πšŽπššπšžπš’πš›πšŽπš(π™Ώπ™Ύπš‚π™Έπšƒπ™Έπš…π™΄πš‚,𝚟)
|π™Ώπ™Ύπš‚π™Έπšƒπ™Έπš…π™΄πš‚|=𝙺
π™Ώπ™Ύπš‚π™Έπšƒπ™Έπš…π™΄πš‚.𝚟>0
πš›πšŽπššπšžπš’πš›πšŽπš(π™³π™Έπ™Όπ™³π™Έπš,[πšπš’πš–,πšπš’πš›])
|π™³π™Έπ™Όπ™³π™Έπš|>0
|π™³π™Έπ™Όπ™³π™Έπš|≀𝙺+𝙺
πšπš’πšœπšπš’πš—πšŒπš(π™³π™Έπ™Όπ™³π™Έπš,[])
π™³π™Έπ™Όπ™³π™Έπš.πšπš’πš–β‰₯0
π™³π™Έπ™Όπ™³π™Έπš.πšπš’πš–<𝙺
π™³π™Έπ™Όπ™³π™Έπš.πšπš’πš›β‰₯0
π™³π™Έπ™Όπ™³π™Έπš.πšπš’πš›β‰€1
𝙺β‰₯0
π™³π™Έπ™Όπš‚β‰₯0
π™³π™Έπ™Όπš‚<𝙺
πš›πšŽπššπšžπš’πš›πšŽπš(π™Ύπ™±π™Ήπ™΄π™²πšƒπš‚,[πš˜πš’πš,πšœπš’πš,𝚑])
πš›πšŽπššπšžπš’πš›πšŽ_𝚊𝚝_πš•πšŽπšŠπšœπš(2,π™Ύπ™±π™Ήπ™΄π™²πšƒπš‚,[πšœπšπšŠπš›πš,πšπšžπš›πšŠπšπš’πš˜πš—,πšŽπš—πš])
π™Ύπ™±π™Ήπ™΄π™²πšƒπš‚.πš˜πš’πšβ‰₯1
π™Ύπ™±π™Ήπ™΄π™²πšƒπš‚.πš˜πš’πšβ‰€|π™Ύπ™±π™Ήπ™΄π™²πšƒπš‚|
π™Ύπ™±π™Ήπ™΄π™²πšƒπš‚.πšœπš’πšβ‰₯1
π™Ύπ™±π™Ήπ™΄π™²πšƒπš‚.πšœπš’πšβ‰€|πš‚π™±π™Ύπš‡π™΄πš‚|
π™Ύπ™±π™Ήπ™΄π™²πšƒπš‚.πšπšžπš›πšŠπšπš’πš˜πš—β‰₯0
πš›πšŽπššπšžπš’πš›πšŽπš(πš‚π™±π™Ύπš‡π™΄πš‚,[πšœπš’πš,𝚝,πš•])
πš‚π™±π™Ύπš‡π™΄πš‚.πšœπš’πšβ‰₯1
πš‚π™±π™Ύπš‡π™΄πš‚.πšœπš’πšβ‰€|πš‚π™±π™Ύπš‡π™΄πš‚|
Purpose

Holds if and only if:

  1. The difference between the end in time and the start in time of each object is equal to its duration in time.

  2. Given a collection of potential observations places π™΅πšπ™Ύπ™Ό, where each observation place is specified by a dimension (i.e.,Β an integer between 0 and k-1) and by a direction (i.e.,Β an integer between 0 and 1), and given for each shifted box of πš‚π™±π™Ύπš‡π™΄πš‚ a set of visible faces, enforce that at least one visible face of each shifted box associated with an object oβˆˆπ™Ύπ™±π™Ήπ™΄π™²πšƒπš‚ should be entirely visible from at least one observation place of π™΅πšπ™Ύπ™Ό at time o.πšœπšπšŠπš›πš as well as at time o.πšŽπš—πš-1. This notion is defined in a more formal way in the Remark slot.

Example
2,{0,1},πšπš’πš–-0 πšπš’πš›-1,πš˜πš’πš-1πšœπš’πš-1𝚑-1,2πšœπšπšŠπš›πš-8πšπšžπš›πšŠπšπš’πš˜πš—-8πšŽπš—πš-16,πš˜πš’πš-2πšœπš’πš-2𝚑-4,2πšœπšπšŠπš›πš-1πšπšžπš›πšŠπšπš’πš˜πš—-15πšŽπš—πš-16,πšœπš’πš-1𝚝-0,0πš•-1,2𝚏-πšπš’πš–-0 πšπš’πš›-1,πšœπš’πš-2𝚝-0,0πš•-2,3𝚏-πšπš’πš–-0 πšπš’πš›-1
2,{0,1},πšπš’πš–-0 πšπš’πš›-1,πš˜πš’πš-1πšœπš’πš-1𝚑-1,2πšœπšπšŠπš›πš-1πšπšžπš›πšŠπšπš’πš˜πš—-8πšŽπš—πš-9,πš˜πš’πš-2πšœπš’πš-2𝚑-4,2πšœπšπšŠπš›πš-1πšπšžπš›πšŠπšπš’πš˜πš—-15πšŽπš—πš-16,πšœπš’πš-1𝚝-0,0πš•-1,2𝚏-πšπš’πš–-0 πšπš’πš›-1,πšœπš’πš-2𝚝-0,0πš•-2,3𝚏-πšπš’πš–-0 πšπš’πš›-1
2,{0,1},πšπš’πš–-0 πšπš’πš›-1,πš˜πš’πš-1πšœπš’πš-1𝚑-1,1πšœπšπšŠπš›πš-1πšπšžπš›πšŠπšπš’πš˜πš—-15πšŽπš—πš-16,πš˜πš’πš-2πšœπš’πš-2𝚑-2,2πšœπšπšŠπš›πš-6πšπšžπš›πšŠπšπš’πš˜πš—-6πšŽπš—πš-12,πšœπš’πš-1𝚝-0,0πš•-1,2𝚏-πšπš’πš–-0 πšπš’πš›-1,πšœπš’πš-2𝚝-0,0πš•-2,3𝚏-πšπš’πš–-0 πšπš’πš›-1
2,{0,1},πšπš’πš–-0 πšπš’πš›-1,πš˜πš’πš-1πšœπš’πš-1𝚑-4,1πšœπšπšŠπš›πš-1πšπšžπš›πšŠπšπš’πš˜πš—-8πšŽπš—πš-9,πš˜πš’πš-2πšœπš’πš-2𝚑-1,2πšœπšπšŠπš›πš-1πšπšžπš›πšŠπšπš’πš˜πš—-15πšŽπš—πš-16,πšœπš’πš-1𝚝-0,0πš•-1,2𝚏-πšπš’πš–-0 πšπš’πš›-1,πšœπš’πš-2𝚝-0,0πš•-2,3𝚏-πšπš’πš–-0 πšπš’πš›-1
2,{0},πšπš’πš–-0 πšπš’πš›-1,πš˜πš’πš-1πšœπš’πš-1𝚑-2,1πšœπšπšŠπš›πš-1πšπšžπš›πšŠπšπš’πš˜πš—-8πšŽπš—πš-9,πš˜πš’πš-2πšœπš’πš-2𝚑-4,3πšœπšπšŠπš›πš-1πšπšžπš›πšŠπšπš’πš˜πš—-15πšŽπš—πš-16,πšœπš’πš-1𝚝-0,0πš•-1,2𝚏-πšπš’πš–-0 πšπš’πš›-1,πšœπš’πš-2𝚝-0,0πš•-2,2𝚏-πšπš’πš–-0 πšπš’πš›-1

The five previous examples correspond respectively to parts (I), (II), (III) and (IV) of FigureΒ 5.352.2 and to FigureΒ 5.352.3. Before explaining these five examples FigureΒ 5.352.1 first illustrates the notion of observations places and of visible faces.

Figure 5.352.1. Entirely visible faces (depicted by a thick line) of rectangles 1, 2, 3, 4, 5, 6 and 7 from the four observation places βŒ©π‘‘π‘–π‘š=0,π‘‘π‘–π‘Ÿ=1βŒͺ, βŒ©π‘‘π‘–π‘š=0,π‘‘π‘–π‘Ÿ=0βŒͺ, βŒ©π‘‘π‘–π‘š=1,π‘‘π‘–π‘Ÿ=1βŒͺ and βŒ©π‘‘π‘–π‘š=1,π‘‘π‘–π‘Ÿ=0βŒͺ (depicted by an arrow)
ctrs/visible1

We first need to introduce a number of definitions in order to illustrate the notion of visibility.

Definition 1 Consider two distinct objects o and o ' of the πšŸπš’πšœπš’πš‹πš•πšŽ constraint (i.e.,Β o,o ' βˆˆπ‘–π‘œπ‘π‘—π‘’π‘π‘‘π‘ ) as well as an observation place defined by the pair βŒ©πšπš’πš–,πšπš’πš›βŒͺβˆˆπ™΅πšπ™Ύπ™Ό. The object o is masked by the object o ' according to the observation place βŒ©πšπš’πš–,πšπš’πš›βŒͺ if there exist two shifted boxes s and s ' respectively associated with o and o ' such that conditionsΒ A, B, C, D and E all hold:

  • (A) o.πšπšžπš›πšŠπšπš’πš˜πš—>0∧o ' .πšπšžπš›πšŠπšπš’πš˜πš—>0∧o.πšŽπš—πš>o ' .πšœπšπšŠπš›πšβˆ§o ' .πšŽπš—πš>o.πšœπšπšŠπš›πš (i.e.,Β the time intervals associated with o and o ' intersect).

  • (B) Discarding dimension πšπš’πš–, s and s ' intersect in all dimensions specified by π™³π™Έπ™Όπš‚ (i.e.,Β objects o and o ' are in vis-Γ -vis).

  • (C) If πšπš’πš›=0

    then o.x[πšπš’πš–]+s.t[πšπš’πš–]β‰₯o ' .x[πšπš’πš–]+s ' .t[πšπš’πš–]+s ' .l[πšπš’πš–]

    else o ' .x[πšπš’πš–]+s ' .t[πšπš’πš–]β‰₯o.x[πšπš’πš–]+s.t[πšπš’πš–]+s.l[πšπš’πš–] (i.e.,Β in dimension πšπš’πš–, o and o ' are ordered in the wrong way according to direction πšπš’πš›).

  • (D) o.πšœπšπšŠπš›πš>o ' .πšœπšπšŠπš›πšβˆ¨o.πšŽπš—πš<o ' .πšŽπš—πš (i.e.,Β instants o.πšœπšπšŠπš›πš or o.πšŽπš—πš are located within interval [o ' .πšœπšπšŠπš›πš,o ' .πšŽπš—πš]; we consider also condition A.).

  • (E) The observation place βŒ©πšπš’πš–,πšπš’πš›βŒͺ occurs within the list of visible faces associated with the face attribute 𝚏 of the shifted box s (i.e.,Β the pair βŒ©πšπš’πš–,πšπš’πš›βŒͺ is a potentially visible face of o).

Definition 2 Consider an object o of the collection π™Ύπ™±π™Ήπ™΄π™²πšƒπš‚ as well as a possible observation place defined by the pair βŒ©πšπš’πš–,πšπš’πš›βŒͺ. The object o is masked according to the observation place βŒ©πšπš’πš–,πšπš’πš›βŒͺ if and only if at least one of the following conditions holds:

  • No shifted box associated with o has the pair βŒ©πšπš’πš–,πšπš’πš›βŒͺ as one of its potentially visible face.

  • The object o is masked according to the possible observation place βŒ©πšπš’πš–,πšπš’πš›βŒͺ by another object o ' .

FiguresΒ 5.352.2 and Β 5.352.3 respectively illustrate DefinitionΒ Definition 1 in the context of an observation place (depicted by a triangle) equal to the pair βŒ©πšπš’πš–=0,πšπš’πš›=1βŒͺ. Note that, in the context of FigureΒ 5.352.3, as the π™³π™Έπ™Όπš‚ parameter of the πšŸπš’πšœπš’πš‹πš•πšŽ constraint only mentions dimension 0 (and not dimension 1), one object may be masked by another object even if the two objects do not intersect in any dimension: i.e.,Β only their respective ordering in the dimension πšπš’πš–=0 as well as their positions in time matter.

Figure 5.352.2. Illustration of DefinitionΒ Definition 1: (I,II) the case where an object o is masked by an object o ' according to dimensions {0,1} and to the observation place βŒ©πšπš’πš–=0,πšπš’πš›=1βŒͺ because (A)Β o and o ' intersect in time, (B)Β o and o ' intersect in dimension 1, (C)Β o and o ' are not well ordered according to the observation place, (D)Β there exists an instant where o ' if present (but not o) and (E)Β βŒ©πšπš’πš–=0,πšπš’πš›=1βŒͺ is a potentially visible face of o; (III,IV) the case where an object o is not masked by an object o ' according to the observation place βŒ©πšπš’πš–=0,πšπš’πš›=1βŒͺ.
ctrs/visible2
Figure 5.352.3. Illustration of DefinitionΒ Definition 1: the case where an object o is masked by an object o ' according to dimension 0 and to the observation place βŒ©πšπš’πš–=0,πšπš’πš›=1βŒͺ because: (A)Β o and o ' intersect in time, (C)Β o and o ' are not well ordered according to the observation place and (D)Β there exists an instant where o ' if present (but not o) and (E)Β βŒ©πšπš’πš–=0,πšπš’πš›=1βŒͺ is a potentially visible face of o.
ctrs/visible3

Definition 3 Consider an object o of the collection π™Ύπ™±π™Ήπ™΄π™²πšƒπš‚ as well as a possible observation place defined by the pair βŒ©πšπš’πš–,πšπš’πš›βŒͺ. The object o is masked according to the observation place βŒ©πšπš’πš–,πšπš’πš›βŒͺ if and only if at least one of the following conditions holds:

  • No shifted box associated with o has the pair βŒ©πšπš’πš–,πšπš’πš›βŒͺ as one of its potentially visible face.

  • The object o is masked according to the possible observation place βŒ©πšπš’πš–,πšπš’πš›βŒͺ by another object o ' .

Definition 4 An object of the collection π™Ύπ™±π™Ήπ™΄π™²πšƒπš‚ constraint is masked according to a set of possible observation places π™΅πšπ™Ύπ™Ό if it is masked according to each observation place of π™΅πšπ™Ύπ™Ό.

We are now in position to define the πšŸπš’πšœπš’πš‹πš•πšŽ constraint.

Definition 5 Given a πšŸπš’πšœπš’πš‹πš•πšŽ(𝙺,π™³π™Έπ™Όπš‚,π™΅πšπ™Ύπ™Ό,π™Ύπ™±π™Ήπ™΄π™²πšƒπš‚,πš‚π™±π™Ύπš‡π™΄πš‚) constraint, the πšŸπš’πšœπš’πš‹πš•πšŽ constraint holds if none of the objects of π™Ύπ™±π™Ήπ™΄π™²πšƒπš‚ is masked according to the dimensions of π™³π™Έπ™Όπš‚ and to the set of possible observation places defined by π™΅πšπ™Ύπ™Ό.

Symmetries
  • Items of π™Ύπ™±π™Ήπ™΄π™²πšƒπš‚ are permutable.

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

Usage

We now give several typical concrete uses of the πšŸπš’πšœπš’πš‹πš•πšŽ constraint, which all mention the πšπš’πšπšπšœπš as well as the πšŸπš’πšœπš’πš‹πš•πšŽ constraints:

  • FigureΒ 5.352.4 corresponds to a ship loading problem where containers are piled within a ship by a crane each time the ship visits a given harbour. In this context we have first to express the fact that a container can only be placed on top of an already placed container and second, that a container can only be taken away if no container is placed on top of it. These two conditions are expressed by one single πšŸπš’πšœπš’πš‹πš•πšŽ constraint for which the π™³π™Έπ™Όπš‚ parameter mentions all three dimensions of the placement space and the π™΅πšπ™Ύπ™Ό parameter mentions the pair βŒ©πšπš’πš–=2,πšπš’πš›=1βŒͺ as its unique observation place. In addition we also use a πšπš’πšπšπšœπš constraint for expressing non -overlapping.

    Figure 5.352.4. Illustration of the ship loading problem
    ctrs/visible4
  • FigureΒ 5.352.5 corresponds to a container loading/unloading problem in the context of a pick -up delivery problem where the loading/unloading takes place with respect to the front door of the container. Beside the πšπš’πšπšπšœπš constraint used for expressing non -overlapping, we use two distinct πšŸπš’πšœπš’πš‹πš•πšŽ constraints:

    • The first πšŸπš’πšœπš’πš‹πš•πšŽ constraint takes care of the location of the front door of the container (each object o has to be loaded/unloaded without moving around any other object, i.e.,Β objects that are in the vis-Γ -vis of o according to the front door of the container). This is expressed by one single πšŸπš’πšœπš’πš‹πš•πšŽ constraint for which the π™³π™Έπ™Όπš‚ parameter mentions all three dimensions of the placement space and the π™΅πšπ™Ύπ™Ό parameter mentions the pair βŒ©πšπš’πš–=1,πšπš’πš›=0βŒͺ as its unique observation place.

    • The second πšŸπš’πšœπš’πš‹πš•πšŽ constraint takes care of the gravity dimension (i.e.,Β each object that has to be loaded should not be put under another object, and reciprocally each object that has to be unloaded should not be located under another object). This is expressed by the same πšŸπš’πšœπš’πš‹πš•πšŽ constraint that was used for the ship loading problem, i.e.,Β a πšŸπš’πšœπš’πš‹πš•πšŽ constraint for which the π™³π™Έπ™Όπš‚ parameter mentions all three dimensions of the placement space and the π™΅πšπ™Ύπ™Ό parameter mentions the pair βŒ©πšπš’πš–=2,πšπš’πš›=1βŒͺ as its unique observation place.

    Figure 5.352.5. Illustration of the pick-up delivery problem
    ctrs/visible5
  • FigureΒ 5.352.6 corresponds to a pallet loading problem where one has to place six objects on a pallet. Each object corresponds to a parallelepiped that has a bar code on one of its four sides (i.e.,Β the sides that are different from the top and the bottom of the parallelepiped). If, for some reason, an object has no bar code then we simply remove it from the objects that will be passed to the πšŸπš’πšœπš’πš‹πš•πšŽ constraint: this is for instance the case of the sixth object. In this context the constraint to enforce (beside the non -overlapping constraint between the parallelepipeds that are assigned to a same pallet) is the fact that the bar code of each object should be visible (i.e.,Β visible from one of the four sides of the pallet). This is expressed by the πšŸπš’πšœπš’πš‹πš•πšŽ constraint given in PartΒ (F) of FigureΒ 5.352.6.

Figure 5.352.6. Illustration of the pallet loading problem
ctrs/visible6
Remark

The πšŸπš’πšœπš’πš‹πš•πšŽ constraint is a generalisation of the πšŠπšŒπšŒπšŽπšœπšœπš’πš‹πš’πš•πš’πšπš’ constraint initially introduced in the context of the πšπš’πšπšπš— constraint.

See also

common keyword: πšπš’πšπšπš—Β (geometrical constraint),

𝚐𝚎𝚘𝚜𝚝, 𝚐𝚎𝚘𝚜𝚝_πšπš’πš–πšŽΒ (geometrical constraint,sweep),

πš—πš˜πš—_πš˜πšŸπšŽπš›πš•πšŠπš™_πšœπš‹πš˜πš‘πšŽπšœΒ (geometrical constraint).

Keywords

constraint type: decomposition, predefined constraint.

filtering: sweep.

geometry: geometrical constraint.