[gecode-users] Advisors : need your advise if worth a look for my propagator! ; )

[Martin Mann]

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: users-bounces at gecode.org [mailto:users-bounces at gecode.org] 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
> 
>