From: Ulrich Scholz <Ulrich.Scholz_at_eml-d.villa-bosch.de>

Date: Sun, 12 Oct 2008 14:24:39 +0200

Date: Sun, 12 Oct 2008 14:24:39 +0200

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_eml-d.villa-bosch.de -- 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.deReceived on Sun Oct 12 2008 - 12:22:44 CEST

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