From: Marco Gavanelli <marco.gavanelli_at_unife.it>

Date: Sun, 12 Oct 2008 15:32:54 +0200

Date: Sun, 12 Oct 2008 15:32:54 +0200

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/Received on Sun Oct 12 2008 - 13:33:46 CEST

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