[gecode-users] Inclusion check for SetVar

[Guido Tack]

Hi!

> I am working in the review of  equal propagator for SetVar, and  I want to
> know if in gecode, the propagator checks if lower bounds are a subsets of
> the upper bounds after doing the union between the lower bounds and the
> intersetion of the upper bounds.
>
> If it does, I would like to know  where is the code, or else I would like
> to know why?

I am not sure I really got your question. The propagator computes something 
like

lbunion = lowerbound(x0) union lowerbound(x1)
lowerbound(x0) = lbunion
lowerbound(x1) = lbunion

ubinter = upperbound(x0) intersected with upperbound(x1)
upperbound(x0) = ubinter
upperbound(x1) = ubinter

If your question is whether after these steps, it is tested that 
lowerbound(x0) subset upperbound(x0) and the same for x1, then yes, that's 
tested. It is hidden behind the "tell" operation 
(e.g. x0.includeI(home, lbuc)). A little deeper in the code of the SetVarImp 
class, there is a function processGlbChange which checks (using the function 
boundsConsistent()) whether the bounds are still consistent. If this fails, 
includeI returns ME_SET_FAILED, which the macro GECODE_ME_CHECK checks and 
translates to ES_FAILED.

So, currently we indeed need to check that the lower bound is a subset of the 
upper bound. We are in the process of developing more efficient data 
structures that can signal directly when something is removed from the upper 
bound that belongs to the lower bound, or something is added to the lower 
bound that is no longer in the upper bound. Stay tuned ;-)

Cheers,
	Guido

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