[gecode-users] exact behaviour of different IntValBranch

[Christian Schulte]

Hi, I'll explain that some time.

The additional cost for recomputation is not that high. If you do some
serious constraint propagation in your problem you will not be able to see
any difference, I'd say.

Best
Christian

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



-----Original Message-----
From: Kish Shen [mailto:kisshen at cisco.com] 
Sent: Friday, July 30, 2010 10:52 PM
To: cschulte at kth.se
Cc: users at gecode.org
Subject: Re: [gecode-users] exact behaviour of different IntValBranch

Christian Schulte wrote:

> 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. 

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.