[gecode-users] random / mod
schulte at imit.kth.se
Fri Aug 25 10:01:56 CEST 2006
Yes, the reason why I did not reply immediately is like with Guido: I
believe that our current engines never mix the generation of branching
descriptions with their use in recomputation. But in general this invariant
does not hold.
The good news, though, is the contrary to what you have asked: if you happen
to implement a randomized branching then batch recomputation will come
without extra cost.
And I really would like to stress the point that making randomized branching
with recomputation is not magic: random generators are stateful but
deterministic programs generating sequences of pseudo-random numbers. So
recording the state of the generator will always be sufficient to make it
work with recomputation.
The only problem I see is that the standard Unix random generator has an
interface that does not expose this fact.
Christian Schulte, http://www.imit.kth.se/~schulte/
From: users-bounces at gecode.org [mailto:users-bounces at gecode.org] On Behalf
Of Guido Tack
Sent: Friday, August 25, 2006 9:56 AM
To: Torsten Anders
Cc: users at gecode.org
Subject: Re: [gecode-users] random / mod
> Here is a related question: would batch recomputation simplify the
> definition of randomized selection schemes? That is, are the
> decisions made by the branching recorded by the batch recomputation
> mechanism such that randomized selection schemes come fore free?
It could be achieved using batch recomputation, but there is a
caveat: a search engine is allowed to ask the same space for a
branching description more than once.
It is possible (in fact not hard) to implement a search engine that
only computes descriptions once for a space. These search engines
would work well with randomized branchings. I don't know what our
built-in search engines currently do, I'll have to take a closer look.
Programming Systems Lab, Saarland University, Germany
Gecode users mailing list
users at gecode.org https://www.gecode.org/mailman/listinfo/gecode-users
More information about the gecode-users