## 5.4. all_min_dist

Origin
Constraint

$\mathrm{\pi \pi \pi }_\mathrm{\pi \pi \pi }_\mathrm{\pi \pi \pi \pi }\left(\mathrm{\pi Ό\pi Έ\pi ½\pi ³\pi Έ\pi \pi },\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }\right)$

Synonyms

$\mathrm{\pi \pi \pi \pi \pi \pi \pi }_\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi }$, $\mathrm{\pi \pi \pi \pi \pi }_\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi }$.

Arguments
 $\mathrm{\pi Ό\pi Έ\pi ½\pi ³\pi Έ\pi \pi }$ $\mathrm{\pi \pi \pi }$ $\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }$ $\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi \pi }\left(\mathrm{\pi \pi \pi }-\mathrm{\pi \pi \pi \pi }\right)$
Restrictions
 $\mathrm{\pi Ό\pi Έ\pi ½\pi ³\pi Έ\pi \pi }>0$ $\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi }$$\left(\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi },\mathrm{\pi \pi \pi }\right)$ $\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }.\mathrm{\pi \pi \pi }\beta ₯0$
Purpose

Enforce for each pair $\left({\mathrm{\pi \pi \pi }}_{i},{\mathrm{\pi \pi \pi }}_{j}\right)$ of distinct variables of the collection $\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }$ that $|{\mathrm{\pi \pi \pi }}_{i}-{\mathrm{\pi \pi \pi }}_{j}|\beta ₯\mathrm{\pi Ό\pi Έ\pi ½\pi ³\pi Έ\pi \pi }$.

Example
$\left(2,β©5,1,9,3βͺ\right)$

The $\mathrm{\pi \pi \pi }_\mathrm{\pi \pi \pi }_\mathrm{\pi \pi \pi \pi }$ 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{\pi Ό\pi Έ\pi ½\pi ³\pi Έ\pi \pi }=2$ of the $\mathrm{\pi \pi \pi }_\mathrm{\pi \pi \pi }_\mathrm{\pi \pi \pi \pi }$ constraint.

Typical
 $\mathrm{\pi Ό\pi Έ\pi ½\pi ³\pi Έ\pi \pi }>1$ $|\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }|>1$
Symmetries
• $\mathrm{\pi Ό\pi Έ\pi ½\pi ³\pi Έ\pi \pi }$ can be decreased to any value $\beta ₯1$.

• Items of $\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }$ are permutable.

• Two distinct values of $\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }.\mathrm{\pi \pi \pi }$ can be swapped.

• One and the same constant can be added to the $\mathrm{\pi \pi \pi }$ attribute of all items of $\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }$.

Usage

The $\mathrm{\pi \pi \pi }_\mathrm{\pi \pi \pi }_\mathrm{\pi \pi \pi \pi }$ 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{\pi \pi \pi }_\mathrm{\pi \pi \pi }_\mathrm{\pi \pi \pi \pi }$ constraint can be modelled as a set of tasks that should not overlap. For each variable $\mathrm{\pi \pi \pi }$ of the $\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }$ collection we create a task $t$ where $\mathrm{\pi \pi \pi }$ and $\mathrm{\pi Ό\pi Έ\pi ½\pi ³\pi Έ\pi \pi }$ 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}|\beta ₯{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{\pi \pi \pi }_\mathrm{\pi \pi \pi }_\mathrm{\pi \pi \pi \pi }$ 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].

generalisation: $\mathrm{\pi \pi \pi \pi \pi }$Β ($\mathrm{\pi \pi \pi \pi }\mathrm{\pi \pi \pi \pi \pi \pi \pi }$, of same length, replaced by orthotope), $\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi }$Β ($\mathrm{\pi \pi \pi \pi }\mathrm{\pi \pi \pi \pi \pi \pi \pi }$, of same length, replaced by $\mathrm{\pi \pi \pi \pi }\mathrm{\pi \pi \pi \pi \pi \pi \pi }$).

specialisation: $\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi }$Β ($\mathrm{\pi \pi \pi \pi }\mathrm{\pi \pi \pi \pi \pi \pi \pi }$, of same length, replaced by $\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi }$).

Keywords
Arc input(s)

$\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }$

Arc generator
$\mathrm{\pi Ά\pi Ώ\pi Ό\pi \pi \pi Έ}$$\left(<\right)\beta ¦\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi \pi }\left(\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi }\mathtt{1},\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi }\mathtt{2}\right)$

Arc arity
Arc constraint(s)
$\mathrm{\pi \pi \pi }\left(\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi }\mathtt{1}.\mathrm{\pi \pi \pi }-\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi }\mathtt{2}.\mathrm{\pi \pi \pi }\right)\beta ₯\mathrm{\pi Ό\pi Έ\pi ½\pi ³\pi Έ\pi \pi }$
Graph property(ies)
$\mathrm{\pi \pi \pi \pi }$$=|\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }|*\left(|\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }|-1\right)/2$

Graph class
 $\beta ’$$\mathrm{\pi °\pi ²\pi \pi ²\pi »\pi Έ\pi ²}$ $\beta ’$$\mathrm{\pi ½\pi Ύ}_\mathrm{\pi »\pi Ύ\pi Ύ\pi Ώ}$

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{\pi \pi \pi }_\mathrm{\pi \pi \pi }_\mathrm{\pi \pi \pi \pi }$ constraint holds since all the arcs of the initial graph belong to the final graph: all the minimum distance constraints are satisfied.