[gecode-users] random / mod

[Lars Otten]

Hi!

On 08/22/06 12:43, Kilian Sprotte wrote:
> Am 22.08.2006 um 11:19 schrieb Lars Otten:
>> What exactly is it that you want to do? I think I took part in the said
>> discussion; eventually I managed to get some form of randomization
>> working
>> and I've successfully been using it for a project, so maybe I can help...
> 
> Hi Lars,
> 
> this would be extremely kind of you!! :) I dont think that my demands
> are so high in fact -- the quality of the random gen is not very
> important, for example.

In fact the 'quality' of the random numbers is not so much the issue here,
and as Mikael Lagerkvist noted some months ago, a fairly 'good' random
number generator already ships with Gecode (as I recall as part of the
testing component).

The problem at hand is more within Gecode's architecture that employs
recomputation. To clarify (and save me some typing) I'll quote my upcoming
Master's thesis:

<quote>
The search engines in Gecode make heavy use of \emph{recomputation}, meaning
that one and the same branching decision might have to be made several times
throughout the search process. Obviously, for recomputation to work
properly, it is essential that the same choice is taken every time, which is
not a problem with fully deterministic, non-randomized heuristics.

With randomized selection schemes, however, this is not self-evident:
Normally, everytime a randomized decision is to be made, a potentially
differing random number will be used. Consequentially a different outcome
might ensue for the same problem configuration.

To overcome this conflict we added the following feature to the search tree
traversal mechanism: When a node in the search tree is first encountered, we
memorize the state of the random number generator (the \emph{random seed})
that the branching decision will be based on. If we subsequently get back to
the same node during recomputation we restore the saved random seed before
the branching decision is made again.
</quote>

> I should tell you that I am more a composer than a programmer and using
> constraints for writing my music (it means my knowledge of c++ is not
> ideal...). This is the currently pretty simple Space I am using together
> with DFS<Simple>(home):
> [...]
> If I dont post very many constraints the result is a bit mechanical --
> instead of posting many more of them to "disturb" the solver, the random
> dist would be very useful, especially, if I would not loose solutions...

If you do it right you won't lose any solutions at all. :)

> Have you published/reported on your project somewhere?

As mentioned above, I'm just finishing my Master's thesis (which in turn is
based on a conference paper on randomization in CP). But it doesn't really
cover the technical aspect of implementing randomization but focuses more on
how to exploit it in theory and practice.

Maybe my quote above helps you to get the hang of it already; otherwise just
ask questions. Also I could maybe offer sending you the resp. portions of my
modified code (parts of it should already have been posted here some time
ago). This is, hoever, still based on an older version of Gecode (1.0.1 I
think) and I currently don't have the time to make the transit to 1.2.x. It
might give you the idea, though...

Cheers,
/Lars


P.S. You might want to CC your future responses to users at gecode.org as well,
so others can profit from and participate in the discussion as well.