[gecode-users] random / mod

[Torsten Anders]

Dear all,

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?

Best,
Torsten

On 22.08.2006, at 14:53, Lars Otten wrote:
> 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.
>
>
> _______________________________________________
> Gecode users mailing list
> users at gecode.org
> https://www.gecode.org/mailman/listinfo/gecode-users
>
>
--
Torsten Anders
Sonic Arts Research Centre • Queen's University Belfast
Frankstr. 49 • D-50996 Köln
Tel: +49-221-3980750
http://www.torsten-anders.de
http://strasheela.sourceforge.net