[Gecode] One constraint = multiple propagators

[Christian Schulte]

Actually, I just submitted a paper the other day that works that out. As the
paper is still under review, I'll just send it to Guido, other people
interested, please get to my be Email.

The key idea (which is already supported in Gecode) is that a propagator can
find out about the event which has triggered it. However what is not yet
done is that also the variable is known. But typically one can emulate that
by putting some state into a propahator.

If you look for an example look to the #ifedf STAGED_PROPAGATORS part in
int/distinct/dom.icc

Christian

--
Christian Schulte, http://www.imit.kth.se/~schulte/ 

-----Original Message-----
From: gecode-bounces at ps.uni-sb.de [mailto:gecode-bounces at ps.uni-sb.de] On
Behalf Of Guido Tack
Sent: Tuesday, April 20, 2004 3:56 PM
To: gecode at ps.uni-sb.de
Subject: [Gecode] One constraint = multiple propagators


Hi!

We have implemented some constraints as multiple propagators, one for each 
propagation rule, to make them react to more specific modification events. 
This raises two questions:
* Efficiency: Multiple propagators need more memory for dependencies and
more 
time during copying. This can become really expensive, as we have seen for 
the intersection constraint. Should we make different versions of
constraints 
available, one that does everything in a single propagator, and one that 
reacts to specific events? Any idea how to find out what makes more sense?
* Entailment: How do we check that the whole constraint is entailed, or 
replace several propagators by a simpler one? Example: A selection
constraint 
that notices that the selector variable is determined could be replaced by 
just a union or whatever. We could either check for entailment in every 
propagator, and let only one of them create the replacement propagator(s),
or 
have some common variable that they use to communicate (again quite 
expensive...)

Another thing that is not quite clear to us is whether there is any way for
a 
propagator to find out which variables really triggered what propagation 
conditions. This could be used to use a single propagator for multiple 
propagation rules.

Regards,

	Guido

-- 
Guido Tack
Programming Systems Lab
http://www.ps.uni-sb.de/~tack
_______________________________________________
Gecode mailing list
Gecode at ps.uni-sb.de http://www.ps.uni-sb.de/mailman/listinfo/gecode