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

From: Marco Gavanelli <marco.gavanelli_at_unife.it>
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.
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/
Received on Sun Oct 05 2008 - 10:21:46 CEST

This archive was generated by hypermail 2.2.0 : Thu Feb 02 2012 - 02:31:58 CET