[gecode-users] Value selection when branching

[Guido Tack]

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