5.103. discrepancy

DESCRIPTIONLINKSGRAPH
Origin

[Focacci01] and [vanHoeve05]

Constraint

πšπš’πšœπšŒπš›πšŽπš™πšŠπš—πšŒπš’(πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚,𝙺)

Arguments
πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(πšŸπšŠπš›-πšπšŸπšŠπš›,πš‹πšŠπš-πšœπš’πš—πš)
π™Ίπš’πš—πš
Restrictions
πš›πšŽπššπšžπš’πš›πšŽπš(πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚,πšŸπšŠπš›)
πš›πšŽπššπšžπš’πš›πšŽπš(πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚,πš‹πšŠπš)
𝙺β‰₯0
𝙺≀|πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚|
Purpose

𝙺 is the number of variables of the collection πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚ that take their value in their respective sets of bad values.

Example
πšŸπšŠπš›-4πš‹πšŠπš-{1,4,6},πšŸπšŠπš›-5πš‹πšŠπš-{0,1},πšŸπšŠπš›-5πš‹πšŠπš-{1,6,9},πšŸπšŠπš›-4πš‹πšŠπš-{1,4},πšŸπšŠπš›-1πš‹πšŠπš-βˆ…,2

The πšπš’πšœπšŒπš›πšŽπš™πšŠπš—πšŒπš’ constraint holds since exactly 𝙺=2 variables (i.e.,Β the first and fourth variables) of the πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚ collection take their value within their respective sets of bad values.

Typical
|πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚|>1
𝙺<|πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚|
Symmetries
  • Items of πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚ are permutable.

  • All occurrences of two distinct values in πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚.πšŸπšŠπš› or πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚.πš‹πšŠπš can be swapped; all occurrences of a value in πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚.πšŸπšŠπš› or πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚.πš‹πšŠπš can be renamed to any unused value.

Remark

Limited discrepancy search was first introduced by M.Β L.Β Ginsberg and W.Β D.Β Harvey as a search technique inΒ [GinsbergHarvey95]. Later on, discrepancy based filtering was presented in the PhD thesis of F.Β FocacciΒ [Focacci01]. Finally the πšπš’πšœπšŒπš›πšŽπš™πšŠπš—πšŒπš’ constraint was explicitly defined in the PhD thesis of W.-J.Β vanΒ HoeveΒ [vanHoeve05].

See also

common keyword: πšŠπš–πš˜πš—πšΒ (counting constraint).

used in graph description: πš’πš—_𝚜𝚎𝚝.

Keywords

constraint type: value constraint, counting constraint.

filtering: arc-consistency.

heuristics: heuristics, limited discrepancy search.

Arc input(s)

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

Arc generator
π‘†πΈπΏπΉβ†¦πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(πšŸπšŠπš›πš’πšŠπš‹πš•πšŽπšœ)

Arc arity
Arc constraint(s)
πš’πš—_𝚜𝚎𝚝(πšŸπšŠπš›πš’πšŠπš‹πš•πšŽπšœ.πšŸπšŠπš›,πšŸπšŠπš›πš’πšŠπš‹πš•πšŽπšœ.πš‹πšŠπš)
Graph property(ies)
𝐍𝐀𝐑𝐂=𝙺

Graph model

The arc constraint corresponds to the constraint πš’πš—_𝚜𝚎𝚝(πšŸπšŠπš›πš’πšŠπš‹πš•πšŽπšœ.πšŸπšŠπš›,πšŸπšŠπš›πš’πšŠπš‹πš•πšŽπšœ.πš‹πšŠπš) defined in this catalogue. We employ the 𝑆𝐸𝐿𝐹 arc generator in order to produce an initial graph with a single loop on each vertex.

PartsΒ (A) andΒ (B) of FigureΒ 5.103.1 respectively show the initial and final graph associated with the Example slot. Since we use the 𝐍𝐀𝐑𝐂 graph property, the loops of the final graph are stressed in bold.

Figure 5.103.1. Initial and final graph of the πšπš’πšœπšŒπš›πšŽπš™πšŠπš—πšŒπš’ constraint
ctrs/discrepancyActrs/discrepancyB
(a) (b)