[gecode-users] branching and copy in Gecode

[Guido Tack]

There is no direct event or notification for backtracking.  But your propagator could have a pointer to the shared data structure (see chapter 27.3 in MPG), and both the data structure and the propagator could have a "time stamp".  When the propagator gets copied, you increment the time stamp in the copy.  Every time you run the propagator, you check if the time stamps of the propagator and the shared data structure match, and if they don't you repair the data structure and set its time stamp to the current propagator's.  This is quite cheap, just an additional integer in the propagator and a simple check in its propagate method.

Cheers,
Guido

On 28/10/2012, at 8:58 PM, Jun He <hejunnudt at gmail.com> wrote:

> Hi,
> 
> Thank you for your explanation.
> 
> I want all the instances of my propagator to share the data structure instead of making a copy, as storing the data structure needs too much memory.  Hence I want my propagator to rollback the data structure when a backtracking happens.  Is there an event to notify the propagator (or some policy to make the propagator detects) when a backtracking happens?  
> 
> Best regards,
> Jun
> 
> 
> On 28/10/12 01:24, Guido Tack wrote:
>> Hi,
>> 
>> backtracking always jumps back to a copy and then recomputes the node that it actually wants to jump to.  So you can maintain your propagator data structures incrementally, as long as they're copied (or marked for recomputation) during cloning.  See chapter 7.2 in MPG for a more detailed explanation of recomputation.
>> 
>> Cheers,
>> Guido
>> 
>> On 28/10/2012, at 2:23 , Jun He <hejunnudt at gmail.com> wrote:
>> 
>>> Hi,
>>> 
>>> In Gecode, copy doesn't happen for every branching of the search tree, and whenever a failure happens it just backtracks to a node between the current failure node and the previous copied node.  If a propagator works dependent on some data structure, and the backtrack jumps to a node that is not copied, then the data structure should be recomputed.  My question is how to maintain the data structure incrementally for the propagator?  Is there an easy setting to make Gecode copy at each branching, so that a simple undo policy can be used to maintain the data structure?
>>> 
>>> Best regards,
>>> Jun
>>> 
>>> _______________________________________________
>>> Gecode users mailing list
>>> users at gecode.org
>>> https://www.gecode.org/mailman/listinfo/gecode-users
>> 
>> -- 
>> Guido Tack,
>> http://www.csse.monash.edu/~guidot/
>> 
>> 
>> 
> 

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.gecode.org/pipermail/users/attachments/20121029/f764702d/attachment.html>