Alright, that's what I expected having Mikaels thesis in mind.
Thanks for the detailed reply, Martin PS. And yesss... the performance in Gecode 1.3.* was already great! ;) Not much room for an increase but I will compare with the Gecode 3.* implementation! Christian Schulte schrieb: > Nope, don't use advisors. Just do what you did before, that's just fine. You > are now even on the safe side as what you did might actually be > non-monotonic which is fine for 3.*. > > The main advantage of advisors is really to implement propagators for > constraints with n variables and getting better asymptotic complexity (for > example, when you have to find out which variable has changed for doing > propagation, a propagator without advisors will always have O(n) complexity > in order to find out which variable has changed and some propagation > algorithms are actually constant time). Or, you really care about how the > domain has changed. > > In a way, the reason why advisors are not that essential in your situation > is that scheduling propagators and executing them is actually very very > efficient in Gecode (okay, I had to brag a little). > > Cheers > Christian > > -----Original Message----- > From: [email protected] [mailto:[email protected]] On Behalf > Of Martin Mann > Sent: Tuesday, May 19, 2009 6:09 PM > To: gecode user list > Subject: [gecode-users] Advisors : need your advise if worth a look for my > propagator! ; ) > > > Hi everybody, > > thanks to your answers Mikael and the silent support and mails from > Daniel Przybilla I have a better understanding of the Advisors, their > use and functionality. > > Now the question appears: is the effort/overhead worth for me or not? > > I had a look at Mikaels thesis and the final statement that Advisors are > mainly advantageous for n-ary constraint and not that useful for e.g. > binary constraints (correct me if I got it wrong). > > Thus, I would like to get your feeling on my constraint, because you are > the experts on your system! ;) > > ================ > My problem: > ================ > > I have a binary constraint propagator p(X,Y) that does a very strong but > expensive filtering on the domains of variables X and Y. Thus I would > like to delay the application until one of the domain sizes is smaller > than a certain threshold. > > In Gecode 1.3.* I managed like that: > - I subscribed the propagator for domain changes on the two variables > - within the propagate function I checked if the minimal domain size of > both is smaller than my threshold > - if so I ran the filtering algorithm, otherwise I returned that nothing > could be propagated (I was lazy and know this is kind of a hack.. ;) ) > > In my Gecode 3.* reimplementation I want to do it in the best way > possible. So the question is: Do I stick to the old "hack" or is it > worth a look to implement Advisors that do the domain size check for me? > > ================================= > The CSP itself is quite simple: > ================================= > > - n variables : X_i with 1 <= i <= n > - one alldiff : distinct( X_1,..,X_n ) > - (n-1) binary constraints : p(X_i, X_(i+1)) with 1 <= i < n > > (for anybody even more interested in details : p encodes a neighboring > constraint in a lattice and the whole CSP encodes a self-avoiding-walk > of length n on a lattice) > > ================================= > > Soo... the again final question: *Is it worth to use an Advisor for my > domain size check? Or is the hack nasty but most probably faster?* > > I know it is hard for you to give a statement without knowledge on the > propagator's details but an expert guess would be sufficient for me. ;) > > Thanks a lot! > > Martin > > _______________________________________________ Gecode users mailing list [email protected] https://www.gecode.org/mailman/listinfo/gecode-users
