[gecode-users] Schedule Branching Recommendations

[Filip Konvička]

> 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