[gecode-users] How to set an arbitrary RandomGenerator for randomized branching?!?

Tue May 19 11:02:53 CEST 2009

Hi,

For getting reproducible results, setting the random number generator
seed in the beginning from the global random number generator is a
good way to do it as long as you are not using non-monotonic
propagators. The rationale for using an LCG as the standard random
number generator in Gecode is that it is simple, fast, gives decent
random numbers, and it has a small state.

However, please note that just using random variable and value
selection will not give you a random solution with any kind of known
distribution. Finding random solutions to CSPs with a given (usually
uniform) distribution is a non-trivial problem. IMHO, XorSample by
Gomes, Sabharwal, and Selman [1] is a nice example of how to get
near-uniform solutions to SAT-problems.

Cheers,
Mikael

[1] http://www.cs.cornell.edu/~sabhar/publications/xorSamplingNIPS06.pdf

On Mon, May 18, 2009 at 7:01 PM, Martin Mann
<mmann at informatik.uni-freiburg.de> wrote:
>
> Alright, what is my scenario:
>
> I have a stochastic simulation e.g. a Markov chain. Within this
> simulation, for each step x_i a CSP is formulated and I would like to
> get a random solution r. This solution r is accepted based on some
> probability. Thus, I can stay at x_i (x_(i+1)=x_i) or proceed to r
> (x_(i+1)=r).
>
> So I have two "areas" where random numbers are produced: (1) the Markov
> chain and (2) the randomized branching within Gecode.
>
> Now I would like to have ONE pseudo random number generator (RNG) used
> for both to ensure that I have reproducable results...
>
> One possible hack is the following:
> - assume RNG_M for the markov chain and RNG_G for gecode internals.
> - for each step I set the seed of RNG_G via a random number drawn from RNG_M
> - I use RNG_M for the Markov chain step check
>
> Would be an option, but it would ease the problem a lot if one could
> directly use the same RNG for both or not?
>
> Another point about arbitrary RNGs is about statistics. I am working in
> a field were e.g. physics care a lot about the random number
> distributions and statistics a pseudo random number generator gives.
> Therefore, these people like to set up their favorite RNG they trust
> most to give low-biased stochastic simulations.
> In the above solution, the RNG_M can be defined freely, the RNG_G not.
>
> That's why I was asking. :) It's not about speed or space, more about
> application.
>
> But so long the above solution will do or has to be sufficient.
>
> Thanks,
>
> Martin
>
>
>
>
> Javier Andrés Mena Zapata schrieb:
>> Hi,
>>
>> Just curiosity... Do you prefer RNG speed, RNG space, general speed or
>> general space?
>>
>> Cheers,
>>
>> On Mon, May 18, 2009 at 2:55 AM, Mikael Zayenz Lagerkvist
>> <zayenz at gmail.com>wrote:
>>
>>> Hi,
>>>
>>> Currently it is not possible to exchange the random number generator.
>>> Furthermore, the implementation uses properties of the random number
>>> generator that would most probably compromise efficiency if they were
>>> abstracted away (for example, the state is limited to a single
>>> unsigned int as seed). If you want to use your own random number
>>> generator, I would suggest writing your own subclasses of ViewSelBase
>>> and ValSelbase similar to ViewSelRnd and ValRnd.
>>>
>>> For curiosity, what is the reason that you want to change the random
>>> number generator used?
>>>
>>> Cheers,
>>> Mikael
>>>
>>> On Sat, May 16, 2009 at 12:37 AM, Martin Mann
>>> <mmann at informatik.uni-freiburg.de> wrote:
>>>> Hi everybody,
>>>>
>>>> I digged a bit into the Gecode source about the randomized branching
>>>> supported since version 3.
>>>>
>>>> In line 124 in gecode/support/random.hpp I found the definition of
>>>> RandomGenerator internally used in the view selection:
>>>>
>>>>
>>> http://www.gecode.org/doc-latest/reference/group__FuncSupport.html#g02fe942f90a57a25639f09960dab4459
>>>> As given there, it is just a typedef onto the
>>>> LinearCongruentialGenerator provided by Gecode but I would like to set
>>>> up my own random number generator...
>>>>
>>>> Is there a possibility to support user defined generators? e.g. in
>>>> coming versions?
>>>>
>>>> If not available right now, maybe you like the following suggestion:
>>>>
>>>> A possibility would be a super class 'RNG' that has to be implemented by
>>>> every generator plus a kind of factory class 'RNF' with static members
>>> only.
>>>> The RNF would be a wrapper around the current RNG instance to use
>>>> (stored in a static internal member). Thus, all Gecode internals that
>>>> need a random number use a static interface of RNF instead of some RNG
>>>> instance members. So the library gets independent of the concrete RNG
>>>> used and you get the possibility to register a user defined RNG within
>>>> the RNF. Per default the RNF can use the linear congruential generator
>>>> provided. The static interface and data member would avoid annoying
>>>> copies of RNGs all around and won't complicate your Gecode
>>> internals/source.
>>>>
>>>> Just a suggestion... if it is already possible just ignore and please
>>>> let me know how to do with the current Gecode version. :)
>>>>
>>>>
>>>> Have a nice weekend,
>>>>
>>>> Martin
>>>>
>>>>
>>>> _______________________________________________
>>>> Gecode users mailing list
>>>> users at gecode.org
>>>> https://www.gecode.org/mailman/listinfo/gecode-users
>>>>
>>>
>>>
>>> --
>>> Mikael Zayenz Lagerkvist, http://www.ict.kth.se/~zayenz/<http://www.ict.kth.se/%7Ezayenz/>
>>>
>>> _______________________________________________
>>> Gecode users mailing list
>>> users at gecode.org
>>> https://www.gecode.org/mailman/listinfo/gecode-users
>>>
>>
>>
>>
>>
>> ------------------------------------------------------------------------
>>
>> _______________________________________________
>> Gecode users mailing list
>> users at gecode.org
>> https://www.gecode.org/mailman/listinfo/gecode-users
>
> --
> Martin Mann, Dipl. Bioinf.
> Bioinformatics - Inst. of Computer Science
> Albert-Ludwigs-University Freiburg
> Tel: ++49-761-203-8259
> Fax: ++49-761-203-7462
> http://www.bioinf.uni-freiburg.de/~mmann/
>
> _______________________________________________
> Gecode users mailing list
> users at gecode.org
> https://www.gecode.org/mailman/listinfo/gecode-users
>

-- 
Mikael Zayenz Lagerkvist, http://www.ict.kth.se/~zayenz/