[Gecode] Announcement: FS constraints prototype

[Christian Schulte]

Failure and nothing does not need a bit? So it should eaxctly as with finite
domains!
	Assigned
	GLB changed
	LUB changed
	GLB+LUB changed
	CARD changed
And the point to note is that all other events also change the cardinality,
right?

Otherwise, congratulations!

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: Friday, December 05, 2003 13:13
> To: gecode at ps.uni-sb.de
> Subject: Re: [Gecode] Announcement: FS constraints prototype
> 
> 
> 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 
> _______________________________________________
> Gecode mailing list
> Gecode at ps.uni-sb.de http://www.ps.uni-sb.de/mailman/listinfo/gecode
>