[gecode-users] Search and Recomputation

[Guido Tack]

On 18 Nov 2011, at 13:29, Max Ostrowski wrote:

> I have 2 general questions on how search works in gecode.
> 
> Search and Propagation
> 
> I just read on page 306 in "Modelling and Programming with Gecode", that
> during search "pristine" clones are stored, where no propagation was made.
> How is this possible. Considering the simple case, without
> recomputation, having a full "trail" of spaces.
> having space[0] to space[n] for the first n decision levels.
> Now i do a choice on some variable x==1.
> Now i would expect doing some propagation.
> Do you copy the space[n+1], do some propagation, and afterwards delete
> the propagated space to do another choice ?
> Do you always propagate all constraints with all choices without storing
> intermediate, usable, results of this propagation?

I'm not sure I understand this question.  The only way to store results of propagation is to store a clone of a space.  That's what a search engine does. either for every choice point, or only for some (in case of recomputation).  Please read the chapter about search engines, it will answer your questions about which spaces are stored (in particular 36.5, hybrid recomputation).  

> 2nd Question:
> 
> Using Recomputation:
> 
> 
> If i have stored a space S and done some choices C1,C2,C3
> 
> S->C1->S1->C2->S2->C3->S3
> 
> and now recognize that space S3 is failed and want to "backtrack" to S2
> i would do
> 
> S->commit(C1)
> S->commit(C2)
> 
> This should lead to a space equivalent to S2. Is this space already
> propagated ?
> If i now call status() on S, is any propagator invoked?
> Does commit redo the propagation?
> Does it just restore the effects of the propagation?
> Does it just repost the decision (as i could do by hand saying post(x==1) )?

It just posts the decision (that's the point of having choices, you only run the entire propagation once, after posting all the choices).  Calling status() will trigger all the propagation that results from the choices you committed to.  Committing to choices is therefore the same as posting constraints (no propagation happens until you call status()).

Cheers,
Guido

-- 
Guido Tack, http://people.cs.kuleuven.be/~guido.tack/