5.215. min_nvalue

DESCRIPTIONLINKSGRAPHAUTOMATON
Origin

N.Β Beldiceanu

Constraint

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

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

𝙼𝙸𝙽 is the minimum number of times that the same value is taken by the variables of the collection πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚.

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

In the example, values 1,7,9 are respectively used 3,5,2 times. So the minimum number of time 𝙼𝙸𝙽 that a same value occurs is 2. Consequently the πš–πš’πš—_πš—πšŸπšŠπš•πšžπšŽ constraint holds.

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

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

Usage

This constraint may be used in order to replace a set of πšŒπš˜πšžπš—πš or πšŠπš–πš˜πš—πš constraints were one would have to generate explicitly one constraint for each potential value. Also useful for constraining the number of occurrences of the less used value without knowing this value in advance and without giving explicitly a lower limit on the number of occurrences of each value as it is done in the πšπš•πš˜πš‹πšŠπš•_πšŒπšŠπš›πšπš’πš—πšŠπš•πš’πšπš’ constraint.

Reformulation

Assume that πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚ is not empty. Let Ξ± and Ξ² respectively denote the smallest and largest possible values that can be assigned to the variables of the πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚ collection. Let the variables O Ξ± ,O Ξ±+1 ,...,O Ξ² respectively correspond to the number of occurrences of values Ξ±,Ξ±+1,...,Ξ² within the variables of the πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚ collection. The πš–πš’πš—_πš—πšŸπšŠπš•πšžπšŽ constraint can be expressed as the conjunction of the following two constraints:

Β Β Β πšπš•πš˜πš‹πšŠπš•_πšŒπšŠπš›πšπš’πš—πšŠπš•πš’πšπš’ (πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚,

Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β βŒ©πšŸπšŠπš•-Ξ± πš—πš˜πšŒπšŒπšžπš›πš›πšŽπš—πšŒπšŽ-O Ξ± ,

Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β πšŸπšŠπš•-Ξ±+1 πš—πš˜πšŒπšŒπšžπš›πš›πšŽπš—πšŒπšŽ-O Ξ±+1 ,

Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β ...

Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β πšŸπšŠπš•-Ξ² πš—πš˜πšŒπšŒπšžπš›πš›πšŽπš—πšŒπšŽ-O Ξ² βŒͺ),

Β Β Β πš–πš’πš—_πš—(𝙼𝙸𝙽,1,〈0,O Ξ± ,O Ξ±+1 ,...,O Ξ² βŒͺ).

We use a πš–πš’πš—_πš— constraint (with its πšπ™°π™½π™Ί parameter set to 1) instead of a πš–πš’πš—πš’πš–πšžπš– constraint in order to discard the smallest value 0.

See also

common keyword: πšŠπš–πš˜πš—πšΒ (counting constraint), πšŒπš˜πšžπš—πš, πšπš•πš˜πš‹πšŠπš•_πšŒπšŠπš›πšπš’πš—πšŠπš•πš’πšπš’Β (value constraint,counting constraint), πš–πšŠπš‘_πš—πšŸπšŠπš•πšžπšŽ, πš—πšŸπšŠπš•πšžπšŽΒ (counting constraint).

Keywords

application area: assignment.

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

constraint type: value constraint, counting constraint.

final graph structure: equivalence.

modelling: minimum number of occurrences.

Arc input(s)

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

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

Arc arity
Arc constraint(s)
πšŸπšŠπš›πš’πšŠπš‹πš•πšŽπšœ1.πšŸπšŠπš›=πšŸπšŠπš›πš’πšŠπš‹πš•πšŽπšœ2.πšŸπšŠπš›
Graph property(ies)
𝐌𝐈𝐍_𝐍𝐒𝐂𝐂=𝙼𝙸𝙽

Graph model

PartsΒ (A) andΒ (B) of FigureΒ 5.215.1 respectively show the initial and final graph. Since we use the 𝐌𝐈𝐍_𝐍𝐒𝐂𝐂 graph property, we show the smallest strongly connected component of the final graph associated with the Example slot.

Figure 5.215.1. Initial and final graph of the πš–πš’πš—_πš—πšŸπšŠπš•πšžπšŽ constraint
ctrs/min_nvalueA
(a)
ctrs/min_nvalueB
(b)
Automaton

FigureΒ 5.215.2 depicts the automaton associated with the πš–πš’πš—_πš—πšŸπšŠπš•πšžπšŽ constraint. To each item of the collection πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚ corresponds a signature variable πš‚ i that is equal to 0.

Figure 5.215.2. Automaton of the πš–πš’πš—_πš—πšŸπšŠπš•πšžπšŽ constraint
ctrs/min_nvalue1