5.100. discrepancy

Origin

[Focacci01] and [vanHoeve05]

Constraint

discrepancy​(VARIABLES,​K)​

Argument(s)

VARIABLES	collection​(var−dvar,​bad−sint)​
K	int

Restriction(s)

required​(VARIABLES,​var)​

required​(VARIABLES,​bad)​

K≥0

K≤|VARIABLES|

Purpose

K is the number of variables of the collection VARIABLES that take their value in their respective sets of bad values.

Example

( 〈 var−4 bad−​{1,​4,​6}​,​ var−5 bad−​{0,​1}​,​ var−5 bad−​{1,​6,​9}​,​ var−4 bad−​{1,​4}​,​ var−1 bad−∅ 〉,​2 )

The discrepancy constraint holds since exactly K=2 variables (i.e., the first and fourth variables) of the VARIABLES collection take their value within their respective sets of bad values.

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 discrepancy constraint was explicitly defined in the PhD thesis of W.-J. van Hoeve [vanHoeve05].

See also

among.

Key words

constraint type: value constraint, counting constraint.

filtering: arc-consistency.

heuristics: heuristics, limited discrepancy search.

Arc input(s)

VARIABLES

Arc generator

SELF↦collection​(variables)​

Arc arity

1

Arc constraint(s)

in_set​(variables.var,​variables.bad)​

Graph property(ies)

NARC=K

---

Graph model

The arc constraint corresponds to the constraint in_set​(variables.var,​variables.bad)​ defined in this catalogue. We employ the SELF arc generator in order to produce an initial graph with a single loop on each vertex.

Parts (A) and (B) of Figure 5.100.1 respectively show the initial and final graph associated with the Example slot. Since we use the NARC graph property, the loops of the final graph are stressed in bold.

Figure 5.100.1. Initial and final graph of the discrepancy constraint

(a)	(b)