Global Constraint Catalog: Cdiffer_from_at_most_k

5.116. differ_from_at_most_k_pos

DESCRIPTION

LINKS

GRAPH

Origin

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

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 most $𝙺$ positions.

Example

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

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

Typical

𝙺 > 0

𝙺 < | 𝚅𝙴𝙲𝚃𝙾𝚁 1 |

| 𝚅𝙴𝙲𝚃𝙾𝚁 1 | > 1

Symmetries

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

Arg. properties

Contractible wrt. $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 1$ and $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 2$ (remove items from same position).

Used in

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

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

Keywords

characteristic of a constraint: vector.

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)

𝐍𝐀𝐑𝐂

\leq 𝙺

Graph model

Parts (A) and (B) of Figure 5.116.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.116.1. Initial and final graph of the $𝚍𝚒𝚏𝚏𝚎𝚛_𝚏𝚛𝚘𝚖_𝚊𝚝_𝚖𝚘𝚜𝚝_𝚔_𝚙𝚘𝚜$ constraint


(a)	(b)

Global Constraint Catalog

5. Global Constraint Catalogue

5.116. differ_from_at_most_k_pos

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

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