5.4. all_min_dist

DESCRIPTIONLINKSGRAPH
Origin

[Regin97]

Constraint

πšŠπš•πš•_πš–πš’πš—_πšπš’πšœπš(π™Όπ™Έπ™½π™³π™Έπš‚πšƒ,πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚)

Synonyms

πš–πš’πš—πš’πš–πšžπš–_πšπš’πšœπšπšŠπš—πšŒπšŽ, πš’πš—πšπšŽπš›_πšπš’πšœπšπšŠπš—πšŒπšŽ.

Arguments
π™Όπ™Έπ™½π™³π™Έπš‚πšƒπš’πš—πš
πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(πšŸπšŠπš›-πšπšŸπšŠπš›)
Restrictions
π™Όπ™Έπ™½π™³π™Έπš‚πšƒ>0
πš›πšŽπššπšžπš’πš›πšŽπš(πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚,πšŸπšŠπš›)
πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚.πšŸπšŠπš›β‰₯0
Purpose

Enforce for each pair (πšŸπšŠπš› i ,πšŸπšŠπš› j ) of distinct variables of the collection πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚ that |πšŸπšŠπš› i -πšŸπšŠπš› j |β‰₯π™Όπ™Έπ™½π™³π™Έπš‚πšƒ.

Example
(2,5,1,9,3)

The πšŠπš•πš•_πš–πš’πš—_πšπš’πšœπš 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 π™Όπ™Έπ™½π™³π™Έπš‚πšƒ=2 of the πšŠπš•πš•_πš–πš’πš—_πšπš’πšœπš constraint.

Typical
π™Όπ™Έπ™½π™³π™Έπš‚πšƒ>1
|πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚|>1
Symmetries
  • π™Όπ™Έπ™½π™³π™Έπš‚πšƒ can be decreased to any value β‰₯1.

  • Items of πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚ are permutable.

  • Two distinct values of πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚.πšŸπšŠπš› can be swapped.

  • One and the same constant can be added to the πšŸπšŠπš› attribute of all items of πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚.

Usage

The πšŠπš•πš•_πš–πš’πš—_πšπš’πšœπš 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 πšŠπš•πš•_πš–πš’πš—_πšπš’πšœπš constraint can be modelled as a set of tasks that should not overlap. For each variable πšŸπšŠπš› of the πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚ collection we create a task t where πšŸπšŠπš› and π™Όπ™Έπ™½π™³π™Έπš‚πšƒ 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 |β‰₯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 πšŠπš•πš•_πš–πš’πš—_πšπš’πšœπš 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: πšπš’πšπšπš—Β (πš•πš’πš—πšŽ πšœπšŽπšπš–πšŽπš—πš, of same length, replaced by orthotope), πšπš’πšœπš“πšžπš—πšŒπšπš’πšŸπšŽΒ (πš•πš’πš—πšŽ πšœπšŽπšπš–πšŽπš—πš, of same length, replaced by πš•πš’πš—πšŽ πšœπšŽπšπš–πšŽπš—πš).

implies: πšŠπš•πš•πšπš’πšπšπšŽπš›πšŽπš—πš_πš’πš—πšπšŽπš›πšŸπšŠπš•.

related: πšπš’πšœπšπšŠπš—πšŒπšŽ.

specialisation: πšŠπš•πš•πšπš’πšπšπšŽπš›πšŽπš—πšΒ (πš•πš’πš—πšŽ πšœπšŽπšπš–πšŽπš—πš, of same length, replaced by πšŸπšŠπš›πš’πšŠπš‹πš•πšŽ).

Keywords

application area: frequency allocation problem, air traffic management.

constraint type: value constraint, decomposition, scheduling constraint.

filtering: bound-consistency.

final graph structure: acyclic.

problems: maximum clique.

Arc input(s)

πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚

Arc generator
πΆπΏπΌπ‘„π‘ˆπΈ(<)β†¦πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(πšŸπšŠπš›πš’πšŠπš‹πš•πšŽπšœ1,πšŸπšŠπš›πš’πšŠπš‹πš•πšŽπšœ2)

Arc arity
Arc constraint(s)
πšŠπš‹πšœ(πšŸπšŠπš›πš’πšŠπš‹πš•πšŽπšœ1.πšŸπšŠπš›-πšŸπšŠπš›πš’πšŠπš‹πš•πšŽπšœ2.πšŸπšŠπš›)β‰₯π™Όπ™Έπ™½π™³π™Έπš‚πšƒ
Graph property(ies)
𝐍𝐀𝐑𝐂=|πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚|*(|πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚|-1)/2

Graph class
β€’ π™°π™²πšˆπ™²π™»π™Έπ™²
β€’ 𝙽𝙾_𝙻𝙾𝙾𝙿

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 πšŠπš•πš•_πš–πš’πš—_πšπš’πšœπš 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 πšŠπš•πš•_πš–πš’πš—_πšπš’πšœπš constraint
ctrs/all_min_distActrs/all_min_distB
(a) (b)