[gecode-users] Schedule Branching Recommendations

[Filip Konvička]

Hi Christian,

> 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.
>   

I should have been more specific here - I was not asking whether it is 
possible now, using the current library, but wheter it is possible at 
all. I'm definitely not asking you to add anything to Gecode now, 
because I don't know exactly what I will need, nor whether it would be 
generally useful. I was just thinking of what could be possible in 
version 8.0 :-)

As for first-class references to propagators - that's why I thought I'd 
do it the other way round: the message queue could be a part of the 
space, accessible both from branching during commits and in the 
propagator as well. This does not require changes in the library, and 
will be sufficien for my needs (should I find out that I really need 
it). Of course, this is not good design, as the propagators/branchings 
need to know the space's type (though some generalization is possible at 
this level too).

> 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.
>   

I did not think of them being copied during cloning, but rather as a 
part of some computation-path-structure reorganization (I don't know 
whether a branching description is ever copied...I thought that perhaps 
some std::vector or the like could be used internally by the library).

Thanks!
Filip

> 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