5.218. minimum_except_0

DESCRIPTIONLINKSGRAPHAUTOMATON
Origin

Derived from πš–πš’πš—πš’πš–πšžπš–.

Constraint

πš–πš’πš—πš’πš–πšžπš–_πšŽπš‘πšŒπšŽπš™πš_0(𝙼𝙸𝙽,πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚,π™³π™΄π™΅π™°πš„π™»πšƒ)

Arguments
π™Όπ™Έπ™½πšπšŸπšŠπš›
πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(πšŸπšŠπš›-πšπšŸπšŠπš›)
π™³π™΄π™΅π™°πš„π™»πšƒπš’πš—πš
Restrictions
𝙼𝙸𝙽>0
π™Όπ™Έπ™½β‰€π™³π™΄π™΅π™°πš„π™»πšƒ
|πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚|>0
πš›πšŽπššπšžπš’πš›πšŽπš(πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚,πšŸπšŠπš›)
πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚.πšŸπšŠπš›β‰₯0
πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚.πšŸπšŠπš›β‰€π™³π™΄π™΅π™°πš„π™»πšƒ
π™³π™΄π™΅π™°πš„π™»πšƒ>0
Purpose

All variables of the collection πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚ are assigned a value that belongs to interval [0,π™³π™΄π™΅π™°πš„π™»πšƒ]. 𝙼𝙸𝙽 is the minimum value of the collection of domain variables πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚, ignoring all variables that take 0 as value. When all variables of the collection πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚ are assigned value 0, 𝙼𝙸𝙽 is set to the default value π™³π™΄π™΅π™°πš„π™»πšƒ.

Example
3,πšŸπšŠπš›-3,πšŸπšŠπš›-7,πšŸπšŠπš›-6,πšŸπšŠπš›-7,πšŸπšŠπš›-4,πšŸπšŠπš›-7,1000000
2,πšŸπšŠπš›-3,πšŸπšŠπš›-2,πšŸπšŠπš›-0,πšŸπšŠπš›-7,πšŸπšŠπš›-2,πšŸπšŠπš›-6,1000000
1000000,πšŸπšŠπš›-0,πšŸπšŠπš›-0,πšŸπšŠπš›-0,πšŸπšŠπš›-0,πšŸπšŠπš›-0,πšŸπšŠπš›-0,1000000

The three examples of the πš–πš’πš—πš’πš–πšžπš–_πšŽπš‘πšŒπšŽπš™πš_0 constraint respectively hold since:

  • Within the first example, 𝙼𝙸𝙽 is set to the minimum value 3 of the collection 〈3,7,6,7,4,7βŒͺ.

  • Within the second example, 𝙼𝙸𝙽 is set to the minimum value 2 (ignoring value 0) of the collection 〈3,2,0,7,2,6βŒͺ.

  • Finally within the third example, 𝙼𝙸𝙽 is set to the default value 1000000 since all items of the collection 〈0,0,0,0,0,0βŒͺ are set to 0.

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

  • All occurrences of two distinct values of πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚.πšŸπšŠπš› can be swapped.

Remark

The joker value 0 makes sense only because we restrict the variables of the πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚ collection to take non -negative values.

Reformulation

By (1)Β associating to each variable V i (i∈[1,|πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚|]) of the πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚ collection a rank variable R i ∈[0,|πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚|-1] with the reified constraint R i =1⇔V i =𝙼𝙸𝙽, and by creating for each pair of variables V i ,V j (i,j<i∈[1,|πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚|]) the reified constraints

Β Β Β V i <V j ⇔R i <R j ,

Β Β Β V i =V j ⇔R i =R j ,

Β Β Β V i >V j ⇔R i >R j ,

and by (2)Β creating the reified constraint

Β Β Β V 1 =0∧V 2 =0∧...∧V n =0⇒𝙼𝙸𝙽=π™³π™΄π™΅π™°πš„π™»πšƒ,

one can reformulate the πš–πš’πš—πš’πš–πšžπš–_πšŽπš‘πšŒπšŽπš™πš_0 constraint in term of 3Β·|πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚|Β·(|πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚|-1) 2+2 reified constraints.

See also

hard version: πš–πš’πš—πš’πš–πšžπš–Β (value 0 is not ignored any more).

Keywords

characteristic of a constraint: joker value, minimum, automaton, automaton without counters, reified automaton constraint.

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

constraint type: order constraint.

Arc input(s)

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

Arc generator
πΆπΏπΌπ‘„π‘ˆπΈβ†¦πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(πšŸπšŠπš›πš’πšŠπš‹πš•πšŽπšœ1,πšŸπšŠπš›πš’πšŠπš‹πš•πšŽπšœ2)

Arc arity
Arc constraint(s)
β€’ πšŸπšŠπš›πš’πšŠπš‹πš•πšŽπšœ1.πšŸπšŠπš›β‰ 0
β€’ πšŸπšŠπš›πš’πšŠπš‹πš•πšŽπšœ2.πšŸπšŠπš›β‰ 0
β€’ β‹πšŸπšŠπš›πš’πšŠπš‹πš•πšŽπšœ1.πš”πšŽπš’=πšŸπšŠπš›πš’πšŠπš‹πš•πšŽπšœ2.πš”πšŽπš’,πšŸπšŠπš›πš’πšŠπš‹πš•πšŽπšœ1.πšŸπšŠπš›<πšŸπšŠπš›πš’πšŠπš‹πš•πšŽπšœ2.πšŸπšŠπš›
Graph property(ies)
πŽπ‘πƒπ„π‘(0,π™³π™΄π™΅π™°πš„π™»πšƒ,πšŸπšŠπš›)=𝙼𝙸𝙽

Graph model

Because of the first two conditions of the arc constraint, all vertices that correspond to 0 will be removed from the final graph.

PartsΒ (A) andΒ (B) of FigureΒ 5.218.1 respectively show the initial and final graph of the second example of the Example slot. Since we use the πŽπ‘πƒπ„π‘ graph property, the vertices of rank 0 (without considering the loops) of the final graph are outlined with a thick circle.

Figure 5.218.1. Initial and final graph of the πš–πš’πš—πš’πš–πšžπš–_πšŽπš‘πšŒπšŽπš™πš_0 constraint
ctrs/minimum_except_0Actrs/minimum_except_0B
(a) (b)

Since the graph associated with the third example does not contain any vertex, πŽπ‘πƒπ„π‘ returns the default value π™³π™΄π™΅π™°πš„π™»πšƒ.

Automaton

FigureΒ 5.218.2 depicts the automaton associated with the πš–πš’πš—πš’πš–πšžπš–_πšŽπš‘πšŒπšŽπš™πš_0 constraint. Let πš…π™°πš i be the i th variable of the πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚ collection. To each pair (𝙼𝙸𝙽,πš…π™°πš i ) corresponds a signature variable πš‚ i as well as the following signature constraint:

((πš…π™°πš i =0)∧(π™Όπ™Έπ™½β‰ π™³π™΄π™΅π™°πš„π™»πšƒ))β‡”πš‚ i =0 ∧

((πš…π™°πš i =0)∧(𝙼𝙸𝙽=π™³π™΄π™΅π™°πš„π™»πšƒ))β‡”πš‚ i =1 ∧

((πš…π™°πš i β‰ 0)∧(𝙼𝙸𝙽=πš…π™°πš i ))β‡”πš‚ i =2 ∧

((πš…π™°πš i β‰ 0)∧(𝙼𝙸𝙽<πš…π™°πš i ))β‡”πš‚ i =3.

Figure 5.218.2. Automaton of the πš–πš’πš—πš’πš–πšžπš–_πšŽπš‘πšŒπšŽπš™πš_0 constraint
ctrs/minimum_except_01
Figure 5.218.3. Hypergraph of the reformulation corresponding to the automaton of the πš–πš’πš—πš’πš–πšžπš–_πšŽπš‘πšŒπšŽπš™πš_0 constraint
ctrs/minimum_except_02