Global Constraint Catalog: Cdiffer_from_at_least_k

5.115. differ_from_at_least_k_pos

DESCRIPTION

LINKS

GRAPH

AUTOMATON

Origin

Inspired by [Frutos97].

Constraint

$𝚍𝚒𝚏𝚏𝚎𝚛_𝚏𝚛𝚘𝚖_𝚊𝚝_𝚕𝚎𝚊𝚜𝚝_𝚔_𝚙𝚘𝚜 (𝙺, 𝚅𝙴𝙲𝚃𝙾𝚁 1, 𝚅𝙴𝙲𝚃𝙾𝚁 2)$

Type

𝚅𝙴𝙲𝚃𝙾𝚁

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

Arguments

$𝙺$	$𝚒𝚗𝚝$
$𝚅𝙴𝙲𝚃𝙾𝚁 1$	$𝚅𝙴𝙲𝚃𝙾𝚁$
$𝚅𝙴𝙲𝚃𝙾𝚁 2$	$𝚅𝙴𝙲𝚃𝙾𝚁$

Restrictions

| 𝚅𝙴𝙲𝚃𝙾𝚁 | \geq 1

𝚛𝚎𝚚𝚞𝚒𝚛𝚎𝚍

(𝚅𝙴𝙲𝚃𝙾𝚁, 𝚟𝚊𝚛)

𝙺 \geq 0

𝙺 \leq | 𝚅𝙴𝙲𝚃𝙾𝚁 1 |

| 𝚅𝙴𝙲𝚃𝙾𝚁 1 | = | 𝚅𝙴𝙲𝚃𝙾𝚁 2 |

Purpose

Enforce two vectors $𝚅𝙴𝙲𝚃𝙾𝚁 1$ and $𝚅𝙴𝙲𝚃𝙾𝚁 2$ to differ from at least $𝙺$ positions.

Example

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

The $𝚍𝚒𝚏𝚏𝚎𝚛_𝚏𝚛𝚘𝚖_𝚊𝚝_𝚕𝚎𝚊𝚜𝚝_𝚔_𝚙𝚘𝚜$ constraint holds since the first and second vectors differ from 3 positions, which is greater than or equal to $𝙺 = 2$ .

Typical

𝙺 > 0

𝙺 < | 𝚅𝙴𝙲𝚃𝙾𝚁 1 |

| 𝚅𝙴𝙲𝚃𝙾𝚁 1 | > 1

Symmetries

Arguments are permutable w.r.t. permutation $(𝙺)$ $(𝚅𝙴𝙲𝚃𝙾𝚁 1, 𝚅𝙴𝙲𝚃𝙾𝚁 2)$ .
$𝙺$ can be decreased to any value $\geq 0$ .
Items of $𝚅𝙴𝙲𝚃𝙾𝚁 1$ and $𝚅𝙴𝙲𝚃𝙾𝚁 2$ are permutable (same permutation used).

Arg. properties

Extensible wrt. $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 1$ and $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 2$ (add items at same position).

Remark

Used in the Arc constraint(s) slot of the $𝚊𝚕𝚕_𝚍𝚒𝚏𝚏𝚎𝚛_𝚏𝚛𝚘𝚖_𝚊𝚝_𝚕𝚎𝚊𝚜𝚝_𝚔_𝚙𝚘𝚜$ constraint.

Used in

$𝚊𝚕𝚕_𝚍𝚒𝚏𝚏𝚎𝚛_𝚏𝚛𝚘𝚖_𝚊𝚝_𝚕𝚎𝚊𝚜𝚝_𝚔_𝚙𝚘𝚜$ .

system of constraints: $𝚊𝚕𝚕_𝚍𝚒𝚏𝚏𝚎𝚛_𝚏𝚛𝚘𝚖_𝚊𝚝_𝚕𝚎𝚊𝚜𝚝_𝚔_𝚙𝚘𝚜$ .

Keywords

characteristic of a constraint: vector, automaton, automaton with counters.

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

constraint type: value constraint.

Arc input(s)

$𝚅𝙴𝙲𝚃𝙾𝚁 1$ $𝚅𝙴𝙲𝚃𝙾𝚁 2$

Arc generator

𝑃𝑅𝑂𝐷𝑈𝐶𝑇

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

Arc arity

Arc constraint(s)

𝚟𝚎𝚌𝚝𝚘𝚛 1 . 𝚟𝚊𝚛 \neq 𝚟𝚎𝚌𝚝𝚘𝚛 2 . 𝚟𝚊𝚛

Graph property(ies)

𝐍𝐀𝐑𝐂

\geq 𝙺

Graph model

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

Figure 5.115.1. Initial and final graph of the $𝚍𝚒𝚏𝚏𝚎𝚛_𝚏𝚛𝚘𝚖_𝚊𝚝_𝚕𝚎𝚊𝚜𝚝_𝚔_𝚙𝚘𝚜$ constraint


(a)	(b)

Automaton: Figure 5.115.2 depicts the automaton associated with the $𝚍𝚒𝚏𝚏𝚎𝚛_𝚏𝚛𝚘𝚖_𝚊𝚝_𝚕𝚎𝚊𝚜𝚝_𝚔_𝚙𝚘𝚜$ constraint. Let $𝚅𝙰𝚁 1_{i}$ and $𝚅𝙰𝚁 2_{i}$ be the $i^{t h}$ variables of the $𝚅𝙴𝙲𝚃𝙾𝚁 1$ and $𝚅𝙴𝙲𝚃𝙾𝚁 2$ collections. To each pair of variables $(𝚅𝙰𝚁 1_{i}, 𝚅𝙰𝚁 2_{i})$ corresponds a signature variable $S_{i}$ . The following signature constraint links $𝚅𝙰𝚁 1_{i}$ , $𝚅𝙰𝚁 2_{i}$ and $S_{i}$ : $𝚅𝙰𝚁 1_{i} = 𝚅𝙰𝚁 2_{i} \Leftrightarrow S_{i}$ .

Figure 5.115.2. Automaton of the $𝚍𝚒𝚏𝚏𝚎𝚛_𝚏𝚛𝚘𝚖_𝚊𝚝_𝚕𝚎𝚊𝚜𝚝_𝚔_𝚙𝚘𝚜$ constraint

Figure 5.115.3. Hypergraph of the reformulation corresponding to the automaton of the $𝚍𝚒𝚏𝚏𝚎𝚛_𝚏𝚛𝚘𝚖_𝚊𝚝_𝚕𝚎𝚊𝚜𝚝_𝚔_𝚙𝚘𝚜$ constraint

Global Constraint Catalog

5. Global Constraint Catalogue

5.115. differ_from_at_least_k_pos

Figure 5.115.1. Initial and final graph of the $𝚍𝚒𝚏𝚏𝚎𝚛_𝚏𝚛𝚘𝚖_𝚊𝚝_𝚕𝚎𝚊𝚜𝚝_𝚔_𝚙𝚘𝚜$ constraint

Figure 5.115.2. Automaton of the $𝚍𝚒𝚏𝚏𝚎𝚛_𝚏𝚛𝚘𝚖_𝚊𝚝_𝚕𝚎𝚊𝚜𝚝_𝚔_𝚙𝚘𝚜$ constraint

Figure 5.115.3. Hypergraph of the reformulation corresponding to the automaton of the $𝚍𝚒𝚏𝚏𝚎𝚛_𝚏𝚛𝚘𝚖_𝚊𝚝_𝚕𝚎𝚊𝚜𝚝_𝚔_𝚙𝚘𝚜$ constraint

Global Constraint Catalog

5. Global Constraint Catalogue

5.115. differ_from_at_least_k_pos

Figure 5.115.1. Initial and final graph of the 𝚍𝚒𝚏𝚏𝚎𝚛_𝚏𝚛𝚘𝚖_𝚊𝚝_𝚕𝚎𝚊𝚜𝚝_𝚔_𝚙𝚘𝚜 constraint

Figure 5.115.2. Automaton of the 𝚍𝚒𝚏𝚏𝚎𝚛_𝚏𝚛𝚘𝚖_𝚊𝚝_𝚕𝚎𝚊𝚜𝚝_𝚔_𝚙𝚘𝚜 constraint

Figure 5.115.3. Hypergraph of the reformulation corresponding to the automaton of the 𝚍𝚒𝚏𝚏𝚎𝚛_𝚏𝚛𝚘𝚖_𝚊𝚝_𝚕𝚎𝚊𝚜𝚝_𝚔_𝚙𝚘𝚜 constraint

Figure 5.115.1. Initial and final graph of the $𝚍𝚒𝚏𝚏𝚎𝚛_𝚏𝚛𝚘𝚖_𝚊𝚝_𝚕𝚎𝚊𝚜𝚝_𝚔_𝚙𝚘𝚜$ constraint

Figure 5.115.2. Automaton of the $𝚍𝚒𝚏𝚏𝚎𝚛_𝚏𝚛𝚘𝚖_𝚊𝚝_𝚕𝚎𝚊𝚜𝚝_𝚔_𝚙𝚘𝚜$ constraint

Figure 5.115.3. Hypergraph of the reformulation corresponding to the automaton of the $𝚍𝚒𝚏𝚏𝚎𝚛_𝚏𝚛𝚘𝚖_𝚊𝚝_𝚕𝚎𝚊𝚜𝚝_𝚔_𝚙𝚘𝚜$ constraint