## 5.4. all_min_dist

 DESCRIPTION LINKS GRAPH
Origin
Constraint

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

Synonyms

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

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

Enforce for each pair $\left({\mathrm{𝚟𝚊𝚛}}_{i},{\mathrm{𝚟𝚊𝚛}}_{j}\right)$ of distinct variables of the collection $\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}$ that $|{\mathrm{𝚟𝚊𝚛}}_{i}-{\mathrm{𝚟𝚊𝚛}}_{j}|\ge \mathrm{𝙼𝙸𝙽𝙳𝙸𝚂𝚃}$.

Example
$\left(2,〈5,1,9,3〉\right)$

The $\mathrm{𝚊𝚕𝚕}_\mathrm{𝚖𝚒𝚗}_\mathrm{𝚍𝚒𝚜𝚝}$ constraint holds since the following expressions $|5-1|$, $|5-9|$, $|5-3|$, $|1-9|$, $|1-3|$, $|9-3|$ are all greater than or equal to the first argument $\mathrm{𝙼𝙸𝙽𝙳𝙸𝚂𝚃}=2$ of the $\mathrm{𝚊𝚕𝚕}_\mathrm{𝚖𝚒𝚗}_\mathrm{𝚍𝚒𝚜𝚝}$ constraint.

Typical
 $\mathrm{𝙼𝙸𝙽𝙳𝙸𝚂𝚃}>1$ $|\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}|>1$
Symmetries
• $\mathrm{𝙼𝙸𝙽𝙳𝙸𝚂𝚃}$ can be decreased to any value $\ge 1$.

• Items of $\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}$ are permutable.

• Two distinct values of $\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}.\mathrm{𝚟𝚊𝚛}$ can be swapped.

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

Usage

The $\mathrm{𝚊𝚕𝚕}_\mathrm{𝚖𝚒𝚗}_\mathrm{𝚍𝚒𝚜𝚝}$ constraint was initially created for handling frequency allocation problems. In [ArtiouchineBaptiste05] it is used for scheduling tasks that all have the same fixed duration in the context of air traffic management in the terminal radar control area of airports.

Remark

The $\mathrm{𝚊𝚕𝚕}_\mathrm{𝚖𝚒𝚗}_\mathrm{𝚍𝚒𝚜𝚝}$ constraint can be modelled as a set of tasks that should not overlap. For each variable $\mathrm{𝚟𝚊𝚛}$ of the $\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}$ collection we create a task $t$ where $\mathrm{𝚟𝚊𝚛}$ and $\mathrm{𝙼𝙸𝙽𝙳𝙸𝚂𝚃}$ respectively correspond to the origin and the duration of $t$.

Some solvers use in a pre -processing phase, while stating constraints of the form $|{X}_{i}-{X}_{j}|\ge {D}_{ij}$ (where ${X}_{i}$ and ${X}_{j}$ are domain variables and ${D}_{ij}$ is a constant), an algorithm for automatically extracting large cliques [BronKerbosch73] from such inequalities in order to state $\mathrm{𝚊𝚕𝚕}_\mathrm{𝚖𝚒𝚗}_\mathrm{𝚍𝚒𝚜𝚝}$ constraints.

Algorithm

K. Artiouchine and P. Baptiste came up with a cubic time complexity algorithm achieving bound-consistency in [ArtiouchineBaptiste05], [ArtiouchineBaptiste07] based on the adaptation of a feasibility test algorithm from M.R. Garey et al. [GareyJohnsonSimonsTarjan81]. Later on, C.-G. Quimper et al., proposed a quadratic algorithm achieving the same level of consistency in [QuimperOrtizPesant06].

See also

generalisation: $\mathrm{𝚍𝚒𝚏𝚏𝚗}$ ($\mathrm{𝚕𝚒𝚗𝚎}\mathrm{𝚜𝚎𝚐𝚖𝚎𝚗𝚝}$, of same length, replaced by orthotope), $\mathrm{𝚍𝚒𝚜𝚓𝚞𝚗𝚌𝚝𝚒𝚟𝚎}$ ($\mathrm{𝚕𝚒𝚗𝚎}\mathrm{𝚜𝚎𝚐𝚖𝚎𝚗𝚝}$, of same length, replaced by $\mathrm{𝚕𝚒𝚗𝚎}\mathrm{𝚜𝚎𝚐𝚖𝚎𝚗𝚝}$).

specialisation: $\mathrm{𝚊𝚕𝚕𝚍𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚝}$ ($\mathrm{𝚕𝚒𝚗𝚎}\mathrm{𝚜𝚎𝚐𝚖𝚎𝚗𝚝}$, of same length, replaced by $\mathrm{𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎}$).

Keywords
Arc input(s)

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

Arc generator
$\mathrm{𝐶𝐿𝐼𝑄𝑈𝐸}$$\left(<\right)↦\mathrm{𝚌𝚘𝚕𝚕𝚎𝚌𝚝𝚒𝚘𝚗}\left(\mathrm{𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎𝚜}\mathtt{1},\mathrm{𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎𝚜}\mathtt{2}\right)$

Arc arity
Arc constraint(s)
$\mathrm{𝚊𝚋𝚜}\left(\mathrm{𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎𝚜}\mathtt{1}.\mathrm{𝚟𝚊𝚛}-\mathrm{𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎𝚜}\mathtt{2}.\mathrm{𝚟𝚊𝚛}\right)\ge \mathrm{𝙼𝙸𝙽𝙳𝙸𝚂𝚃}$
Graph property(ies)
$\mathrm{𝐍𝐀𝐑𝐂}$$=|\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}|*\left(|\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}|-1\right)/2$

Graph class
 $•$$\mathrm{𝙰𝙲𝚈𝙲𝙻𝙸𝙲}$ $•$$\mathrm{𝙽𝙾}_\mathrm{𝙻𝙾𝙾𝙿}$

Graph model

We generate a clique with a minimum distance constraint between each pair of distinct vertices and state that the number of arcs of the final graph should be equal to the number of arcs of the initial graph.

Parts (A) and (B) of Figure 5.4.1 respectively show the initial and final graph associated with the Example slot. The $\mathrm{𝚊𝚕𝚕}_\mathrm{𝚖𝚒𝚗}_\mathrm{𝚍𝚒𝚜𝚝}$ constraint holds since all the arcs of the initial graph belong to the final graph: all the minimum distance constraints are satisfied.

##### Figure 5.4.1. Initial and final graph of the $\mathrm{𝚊𝚕𝚕}_\mathrm{𝚖𝚒𝚗}_\mathrm{𝚍𝚒𝚜𝚝}$ constraint  (a) (b)