[gecode-users] exact behaviour of different IntValBranch

[Kish Shen]

Hi Guido,

Guido Tack wrote:

> That's not quite correct, INT_VAL_MED creates (x==n) v (x != n) just like INT_VAL_{MIN,MAX}.  And the median is computed again for each new node.
> 

Yes, that make sense, and is what I assumed it did (as I wrote in my 
original message).

So as I thought, you need to compute the median again. Does it make 
sense to provide something like what ECLiPSe does, to avoid the expense 
of computing the median? In terms of value selected, it probably does 
not make a huge difference -- the important thing is just which part of 
the domain you want to start selecting values from. You just need to 
remember in the x != n case, you want to select a value as close to n as 
possible.

> The splitting cases are INT_SPLIT_MIN, which does (x <= n) v (x > n) for n = (x.min()+x.max())/2, or INT_SPLIT_MAX where the two choices are swapped.  That's why the documentation talks about values (plural) here: The branching does not assign a single value to the variable, but splits the domain (of course, when the domain had size 2, the result of the split is a single value).
> 
> A good way to find out what the branchings do exactly is to have a look at the search tree in Gist.
> 


Ah, I think I understand this now. It means instead of always labelling
a variable to a value, its domain is simply reduced, and the variable 
can be selected again and again until it is reduced to 1.

Thanks and cheers,

Kish


-- 
This e-mail may contain confidential and privileged material for the
sole use of the intended recipient. Any review, use, distribution or
disclosure by others is strictly prohibited. If you are not the intended
recipient (or authorized to receive for the recipient), please contact
the sender by reply e-mail and delete all copies of this message.
Cisco Systems Limited (Company Number: 02558939), is registered in
England and Wales with its registered office at 1 Callaghan Square,
Cardiff, South Glamorgan CF10 5BT.