[gecode-users] random / mod

[Christian Schulte]

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.

Cheers
Christian

--
Christian Schulte, http://www.imit.kth.se/~schulte/ 

-----Original Message-----
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


Hi Torsten.

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

Cheers,
	Guido

-- 
Guido Tack
Programming Systems Lab, Saarland University, Germany
http://www.ps.uni-sb.de/~tack




_______________________________________________
Gecode users mailing list
users at gecode.org https://www.gecode.org/mailman/listinfo/gecode-users