[Gecode] propagators, events, updated variables and domain deltas

[Christian Schulte]

Hi,

you are right on all questions. The idea is to keep the kernel very simple
and yet efficient.

Assume the question about which variable is modified. You only have to pay
for it in a propagator who uses it and the price is just linear time (there
are hardly any propagation algorithms with sublinear complexity...) and
linear space (this is also true).

I am currently working with somebody else on an architecture which will
provide these services at sublinear cost but we are still far away at
something that is efficient and simple enough to beat the naïve way.

And even if you had seomthing like a delta, it is actually typically not
what you need: a propagator quite often works on a particular data structure
geared towards the propagation algorithm. This data structure needs to be
updated according to what has changed. So the point is that it does not
really matter whether you compute on data structure plus delta or on data
structure plus new domain.

And of course, if you want to know which variables have been modified, you
don't have to store entire domains but just the size of the domain.

All the best
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 Grégoire Dooms
Sent: Friday, March 04, 2005 12:34 PM
To: Technical discussions about Gecode
Subject: [Gecode] propagators, events, updated variables and domain deltas


Hi,

I've been reading the source code of gecode and I would like to ask you 
a few basic questions.

Looking at the implementation of singleton elimination in 
int/distinct/val.icc, the propagator scans all the variables in order to 
know which are singletons and which are not.
It looks like there is no way for a propagator to know which variable(s) 
triggered it. Is this right ?

When a propagator is awakened by a variable (int or set) domain update, 
I would like to be able to know which values where taken out of the 
domain. Is there an other way than to compare the new domains of the 
variables with a previously stored copy of these domains ?

--
Grégoire Dooms
_______________________________________________
Gecode mailing list
Gecode at ps.uni-sb.de http://www.ps.uni-sb.de/mailman/listinfo/gecode