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

From: Marco Gavanelli <marco.gavanelli_at_...17...>
Date: Sun, 05 Oct 2008 11:57:21 +0200
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.
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
Received on Sun Oct 05 2008 - 10:21:46 CEST

This archive was generated by hypermail 2.3.0 : Sat Jul 20 2019 - 06:14:56 CEST