5.300. open_maximum

DESCRIPTIONLINKSAUTOMATON
Origin

Derived from πš–πšŠπš‘πš’πš–πšžπš–

Constraint

πš˜πš™πšŽπš—_πš–πšŠπš‘πš’πš–πšžπš–(π™Όπ™°πš‡,πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚)

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

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

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

The πš˜πš™πšŽπš—_πš–πšŠπš‘πš’πš–πšžπš– constraint holds since its first argument π™Όπ™°πš‡=5 is set to the maximum 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).

Typical
|πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚|>1
πš›πšŠπš—πšπšŽ(πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚.πšŸπšŠπš›)>1
Symmetries
  • Items of πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚ are permutable.

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

See also

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

hard version: πš–πšŠπš‘πš’πš–πšžπš–.

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

Keywords

characteristic of a constraint: maximum, 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.300.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 S i as well as the following signature constraint: (𝙱 i =1βˆ§π™Όπ™°πš‡<πš…π™°πš i ⇔S i =0) ∧(𝙱 i =1βˆ§π™Όπ™°πš‡=πš…π™°πš i ⇔S i =1) ∧(𝙱 i =1βˆ§π™Όπ™°πš‡>πš…π™°πš i ⇔S i =2) ∧(𝙱 i =0βˆ§π™Όπ™°πš‡<πš…π™°πš i ⇔S i =3) ∧(𝙱 i =0βˆ§π™Όπ™°πš‡=πš…π™°πš i ⇔S i =4) ∧(𝙱 i =0βˆ§π™Όπ™°πš‡>πš…π™°πš i ⇔S i =5).

Figure 5.300.1. Automaton of the πš˜πš™πšŽπš—_πš–πšŠπš‘πš’πš–πšžπš– constraint
ctrs/open_maximum-1-tikz
Figure 5.300.2. Hypergraph of the reformulation corresponding to the automaton of the πš˜πš™πšŽπš—_πš–πšŠπš‘πš’πš–πšžπš– constraint
ctrs/open_maximum-2-tikz