5.346. used_by_interval

DESCRIPTIONLINKSGRAPH
Origin

Derived from 𝚞𝚜𝚎𝚍_πš‹πš’.

Constraint

𝚞𝚜𝚎𝚍_πš‹πš’_πš’πš—πšπšŽπš›πšŸπšŠπš•(πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚1,πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚2,πš‚π™Έπš‰π™΄_π™Έπ™½πšƒπ™΄πšπš…π™°π™»)

Arguments
πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚1πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(πšŸπšŠπš›-πšπšŸπšŠπš›)
πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚2πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(πšŸπšŠπš›-πšπšŸπšŠπš›)
πš‚π™Έπš‰π™΄_π™Έπ™½πšƒπ™΄πšπš…π™°π™»πš’πš—πš
Restrictions
|πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚1|β‰₯|πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚2|
πš›πšŽπššπšžπš’πš›πšŽπš(πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚1,πšŸπšŠπš›)
πš›πšŽπššπšžπš’πš›πšŽπš(πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚2,πšŸπšŠπš›)
πš‚π™Έπš‰π™΄_π™Έπ™½πšƒπ™΄πšπš…π™°π™»>0
Purpose

Let N i (respectively M i ) denote the number of variables of the collection πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚1 (respectively πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚2) that take a value in the interval [πš‚π™Έπš‰π™΄_π™Έπ™½πšƒπ™΄πšπš…π™°π™»Β·i,πš‚π™Έπš‰π™΄_π™Έπ™½πšƒπ™΄πšπš…π™°π™»Β·i+πš‚π™Έπš‰π™΄_π™Έπ™½πšƒπ™΄πšπš…π™°π™»-1]. For all integer i we have M i >0β‡’N i >0.

Example
πšŸπšŠπš›-1,πšŸπšŠπš›-9,πšŸπšŠπš›-1,πšŸπšŠπš›-8,πšŸπšŠπš›-6,πšŸπšŠπš›-2,1,0,7,7,3

In the example, the third argument πš‚π™Έπš‰π™΄_π™Έπ™½πšƒπ™΄πšπš…π™°π™»=3 defines the following family of intervals [3Β·k,3Β·k+2], where k is an integer. Consequently the values of the collection πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚2=〈1,0,7,7βŒͺ are respectively located within intervals [0,2], [0,2], [6,8], [6,8]. Therefore intervals [0,2] and [6,8] are respectively used 2 and 2 times.

Similarly, the values of the collection πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚1=〈1,9,1,8,6,2βŒͺ are respectively located within intervals [0,2], [9,11], [0,2], [6,8], [6,8], [0,2]. Therefore intervals [0,2], [6,8] and [9,11] are respectively used 3, 2 and 1 times.

Consequently, the 𝚞𝚜𝚎𝚍_πš‹πš’_πš’πš—πšπšŽπš›πšŸπšŠπš• constraint holds since, for each interval associated with the collection πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚2=〈1,0,7,7βŒͺ, its number of occurrences within πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚1=〈1,9,1,8,6,2βŒͺ is greater than or equal to its number of occurrences within πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚2:

  • Interval [0,2] occurs 3 times within 〈1,9,1,8,6,2βŒͺ and 2 times within 〈1,0,7,7βŒͺ.

  • Interval [6,8] occurs 2 times within 〈1,9,1,8,6,2βŒͺ and 2 times within 〈1,0,7,7βŒͺ.

Symmetries
  • Items of πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚1 are permutable.

  • Items of πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚2 are permutable.

  • An occurrence of a value of πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚1.πšŸπšŠπš› that belongs to the k-th interval, of size πš‚π™Έπš‰π™΄_π™Έπ™½πšƒπ™΄πšπš…π™°π™», can be replaced by any other value of the same interval.

  • An occurrence of a value of πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚2.πšŸπšŠπš› that belongs to the k-th interval, of size πš‚π™Έπš‰π™΄_π™Έπ™½πšƒπ™΄πšπš…π™°π™», can be replaced by any other value of the same interval.

Reformulation

The 𝚞𝚜𝚎𝚍_πš‹πš’_πš’πš—πšπšŽπš›πšŸπšŠπš•(βŒ©πšŸπšŠπš›-U 1 πšŸπšŠπš›-U 2 ,...,πšŸπšŠπš›-U |πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚1| βŒͺ,βŒ©πšŸπšŠπš›-V 1 πšŸπšŠπš›-V 2 ,...,πšŸπšŠπš›-V |πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚2| βŒͺ,πš‚π™Έπš‰π™΄_π™Έπ™½πšƒπ™΄πšπš…π™°π™») constraint can be expressed by introducing |πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚1|+|πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚2| quotient variables

Β Β Β U i =πš‚π™Έπš‰π™΄_π™Έπ™½πšƒπ™΄πšπš…π™°π™»Β·P i +R i , R i ∈[0,πš‚π™Έπš‰π™΄_π™Έπ™½πšƒπ™΄πšπš…π™°π™»-1] (i∈[1,|πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚1|]),

Β Β Β V i =πš‚π™Έπš‰π™΄_π™Έπ™½πšƒπ™΄πšπš…π™°π™»Β·Q i +S i , S i ∈[0,πš‚π™Έπš‰π™΄_π™Έπ™½πšƒπ™΄πšπš…π™°π™»-1] (i∈[1,|πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚2|]),

in term of a conjunction of |πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚2| reified constraints of the form:

Β Β Β βˆ‘ 1≀j≀|πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚1| (Q i =P j )β‰₯βˆ‘ 1≀j≀|πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚2| (Q i =Q j ) (i∈[1,|πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚2|]).

Used in

πš”_𝚞𝚜𝚎𝚍_πš‹πš’_πš’πš—πšπšŽπš›πšŸπšŠπš•.

See also

implied by: πšœπšŠπš–πšŽ_πš’πš—πšπšŽπš›πšŸπšŠπš•.

soft variant: 𝚜𝚘𝚏𝚝_𝚞𝚜𝚎𝚍_πš‹πš’_πš’πš—πšπšŽπš›πšŸπšŠπš•_πšŸπšŠπš›Β (variable-based violation measure).

specialisation: 𝚞𝚜𝚎𝚍_πš‹πš’Β (πšŸπšŠπš›πš’πšŠπš‹πš•πšŽ/πšŒπš˜πš—πšœπšπšŠπš—πš replaced by πšŸπšŠπš›πš’πšŠπš‹πš•πšŽ).

system of constraints: πš”_𝚞𝚜𝚎𝚍_πš‹πš’_πš’πš—πšπšŽπš›πšŸπšŠπš•.

Keywords

constraint arguments: constraint between two collections of variables.

modelling: inclusion, interval.

Arc input(s)

πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚1 πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚2

Arc generator
π‘ƒπ‘…π‘‚π·π‘ˆπΆπ‘‡β†¦πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(πšŸπšŠπš›πš’πšŠπš‹πš•πšŽπšœ1,πšŸπšŠπš›πš’πšŠπš‹πš•πšŽπšœ2)

Arc arity
Arc constraint(s)
πšŸπšŠπš›πš’πšŠπš‹πš•πšŽπšœ1.πšŸπšŠπš›/πš‚π™Έπš‰π™΄_π™Έπ™½πšƒπ™΄πšπš…π™°π™»=πšŸπšŠπš›πš’πšŠπš‹πš•πšŽπšœ2.πšŸπšŠπš›/πš‚π™Έπš‰π™΄_π™Έπ™½πšƒπ™΄πšπš…π™°π™»
Graph property(ies)
β€’ for all connected components: ππ’πŽπ”π‘π‚π„β‰₯ππ’πˆππŠ
β€’ ππ’πˆππŠ=|πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚2|

Graph model

PartsΒ (A) andΒ (B) of FigureΒ 5.346.1 respectively show the initial and final graph associated with the Example slot. Since we use the ππ’πŽπ”π‘π‚π„ and ππ’πˆππŠ graph properties, the source and sink vertices of the final graph are stressed with a double circle. Since there is a constraint on each connected component of the final graph we also show the different connected components. Each of them corresponds to an equivalence class according to the arc constraint. Note that the vertex corresponding to the variable that takes value 9 was removed from the final graph since there is no arc for which the associated equivalence constraint holds. The 𝚞𝚜𝚎𝚍_πš‹πš’_πš’πš—πšπšŽπš›πšŸπšŠπš• constraint holds since:

  • For each connected component of the final graph the number of sources is greater than or equal to the number of sinks.

  • The number of sinks of the final graph is equal to |πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚2|.

Figure 5.346.1. Initial and final graph of the 𝚞𝚜𝚎𝚍_πš‹πš’_πš’πš—πšπšŽπš›πšŸπšŠπš• constraint
ctrs/used_by_intervalA
(a)
ctrs/used_by_intervalB
(b)
Signature

Since the initial graph contains only sources and sinks, and since sources of the initial graph cannot become sinks of the final graph, we have that the maximum number of sinks of the final graph is equal to |πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚2|. Therefore we can rewrite ππ’πˆππŠ=|πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚2| to ππ’πˆππŠβ‰₯|πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚2| and simplify ππ’πˆππŠ Β― Μ² to ππ’πˆππŠ Β―.