5.345. used_by

DESCRIPTIONLINKSGRAPHAUTOMATON
Origin

N.Β Beldiceanu

Constraint

𝚞𝚜𝚎𝚍_πš‹πš’(πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚1,πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚2)

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

All the values of the variables of collection πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚2 are used by the variables of collection πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚1.

Example
πšŸπšŠπš›-1,πšŸπšŠπš›-9,πšŸπšŠπš›-1,πšŸπšŠπš›-5,πšŸπšŠπš›-2,πšŸπšŠπš›-1,1,1,2,5

The 𝚞𝚜𝚎𝚍_πš‹πš’ constraint holds since, for each value occurring within the collection πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚2=〈1,1,2,5βŒͺ, its number of occurrences within πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚1=〈1,9,1,5,2,1βŒͺ is greater than or equal to its number of occurrences within πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚2:

  • Value 1 occurs 3 times within 〈1,9,1,5,2,1βŒͺ and 2 times within 〈1,1,2,5βŒͺ.

  • Value 2 occurs 1 times within 〈1,9,1,5,2,1βŒͺ and 1 times within 〈1,1,2,5βŒͺ.

  • Value 5 occurs 1 times within 〈1,9,1,5,2,1βŒͺ and 1 times within 〈1,1,2,5βŒͺ.

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

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

  • All occurrences of two distinct values in πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚1.πšŸπšŠπš› or πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚2.πšŸπšŠπš› can be swapped; all occurrences of a value in πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚1.πšŸπšŠπš› or πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚2.πšŸπšŠπš› can be renamed to any unused value.

Algorithm

As described inΒ [BeldiceanuKatrielThiel04a] we can pad πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚2 with dummy variables such that its cardinality will be equal to that cardinality of πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚1. The domain of a dummy variable contains all of the values. Then, we have a πšœπšŠπš–πšŽ constraint between the two sets. Direct arc-consistency and bound-consistency algorithms based on a flow model are also proposed inΒ [BeldiceanuKatrielThiel04a], [BeldiceanuKatrielThiel05], [Katriel05].

Reformulation

The 𝚞𝚜𝚎𝚍_πš‹πš’(βŒ©πšŸπšŠπš›-U 1 πšŸπšŠπš›-U 2 ,...,πšŸπšŠπš›-U |πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚1| βŒͺ,βŒ©πšŸπšŠπš›-V 1 πšŸπšŠπš›-V 2 ,...,πšŸπšŠπš›-V |πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚2| βŒͺ) constraint can be expressed in term of a conjunction of |πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚2| reified constraints of the form:

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

Used in

πš’πš—πš_πšŸπšŠπš•πšžπšŽ_πš™πš›πšŽπšŒπšŽπšπšŽ_πšŒπš‘πšŠπš’πš—, πš”_𝚞𝚜𝚎𝚍_πš‹πš’.

See also

generalisation: 𝚞𝚜𝚎𝚍_πš‹πš’_πš’πš—πšπšŽπš›πšŸπšŠπš•Β (πšŸπšŠπš›πš’πšŠπš‹πš•πšŽ replaced by πšŸπšŠπš›πš’πšŠπš‹πš•πšŽ/πšŒπš˜πš—πšœπšπšŠπš—πš), 𝚞𝚜𝚎𝚍_πš‹πš’_πš–πš˜πšπšžπš•πš˜Β (πšŸπšŠπš›πš’πšŠπš‹πš•πšŽ replaced by πšŸπšŠπš›πš’πšŠπš‹πš•πšŽ mod πšŒπš˜πš—πšœπšπšŠπš—πš), 𝚞𝚜𝚎𝚍_πš‹πš’_πš™πšŠπš›πšπš’πšπš’πš˜πš—Β (πšŸπšŠπš›πš’πšŠπš‹πš•πšŽ replaced by πšŸπšŠπš›πš’πšŠπš‹πš•πšŽβˆˆπš™πšŠπš›πšπš’πšπš’πš˜πš—).

implied by: πšœπšŠπš–πšŽ.

implies: 𝚞𝚜𝚎𝚜.

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

system of constraints: πš”_𝚞𝚜𝚎𝚍_πš‹πš’.

Keywords

characteristic of a constraint: automaton, automaton with array of counters.

combinatorial object: multiset.

constraint arguments: constraint between two collections of variables.

filtering: flow, arc-consistency, bound-consistency, DFS-bottleneck.

modelling: inclusion.

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.345.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 assigned to value 9 was removed from the final graph since there is no arc for which the associated equality 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.345.1. Initial and final graph of the 𝚞𝚜𝚎𝚍_πš‹πš’ constraint
ctrs/used_byA
(a)
ctrs/used_byB
(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 ππ’πˆππŠ Β―.

Automaton

FigureΒ 5.345.2 depicts the automaton associated with the 𝚞𝚜𝚎𝚍_πš‹πš’ constraint. To each item of the collection πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚1 corresponds a signature variable πš‚ i that is equal to 0. To each item of the collection πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚2 corresponds a signature variable πš‚ i+|πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚1| that is equal to 1.

Figure 5.345.2. Automaton of the 𝚞𝚜𝚎𝚍_πš‹πš’ constraint
ctrs/used_by1