[gecode-users] exact behaviour of different IntValBranch

[Christian Schulte]

Hi Kish,

Actually, it is as you understood: binary choices only (apart from
INT_VALUES_*). 

Let's take INT_VAR_SIZE_MIN and INT_VAL_MIN as an example and suppose that
you have selected the variable x with 
the smallest domain that is first in the array you branch on and that the
min of x is n. That means you create a choice (x = n) v (x != n). After
exploring either of the choices and doing propagation the brancher is run
again: it will find the first variable with smallest domain. That might be
or might not be the same variable as x. 

This gives better choices wrt the heuristic than sticking to the original x.
Suppose you do it the Eclipse way and have selected a variable x with values
{n_0, ..., n_k}. Then you try in turn that x=n_0, x=n_1, ... That might be
bad. Look at the second alternative x=n_1. What Gecode does is that it
propagates first that x != n_0 and then it chooses a variable again: this
choice is likely to be better as the additional information from propagating
x != n_0 is available.

Let's take INT_VAL_MED as an example with x as selected variable and n the
median. Then you create a choice (x <= n) v (x > n).

Let's take INT_VALUES_MIN as an example with x as selected variable with
values {n_0, ..., n_k}. Then a choice (x = n_0) v ... v (x = n_k) is
created. So, that's in fact the Eclipse style.

I hope that helps. 

Do you think it's worth explaining that in MPG?

Cheers
Christian  

--
Christian Schulte, web.ict.kth.se/~cschulte/


-----Original Message-----
From: users-bounces at gecode.org [mailto:users-bounces at gecode.org] On Behalf
Of Kish Shen
Sent: Friday, July 30, 2010 8:48 PM
To: users at gecode.org
Subject: [gecode-users] exact behaviour of different IntValBranch

Hi,

I am trying to understand how the different value selection strategies 
(IntValBranch) works. In particular, the exact behaviour after failures,
when a different value need to be selected.

I have always understood a value selection strategy (as used in ECLiPSe, 
for example), to define an order in which values from the domain of a 
variable is selected, i.e. the variable is set to the first value in 
this order, and on failures, the variable is set to the subsequent 
values in order.

 From reading Modelling with Gecode, I understand that most selections 
are done as binary choices, that is, a value is selected, and if another
value is required, the previously selected value is excluded from the 
domain (with propagation), before selecting the next value. I assume 
this does not apply to INT_VALUES_MIN/MAX. Are these the only exceptions?

For INT_VAL_MED, does this mean that the median is used for each 
selection? That is, you exclude the previous median value, and then
now select the new median in the updated domain? If this is the case,
does it mean the median has to be calculated each time? [this is a
relatively expensive operation in ECLiPSe's finite domain libraries,
and the for the "median" value selection strategy,  the median is 
calculated only once initially, subsequent selected values alternate 
between the next lower and higher value than the initial median].

For the INT_VAL_SPLIT* and INT_VAL_RANGE* strategies, the documentation
mention values (plural) being selected, rather than a single value. What 
does this mean exactly? I assume the variable still needs to be set to a
single value from the selected values? Does this simply mean that within 
the selected values, specific values are tried in some order, but 
without excluding previous values and propagating the consequences (as 
in INT_VALUES*, but not for the whole domain, just the selected values?).

Thanks in advance for any help and information!

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.

_______________________________________________
Gecode users mailing list
users at gecode.org
https://www.gecode.org/mailman/listinfo/gecode-users