## 5.268. multi_inter_distance

Origin
Constraint

$\mathrm{𝚖𝚞𝚕𝚝𝚒}_\mathrm{𝚒𝚗𝚝𝚎𝚛}_\mathrm{𝚍𝚒𝚜𝚝𝚊𝚗𝚌𝚎}\left(\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂},\mathrm{𝙻𝙸𝙼𝙸𝚃},\mathrm{𝙳𝙸𝚂𝚃}\right)$

Synonyms

$\mathrm{𝚖𝚞𝚕𝚝𝚒}_\mathrm{𝚊𝚕𝚕}_\mathrm{𝚖𝚒𝚗}_\mathrm{𝚍𝚒𝚜𝚝𝚊𝚗𝚌𝚎}$, $\mathrm{𝚖𝚞𝚕𝚝𝚒}_\mathrm{𝚊𝚕𝚕}_\mathrm{𝚖𝚒𝚗}_\mathrm{𝚍𝚒𝚜𝚝}$, $\mathrm{𝚜𝚕𝚒𝚍𝚒𝚗𝚐}_\mathrm{𝚊𝚝𝚖𝚘𝚜𝚝}$, $\mathrm{𝚊𝚝𝚖𝚘𝚜𝚝}_\mathrm{𝚜𝚕𝚒𝚍𝚒𝚗𝚐}$.

Arguments
 $\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}$ $\mathrm{𝚌𝚘𝚕𝚕𝚎𝚌𝚝𝚒𝚘𝚗}\left(\mathrm{𝚟𝚊𝚛}-\mathrm{𝚍𝚟𝚊𝚛}\right)$ $\mathrm{𝙻𝙸𝙼𝙸𝚃}$ $\mathrm{𝚒𝚗𝚝}$ $\mathrm{𝙳𝙸𝚂𝚃}$ $\mathrm{𝚒𝚗𝚝}$
Restrictions
 $\mathrm{𝚛𝚎𝚚𝚞𝚒𝚛𝚎𝚍}$$\left(\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂},\mathrm{𝚟𝚊𝚛}\right)$ $\mathrm{𝙻𝙸𝙼𝙸𝚃}>0$ $\mathrm{𝙳𝙸𝚂𝚃}>0$
Purpose

Enforce that at most $\mathrm{𝙻𝙸𝙼𝙸𝚃}$ variables of the collection $\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}$ are assigned values in any set consisting of $\mathrm{𝙳𝙸𝚂𝚃}$ consecutive integer values.

Example
$\left(〈4,0,9,4,7〉,2,3\right)$

The $\mathrm{𝚖𝚞𝚕𝚝𝚒}_\mathrm{𝚒𝚗𝚝𝚎𝚛}_\mathrm{𝚍𝚒𝚜𝚝𝚊𝚗𝚌𝚎}$ constraint holds since, for each set of $\mathrm{𝙳𝙸𝚂𝚃}=3$ consecutive values, no more than $\mathrm{𝙻𝙸𝙼𝙸𝚃}=2$ variables of the $\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}$ collection $〈4,0,9,4,7〉$ are assigned a value from that set:

• At most two, in fact one, variables of the $\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}$ collection are assigned a value from the set $\left\{0,1,2\right\}$.

• At most two, in fact zero, variables of the $\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}$ collection are assigned a value from the set $\left\{1,2,3\right\}$.

• At most two, in fact two, variables of the $\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}$ collection are assigned a value from the set $\left\{2,3,4\right\}$.

• At most two, in fact two, variables of the $\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}$ collection are assigned a value from the set $\left\{3,4,5\right\}$.

• At most two, in fact two, variables of the $\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}$ collection are assigned a value from the set $\left\{4,5,6\right\}$.

• At most two, in fact one, variables of the $\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}$ collection are assigned a value from the set $\left\{5,6,7\right\}$.

• At most two, in fact one, variables of the $\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}$ collection are assigned a value from the set $\left\{6,7,8\right\}$.

• At most two, in fact two, variables of the $\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}$ collection are assigned a value from the set $\left\{7,8,9\right\}$.

Typical
 $\mathrm{𝙻𝙸𝙼𝙸𝚃}>1$ $\mathrm{𝙻𝙸𝙼𝙸𝚃}<|\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}|$ $\mathrm{𝙳𝙸𝚂𝚃}>1$ $\mathrm{𝙳𝙸𝚂𝚃}<$$\mathrm{𝚛𝚊𝚗𝚐𝚎}$$\left(\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}.\mathrm{𝚟𝚊𝚛}\right)$
Symmetries
• Items of $\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}$ are permutable.

• One and the same constant can be added to the $\mathrm{𝚟𝚊𝚛}$ attribute of all items of $\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}$.

• $\mathrm{𝙻𝙸𝙼𝙸𝚃}$ can be increased.

• $\mathrm{𝙼𝙸𝙽𝙳𝙸𝚂𝚃}$ can be decreased to any value $\ge 1$.

Arg. properties

Contractible wrt. $\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}$.

Usage

The $\mathrm{𝚖𝚞𝚕𝚝𝚒}_\mathrm{𝚒𝚗𝚝𝚎𝚛}_\mathrm{𝚍𝚒𝚜𝚝𝚊𝚗𝚌𝚎}$ constraint was tested for scheduling tasks that all have the same fixed duration in the context of air traffic management.

Algorithm

P. Ouellet and C.-G. Quimper came up with a cubic time complexity algorithm achieving bound-consistency in [OuelletQuimper11].

generalisation: $\mathrm{𝚌𝚞𝚖𝚞𝚕𝚊𝚝𝚒𝚟𝚎}$ ($\mathrm{𝚕𝚒𝚗𝚎}\mathrm{𝚜𝚎𝚐𝚖𝚎𝚗𝚝}$, of same length, replaced by $\mathrm{𝚕𝚒𝚗𝚎}\mathrm{𝚜𝚎𝚐𝚖𝚎𝚗𝚝}$).
specialisation: $\mathrm{𝚊𝚕𝚕}_\mathrm{𝚖𝚒𝚗}_\mathrm{𝚍𝚒𝚜𝚝}$ ($\mathrm{𝙻𝙸𝙼𝙸𝚃}$ parameter set to 1), $\mathrm{𝚌𝚊𝚛𝚍𝚒𝚗𝚊𝚕𝚒𝚝𝚢}_\mathrm{𝚊𝚝𝚖𝚘𝚜𝚝}$ (window of $\mathrm{𝙳𝙸𝚂𝚃}$ consecutive values replaced by window of size 1).