[gecode-users] Schedule Branching Recommendations

[Christian Schulte]

Hi Filip,

as you might have guessed, Gecode has nothing built in that is not used. So
far, we had no need to have first class references to propagators. That
entails that communication with a propagator currently is not possible.
That's another thing we knew would come up some day, but so far there was no
need. If you see a little clearer of what you want, we will try to come up
with something that does the job. 

Actually, I believe the only thing that's needed are first-class references
to a propagator that you can store somewhere (this is not totally
straightforward as these references must be updated during cloning and the
current architecture for cloning takes advantage of the fact that there are
no references to propagator but at a single well-defined location). But
that's something we could easily squeeze in for 2.0.

Another small point, branching descriptions are not copied: they act as a
closure to a space and are hence maintained by the search engine
independently of cloning.

Christian

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

-----Original Message-----
From: Filip Konvicka [mailto:filip.konvicka at logis.cz] 
Sent: Tuesday, August 28, 2007 11:09 AM
To: cschulte at kth.se
Cc: users at gecode.org
Subject: Re: [gecode-users] Schedule Branching Recommendations



> Hi Filip,
>
> well, well. Let me just summarize some facts:
>
>  - Your idea will work but, as you say yourself, is not going to win any
>    software design beauty contest. It might be good to tinker, but for
>    Gecode itself a design will be needed that does not require to change
>    a space (that's typically a user's model) when using a propagator
>    cum branching.
>   

:-D

Yes, I realize that the approach is not generally applicable and is not 
"clean" at all, and I am looking forward for your general solution!

>  - The idea that this data is just a cache is very helpful. Indeed, we
>    use the very same idea to great advantage in many propagators that
>    ship with Gecode: do not copy the data just reconstruct it when needed,
>    and if the data is already there keep it up to date while doing
>    propagation. If the data becomes to messy, just flush the cache (data)
>    an reconstruct it.
>   

This I understand, and this is also one of the things that make Gecode 
so nice for me.

>  - Invoking the status method of a space will always compute a fixpoint,
>    regardless of recomputation or not (as does the attempt to clone a
>    space). This also entails that when the status method of a branching
>    is called, the home is at fixpoint (stable).
>
>  - Invoking a commit method however will not compute a fixpoint: the very
>    idea of making recomputation efficient relies on this.
>
>  - You might be able to speed up branching considerably if you take 
> advantage
>    of branching descriptions. They must store information to actually 
> perform
>    a commit operation (as the space is typically not at fixpoint, see 
> above).
>    You have the possibility to add additional information to the branching

>    description that assists in maintaing your data.
>   

I think that in most cases, the branching descriptions can be really 
small and fast to copy. Currently I don't think I'd use it for 
maintaining the data.

I was thinking about one more thing - whether it is possible to 
communicate with existing propagators to extend the constraints on the 
fly. In the case of scheduling constraints, this could be adding tasks 
to a resource for example. Again, I think this could be done in commit, 
I'm just not sure whether it's possible to somehow access the 
propagators. One way I thought of is having some dedicated "spare" 
variables (probably quite clean, but not much flexible and quite 
costly); another approach that I think could work is implementing a 
(probably one-way) "message queue" for the communication. I realize that 
in this case, a variable would have to be associated with the queue that 
would wake up the propagator when needed.

> The idea to maintain the data as a cache is orthogonal to these facts.
>
> Hope that helps
>   
It certainly does. Thanks very much, Christian!

Cheers,
Filip