[gecode-users] Value selection when branching

[Christian Schulte]

It is all true what Guido says, but something more useful is the following:
also random number generators are deterministic programs. The only problem
is when you use the OS random number generator: here the state of the random
number generator is hidden.

So what you can do is the following: look up a random number generator (such
as in Knuth "Seminumerical Algorithms"). Store the state of the generator in
the branching. Then your branching can guarantee that for the same state of
the branching you will always return the same random values. 

This then also works with recomputation.

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: Tuesday, February 07, 2006 4:38 PM
To: users at gecode.org
Subject: Re: [gecode-users] Value selection when branching


Hi.

> I still haven't solved the previous problem (about the strange 
> propagation behaviour), but since for the moment there is a 
> workaround, I have started to work on some other things at the same 
> time, one of them random value selection when branching.

Uh, I tried that too and failed miserably ;-)

> I've also added the value BVAL_RAND to BvalSel for the case 
> distinction inside the create method in select-val.icc, everything 
> compiles and runs without errors. Moreover I've added a command line 
> parameter "-seed" to set the global random seed.
>
> To just test this new part I changed some existing examples to use 
> BVAL_RAND, e.g. all-intervall.cc.
>
> Still using the default BVAL_MIN I obtain:
> $ /examples/all-interval 10 -solutions 200 | grep solutions
> 	solutions:    74
>
> But then, after the change to BVAL_RAND:
> $ ./examples/all-interval 10 -solutions 200 -seed 1 | grep solutions
> 	solutions:    3
> $ ./examples/all-interval 10 -solutions 200 -seed 2 | grep solutions
> 	solutions:    118
> $ ./examples/all-interval 10 -solutions 200 -seed 3 | grep solutions
> 	solutions:    100
> $ ./examples/all-interval 10 -solutions 200 -seed 37582 | grep solutions
> 	solutions:    125
>
> ...and so on, you get the idea. Clearly something is wrong here. ;) 
> Even though values are chosen randomly, in the end the number of 
> solutions should be the same. And since for this setting all that was 
> changed/added are the things above, the error should be within there. 
> Still I can't see the problem, esp. when comparing it to the existing 
> value selection classes.

To understand this behaviour, you have to understand how the search engine 
works. One severe problem is recomputation: this requires that the branching

is deterministic, i.e. for equivalent spaces it must always result in the 
same choice. This is clearly not the case here. You could switch off 
recomputation by giving -c_d 1 -a_d 1 as command line parameters. Please try

out if that changes anything.
It might still not work, because even if you never recompute spaces, you are

not guaranteed that for one space at one point in the search tree the 
branching is evaluated only once. The only way out of this trap is to use 
something that will be completely deterministic, so that for equivalent 
spaces you will always get the same choice.

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