5.121. discrepancy
DESCRIPTION | LINKS | GRAPH |
- Origin
- Constraint
- Arguments
- Restrictions
- Purpose
is the number of variables of the collection that take their value in their respective sets of bad values.
- Example
-
The constraint holds since exactly variables (i.e.,Β the first and fourth variables) of the collection take their value within their respective sets of bad values.
- Typical
- 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.
- Arg. properties
Functional dependency: determined by .
Aggregate: , .
- 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
- Keywords
constraint arguments: pure functional dependency.
constraint type: value constraint, counting constraint.
- 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.121.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.121.1. Initial and final graph of the constraint
(a) (b)