[gecode-users] member function branching

[Guido Tack]

Patrik Haslum wrote:
> I've implemented a "proper" custom branching (with branching  
> descriptions etc). I've also run some experiments testing the effect  
> of changing the c-d parameter, and results are not what I expected.
>
> I used two different settings, c-d = 8 and c-d = 1, with both  
> "basic" branching (i.e., only calling the built-in "branch"  
> function, for each of two variable arrays, in the space constructor)  
> and with my custom branching. In *all* cases, using c-d = 8 does  
> more propagation than using c-d = 1! Runtimes do not always  
> correlate with the amount of propagation done, but, for the custom  
> branching strategy at least, using c-d = 1 is faster on all non- 
> trivial problems. (A summary of the experiment results is attached.)
>
> Is there an explanation for this result?

At least part of it is the expected result.  Recomputation (which you  
enable using c-d=8) trades memory for run-time: you need less memory,  
because you store fewer copies, but you need more time, because you  
have to recompute.  And recomputation of course involves propagation,  
so the number of propagation steps is bound to increase.
In practice, however, it turns out that recomputation often saves run- 
time, first because copying takes time, too, and second because it is  
optimistic: don't make too many copies, because the solution will be  
where the heuristic predicts it, so many copies would never be used.   
Of course, this is problem-specific, so it might just not work in your  
case.
All this is discussed in [1] and [2], if you want to read more about it.

Cheers,
	Guido

[1] C. Schulte. Comparing trailing and copying for constraint  
programming. In D. D. Schreye, editor,
Proceedings of the Sixteenth International Conference on Logic  
Programming, pages 275–289, Las Cruces,
NM, USA, 1999. The MIT Press.

[2] C. Schulte. Programming Constraint Services, volume 2302 of LNCS  
(LNAI). Springer, 2002.