Christian Schulte wrote:
Let's take INT_VAR_SIZE_MIN and INT_VAL_MIN as an example and suppose thatyou have selected the variable x with the smallest domain that is first in the array you branch on and that themin 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 beor might not be the same variable as x.
Ah, this is the part I did not know (that you might not be using the same variable). This is indeed different from what ECLiPSe (and most likely other backtracking constraint solver) does.
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.
However, propagation of x != n_0 can also occur with ECLiPSe -- it does not affect your selection of variable (i.e. you will still label x), but it may reduce the domain of x and other variables. On the other hand, you perform additional propagations that might not pay off. Both of these value choices strategy are available in the search/6 predicate of the ic library.
I was first made aware of this difference in discussion with Helmut Simonis (who also introduced search/6 to ECLiPSe), and he said that it is not always clear which strategy is better, and depends on the problem being solved, which is why both are provided in search/6.
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 assume you don't do any propagations here; as already discussed, it is not the only possibility.
I think it is also worth noting that INT_VALUES_MIN strategy is more expensive in a recomputation based system than a backtracking system, because in a recomputation system you need to remember all the choices, rather than just the value selected.
I hope that helps.Do you think it's worth explaining that in MPG?
Yes, I think it is worth explaining. I had very great problems understanding the search chapter in the MPG (actually the MG then :-)),
until I had my discussion with Helmut. It was not obvious to me that you had binary choices at each choicepoint until that discussion.This was when I first started implementing the Gecode interface more than a year ago. However, the fact that you perform variable selection again was not known to me until your message today, so I think it is worth discussing both points.
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 [email protected] https://www.gecode.org/mailman/listinfo/gecode-users
