5.120. element_matrix

DESCRIPTIONLINKSGRAPHAUTOMATON
Origin

CHIP

Constraint

πšŽπš•πšŽπš–πšŽπš—πš_πš–πšŠπšπš›πš’πš‘(π™Όπ™°πš‡_𝙸,π™Όπ™°πš‡_𝙹,π™Έπ™½π™³π™΄πš‡_𝙸,π™Έπ™½π™³π™΄πš‡_𝙹,π™Όπ™°πšƒπšπ™Έπš‡,πš…π™°π™»πš„π™΄)

Synonyms

πšŽπš•πšŽπš–_πš–πšŠπšπš›πš’πš‘, πš–πšŠπšπš›πš’πš‘.

Arguments
π™Όπ™°πš‡_π™Έπš’πš—πš
π™Όπ™°πš‡_π™Ήπš’πš—πš
π™Έπ™½π™³π™΄πš‡_π™ΈπšπšŸπšŠπš›
π™Έπ™½π™³π™΄πš‡_π™ΉπšπšŸπšŠπš›
π™Όπ™°πšƒπšπ™Έπš‡πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(πš’-πš’πš—πš,πš“-πš’πš—πš,𝚟-πš’πš—πš)
πš…π™°π™»πš„π™΄πšπšŸπšŠπš›
Restrictions
π™Όπ™°πš‡_𝙸β‰₯1
π™Όπ™°πš‡_𝙹β‰₯1
π™Έπ™½π™³π™΄πš‡_𝙸β‰₯1
π™Έπ™½π™³π™΄πš‡_π™Έβ‰€π™Όπ™°πš‡_𝙸
π™Έπ™½π™³π™΄πš‡_𝙹β‰₯1
π™Έπ™½π™³π™΄πš‡_π™Ήβ‰€π™Όπ™°πš‡_𝙹
πš›πšŽπššπšžπš’πš›πšŽπš(π™Όπ™°πšƒπšπ™Έπš‡,[πš’,πš“,𝚟])
πš’πš—πšŒπš›πšŽπšŠπšœπš’πš—πš_𝚜𝚎𝚚(π™Όπ™°πšƒπšπ™Έπš‡,[πš’,πš“])
π™Όπ™°πšƒπšπ™Έπš‡.πš’β‰₯1
π™Όπ™°πšƒπšπ™Έπš‡.πš’β‰€π™Όπ™°πš‡_𝙸
π™Όπ™°πšƒπšπ™Έπš‡.πš“β‰₯1
π™Όπ™°πšƒπšπ™Έπš‡.πš“β‰€π™Όπ™°πš‡_𝙹
|π™Όπ™°πšƒπšπ™Έπš‡|=π™Όπ™°πš‡_𝙸*π™Όπ™°πš‡_𝙹
Purpose

The π™Όπ™°πšƒπšπ™Έπš‡ collection corresponds to the two-dimensional matrix π™Όπ™°πšƒπšπ™Έπš‡[1..π™Όπ™°πš‡_𝙸,1..π™Όπ™°πš‡_𝙹]. πš…π™°π™»πš„π™΄ is equal to the entry π™Όπ™°πšƒπšπ™Έπš‡[π™Έπ™½π™³π™΄πš‡_𝙸,π™Έπ™½π™³π™΄πš‡_𝙹] of the previous matrix.

Example
4,3,1,3,πš’-1πš“-1𝚟-4,πš’-1πš“-2𝚟-1,πš’-1πš“-3𝚟-7,πš’-2πš“-1𝚟-1,πš’-2πš“-2𝚟-0,πš’-2πš“-3𝚟-8,πš’-3πš“-1𝚟-3,πš’-3πš“-2𝚟-2,πš’-3πš“-3𝚟-1,πš’-4πš“-1𝚟-0,πš’-4πš“-2𝚟-0,πš’-4πš“-3𝚟-6,7

The πšŽπš•πšŽπš–πšŽπš—πš_πš–πšŠπšπš›πš’πš‘ constraint holds since its last argument πš…π™°π™»πš„π™΄=7 is equal to the 𝚟 attribute of the k th item of the π™Όπ™°πšƒπšπ™Έπš‡ collection such that π™Όπ™°πšƒπšπ™Έπš‡[k].i=π™Έπ™½π™³π™΄πš‡_𝙸=1 and π™Όπ™°πšƒπšπ™Έπš‡[k].j=π™Έπ™½π™³π™΄πš‡_𝙹=3.

Typical
π™Όπ™°πš‡_𝙸>1
π™Όπ™°πš‡_𝙹>1
|π™Όπ™°πšƒπšπ™Έπš‡|>3
πš–πšŠπš‘πšŸπšŠπš•(π™Όπ™°πšƒπšπ™Έπš‡.πš’)>1
πš–πšŠπš‘πšŸπšŠπš•(π™Όπ™°πšƒπšπ™Έπš‡.πš“)>1
πš›πšŠπš—πšπšŽ(π™Όπ™°πšƒπšπ™Έπš‡.𝚟)>1
Symmetry

All occurrences of two distinct values in π™Όπ™°πšƒπšπ™Έπš‡.𝚟 or πš…π™°π™»πš„π™΄ can be swapped; all occurrences of a value in π™Όπ™°πšƒπšπ™Έπš‡.𝚟 or πš…π™°π™»πš„π™΄ can be renamed to any unused value.

Reformulation

The πšŽπš•πšŽπš–πšŽπš—πš_πš–πšŠπšπš›πš’πš‘(π™Όπ™°πš‡_𝙸,π™Όπ™°πš‡_𝙹,π™Έπ™½π™³π™΄πš‡_𝙸,π™Έπ™½π™³π™΄πš‡_𝙹,π™Όπ™°πšƒπšπ™Έπš‡,πš…π™°π™»πš„π™΄) constraint can be expressed in term of π™Όπ™°πš‡_𝙸 πšŽπš•πšŽπš–πšŽπš—πš(π™Έπ™½π™³π™΄πš‡_𝙹,𝙻𝙸𝙽𝙴 i ,πš…π™°πš i ) (i∈[1,π™Όπ™°πš‡_𝙸]), where 𝙻𝙸𝙽𝙴 i corresponds to the i-th line of the matrix π™Όπ™°πšƒπšπ™Έπš‡ and of one πšŽπš•πšŽπš–πšŽπš—πš(π™Έπ™½π™³π™΄πš‡_𝙸,βŒ©πš…π™°πš 1 ,πš…π™°πš 2 ,...,πš…π™°πš π™Όπ™°πš‡_𝙸 βŒͺ,πš…π™°π™»πš„π™΄) constraint.

If we consider the Example slot we get the following πšŽπš•πšŽπš–πšŽπš—πš constraints:

Systems

nth in Choco, element in Gecode.

See also

common keyword: πšŽπš•πšŽπš–, πšŽπš•πšŽπš–πšŽπš—πšΒ (array constraint).

Keywords

characteristic of a constraint: automaton, automaton without counters, reified automaton constraint, derived collection.

constraint arguments: ternary constraint.

constraint network structure: centered cyclic(3) constraint network(1).

constraint type: data constraint.

filtering: arc-consistency.

modelling: array constraint, matrix.

Derived Collection
πšŒπš˜πš•π™Έπšƒπ™΄π™Ό-πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(πš’πš—πšπšŽπš‘_πš’-πšπšŸπšŠπš›,πš’πš—πšπšŽπš‘_πš“-πšπšŸπšŠπš›,πšŸπšŠπš•πšžπšŽ-πšπšŸπšŠπš›),πš’πšπšŽπš–(πš’πš—πšπšŽπš‘_πš’-π™Έπ™½π™³π™΄πš‡_𝙸,πš’πš—πšπšŽπš‘_πš“-π™Έπ™½π™³π™΄πš‡_𝙹,πšŸπšŠπš•πšžπšŽ-πš…π™°π™»πš„π™΄)]
Arc input(s)

π™Έπšƒπ™΄π™Ό π™Όπ™°πšƒπšπ™Έπš‡

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

Arc arity
Arc constraint(s)
β€’ πš’πšπšŽπš–.πš’πš—πšπšŽπš‘_πš’=πš–πšŠπšπš›πš’πš‘.πš’
β€’ πš’πšπšŽπš–.πš’πš—πšπšŽπš‘_πš“=πš–πšŠπšπš›πš’πš‘.πš“
β€’ πš’πšπšŽπš–.πšŸπšŠπš•πšžπšŽ=πš–πšŠπšπš›πš’πš‘.𝚟
Graph property(ies)
𝐍𝐀𝐑𝐂=1

Graph model

Similar to the πšŽπš•πšŽπš–πšŽπš—πš constraint except that the arc constraint is updated according to the fact that we have a two -dimensional matrix.

PartsΒ (A) andΒ (B) of FigureΒ 5.120.1 respectively show the initial and final graph associated with the Example slot. Since we use the 𝐍𝐀𝐑𝐂 graph property, the unique arc of the final graph is stressed in bold.

Figure 5.120.1. Initial and final graph of the πšŽπš•πšŽπš–πšŽπš—πš_πš–πšŠπšπš›πš’πš‘ constraint
ctrs/element_matrixA
(a)
ctrs/element_matrixB
(b)
Signature

Because of the first condition of the arc constraint the final graph cannot have more than one arc. Therefore we can rewrite 𝐍𝐀𝐑𝐂=1 to 𝐍𝐀𝐑𝐂β‰₯1 and simplify 𝐍𝐀𝐑𝐂 Β― Μ² to 𝐍𝐀𝐑𝐂 Β―.

Automaton

FigureΒ 5.120.2 depicts the automaton associated with the πšŽπš•πšŽπš–πšŽπš—πš_πš–πšŠπšπš›πš’πš‘ constraint. Let 𝙸 k , 𝙹 k and πš… k respectively be the πš’, the πš“ and the 𝚟 k th attributes of the π™Όπ™°πšƒπšπ™Έπš‡ collection. To each sextuple (π™Έπ™½π™³π™΄πš‡_𝙸,π™Έπ™½π™³π™΄πš‡_𝙹,πš…π™°π™»πš„π™΄,𝙸 k ,𝙹 k ,πš… k ) corresponds a 0-1 signature variable πš‚ k as well as the following signature constraint: ((π™Έπ™½π™³π™΄πš‡_𝙸=𝙸 k )∧(π™Έπ™½π™³π™΄πš‡_𝙹=𝙹 k )∧(πš…π™°π™»πš„π™΄=πš… k ))β‡”πš‚ k .

Figure 5.120.2. Automaton of the πšŽπš•πšŽπš–πšŽπš—πš_πš–πšŠπšπš›πš’πš‘ constraint
ctrs/element_matrix1
Figure 5.120.3. Hypergraph of the reformulation corresponding to the automaton of the πšŽπš•πšŽπš–πšŽπš—πš_πš–πšŠπšπš›πš’πš‘ constraint
ctrs/element_matrix2