[gecode-users] value-consistency definition

[Guido Tack]

Hi.

> I've searched for a definition of value-consistency, but I don't  
> really
> find it.

Unlike bounds-consistency or domain-consistency, it's not standard  
terminology, I think.

> What I've understood is that using the value-consistency is no more  
> than
> a constraint checking. So, there's no propagation in this case.
>
> Saying that a constraint is value-consistent should then mean that it
> exists a value for each involved variable such that the constraint is
> satisfied.
>
> Examples :
> X in {1, 2, 3}
> Y in {3, 4, 5}
> the constraint X = Y is value-consistent.
>
> X in {1, 2, 3}
> Y in {4, 5, 6}
> the constraint X = Y isn't value-consistent.
>
> Am I right ?

No, it's even weaker. We haven't defined it formally, but our  
intuition for the ICL_VAL consistency level is that the constraint  
will only propagate if at least one of its variables is assigned to a  
single value. A formal definition would be something like "for all  
variables with singleton domains, there exist values in the domains  
of the other variables that are consistent with the constraint".

We can slightly modify your example:

For X in {1}, Y in {1,2,3}, X=Y is value consistent
For X in {1}, Y in {2,3}, X=Y is not value consistent

But:
For X in {1,2}, Y in {3,4}, X=Y is value consistent!

For the implementation, it usually means that the propagator  
subscribes with the PC_INT_VAL propagation condition (for int  
variables), so that it is only woken up when a variable gets  
assigned. In fact, the propagator might be even weaker, only deciding  
whether the constraint holds if /all/ its variables are assigned.  
This is actually the minimal thing a propagator has to do.

Cheers,
	Guido

-- 
Guido Tack
Programming Systems Lab, Saarland University, Germany
http://www.ps.uni-sb.de/~tack