5.11. all_min_dist

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{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}|<2\vee \mathrm{𝙼𝙸𝙽𝙳𝙸𝚂𝚃}<$$\mathrm{𝚛𝚊𝚗𝚐𝚎}$$\left(\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}.\mathrm{𝚟𝚊𝚛}\right)$ $\mathrm{𝚛𝚎𝚚𝚞𝚒𝚛𝚎𝚍}$$\left(\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂},\mathrm{𝚟𝚊𝚛}\right)$
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.

All solutions

Figure 5.11.1 gives all solutions to the following non ground instance of the $\mathrm{𝚊𝚕𝚕}_\mathrm{𝚖𝚒𝚗}_\mathrm{𝚍𝚒𝚜𝚝}$ constraint: ${V}_{1}\in \left[0,5\right]$, ${V}_{2}\in \left[3,9\right]$, ${V}_{3}\in \left[5,7\right]$, ${V}_{4}\in \left[2,10\right]$, $\mathrm{𝚊𝚕𝚕}_\mathrm{𝚖𝚒𝚗}_\mathrm{𝚍𝚒𝚜𝚝}$$\left(\mathbf{3},〈{V}_{1},{V}_{2},{V}_{3},{V}_{4}〉\right)$.

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{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}$.

Arg. properties

Contractible wrt. $\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].

Counting
 Length ($n$) 2 3 4 5 6 7 8 Solutions 8 24 120 720 5040 40320 362880

Number of solutions for $\mathrm{𝚊𝚕𝚕}_\mathrm{𝚖𝚒𝚗}_\mathrm{𝚍𝚒𝚜𝚝}$: domains $0..n$

Length ($n$)2345678
Total824120720504040320362880
 Parameter value

1624120720504040320362880
22------

Solution count for $\mathrm{𝚊𝚕𝚕}_\mathrm{𝚖𝚒𝚗}_\mathrm{𝚍𝚒𝚜𝚝}$: domains $0..n$

generalisation: $\mathrm{𝚍𝚒𝚏𝚏𝚗}$ ($\mathrm{𝚕𝚒𝚗𝚎}\mathrm{𝚜𝚎𝚐𝚖𝚎𝚗𝚝}$, of same length, replaced by orthotope), $\mathrm{𝚍𝚒𝚜𝚓𝚞𝚗𝚌𝚝𝚒𝚟𝚎}$ ($\mathrm{𝚕𝚒𝚗𝚎}\mathrm{𝚜𝚎𝚐𝚖𝚎𝚗𝚝}$, of same length, replaced by $\mathrm{𝚕𝚒𝚗𝚎}\mathrm{𝚜𝚎𝚐𝚖𝚎𝚗𝚝}$), $\mathrm{𝚖𝚞𝚕𝚝𝚒}_\mathrm{𝚒𝚗𝚝𝚎𝚛}_\mathrm{𝚍𝚒𝚜𝚝𝚊𝚗𝚌𝚎}$ ($\mathrm{𝙻𝙸𝙼𝙸𝚃}$ parameter introduced to specify capacity $\ge$1).

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

Keywords
Cond. implications

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

implies $\mathrm{𝚜𝚘𝚏𝚝}_\mathrm{𝚊𝚕𝚕}_\mathrm{𝚎𝚚𝚞𝚊𝚕}_\mathrm{𝚖𝚊𝚡}_\mathrm{𝚟𝚊𝚛}$$\left(𝙽,\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}\right)$

when  $𝙽\ge |\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}|-1$.

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.11.2 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.