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

[Christian Schulte]

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


-- 
Martin Mann, Dipl. Bioinf.
Bioinformatics - Inst. of Computer Science
Albert-Ludwigs-University Freiburg
Tel: ++49-761-203-8259
Fax: ++49-761-203-7462
http://www.bioinf.uni-freiburg.de/~mmann/

_______________________________________________
Gecode users mailing list
users at gecode.org
https://www.gecode.org/mailman/listinfo/gecode-users