Re: [eclipse-clp-users] alldifferent/1 from ic vs. ic_global

[Joachim S. <jsc...@co...>]

On 06/04/2023 09:55, Panagiotis Stamatopoulos wrote:
> Hello All,
> 
> Is there any possibility for the same program to be more efficient
> when it uses ic:alldifferent/1 than its counterpart that exploits
> ic_global:alldifferent/1? It seems quite strange to me and I wonder
> if I am doing something wrong.


Yes, this is possible, and even quite common.  The reason is that there is a 
trade-off between the potential strength of propagation, and the effort with 
which this can be achieved.

For example, the stronger algorithm of ic_global:alldifferent/1 can detect 
failures before any variables are instantiated, e.g.

     ?- length(Xs,3), Xs#::1..3, ic_global:alldifferent(Xs), max(Xs)#=2.
     No (0.00s cpu)

which the simple ic:alldifferent/1 implementation misses:

     ?- length(Xs,3), Xs#::1..3, ic:alldifferent(Xs), max(Xs)#=2.
     Xs = [_762{[1,2]},_776{[1,2]},_790{[1,2]}]
     There are 4 delayed goals.
     Yes (0.00s cpu)

To be able to achieve this, ic_global:alldifferent/1

  * wakes up on every variable domain reduction
  * runs an algorithms with a complexity of at least O(N*log(N))

whereby ic:alldifferent/1

  * only wakes up when a variable is instantiated
  * costs only O(N) time


Better propagation may lead to a smaller search tree and therefore has the 
potential for exponential speed-up.  But if the extra propagation does not lead 
to enough search space reduction, the effort is wasted and an overall slowdown 
can result.  This phenomenon is not specific to alldifferent, but to all global 
constraints where propagation algorithms of different strength and complexity exist.


An additional remark: in some cases, it could even be advantageous to call both 
versions together via

     [ic,ic_global]:alldifferent(Xs)

You then get full strength propagation from ic_global, and potentially quicker 
discovery of simple failures from the ic version.


-- Joachim