Global Constraint Catalog: Call_differ_from_at_most_k

5.3. all_differ_from_at_most_k_pos

DESCRIPTION

LINKS

GRAPH

Origin

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

Constraint

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

Type

𝚅𝙴𝙲𝚃𝙾𝚁

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

Arguments

$𝙺$	$𝚒𝚗𝚝$
$𝚅𝙴𝙲𝚃𝙾𝚁𝚂$	$𝚌𝚘𝚕𝚕𝚎𝚌𝚝𝚒𝚘𝚗 (𝚟𝚎𝚌 - 𝚅𝙴𝙲𝚃𝙾𝚁)$

Restrictions

𝚛𝚎𝚚𝚞𝚒𝚛𝚎𝚍

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

| 𝚅𝙴𝙲𝚃𝙾𝚁 | \geq 1

| 𝚅𝙴𝙲𝚃𝙾𝚁 | \geq 𝙺

𝙺 \geq 0

𝚛𝚎𝚚𝚞𝚒𝚛𝚎𝚍

(𝚅𝙴𝙲𝚃𝙾𝚁𝚂, 𝚟𝚎𝚌)

𝚜𝚊𝚖𝚎_𝚜𝚒𝚣𝚎

(𝚅𝙴𝙲𝚃𝙾𝚁𝚂, 𝚟𝚎𝚌)

Purpose

Enforce all pairs of distinct vectors of the $𝚅𝙴𝙲𝚃𝙾𝚁𝚂$ collection to differ from at most $𝙺$ positions.

Example

(2, 〈𝚟𝚎𝚌 - 〈0, 3, 0, 6〉, 𝚟𝚎𝚌 - 〈0, 3, 4, 1〉, 𝚟𝚎𝚌 - 〈0, 3, 4, 6〉〉)

The $𝚊𝚕𝚕_𝚍𝚒𝚏𝚏𝚎𝚛_𝚏𝚛𝚘𝚖_𝚊𝚝_𝚖𝚘𝚜𝚝_𝚔_𝚙𝚘𝚜$ constraint holds since:

The first and second vectors differ from 2 positions, which is less than or equal to $𝙺 = 2$ .
The first and third vectors differ from 1 position, which is less than or equal to $𝙺 = 2$ .
The second and third vectors differ from 1 position, which is less than or equal to $𝙺 = 2$ .

Typical

𝙺 > 0

𝙺 < | 𝚅𝙴𝙲𝚃𝙾𝚁 |

| 𝚅𝙴𝙲𝚃𝙾𝚁𝚂 | > 1

Symmetries

Items of $𝚅𝙴𝙲𝚃𝙾𝚁𝚂$ are permutable.
Items of $𝚅𝙴𝙲𝚃𝙾𝚁𝚂 . 𝚟𝚎𝚌$ are permutable (same permutation used).

Arg. properties

Contractible wrt. $𝚅𝙴𝙲𝚃𝙾𝚁𝚂$ .
Contractible wrt. $𝚅𝙴𝙲𝚃𝙾𝚁𝚂 . 𝚟𝚎𝚌$ (remove items from same position).

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

used in graph description: $𝚍𝚒𝚏𝚏𝚎𝚛_𝚏𝚛𝚘𝚖_𝚊𝚝_𝚖𝚘𝚜𝚝_𝚔_𝚙𝚘𝚜$ .

Keywords

characteristic of a constraint: disequality, vector.

constraint type: system of constraints, decomposition.

final graph structure: no loop, symmetric.

Arc input(s)

$𝚅𝙴𝙲𝚃𝙾𝚁𝚂$

Arc generator

𝐶𝐿𝐼𝑄𝑈𝐸

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

Arc arity

Arc constraint(s)

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

(𝙺, 𝚟𝚎𝚌𝚝𝚘𝚛𝚜 1 . 𝚟𝚎𝚌, 𝚟𝚎𝚌𝚝𝚘𝚛𝚜 2 . 𝚟𝚎𝚌)

Graph property(ies)

𝐍𝐀𝐑𝐂

= | 𝚅𝙴𝙲𝚃𝙾𝚁𝚂 | * | 𝚅𝙴𝙲𝚃𝙾𝚁𝚂 | - | 𝚅𝙴𝙲𝚃𝙾𝚁𝚂 |

Graph class

•

𝙽𝙾_𝙻𝙾𝙾𝙿

•

𝚂𝚈𝙼𝙼𝙴𝚃𝚁𝙸𝙲

Graph model

The Arc constraint(s) slot uses the $𝚍𝚒𝚏𝚏𝚎𝚛_𝚏𝚛𝚘𝚖_𝚊𝚝_𝚖𝚘𝚜𝚝_𝚔_𝚙𝚘𝚜$ constraint defined in this catalogue.

Parts (A) and (B) of Figure 5.3.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. The previous constraint holds since exactly $3 \cdot (3 - 1) = 6$ arc constraints hold.

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


(a)	(b)

Signature

Since we use the $𝐶𝐿𝐼𝑄𝑈𝐸 (\neq)$ arc generator on the items of the $𝚅𝙴𝙲𝚃𝙾𝚁𝚂$ collection, the expression $| 𝚅𝙴𝙲𝚃𝙾𝚁𝚂 | \cdot | 𝚅𝙴𝙲𝚃𝙾𝚁𝚂 | - | 𝚅𝙴𝙲𝚃𝙾𝚁𝚂 |$ corresponds to the maximum number of arcs of the final graph. Therefore we can rewrite the graph property $𝐍𝐀𝐑𝐂$ $=$ $| 𝚅𝙴𝙲𝚃𝙾𝚁𝚂 | \cdot | 𝚅𝙴𝙲𝚃𝙾𝚁𝚂 | - | 𝚅𝙴𝙲𝚃𝙾𝚁𝚂 |$ to $𝐍𝐀𝐑𝐂$ $\geq$ $| 𝚅𝙴𝙲𝚃𝙾𝚁𝚂 | \cdot | 𝚅𝙴𝙲𝚃𝙾𝚁𝚂 | - | 𝚅𝙴𝙲𝚃𝙾𝚁𝚂 |$ . This leads to simplify $\underset{̲}{\bar{𝐍𝐀𝐑𝐂}}$ to $\bar{𝐍𝐀𝐑𝐂}$ .

Global Constraint Catalog

5. Global Constraint Catalogue

5.3. all_differ_from_at_most_k_pos

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

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