Re: [eclipse-clp-users] Integer Set Library: Performance related to initial domain size?

Dear Ulrich,

Ulrich Scholz wrote:
> Dear Marco and all,
> 
> some simple tests show that the performance of the fd_sets library is
> related to domain size:
> 
> Consider the three clauses below.  All require a non-empty set to have an
> empty intersection with itself, thus they all should fail.
> 
> t1 does not fail but yields delayed goals.  So to detect the inconsistency,
> we have to search for a solution.
> 
> t2 does this search and fails as expected.
> 
> t3 is the same clause as t2, with the difference of using a largely extended
> domain.  Unfortunately, the inconsistency is found much slower that for
> clause t2.

so you confirm my expectations: no big difference concerning propagation 
itself, big difference with search.

> Is there a set constraint solver that allows to find such inconsistencies
> symbolically, i.e., without searching for an actual solution?

A different CLP(SET) solver is {log} (read as 'setlog'). You can 
download it from:

http://www.math.unipr.it/~gianfr/setlog.Home.html

This solver has different capabilities with respect to the fd_sets 
library embedded in ECLiPSe, so in some cases it can be faster, in 
others it can be slower. Anyway, you can give it a try.

In the particular example you suggested, it fails immediately:

{log}=> disj(X,X).


X = {}

Another solution?  (y/n)y

no

{log}=> disj(X,X), Y in X.

no

Cheers,
Marco

> :- lib(fd_sets).
> :- use_module(library(fd)).
> 
> t1 :-
>     intsets([T], _, 0, 10),
>  
>     integers([C]),
>     C #>= 1,
>     #(T,C),
>     
>     T disjoint T.
> 
> t2 :-
>     intsets([T], _, 0, 10),
>  
>     integers([C]),
>     C #>= 1,
>     #(T,C),
>     
>     T disjoint T,
> 
>     insetdomain(T, _, _, _).
> 
> t3 :-
>     intsets([T], _, 0, 10000),
>  
>     integers([C]),
>     C #>= 1,
>     #(T,C),
>     
>     T disjoint T,
> 
>     insetdomain(T, _, _, _).
> 
> 
> 
> On Sun, Oct 05, 2008 at 11:57:21AM +0200, Marco Gavanelli wrote:
>> Ulrich Scholz wrote:
>>> Dear all,
>>>
>>> I have a question about the Integer Sets library: How is the performance
>>> related to the initial size of the domains?
>>>
>>> Assume you have a Integer Sets constraint problem and the initial domains of
>>> the variables are subsets of the set {1, ..., N1}.  
>>>
>>> Furthermore, assume that the problem's solution is invariant regarding
>>> increasing initial domain size.  So, for example, it would have the same
>>> solution (*) if we chose the initial domain size to be subsets of the set
>>> {1, ..., N2}, N2 > N1.
>>>
>>> Now we increase N2.  How does the performance behave?
>>>
>>>
>>> The reason I ask is: Set variables have to be defined with a domain.  In my
>>> application, the number of variables and their relation (subset, \=, etc.)
>>> are known before the actual domains of the variables.  So I have to "guess"
>>> their domains.  If there is no performace penalty, I just choose the domains
>>> "large enough". 
>> Dear Ulrich,
>>
>> I am not an expert, and I was waiting for other people to answer, but 
>> since you got no reply, even a non-expert comment might be useful.
>>
>> I think that the performance of constraint propagation should not change 
>> that much if you take a large domain. However, if you have a search 
>> procedure that checks all the combinations, of course the search space 
>> grows exponentially with the number of elements in the upper bound.
>>
>> Hope that helps.
>> Cheers,
>> Marco
> 


-- 
Marco Gavanelli, Ph.D. in Computer Science
Dept of Engineering
University of Ferrara
Via Saragat 1 - 44100 Ferrara (Italy)
Tel  +39-0532-97-4833
Fax  +39-0532-97-4870
http://www.ing.unife.it/docenti/MarcoGavanelli/