[Gecode] Announcement: FS constraints prototype

[Guido Tack]

Hi Denys!

On Friday 05 December 2003 12:03, duchier at ps.uni-sb.de wrote:
> er... isn't that backwards? it should be:
>
>       S_1\subseteq S_2\cap S_3
>       S_1\supseteq S_2\cup S_3

Hm, according to Tobias' thesis it's "subset of union" and "superset of 
intersection" ?!? ;-)

> That's essentially the way it is done in Mozart: each FS variable
> keeps track of min/max for cardinality. FS.card simply posts a
> propagator between the FS variable and a FD variable that propagates
> these bounds both ways.
>
> Please, keep a similar design.  We certainly don't want to introduce
> cardinality variables and propagators for _all_ sets.

Hm, maybe I should try to explain this in a bit more detailed way:

A propagator subscribes to certain modification events (MEs) of a variable, so 
that it is only invoked if that event has occured. All finite set MEs have to 
be represented using 3 bits, we chose "nothing happened", "failure", 
"assigned", "lower bound changed", "upper bound changed", "both bounds 
changed". So there are only two more MEs, which is not enough to encode 
combinations of the above with,e.g., "cardinality changed". This is our main 
technical argument against representing cardinality in a core set variable.

Of course this makes the cardinality propagators a bit less efficient than 
possible: Everytime the bounds change, they have to be invoked and test 
whether the cardinality changed as well - this cannot be done by the tell 
operations of the core fs variable.

Is it true that in Mozart, no cardinality information is propagated at all 
unless you explicitly create a cardinality variable? We could easily follow 
that model (and you gave a good reason to do so).

Guido

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