Global Constraint Catalog: Cmin

5.214. min_n

DESCRIPTION

LINKS

GRAPH

AUTOMATON

Origin

[Beldiceanu01]

Constraint

$𝚖𝚒𝚗_𝚗 (𝙼𝙸𝙽, 𝚁𝙰𝙽𝙺, 𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂)$

Arguments

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

Restrictions

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

𝚁𝙰𝙽𝙺 \geq 0

𝚁𝙰𝙽𝙺 < | 𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 |

𝚛𝚎𝚚𝚞𝚒𝚛𝚎𝚍

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

Purpose

$𝙼𝙸𝙽$ is the minimum value of rank $𝚁𝙰𝙽𝙺$ (i.e., the ${𝚁𝙰𝙽𝙺}^{t h}$ smallest distinct value) of the collection of domain variables $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$ . Sources have a rank of 0.

Example

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

The $𝚖𝚒𝚗_𝚗$ constraint holds since its first argument $𝙼𝙸𝙽 = 3$ is fixed to the second (i.e., $𝚁𝙰𝙽𝙺 + 1$ ) smallest distinct value of the collection $〈 3, 1, 7, 1, 6 〉$ . Note that identical values are only counted once: this is why the minimum of order 1 is 3 instead of 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 $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$ .

Algorithm

[Beldiceanu01].

Reformulation

The constraint $𝚊𝚖𝚘𝚗𝚐_𝚟𝚊𝚛$ $(1, 〈 𝙼𝙸𝙽 〉, 𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂)$ enforces $𝙼𝙸𝙽$ to be assigned one of the values of $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$ . The constraint $𝚗𝚟𝚊𝚕𝚞𝚎$ $(𝙽𝚅𝙰𝙻, 𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂)$ provides a hand on the number of distinct values assigned to the variables of $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$ . By associating to each variable $V_{i}$ $(i \in [1, | 𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 |])$ of the $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$ collection a rank variable $R_{i} \in [0, | 𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 | - 1]$ with the reified constraint $R_{i} = 𝚁𝙰𝙽𝙺 \Leftrightarrow V_{i} = 𝙼𝙸𝙽$ , the inequality $R_{i} < 𝙽𝚅𝙰𝙻$ , and by creating for each pair of variables $V_{i}, V_{j}$ $(i, j < i \in [1, | 𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 |])$ the reified constraints

$V_{i} < V_{j} \Leftrightarrow R_{i} < R_{j}$ ,

$V_{i} = V_{j} \Leftrightarrow R_{i} = R_{j}$ ,

$V_{i} > V_{j} \Leftrightarrow R_{i} > R_{j}$ ,

one can reformulate the $𝚖𝚒𝚗_𝚗$ constraint in term of $3 \cdot \frac{| 𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 | \cdot (| 𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 | - 1)}{2} + 1$ reified constraints.

See also

comparison swapped: $𝚖𝚊𝚡_𝚗$ .

generalisation: $𝚖𝚒𝚗𝚒𝚖𝚞𝚖$ (absolute minimum replaced by minimum or order $𝚗$ ).

used in reformulation: $𝚊𝚖𝚘𝚗𝚐_𝚟𝚊𝚛$ , $𝚗𝚟𝚊𝚕𝚞𝚎$ .

Keywords

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

constraint type: order constraint.

Arc input(s)

$𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$

Arc generator

𝐶𝐿𝐼𝑄𝑈𝐸

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

Arc arity

Arc constraint(s)

⋁ (\begin{matrix} 𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎𝚜 1 . 𝚔𝚎𝚢 = 𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎𝚜 2 . 𝚔𝚎𝚢, \\ 𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎𝚜 1 . 𝚟𝚊𝚛 < 𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎𝚜 2 . 𝚟𝚊𝚛 \end{matrix})

Graph property(ies)

𝐎𝐑𝐃𝐄𝐑

(𝚁𝙰𝙽𝙺, 𝙼𝙰𝚇𝙸𝙽𝚃, 𝚟𝚊𝚛) = 𝙼𝙸𝙽

Graph model

Parts (A) and (B) of Figure 5.214.1 respectively show the initial and final graph associated with the Example slot. Since we use the $𝐎𝐑𝐃𝐄𝐑$ graph property, the vertex of rank 1 (without considering the loops) of the final graph is shown in grey.

Figure 5.214.1. Initial and final graph of the $𝚖𝚒𝚗_𝚗$ constraint


(a)	(b)

Automaton: Figure 5.214.2 depicts the automaton associated with the $𝚖𝚒𝚗_𝚗$ constraint. Figure 5.214.2 depicts the automaton associated with the $𝚖𝚒𝚗_𝚗$ constraint. To each item of the collection $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$ corresponds a signature variable $𝚂_{i}$ that is equal to 1.

Figure 5.214.2. Automaton of the $𝚖𝚒𝚗_𝚗$ constraint

Global Constraint Catalog

5. Global Constraint Catalogue

5.214. min_n

Figure 5.214.1. Initial and final graph of the $𝚖𝚒𝚗_𝚗$ constraint

Figure 5.214.2. Automaton of the $𝚖𝚒𝚗_𝚗$ constraint

W3C: XHTML - last update: 2010-12-6. SD.

Global Constraint Catalog

5. Global Constraint Catalogue

5.214. min_n

Figure 5.214.1. Initial and final graph of the 𝚖𝚒𝚗_𝚗 constraint

Figure 5.214.2. Automaton of the 𝚖𝚒𝚗_𝚗 constraint

W3C: XHTML - last update: 2010-12-6. SD.

Figure 5.214.1. Initial and final graph of the $𝚖𝚒𝚗_𝚗$ constraint

Figure 5.214.2. Automaton of the $𝚖𝚒𝚗_𝚗$ constraint