Global Constraint Catalog: Cmax

5.244. max_nvalue

DESCRIPTION

LINKS

GRAPH

AUTOMATON

Origin

Derived from $𝚗𝚟𝚊𝚕𝚞𝚎$ .

Constraint

$𝚖𝚊𝚡_𝚗𝚟𝚊𝚕𝚞𝚎 (𝙼𝙰𝚇, 𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂)$

Arguments

$𝙼𝙰𝚇$	$𝚍𝚟𝚊𝚛$
$𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$	$𝚌𝚘𝚕𝚕𝚎𝚌𝚝𝚒𝚘𝚗 (𝚟𝚊𝚛 - 𝚍𝚟𝚊𝚛)$

Restrictions

𝙼𝙰𝚇 \geq 1

𝙼𝙰𝚇 \leq | 𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 |

𝚛𝚎𝚚𝚞𝚒𝚛𝚎𝚍

(𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂, 𝚟𝚊𝚛)

Purpose

$𝙼𝙰𝚇$ is the maximum number of times that the same value is taken by the variables of the collection $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$ .

Example

(3, 〈9, 1, 7, 1, 1, 6, 7, 7, 4, 9〉)

(1, 〈9, 1, 7, 3, 2, 6〉)

(6, 〈5, 5, 5, 5, 5, 5〉)

In the first example, values $1, 4, 6, 7, 9$ are respectively used $3, 1, 1, 3, 2$ times. So the maximum number of time $𝙼𝙰𝚇$ that a same value occurs is 3. Consequently the corresponding $𝚖𝚊𝚡_𝚗𝚟𝚊𝚕𝚞𝚎$ constraint holds.

Typical

𝙼𝙰𝚇 > 1

𝙼𝙰𝚇 < | 𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 |

| 𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 | > 1

𝚛𝚊𝚗𝚐𝚎

(𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 . 𝚟𝚊𝚛) > 1

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.

Arg. properties

Functional dependency: $𝙼𝙰𝚇$ determined by $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$ .

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 mostly used value without knowing this value in advance and without giving explicitly an upper 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}, \dots, O_{β}$ respectively correspond to the number of occurrences of values $α, α + 1, \dots, β$ within the variables of the $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$ collection. The $𝚖𝚊𝚡_𝚗𝚟𝚊𝚕𝚞𝚎$ constraint can be expressed as the conjunction of the following two constraints:

$𝚐𝚕𝚘𝚋𝚊𝚕_𝚌𝚊𝚛𝚍𝚒𝚗𝚊𝚕𝚒𝚝𝚢$ $(𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂,$

$〈 𝚟𝚊𝚕 - α 𝚗𝚘𝚌𝚌𝚞𝚛𝚛𝚎𝚗𝚌𝚎 - O_{α},$

$𝚟𝚊𝚕 - α + 1 𝚗𝚘𝚌𝚌𝚞𝚛𝚛𝚎𝚗𝚌𝚎 - O_{α + 1},$

$\dots$

$𝚟𝚊𝚕 - β 𝚗𝚘𝚌𝚌𝚞𝚛𝚛𝚎𝚗𝚌𝚎 - O_{β} 〉)$ ,

$𝚖𝚊𝚡𝚒𝚖𝚞𝚖$ $(𝙼𝙰𝚇, 〈 O_{α}, O_{α + 1}, \dots, O_{β} 〉)$ .

Counting

Length ( $n$ )	2	3	4	5	6	7	8
Solutions	9	64	625	7776	117649	2097152	43046721

Number of solutions for $𝚖𝚊𝚡_𝚗𝚟𝚊𝚕𝚞𝚎$ : domains $0 . . n$

ctrs/max_nvalue-1-tikz

ctrs/max_nvalue-2-tikz

Length (

n

)

Total

625

7776

117649

2097152

43046721

Parameter

value

120

720

5040

40320

362880

420

5400

78750

1305360

24449040

1500

29820

646800

15382080

150

3780

96040

2577960

252

8232

258048

392

16128

576

Solution count for $𝚖𝚊𝚡_𝚗𝚟𝚊𝚕𝚞𝚎$ : domains $0 . . n$

ctrs/max_nvalue-3-tikz

ctrs/max_nvalue-4-tikz

Keywords

application area: assignment.

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

constraint arguments: pure functional dependency.

constraint type: value constraint, counting constraint.

final graph structure: equivalence.

modelling: maximum number of occurrences, functional dependency.

Arc input(s)

$𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$

Arc generator

𝐶𝐿𝐼𝑄𝑈𝐸

\mapsto 𝚌𝚘𝚕𝚕𝚎𝚌𝚝𝚒𝚘𝚗 (𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎𝚜 1, 𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎𝚜 2)

Arc arity

Arc constraint(s)

𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎𝚜 1 . 𝚟𝚊𝚛 = 𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎𝚜 2 . 𝚟𝚊𝚛

Graph property(ies)

𝐌𝐀𝐗_𝐍𝐒𝐂𝐂

= 𝙼𝙰𝚇

Graph model

Because of the arc constraint, each strongly connected component of the final graph corresponds to a distinct value that is assigned to a subset of variables of the $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$ collection. Therefore the number of vertices of the largest strongly connected component is equal to the mostly used value.

Parts (A) and (B) of Figure 5.244.1 respectively show the initial and final graph associated with the first example of the Example slot. Since we use the $𝐌𝐀𝐗_𝐍𝐒𝐂𝐂$ graph property, we show the largest strongly connected component of the final graph.

Figure 5.244.1. Initial and final graph of the $𝚖𝚊𝚡_𝚗𝚟𝚊𝚕𝚞𝚎$ constraint

(a)

(b)

Automaton: Figure 5.244.2 depicts the automaton associated with the $𝚖𝚊𝚡_𝚗𝚟𝚊𝚕𝚞𝚎$ constraint. To each item of the collection $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$ corresponds a signature variable $S_{i}$ that is equal to 0.

Figure 5.244.2. Automaton of the $𝚖𝚊𝚡_𝚗𝚟𝚊𝚕𝚞𝚎$ constraint

Global Constraint Catalog

5. Global Constraint Catalogue

5.244. max_nvalue

Figure 5.244.1. Initial and final graph of the $𝚖𝚊𝚡_𝚗𝚟𝚊𝚕𝚞𝚎$ constraint

Figure 5.244.2. Automaton of the $𝚖𝚊𝚡_𝚗𝚟𝚊𝚕𝚞𝚎$ constraint

Global Constraint Catalog

5. Global Constraint Catalogue

5.244. max_nvalue

Figure 5.244.1. Initial and final graph of the 𝚖𝚊𝚡_𝚗𝚟𝚊𝚕𝚞𝚎 constraint

Figure 5.244.2. Automaton of the 𝚖𝚊𝚡_𝚗𝚟𝚊𝚕𝚞𝚎 constraint

Figure 5.244.1. Initial and final graph of the $𝚖𝚊𝚡_𝚗𝚟𝚊𝚕𝚞𝚎$ constraint

Figure 5.244.2. Automaton of the $𝚖𝚊𝚡_𝚗𝚟𝚊𝚕𝚞𝚎$ constraint