5.251. open_minimum

DESCRIPTIONLINKSAUTOMATON
Origin

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

Constraint

πš˜πš™πšŽπš—_πš–πš’πš—πš’πš–πšžπš–(𝙼𝙸𝙽,πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚)

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

𝙼𝙸𝙽 is the minimum value of the variables πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚[i].πšŸπšŠπš›, (1≀i≀|πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚|) for which πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚[i].πš‹πš˜πš˜πš•=1 (at least one of the Boolean variables is set to 1).

Example
3,πšŸπšŠπš›-3πš‹πš˜πš˜πš•-1,πšŸπšŠπš›-1πš‹πš˜πš˜πš•-0,πšŸπšŠπš›-7πš‹πš˜πš˜πš•-0,πšŸπšŠπš›-5πš‹πš˜πš˜πš•-1,πšŸπšŠπš›-5πš‹πš˜πš˜πš•-1

The πš˜πš™πšŽπš—_πš–πš’πš—πš’πš–πšžπš– constraint holds since its first argument 𝙼𝙸𝙽=3 is set to the minimum value of values 3,1,7,5,5 for which the corresponding Boolean 1,0,0,1,1 is set to 1 (i.e.,Β values 3,5,5).

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

  • One and the same constant can be added to 𝙼𝙸𝙽 as well as to the πšŸπšŠπš› attribute of all items of πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚.

Remark

The πš˜πš™πšŽπš—_πš–πš’πš—πš’πš–πšžπš– constraint is used in the reformulation of the πšπš›πšŽπšŽ_πš›πšŠπš—πšπšŽ constraint.

See also

comparison swapped: πš˜πš™πšŽπš—_πš–πšŠπš‘πš’πš–πšžπš–.

hard version: πš–πš’πš—πš’πš–πšžπš–.

used in graph description: πš’πš—_𝚜𝚎𝚝.

uses in its reformulation: πšπš›πšŽπšŽ_πš›πšŠπš—πšπšŽ.

Keywords

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

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

constraint type: order constraint, open constraint, open automaton constraint.

Automaton

FigureΒ 5.251.1 depicts the automaton associated with the πš˜πš™πšŽπš—_πš–πš’πš—πš’πš–πšžπš– constraint. Let πš…π™°πš i ,𝙱 i be the i th item of the πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚ collection. To each triple (𝙼𝙸𝙽,πš…π™°πš i ,𝙱 i ) corresponds a signature variable πš‚ i as well as the following signature constraint: (𝙱 i =1βˆ§π™Όπ™Έπ™½<πš…π™°πš i β‡”πš‚ i =0) ∧(𝙱 i =1βˆ§π™Όπ™Έπ™½=πš…π™°πš i β‡”πš‚ i =1) ∧(𝙱 i =1βˆ§π™Όπ™Έπ™½>πš…π™°πš i β‡”πš‚ i =2) ∧(𝙱 i =0βˆ§π™Όπ™Έπ™½<πš…π™°πš i β‡”πš‚ i =3) ∧(𝙱 i =0βˆ§π™Όπ™Έπ™½=πš…π™°πš i β‡”πš‚ i =4) ∧(𝙱 i =0βˆ§π™Όπ™Έπ™½>πš…π™°πš i β‡”πš‚ i =5).

Figure 5.251.1. Automaton of the πš˜πš™πšŽπš—_πš–πš’πš—πš’πš–πšžπš– constraint
ctrs/open_minimum1
Figure 5.251.2. Hypergraph of the reformulation corresponding to the automaton of the πš˜πš™πšŽπš—_πš–πš’πš—πš’πš–πšžπš– constraint
ctrs/open_minimum2