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

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.


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

Thanks,

Ulrich


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

-- 
Ulrich Scholz            

Phone: +49-6221-533244
Email: ulrich.scholz_at_...10...

--

European Media Laboratory GmbH
Schloss-Wolfsbrunnenweg 33
69118 Heidelberg

Amtsgericht Mannheim / HRB 335719
Managing Partner: Dr. h.c. Klaus Tschira, Scientific and Managing
Director: Prof. Dr.-Ing. Andreas Reuter

www.eml-d.villa-bosch.de