Global Constraint Catalog: Camong_diff

5.17. among_diff_0

DESCRIPTION

LINKS

GRAPH

AUTOMATON

Origin

Used in the automaton of $𝚗𝚟𝚊𝚕𝚞𝚎$ .

Constraint

$𝚊𝚖𝚘𝚗𝚐_𝚍𝚒𝚏𝚏_0 (𝙽𝚅𝙰𝚁, 𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂)$

Arguments

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

Restrictions

𝙽𝚅𝙰𝚁 \geq 0

𝙽𝚅𝙰𝚁 \leq | 𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 |

𝚛𝚎𝚚𝚞𝚒𝚛𝚎𝚍

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

Purpose

$𝙽𝚅𝙰𝚁$ is the number of variables of the collection $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$ that take a value different from 0.

Example

(3, 〈0, 5, 5, 0, 1〉)

The $𝚊𝚖𝚘𝚗𝚐_𝚍𝚒𝚏𝚏_0$ constraint holds since exactly 3 values of the collection of values $〈 0, 5, 5, 0, 1 〉$ are different from 0.

Typical

𝙽𝚅𝙰𝚁 > 0

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

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

𝚊𝚝𝚕𝚎𝚊𝚜𝚝

(1, 𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂, 0)

Symmetries

Items of $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$ are permutable.
An occurrence of a value of $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 . 𝚟𝚊𝚛$ that is different from 0 can be replaced by any other value that is also different from 0.

generalisation: $𝚊𝚖𝚘𝚗𝚐$ ( $𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎 \neq 0$ replaced by $𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎 \in 𝚟𝚊𝚕𝚞𝚎𝚜$ ).

Keywords

characteristic of a constraint: joker value, automaton, automaton with counters.

constraint network structure: alpha-acyclic constraint network(2).

constraint type: value constraint, counting constraint.

filtering: arc-consistency.

Arc input(s)

$𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$

Arc generator

𝑆𝐸𝐿𝐹

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

Arc arity

Arc constraint(s)

𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎𝚜 . 𝚟𝚊𝚛 \neq 0

Graph property(ies)

𝐍𝐀𝐑𝐂

= 𝙽𝚅𝙰𝚁

Graph model

Since this is a unary constraint we employ the $𝑆𝐸𝐿𝐹$ arc generator in order to produce an initial graph with a single loop on each vertex.

Parts (A) and (B) of Figure 5.17.1 respectively show the initial and final graph associated with the Example slot. Since we use the $𝐍𝐀𝐑𝐂$ graph property, the loops of the final graph are stressed in bold.

Figure 5.17.1. Initial and final graph of the $𝚊𝚖𝚘𝚗𝚐_𝚍𝚒𝚏𝚏_0$ constraint


(a)	(b)

Automaton: Figure 5.17.2 depicts the automaton associated with the $𝚊𝚖𝚘𝚗𝚐_𝚍𝚒𝚏𝚏_0$ constraint. To each variable ${𝚅𝙰𝚁}_{i}$ of the collection $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$ corresponds a 0-1 signature variable $𝚂_{i}$ . The following signature constraint links ${𝚅𝙰𝚁}_{i}$ and $𝚂_{i}$ : ${𝚅𝙰𝚁}_{i} \neq 0 \Leftrightarrow 𝚂_{i}$ . The automaton counts the number of variables of the $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$ collection that take a value different from 0 and finally assigns this number to $𝙽𝚅𝙰𝚁$ .

Figure 5.17.2. Automaton of the $𝚊𝚖𝚘𝚗𝚐_𝚍𝚒𝚏𝚏_0$ constraint

Figure 5.17.3. Hypergraph of the reformulation corresponding to the automaton of the $𝚊𝚖𝚘𝚗𝚐_𝚍𝚒𝚏𝚏_0$ constraint

Global Constraint Catalog

5. Global Constraint Catalogue

5.17. among_diff_0

Figure 5.17.1. Initial and final graph of the $𝚊𝚖𝚘𝚗𝚐_𝚍𝚒𝚏𝚏_0$ constraint

Figure 5.17.2. Automaton of the $𝚊𝚖𝚘𝚗𝚐_𝚍𝚒𝚏𝚏_0$ constraint

Figure 5.17.3. Hypergraph of the reformulation corresponding to the automaton of the $𝚊𝚖𝚘𝚗𝚐_𝚍𝚒𝚏𝚏_0$ constraint

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

Global Constraint Catalog

5. Global Constraint Catalogue

5.17. among_diff_0

Figure 5.17.1. Initial and final graph of the 𝚊𝚖𝚘𝚗𝚐_𝚍𝚒𝚏𝚏_0 constraint

Figure 5.17.2. Automaton of the 𝚊𝚖𝚘𝚗𝚐_𝚍𝚒𝚏𝚏_0 constraint

Figure 5.17.3. Hypergraph of the reformulation corresponding to the automaton of the 𝚊𝚖𝚘𝚗𝚐_𝚍𝚒𝚏𝚏_0 constraint

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

Figure 5.17.1. Initial and final graph of the $𝚊𝚖𝚘𝚗𝚐_𝚍𝚒𝚏𝚏_0$ constraint

Figure 5.17.2. Automaton of the $𝚊𝚖𝚘𝚗𝚐_𝚍𝚒𝚏𝚏_0$ constraint

Figure 5.17.3. Hypergraph of the reformulation corresponding to the automaton of the $𝚊𝚖𝚘𝚗𝚐_𝚍𝚒𝚏𝚏_0$ constraint