Re: [eclipse-clp-users] Domains of ic variables

Dario Campagna wrote:
> Hi,
> 
> 	I have a question regarding the domain representation of ic variables.
> 
> Let us consider the following goal
> 
> [eclipse 4]: A #:: [-1000000000 .. 1 , 4, 6, 9, 13 .. 16, 20 .. 60],  
> get_domain(A,D), writeln(D).
> [-1000000000 .. 1, 4, 6, 9, 13 .. 16, 20 .. 60]
> 
> A = A{[-1000000000 .. 1, 4, 6, 9, 13 .. 16, 20 .. 60]}
> D = [-1000000000 .. 1, 4, 6, 9, 13 .. 16, 20 .. 60]
> Yes (0.16s cpu)
> 
> The predicate writeln print the domain we indicated for A.
> 
> Let us consider this slightly different goal
> 
> [eclipse 5]: A #:: [-10000000000 .. 1 , 4, 6, 9, 13 .. 16, 20 .. 60],  
> get_domain(A,D), writeln(D).
> -10000000000 .. 60
> 
> A = A{-10000000000 .. 60}
> D = -10000000000 .. 60
> 
> 
> Delayed goals:
> 	ic_kernel : exclude_range(A{-10000000000 .. 60}, 17, 19)
> 	ic_kernel : exclude_range(A{-10000000000 .. 60}, 10, 12)
> 	ic_kernel : exclude_range(A{-10000000000 .. 60}, 7, 8)
> 	ic_kernel : exclude_range(A{-10000000000 .. 60}, 5, 5)
> 	ic_kernel : exclude_range(A{-10000000000 .. 60}, 2, 3)
> Yes (0.00s cpu)
> 
> This time the predicate writeln/1 print a domain that is different  
> from the one we indicated for A.
> 
> Why in the result of [eclipse 5] the domain of A is an interval and we  
> have five delayed constraints for the variable A?
> Is it possible to obtain a result equivalent to the one obtained with  
> [eclipse 4] in cases similar to [eclipse 5]?
> 
Hi Dario,

ic is not really designed to deal with large domains with holes (i.e. 
excluded values), such as the domains you are playing with.

In ic, a domain with holes are represented with a bitmap, with each bit 
representing a value in the domain. Thus it takes N bits to represent a 
domain of N values. Thus, for your first domin,

[-1000000000 .. 1 , 4, 6, 9, 13 .. 16, 20 .. 60]

requires 60 - -1000000000 bits to represent it, or about 125 megabytes. 
With most modern computers, there is just about enough memory to allow 
one or perhaps a few variables with such a domain. You will overflow the 
stack if you try to assign this domain to more than one variable, if you 
run ECLiPSe with the default global stack size.

In fact, if you look at your example,

 > A = A{[-1000000000 .. 1, 4, 6, 9, 13 .. 16, 20 .. 60]}
 > D = [-1000000000 .. 1, 4, 6, 9, 13 .. 16, 20 .. 60]
 > Yes (0.16s cpu)

you can see that this used 0.16s of cpu time to assign the domain to one 
variable, which is extremely expensive, and is an indication that this 
is not a good thing to do.

If you look at the C code that implements lib(ic), you will see that if 
the interval is beyond a very large size (about 2^30 in 32 bit 
machines), a bitmap will not be allocated, this is what happened in your 
second example.

In general, the larger the size of your domain, the less useful are 
holes in the domain, in terms of reducing the amount of search you need 
to find a solution, so having large domains with holes in them are not 
particularly useful. You can argue that ic should not use bitmaps to 
represent large domains (say 10000 or 100000 and larger), and use some 
other mechanisms to represent the domain (e.g. lists of intervals as 
used in lib(fd)) but this would probably complicate the implementation 
significantly.

Cheers,

Kish Shen

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