Global Constraint Catalog: Cnot_all

5.282. not_all_equal

DESCRIPTION

LINKS

GRAPH

AUTOMATON

Origin

CHIP

Constraint

$𝚗𝚘𝚝_𝚊𝚕𝚕_𝚎𝚚𝚞𝚊𝚕 (𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂)$

Argument

𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂

𝚌𝚘𝚕𝚕𝚎𝚌𝚝𝚒𝚘𝚗 (𝚟𝚊𝚛 - 𝚍𝚟𝚊𝚛)

Restrictions

𝚛𝚎𝚚𝚞𝚒𝚛𝚎𝚍

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

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

Purpose

The variables of the collection $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$ should take more than a single value.

Example

(〈3, 1, 3, 3, 3〉)

The $𝚗𝚘𝚝_𝚊𝚕𝚕_𝚎𝚚𝚞𝚊𝚕$ constraint holds since the collection $〈 3, 1, 3, 3, 3 〉$ involves more than one value (i.e., values 1 and 3).

Typical

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

𝚗𝚟𝚊𝚕

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

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

Extensible wrt. $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$ .

Algorithm

If the intersection of the domains of the variables of the $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$ collection is empty the $𝚗𝚘𝚝_𝚊𝚕𝚕_𝚎𝚚𝚞𝚊𝚕$ constraint is entailed. Otherwise, when only a single variable $V$ remains not fixed, remove the unique value (unique since the constraint is not entailed) taken by the other variables from the domain of $V$ .

Reformulation

The $𝚗𝚘𝚝_𝚊𝚕𝚕_𝚎𝚚𝚞𝚊𝚕$ $(𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂)$ constraint can be expressed as $𝚊𝚝𝚕𝚎𝚊𝚜𝚝_𝚗𝚟𝚊𝚕𝚞𝚎$ $(2, 𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂)$ .

Counting

Length ( $n$ )	2	3	4	5	6	7	8
Solutions	6	60	620	7770	117642	2097144	43046712

Number of solutions for $𝚗𝚘𝚝_𝚊𝚕𝚕_𝚎𝚚𝚞𝚊𝚕$ : domains $0 . . n$

ctrs/not_all_equal-1-tikz

ctrs/not_all_equal-2-tikz

Systems

rel in Gecode.

See also

generalisation: $𝚗𝚟𝚊𝚕𝚞𝚎$ (introduce a variable for counting the number of distinct values).

implied by: $𝚊𝚕𝚕𝚍𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚝$ .

negation: $𝚊𝚕𝚕_𝚎𝚚𝚞𝚊𝚕$ .

specialisation: $𝚗𝚎𝚚$ (when go down to two variables).

used in reformulation: $𝚊𝚝𝚕𝚎𝚊𝚜𝚝_𝚗𝚟𝚊𝚕𝚞𝚎$ .

Keywords

characteristic of a constraint: disequality, automaton, automaton without counters, reified automaton constraint.

constraint network structure: sliding cyclic(1) constraint network(1).

constraint type: value constraint.

filtering: arc-consistency.

final graph structure: equivalence.

Arc input(s)

$𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$

Arc generator

𝐶𝐿𝐼𝑄𝑈𝐸

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

Arc arity

Arc constraint(s)

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

Graph property(ies)

𝐍𝐒𝐂𝐂

> 1

Graph model

Parts (A) and (B) of Figure 5.282.1 respectively show the initial and final graph associated with the Example slot. Since we use the $𝐍𝐒𝐂𝐂$ graph property we show the different strongly connected components of the final graph. Each strongly connected component corresponds to a value that is assigned to some variables of the $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$ collection. The $𝚗𝚘𝚝_𝚊𝚕𝚕_𝚎𝚚𝚞𝚊𝚕$ holds since the final graph contains more than one strongly connected component.

Figure 5.282.1. Initial and final graph of the $𝚗𝚘𝚝_𝚊𝚕𝚕_𝚎𝚚𝚞𝚊𝚕$ constraint


(a)	(b)

Automaton: Figure 5.282.2 depicts the automaton associated with the $𝚗𝚘𝚝_𝚊𝚕𝚕_𝚎𝚚𝚞𝚊𝚕$ constraint. To each pair of consecutive variables $({𝚅𝙰𝚁}_{i}, {𝚅𝙰𝚁}_{i + 1})$ of the collection $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$ corresponds a signature variable $S_{i}$ . The following signature constraint links ${𝚅𝙰𝚁}_{i}$ , ${𝚅𝙰𝚁}_{i + 1}$ and $S_{i}$ : ${𝚅𝙰𝚁}_{i} = {𝚅𝙰𝚁}_{i + 1} \Leftrightarrow S_{i}$ .

Figure 5.282.2. Automaton of the $𝚗𝚘𝚝_𝚊𝚕𝚕_𝚎𝚚𝚞𝚊𝚕$ constraint

Figure 5.282.3. Hypergraph of the reformulation corresponding to the automaton of the $𝚗𝚘𝚝_𝚊𝚕𝚕_𝚎𝚚𝚞𝚊𝚕$ constraint

Global Constraint Catalog

5. Global Constraint Catalogue

5.282. not_all_equal

Figure 5.282.1. Initial and final graph of the $𝚗𝚘𝚝_𝚊𝚕𝚕_𝚎𝚚𝚞𝚊𝚕$ constraint

Figure 5.282.2. Automaton of the $𝚗𝚘𝚝_𝚊𝚕𝚕_𝚎𝚚𝚞𝚊𝚕$ constraint

Figure 5.282.3. Hypergraph of the reformulation corresponding to the automaton of the $𝚗𝚘𝚝_𝚊𝚕𝚕_𝚎𝚚𝚞𝚊𝚕$ constraint

Global Constraint Catalog

5. Global Constraint Catalogue

5.282. not_all_equal

Figure 5.282.1. Initial and final graph of the 𝚗𝚘𝚝_𝚊𝚕𝚕_𝚎𝚚𝚞𝚊𝚕 constraint

Figure 5.282.2. Automaton of the 𝚗𝚘𝚝_𝚊𝚕𝚕_𝚎𝚚𝚞𝚊𝚕 constraint

Figure 5.282.3. Hypergraph of the reformulation corresponding to the automaton of the 𝚗𝚘𝚝_𝚊𝚕𝚕_𝚎𝚚𝚞𝚊𝚕 constraint

Figure 5.282.1. Initial and final graph of the $𝚗𝚘𝚝_𝚊𝚕𝚕_𝚎𝚚𝚞𝚊𝚕$ constraint

Figure 5.282.2. Automaton of the $𝚗𝚘𝚝_𝚊𝚕𝚕_𝚎𝚚𝚞𝚊𝚕$ constraint

Figure 5.282.3. Hypergraph of the reformulation corresponding to the automaton of the $𝚗𝚘𝚝_𝚊𝚕𝚕_𝚎𝚚𝚞𝚊𝚕$ constraint